# Interview Questions 15

September 5, 2010 12 Comments

1. Input Data : {[1,3],[2,4],[10,11],[4,6]}

Output: {[1,6],[10,11]}

We have to merge all the ranges that are overlapping. You can consider Input data as any Data structure.

2. Given a char array with words in it, find all ‘a’ characters and replace with xyz. Modify the input array, do not create a copy of the array.

3. How do you output the nodes from a binary search tree given a range

4. Implement a function

public long[] GetMultiplesOfTwoLessThan(int num)

eg if num is given as 30, output array should contain {1,2,4,8,16}. It shouldn’t contain 32 since 32 is more than the given number.

Another exp: if num is 300 then output will be {1,2,4,8,16,32,64,128,256}

**Super optimized solution desired**

5. Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square.

6. Print all edge nodes of a complete binary tree anti-clockwise.

That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.

In other words, print the boundary of the tree.

Variant: Print the same for a tree that is not complete.

7. Given 3 product categories and a respective file of a huge size containing only the list of order numbers in sorted manner. Write an algorithm (best possible time complexity to be achieved) which can find common order numbers in all 3 files.

8. Implement **boolean ValidateIP(string inpIP)**

9. Given a file in which the data is stored in the form

ABC

_DEF

_GEH

XYZ

_PQR

__STY

Construct an nary tree out of it in O(n) time such that DEF and GEH are the children of ABC and XYZ is the sibling of ABC, PQR is child of XYZ and STY is child of PQR. The spaces after the beginning of a line specify the relation of a node to its predecessors.

10. Why auto variables are not stored in heap?

11. Each cell of an N x N grid is either a 0 or a 1. You are given two such N x N grids, the initial grid and the final grid. There is a button against each row and each column of the initial N x N grid. Pressing a row-button toggles the values of all the cells in that row, and pressing a column-button toggles the values of all the cells in that column. You are required to find the minimum number of button presses required to transform the grid from the initial configuration to the final configuration, and the buttons that must be pressed in order to make this transformation.

1. Sort the sets according to first number. Then keep on contracting based on whether the adjacent sets are contractable or not. O(nlogn). To check contractable

ensure that they are overlapping.

2. First pass find the count of a’s. start the second pass from right and keep shifting the elements 3*count of a. Whenever you encounter an ‘a’ replace it with xyz and decrement the count of a.

5. Start from 16 and keep building the list. We start from 16 because 16 can form only one square with any other number (which btw is 9).

4. I didn’t understand the meaning of super optimized. A O(logn) solution is evident. Are we looking at O(log log n)? In that case we can do a binary search on exponential powers of two to find the power less than the given number. But printing all the powers would still make it O(logn).

6. I would do it through 3 different functions. First to print all the left side, second to print all the leaves, third to print all the right side. A detailed solution will be an overkill. 🙂

Regarding the 6th question:

this can be done using a single function which do inorder traversal of tree. We can keep some flags to know when we are on left side , when at leaves and when we are on right edge.

/* here is the implmentation */

void printL(struct node* node,struct node* root){

if(node->left == NULL && node->right == NULL)

{ printf(“%d “, node->data);

rootLeft = 0;

}

if(node->left != NULL)

{ if(rootLeft == 1)

printf(“%d “, node->data);

printL(node->left,root);

}

if(node->right!=NULL)

{ if(node == root) rootRight = 1;

printL(node->right,root);

if(rootRight == 1 && node!=root)

printf(“%d “,node->data);

}

}

/* ends here */

here rootRight(initially false) and rootLeft(initially true) are global varibles. When we reach the first/leftmost leaf, set rootLeft to be false and when we reach in the right subtree, make rootRight as true. “root ” parameter is passed just to check keep track of main root of tree.

I tried this code, it works fine with complete BST. 🙂

@Amar

All the above problems are actually meant to be

coded. There is hardly any algorithm involved in them. Only the bits of code make them interesting to some extent.Regarding the

super optimizedsolution to the problem, again I was referring to implementation. I could drill down a code to improve its performance by savingcycles of cpu. The super optimized solution requires good knowledge of hardware andbit manipulations. 🙂Hi Avi,

i was wondering…..does the code tag works here…?

#include

int main()

{ printf("something");

return 0;

}

yes it does I guess

Use “[” sourcecode language=”C” “]”

`"[" /sourcecode "]"`

`I have put [ and ] in quotes, but these should be used without them`

Complete code for question 6:

Avi, is this code OK for the problem or is there some better solution 🙂

@Ashwani

You should not use Global variables in recursive code. It is considered cheating.

There is a common trick to make such codes

not useglobals. Just modify the code to not use globals and this will work 🙂@Ashwani

It seems you placed a space between [ and sourcecode. This stupid wordpress could not understand it. Will edit your code and repost it and then study it.

BTW its the first

codepost on this blog except mine :P.Implementation for problem 4:

is a buggy statement. Correct it and thats it 🙂

Also you can completely avoid the function call and do it without using an array, which is the reason of the above bug.

Hi avi, i used “p[j] == 0” to terminate the for loop in case the returned array from function contains less than 32 entries(it wud have 32 entries if input is largest int of 4 bytes) and rest would be zeros(as i got zero initialized array from malloc on linux machine 🙂 ). I could not understand the reason of the bug, can u tell me in some more detail.

Regarding question 6, instead of using global variables , i could pass them as parameters in the “printL” function..!! is this the trick or there is sth else ?

@Ashwani

malloc does notguarantee that all the data which it allocates will be initialized to 0. 🙂You should either change it to

callocor do something else.Yes, passing the variables as parameters (more precisely as

pointers) is what is considered a cleaner approach. The code sometimes get dirtier but is worth it because on a larger scale you never want globals in your project. So in recursive code, you should always avoid globals. 🙂