Solutions to Interview Questions 1

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.

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

7 Responses to Solutions to Interview Questions 1

  1. spandan says:

    can clarify the soln to question number 4..please

    • Avi Dullu says:

      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.

  2. spandan says:

    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

    • Avi Dullu says:

      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.

  3. sathya says:

    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?

  4. spandan says:

    Hey how to apply for google off campus.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: