# Solutions to Interview Questions 1

May 14, 2010 7 Comments

Sorry guys for posting too late here … I have been in a dream world since I got accepted at **Google, Bangalore**. I have left my college campus and now am at home and will be updating the blog more than before :). Now I shall start posting solutions to the problems here ( some of them even I don’t know so will have to think over them 😛 ) and also will be looking and **creating** new problems.

This post provides the solution/approaches to solve the problems listed by me in Interview Questions 1.

The solutions here are derived through the comments section and by me. So please post any corrections or improvements.

**Question 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.

**Solution 1** [ given by spsneo in the comments] : 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.

**Question 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.

**Solution 2**: The order will be O(k) because the (k+1)th number will have to be a repeated one and it will be the solution in the worst case. So, the method is simply to remember the numbers ( < k) seen and mark the index corresponding to them as -ve. So, whenever you see a number, say i, it will be < k, and you mark the number at arr[i] as -arr[i]. If it is already a -ve number then it is the solution. Do this from arr[0] up till the solution condition is not met. In this case, the array can be acquired back, just negate the negative numbers, but still the array has to be modified. If it is not the case, then O(k) space will be needed.

** Question 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”

** Solution 3**: The detailed solution to this problem is discussed in my post Programming Problem Solution 2.

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

**Solution 4**: Start from the one’s digit and move towards the left till the digits are in increasing order. When you find the nth digit (from left) is smaller than (n-1)th digit (from left), you stop here. The digits you have encountered till now, including the nth digit from left, will be sufficient for you to construct the next immediate largest number. If there is no (n+1)th digit, i.e. the number is like 875, then there is no solution, obviously :). Else, you can easily see that you only have to construct the next largest number by carefully rearranging the digits you selected in the previous step. So, replace the nth digit with the immediate larger of the (n-1) digits from left and then sort the remaining digits in ascending order and append it to the already constructed number. (It’s complex to explain here :P)

eg. 23471

nth = 4

n-1th = 7

the larger digit among 7 and 1 ** which is immediately larger than 4** is 7. So append **7** to **23**.

The number till now is **237**.

The digits remain 1,4. Sort them .. 14

Append it to 237

Resulting number 23714

Another Eg. 83496521

nth = 4

n-1th = 9

the larger digit among 9,6,5,2,1 **which is immediately larger than 4 is 5**. So append 5 to 83.

The number till now is **835**

The digits remain 9,6,2,1,4. Sort them : 12469

Append it to existing number 83512469

Please post if any test case does not satisfy this.

can clarify the soln to question number 4..please

I’m sorry for the typos I had made. I have updated the solution so you can refer back to it.

Anyways, in the example given, when we move from one’s digit i.e. 5 towards the left we see 7 which is in ascending order, so we move further and see 4 which is not in ascending order. So we rotate 475 by 1 towards the left so that it becomes 547 and keep the remaining number as is.

for question 2….

Its clear how to do it in O(n) in O(k) space ..

How to do it in O(n) in O(1) space is not clear….can u please elaborate.

thanks

It is a standard technique used to find duplicated numbers in an array where one can modify the contents of the array. Just take an example array and follow the steps. You will easily figure out.

for 4th q if no. is 23471 according to ur logic d rotated no. will be 23147 which is lessser dan thr original. Hw to go wit dat?

Thanx for pointing out the error. I have updated the solution. 🙂

Hey how to apply for google off campus.