I’ve been through a lot of CS interviews recently and so I have come across many interesting problems. I find many of them worth sharing. So I am writing this short series of posts on this topic. All of these interviews were for a job post of Software Development Engineer. If you happen to be reading this, as a sort of preparation for an interview, I suggest you attempt to solve the problem yourself and then see how you like my solution (please correct me for any mistakes!). Most interviewers also ask for code. I am not posting that here, since after getting the solution, coding it should be fairly straightforward with a little practice.
Given a binary tree, how will you convert it into a doubly-linked circular list in-place? That is, the left-child and right-child pointers of a node in the tree should be considered as left-node and right-node pointers in the doubly-linked list.
The key here is that only a constant amount of extra space is allowed as the conversion should be performed in-place. That is, we cannot save the data in another, more convenient data structure and then perform the conversion to a linked list.
An important tip is to think of recursive algorithms when faced with problems about trees and especially binary trees.
Using this tip, we think of solving this problem recursively. When we are given the binary tree, what we are actually given is the head pointer of the tree. Thus, we have the head node, say head. We also immediately have the head nodes of the left and right subtrees of this node (head->left and head->right, using C-like notation). Now, we can simply solve the problem recursively. Thus, we can get the following pseudo-code:
getDLL(head):
[Takes the head pointer of a tree, and returns a circular DLL as required above containing the nodes in the given tree.]
- save = head
- leftList = getDLL(head->left)
- rightList = getDLL(head->right)
- Now, combine the above, in-order: (leftList, save, rightList). Don’t forget to make it circular by joining the first and the last nodes.
Note that I have not handled the base cases. I am just illustrating the idea. Clearly, the base cases to consider are when either of the sub-trees are empty. If, so just return whatever list is remaining, without adding any null nodes.
Ok, now that you’ve understood the solution, don’t think it’s over. Analyse the complexity. Time complexity is linear in the number of nodes in the tree, i.e. O(N), where N is the number of nodes in the tree. Why? In each, recusive call, the amount of work done other than the recursive calls is constant. [If you are not convinced, complete the code and see for yourself.] Also the number of recursive calls equals the number of nodes. Thus, the result. What is the space complexity? It is not constant because recursion uses the stack. How much space is that?! The maximum size of the stack is proportional to the depth of the tree (why??). I don’t yet know a solution that eliminates this logarithmic space requirement.
It is known that when function calls are made, activation records are created and pushed on top of a stack, which is managed by the operating system. In some systems the stack grows upwards and on some other systems the stack grows downwards. How will you find out if a stack grows upwards or downwards for a program on a particular computer?
This problem is actually pretty easy if you think about it. You are being asked to find if the address of elements of the activation record increase or decrease with nested function calls. The solution is to write a simple C program that saves the address of a local variable (as it is stored on the stack) in a global variable and then this information can be used in the main function, to determine if the stack grows up or down:
#include <stdio.h>
int a,b;
void f(){
int b; a = &b;
}
void main(){
int c; b = &c;
f();
if(a>b) { /*Stack grows down*/ }
else { /*Stack grows up*/ }
}
Consider the following code snippets:
for(int i=0;i<100;i++) for(int j=0;j<1000;j++) ;
and,
for(int j=0;j<1000;j++) for(int i=0;i<100;i++) ;
Disregarding all compiler and processor level optimizations, which of these two codes runs faster? Why?
It seems like a nasty puzzle, but the answer is actually pretty simple. We note that all constituent assembly level instructions are of the types: zero assignment, increment, comparison and jump. Let us count them. The first snippet has 101 zero assignment statements, 100,000 increment statements, 1001*100+101 = 100,201 comparison and jump statements. The second snippet has 1001 zero assignment statements, 100,000 increment statements, 1000*101+1001 = 102,001 comparison and jump statements. Clearly, the first one is faster.
Anyways.
