Interview Questions 15

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.

Advertisements

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

12 Responses to Interview Questions 15

  1. Amar says:

    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. 🙂

    • Ashwani Sindhu says:

      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. 🙂

    • Avi Dullu says:

      @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 optimized solution to the problem, again I was referring to implementation. I could drill down a code to improve its performance by saving cycles of cpu. The super optimized solution requires good knowledge of hardware and bit manipulations. 🙂

  2. Ashwani Sindhu says:

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

    #include
    int main()
    { printf("something");
    return 0;
    }

  3. Avi Dullu says:

    yes it does I guess

    #include<stdio.h>
    
    int main() {
    
    printf("Hello World");
    return 0;
    }
    

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

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

  4. Ashwani Sindhu says:

    Complete code for question 6:

    #include<stdio.h>
    #include<stdlib.h>
    
    struct node {
    	int data;
    	struct node *left;
    	struct node *right;
    };
    
    int rootLeft =1;
    int rootRight =0;
    struct node* NewNode(int data){
    	struct node* node = malloc(sizeof(struct node));
    	node->data = data;
    	node->left = NULL;
    	node->right = NULL;
    	return node;
    }
    
    struct node* insert(struct node* node , int data) {
    	if(node==NULL)
    		return NewNode(data);
    	else{
    	if(datadata) node->left = insert(node->left, data);
    	else node->right = insert(node->right,data);
    
    	return node;
    	}
    }
    
    /*
    ** In the function below, the internal nodes are printed until the first/leftmost leaf node and after the last/rightmost leaf node.
    ** The first leaf node is identified when code enters the first "if" block for the first time, the last leaf node is identified by
    ** using the "count" variable which is like a sum along the path from root to leaf and is zero only for rightmost leaf as only its 
    ** path from root is formed by nodes which are right child of their parent.
    */
    void printL(struct node* node,struct node* root,int count){
    	
    	if(node->left == NULL && node->right == NULL)
    	{	printf("%d ", node->data);
    		rootLeft = 0;
    		if(count == 0)
    		rootRight = 1;
    	}
    	if(node->left != NULL)
    	{	if(rootLeft == 1)
    		printf("%d ", node->data);
    		printL(node->left,root,(1+count));
    	}
    	if(node->right!=NULL)
    	{	
    		printL(node->right,root,count);
    		if(rootRight == 1 && node!=root)
    		printf("%d ",node->data);
    	}
    }
    
    int main()
    {
    	struct node* root=NULL;
    	/* constructing a complete binary tree of depth 4 */
    	root = insert(root,150);
    	root = insert(root,100);
    	root = insert(root,200);
    	root = insert(root,70);
    	root = insert(root,120);
    	root = insert(root,170);
    	root = insert(root,250);
    	root = insert(root,30);
    	root = insert(root,80);
    	root = insert(root,110);
    	root = insert(root,130);
    	root = insert(root,160);
    	root = insert(root,190);
    	root = insert(root,210);
    	root = insert(root,270);	
    	root = insert(root,25);
    	root = insert(root,40);
    	root = insert(root,75);
    	root = insert(root,85);
    	root = insert(root,105);
    	root = insert(root,115);
    	root = insert(root,125);
    	root = insert(root,140);
    	root = insert(root,155);
    	root = insert(root,165);
    	root = insert(root,180);
    	root = insert(root,195);
    	root = insert(root,205);
    	root = insert(root,220);
    	root = insert(root,265);
    	root = insert(root,290);
    	
    	printL(root,root,0);
    
    	return 0;
    }
    
    

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

    • Avi Dullu says:

      @Ashwani

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

      There is a common trick to make such codes not use globals. Just modify the code to not use globals and this will work 🙂

  5. Avi Dullu says:

    @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 code post on this blog except mine :P.

  6. Ashwani Sindhu says:

    Implementation for problem 4:

    #include<stdio.h>
    #include<stdlib.h>
    
    /* If input itself is also a power of 2, it is also printed */
    int * GetMultiplesOfTwoLessThan(int num){
    	int i=0,t=1;
    	int *arr = (int*)malloc(sizeof(int)*32);
    	
    	while(num!=0)
    	{
    		num>>=1;
    		arr[i] = t<<i;
    		++i;
    	}
    	return arr;
    }
    
    
    /* Driver function to test above function */
    int main()
    {
    	int *p,j;
    	p = GetMultiplesOfTwoLessThan(30000);
    	for(j=0;j<32;++j)
    	{	if(p[j] == 0) break;
    		printf("%d\n",p[j]);
    	}	
    
    }
    
    • Avi Dullu says:
      if (p[j] == 0)
      

      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.

      • Ashwani Sindhu says:

        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 ?

  7. Avi Dullu says:

    @Ashwani

    malloc does not guarantee that all the data which it allocates will be initialized to 0. 🙂
    You should either change it to calloc or 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. 🙂

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: