Tag Archives: Recursion

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Q: What is the unknown?

A: To reverse nodes in a linked list k at a time and return the modified list.

Q: What are the data?

A: A linked list and an integer k.

Q: What are the constraints?

A: From the example above, we should probably assume this is a singly linked list. We cannot change the value in the node (Actually this is a very good idea in modifying linked list). Constant memory only. If at some point, the number of nodes is not the multiple of k, these nodes should remain the same order.

Q: Have you seen it before or at least something similar?

A: Yes I think I have. A similar problem is to reverse a singly linked list in place. I solved it before and it only took constant memory. I think we can apply the solution of that problem to each K nodes for reversing purpose.

Q: Good. For the whole problem, what kind of strategy should we use? Suppose we have reversed K nodes in the list, what about the rest of list?

A:  We do the same for the rest and connect with the k nodes reversed previously.

Q: Can you describe it in more details?

A: OK, for the rest of the linked list we reverse the nodes in k-Group and connect with previously reversed k nodes. Ah I see where this is heading. We are looking at a recursion here.

Q: Yes we are. Now think about the base case of this recursion.

A: That would be the number of remaining nodes is not a multiple of k and we should just connect them with the previously reversed part.

Q: What about the recursive case?

A: Hmm, we should reverse the current k nodes at hand. reverse the next k nodes and connect with them. Then return the current reversed part so the previously reversed part can connect with it.

Q: OK not super clear but I guess you have the idea.  In the base case, how do you determine if the number of remaining nodes is a multiple of k?

A: Starting from where we are, go k steps further. If at any point, we hit null, then we know there are enough nodes for reversal.

Q: Good. The take-away message here is that recursion could be a very handy trick for solving linked list related problems. So keep it in your toolbox.

Code on github:

Enhanced by Zemanta

Binary Tree Postorder Traversal Non-recursive Version

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

(Java Code on Github at the bottom of the post. )

My thoughts and solutions:

Well the recursive solution is indeed trivial but quite elegant. However, sometimes we may hit a stack overflow exception and that’s why we need the iterative version. To convert a recursive solution into an iterative one, we have to implement our own stack.

So what should we put in our own stack? Think about the recursive version. For example, for each node that does not satisfy the condition of the base case, the function immediately calls on itself with the current node’s left child (if it exists), leaving its right child (if it exists) and its current value unprocessed. So the items going to the stack are nodes that are not fully processed: either its left or right child has not been visited yet.

So the stack is for tree nodes, but we also need to know whether the children of each node have been visited. The original node class does not support this. One simple solution is to wrap the TreeNode class in another class and I call it NodeInfo (it is a private class inside the PostorderTraversal class) and we create a stack of NodeInfo:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
private class NodeInfo{
    TreeNode node;
    boolean isLeftVisited;
    boolean isRightVisited;
    
    public NodeInfo(TreeNode node){
        this.node = node;
        isLeftVisited = false;
        isRightVisited = false;
        if(node.left == null) isLeftVisited = true;
        if(node.right == null) isRightVisited = true;
    }
}

OK, how does this work? Remember that for post order traversal, it has the following order:

  • Visit left subtree
  • Visit right subtree
  • Visit current node

So we can push our root wrapped in NodeInfo object to the stack. Then, as long as the stack is not empty:

  • we peek at the top node.
  • if the node has left child and it is not visited, set isLeftVisited to true and visitSubtree(left)
  • else if the node has right child and it is not visited, set isRightVisited to true and visitSubtree(right)
  • else if both children are visited, pop the top node and add its value to an ArrayList solution.

How do we visit the subtree?

while the node is not a leaf:

  • push itself to the stack
  • if it has unvisited  left child, set isLeftVisited to true and point itself to its left child
  • else if it has unvisited  right child, set isRightVisited to true and point itself to its right child

When the loop ends, the node should point to a leaf node so just add its value to the ArrayList solution.

I had trouble at first worrying about visiting only one side of a node in the loop, like we are missing them. But then I realized that all nodes with unvisited children are push to the stack along the way to the leaves so no worries.

Code on github:

Enhanced by Zemanta

Sorting Algorithm —- A Conversation

Algorithm is one the fundamental components that a programmer should master. But every time I read a book about it, I see intrusive instructions about how to solve a problem using several algorithms. Well they just tell you that you should use this and that. Sure, they are brilliant ideas, but how do those ideas come up? If we do not know this process, it is hard to say we have really learned.

I’ve been reading the book “How to solve it” by George Pólya. It is a great book that shows you how to approach a problem using various steps. You can ask about certain questions and answer them to get a better chance to obtain the final solution. Although this book is about mathematics, I think it also applies for algorithms or even just problems in general. So I’d like to write the conversation I made myself to show the process of how we get an algorithm without giving intrusive instructions. These are just my humble ideas and suggestions are always welcome.

This problem is about sorting: Suppose you have 100 numbers. They are 100 different cards and out of order. How can you sort them in ascending order?

Q: What is the unknown? What is your goal?
A: Find out a way to sort the numbers.
Q: What are the data?
A: 100 numbers written on cards that are not in order.
Q: Have you seen it before?
A: Well it is not hard to imagine. Just like you are sorting poker cards.
Q: OK Now tell me, how would you sort those cards?
A: Well, to start, I just pick a number and put it on the table. Then pick another one and compare this one with the former one. Based on the comparison, place it in the right position. And pick another one and compare this one with the former two and then place it in the right position. So this procedure just repeats: pick a new one, compare with the former ones and place it in the right position until there are no more new numbers to pick. I think this is a natural process to do.
Q: OK so you are doing a procedure repeatedly. What kind of component in programming is related to this?
A: Well loops. Eh and recursion?
Q: OK, so which one matches your need here?
A: I would say loop.
Q: So what should you do in the loop?
A: Like I said, pick a new number, compare with the former ones and place it in the right place.
Q: What is the ending condition?
A: The ending condition is that there is no more new number to pick.
Q: OK, you are comparing new number with former ones. what pattern do they have?
A: I’m not sure what you mean…
Q: OK, look at the unknown. What do we want to do with the data?
A: Sort the data and make sure they are in order.
Q: Now do the former numbers satisfy this condition when you exam them?
A: Eh, yeah sure.
Q: So they are…?
A: Sorted. in order.
Q: So every time you pick a new number, you are comparing it to data that are…?
A: Sorted. Yes I always compare the new number with data that are already sorted.
Q: Good. Now you mentioned that you need to place the new number correctly. Can you explain how to do it?
A: Well, we could start comparing the new number with the ones in the former sorted part one by one. If we found one N that is greater than the new number, then we should put it right before N.
Q: Well, what if the new number is larger than all numbers in the former sorted numbers?
A: In that case, we just put it at the end of the sorted numbers.
Q: Good. Do the former numbers have any other patterns?
A: Eh, every time I put a new number to the sorted part. So they are changing, if that counts.
Q: Sure. So it is changing and you need to use it every time. What should you do about it?
A: I guess I need to keep track of it.
Q: Good. Now you know you need a loop and what to do in the loop. Sounds like you have a plan. Be sure to check each step. Consider special cases. And when you are done, test it with some data to make sure you have the right algorithm.
=============================================================================
Q: Great now you have a solution for this problem. Is it possible to do it differently?
A: Eh, I don’t know.
Q: You mentioned recursion. Is it possible to solve this problem using recursion?
A: ….
Q: How does recursion usually works? What kind of problem does recursion apply to?
A: If you can solve a problem by dividing it into one or several sub-problems with smaller size that are similar or the same to the original problem, then you can consider recursion.
Q: Good, so can we apply it on our problem? What is the smaller problem here?
A: Well I can try. A smaller problem for us would be to sort a smaller collection of numbers. Say you have 50 numbers instead of 100.
Q: OK but your sub-problem must relate to the original problem. So these 50 numbers must be inside…
A: Oh right, these 50 numbers must be a subset of the original 100 numbers.
Q: Good. Now we only considered 50 numbers. What about the rest 50?
A: …
Q: You sorted 50 numbers. To get all 100 numbers sorted, what should you do about the rest?
A: Eh I guess we should sort them too. But I don’t know if we are heading to the right direction. At most we get two separately sorted collections. That is not the solution for the original problem.
Q: I’m glad you ask this question. Now the problem is whether we could get the sorted 100 numbers from two sorted subsets. Can you think about if this is possible?
A: …
Q: Can you think about an example of this situation?
A: OK, say we have 10 numbers: 3, 2, 1, 5, 6, 7, 9, 0, 8, 4. The final sorted array should be R(0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Assume we have two sorted subsets A (1,3,5,7,8) and B(0, 2, 4, 6, 9).  We are trying to get R from A and B. Hmm… interesting. We could just compare the head elements of both A and B, extract the smaller one from the collection it belongs to and put it in another collection C. W should repeat this process until one collection is empty (because of the extraction). Then if the other collection is not empty, just add the rest elements to C.
Q: Good call. Now for recursion, there are two cases. What are they?
A: Base case and recursive case.
Q: What is the base case?
A: The base case should be the case that the collection we are sorting only has one element and we can just return it.
Q: What about the recursive case?
A: eh we can divide the current collection in consideration into two subsets. Call the sort function on them and merge their results together and return it!
Q: Nice. Now you have a plan. Make sure you check each step and use some test cases on your algorithm.
Link to the Java Code on GitHub
Enhanced by Zemanta