# Interview Questions 1

January 15, 2010 9 Comments

**[Update]** The solutions to the problems in this post as discussed at Solutions to Interview Questions 1.

1. Consider a binary tree, and listing of its nodes in the inorder traversal. Now write a function such that given any node in the tree it returns the next node that is visited by in the inorder traversal program.

E.g. if the is tree is like root – 1 has children 2, 3. 2 has children 4, 5. Then given 4, it should return 2 and given 5 it should return 1 etc.

2. Given an array of n numbers in which all the members are less than or equal to k (k<n). device an algorithm of order O(k) to find the first repeating element.

3. You r given a large string of characters lets call it Sbig. Then there is a small set of characters lets call it Ssmall. You have to find smallest substring of Sbig which contains all characters in Ssmall.

For example you are given Sbig = "hello what are you doing"

Ssmall= "eo"

answer is "ello"

4. Given a positive integer having all unique digits. Find the immediate next greater number having the same digits.

can you share your solution to problem 3: I thought about it for a while, wondering what a optimal solution looks like.

My idea was basically store the indexes of the occurrence of each letter , in this case, e and o

and generate all unique combinations of it. Then take the one that has minimum difference between the min and max.

Btw… I like your blog:)

I have put up a post explaining the solution to this problem along with the program (in C) which does the job. You can read the solution from it.

And thanx a lot for the appreciation 🙂

Pingback: Programming Problem Solution 2 « Avi Dullu's Radio Station

For question 1 –

if the tree is modified to a threaded tree, it is easy to find inorder successor.

if the tree is not allowed to modify, we can traverse down the tree in usual inorder manner, and find the successor. (for this we can use recursive algorithm or morris traversal).

Is there any better solution?

@spsneo

Firstly, You cannot modify the tree.

Secondly, doing the usual inorder traversal is not counted because you are not given the root of the tree. You have a pointer to the node only. You can assume that each node has a pointer to its parent.

Now try to think of the solution. There are just 3 cases to be handled, just find out who should be the inorder successor in each of the tree cases. 🙂

@avi

If each node has a pointer to its parent, then it is easy-

1) The node is a leaf-node and it is the left child of its parent – its parent is the inorder successor

2) The node is a leaf-node and it is the right child of its parent – keep on going up till there is a node which is a left child of its parent, this parent is the inorder successor

3)The node has a right child – leftmost leaf of the subtree rooted at its right child.

Please correct me, if I am wrong.

Nothing wrong 🙂

For problem 2:

Using O(k) space is allowed?

I don’t know the actual constraints of the problem, but I could solve it by only temporarily modifying the array i.e. after the algorithm the array elements were restored in their actual positions.

Anyways, share any solution you have in mind.