Wednesday, February 13, 2013

Microsoft Interview of Monika Bisla

Written Test (Nov, 2012):
30 MCQs based on Algorithms & logical aptitude and 2 coding problems.

Telephonic Interview (7th January, 2013):
All questions related to your resume & projects and some behavioral questions.

Interviews (27th January, 2013):

Round 1:
  1. Write code for run-length encoding of a given string in-place (without using any extra memory).
    Sample Input: aaaaaaaaaabcccccc Output: a10bc6
  2. Write code for a function which converts a given integer to a string. (Use only one for-loop).Check for all the boundary cases.
  3. Suppose you are going to organize a party from 9:00 am to 20:00 pm. You have invited 'n' number of guests for the party. You are given the arrival time and the departure time of all guests. Every time a new guest arrives, you give him a glass of wine and when he leaves, you take the glass back. If someone has left and returned the glass, you can give the same glass to a new guest who has just arrived.
    Based on the given schedule for guests, determine the minimum number of glasses required for the party. A guest can come or leave at any time, but you are given the fixed schedule. Write code for the given problem.
Round 2:
Some questions related to resume and subjects studied in the curriculum.
  1. How can we do a Tree Traversal without using a stack (not even the stack for recursion). Write code for an in-order traversal without using stack. What would be the changes in the function if we want to do a pre-order or post-order traversal?
  2. Write code for finding loop in the singly linked list and fixing it.
  3. Given a linked list with two pointers, one is next pointer and another is a random pointer which can point to any node in the list (forward, backward or itself), you have to make a copy of this list without tempering the original list. Write the code for the same in O(n) time complexity.
Round 3:
  1. Give different possible approaches for Checking whether two strings are anagrams (with and without using hash tables). What are the possible advantages and drawbacks of each approach? Write code for the approach which involves first sorting the two strings and then matching character by character (O(n lg n) approach). Which sorting you will use and why? Write test cases also.
  2. Write code for counting the number of inversions in an array in the minimum time possible. What could be different possible approaches?
  3. Given two huge numbers represented as linked list, write a function to add them and return a number in the same format.
    Ex: 950 represented as 9->5->0->NULL
    150 represented as 1->5->0->NULL
    then, the output should be 1->1->0->0->NULL
  4. We have ‘n’ people in a party, out of whom only one can be a celebrity. And he may or may not be present in the party. A celebrity is known to everyone but he does not know anyone. All other person may or may not know each other. If a person ‘A’ knows ‘B’, it does not implies that ‘B’ also knows ‘A’. You can ask only one question to someone ‘Do you know this (‘X’) person?’ and he can only reply in YES or NO. Your job is to find the celebrity in minimum number of questions.
Round 4:
First he asked general questions from resume.
  1. Write code for finding the least common ancestor of two given nodes in a binary tree. ( both recursive and iterative approach).
  2. Which data-structure you will use for implementing the ‘malloc’ and ‘free’ functions? (You have been given with a pointer which points to a large chunk of memory).Write full codes for implementing these two functions.
Each face-to-face round duration was approximately 1 hour. Results were declared after 4 days of interviews. Every interview was an eliminating round. Questions were not very hard but they were very keen on accuracy and efficiency of code (it should run on all possible input cases).

Friday, December 28, 2012

Amazon Interview of Vaibhav Shukla

Round 1 : Written (Online @ Interview Streets)
Apti , C/OS mcqs(Test your C Skills level) and 2 codes
  1. Given a tree, return its mirror image.
  2. Given a tree and an integer SUM , return true if there is a root-to-leaf path such that sum of all the node values result to given SUM.


Round 2 : Written 4 coding questions
  1. You have a singly linked list where apart from 'next' pointer , each node has a random pointer which can point to anything (either any node or may be NULL).
    Create a clone of this list and return its head. Figure could be helpful.
  2. Given an array of the form {a1,a2,a3.....an,b1,b2,b3......bn,c1,c2,c3........cn}
    Write a funtion to rearrange the array in the form {a1,b1,c1,a2,b2,c2,a3,b3,c3..........an,bn,cn}
  3. Given a binary tree in which each node has an extra "next" pointer . Populate this next pointer of each node with its InOrderSuccessor

    InorderSuccesor of a node is the next node appearing while travering the tree InOrder.

    struct node {
        int data;
        struct node *left;
        struct node *right;
        struct node *next;
    };
  4. Given a Binary tree , a start node and an integer K, Find/Print all nodes @ distance K from the start node
    function prototype - void findNodesAtK(struct node *root, struct node *start,int K);

Round 3 : Telephonic Interview
He told me that he'll be asking coding questions and puzzles only.His focus was on optimization.
  1. 25 horses , 5 can race at one time. Minimum number of races to find three fastest horses.Though its a well known puzzle,he wanted me to code this :P
  2. Given a binary matrix where each row has 1s followed by 0.There can also be a row with no 1s(or all zeros) . Return a row with maximum number of zeros.
    Gave two three approach, he wanted me to give optimal solution.From n^2 to nlogn to n .
  3. Given a integer array , return maximum product subarray. You just have to return maximum sum.

Round 4 : Face to Face Interview
Again focus was on Coding and Problem Solving Skills
  1. There is a town having civilians and a Mayor . You have been given an API bool xKnowsy(x,y) which will return true IFF x knows y.
    Now you have to find the Mayor based on following constraints
         a. Mayor doesn't know any civilian.
         b. Every civilian knows the Mayor.
         c. and between civilian,they may or may not know each other.
    Write a code to find the mayor using the given API.
  2. Implement Google's auto-completion feature i.e as you keep on typing characters,you see the sentences or words appearing below.
    Then he modified the problem and said , You have a dictionary having words, every time I type a character,return me the list of top 5 words appearing as in google's search bar.
    For example : if dictionary has words: if,in,info,int,integer,it. Then on typing i , words suggestion would be if,in,it
    then if the next character entered is n i.e now "in" , so possible suggestions are in,info,int,integer
    Again he modified the problem to search the word entered using the same struture that i used for above problem.
  3. Few questions on my resume-extra curricular activities. (He was Rajan sir's class mate from RLA :P)

Round 5 : Face to face interview

Mixed questions
  1. Performing Big Int Addition using linked lists
       1->2->3
    + 2->1->2
    -------------
       3->3->5
    -------------

    The resultant addition linked list has to be returned. He asked me about different test cases that i would be handling.
        a. Linked lists can be of different length.
        b. On adding last to digits, if the carry is there, then one extra node would be there in the resultant
     linked list. and rest basic test cases(NULL check etc).
    Then he modified the problem and asked to solve it recursively. The addition should be done recursively.
  2. Given a linked list and an integer K . Reverse the nodes in groups of K.
  3. Vaibhav is connected to A,B,C,D on facebook. A is connected to P, P to R and may be other. like wise B->E->F->C. This type of structure was given in which a person may be connected to other, in such a way that there could be more than one path between any two given people.
    Now, given two people. Find the shortest path between the two.
    Note : Don't use Dijkstra's.Actually you can (he wanted something else :P)
  4. How TCP verifies that packets are reachng the destination in sequence?
  5. Explain the process of page load when you hit www.amazon.com in url bar,in brief.
  6. Diff between threads and process. Why are threads called light weight ? What is a system call ? Difference between system call and interrupt.
  7. You are moving in an infinite string of words.At any point in time,you'll be asked to stop. Then on whichever word you are, return all the anagrams of that word present in the infinite string.
  8. Probability : Given two jars and 50 blue ball and 50 red balls. Distribute the balls in two jars in such a way so as the probability of picking up a red ball is always maximum.

After a month :
Round 6 : Face to Face interview (Algo/DS)

  1. A number i is given in its binary form, Find the next greater number than i having equal number of Set bits.
    Example : If i = 011001 , then next greater number with equal number of 1s will be 011010.
    Hint : Try more examples and figure out a pattern.
  2. Given an integer Array and a number K , find a Pair (just one) in the array whose sum equals to given K.
    Two three approaches were discussed and he wanted to optimize the solution as much as possible.
    Last constraint was : Without sorting the array, do it in O(n) time.
  3. You are given an array of Strings, return TRUE if and only if All the strings can be connected in one chain.
    Condition for connectivity is , if the last character of one string matches first character of second string, the two string can be connected.

    Example : String []arr ={"abc", "cde", "cad" , "def" , "eac"} will return TRUE coz all strings can be connected in one chain
    "abc"->"cde"->"eac"->"cad"->"def"

    Another Example : String []arr ={"acb" , "cde", "def", "ead" } returns False coz "cde"->"ead"->"def" is the possible chain but "acb" is left out.

    Note : Its not necessary to start with the first String and form the chain, It may happen that you won't get a chain if you start with first string but you can get a chain if you Start with any other String. If there exists a possible chain, then your solution should return True.

    In the second example , if the first String was suppose "fcb" , then a possible chain would have exists "cde"->"ead"->"def"->"fcb" so True.

Monday, October 22, 2012

National Instruments Interview of Monika Bisla

Written:


  • sqrt(b^2 - 4ac), if a =[0, 0.5] and b=[4, infinity), Whats the range of c?
  • Write a recursive function to get the product of all the digits of a number.(eg: for 123: output 1*2*3; for 56: output 5*6=30)
  • Find the 100th number of the series 2, 4, 8, 14, 22, 32....
  • Find the 20,000th element of the series 1, 2,2, 3,3,3, 4,4,4,4, ....
  • Write a single statement to check whether a given number is a power of 2.
  • T(n) = 2*T(n-1)+2^(n-1); T(1) = 1. Find T(7).

  •  int index, i=0, k=0, j=0;  
     for(index=0; index <= some_number; index++){  
       i = i+1;  
       if( (i/5) == 1 ){  
         i=0;  
         k = k+1;  
         if( (k/5) == 1){  
           k=0;  
           j = j+1;  
         }  
       }  
     }  
    

    What's the value of i, k, j interms of 'some_number' after the the execution of for loop?
  • A bag contains 3 coins out of which * 1 coin is painted RED both the sides * 1 coin is painted BLUE both the sides* 1 coin is painted RED with one side and BLUE with another. Two coins are selected from the bag and tossed. Find the probability of  getting both as RED.
  • What's the effect of(or write a common code) the following code on an array of 8 elements?
     for(i=0; i<4; i++)  
       a[i] += a[i+4];  
     for(i=0; i<4; i++)  
       a[i] += a[i+2];  
     for(i=0; i<4; i++)  
       a[i] += a[i+1];  
    
  • Write a function for generating random number between a given range.
    Using above, write a function to generate random integers between a given range such that probability of each integer is same.
  • How many edges are there in a complete graph of n vertices.
    Using the formula in question above, find number of graphs possible with ‘n’ vertices (graphs need not to be complete).
  • Calculate number of inversions in a given array.
    In general what would be the number of inversions in the worst case and what is that worst case.
  • Let us define a walk from v to v in the given graph:

    Number of 1-walk is represented by W(1) and given by:
            V-V                               // W(1) = 1
    Number of 2-walk is represented by W(2) and given by:
            V-V-V
            V-W-V                           //W(2) = 2
    Find W(3) and W(4).
    Also find W(n) in general.
  • Draw a DFA for a language which ends with 0101.
Interview 1:
In this interview, they basically discussed written test only and some extra questions:
  • Write code for making a copy of Binary Tree.
  • Write code for finding maximum root to leaf path sum.
    Write code for both approaches (top-down and bottom-up).
Interview 2:
  • Given a long formula for a carbon compound, Write a code for counting the number of carbon atoms.
    Ex: (C2H6(CH2)6CH2C3H4)4CH2C6H6C5H5
    Handle all the cases.
    Give code for iterative as well as recursive approach.
  • Given a Binary tree, where internal nodes of the tree represents an AND or an OR gate and leaf nodes consists of values either 0 or 1.
    Write code for finding the final resultant at the root node.
  • In the Question given above, add one more argument to your function which gives the expected value of the result.
    If result calculated by your function and expected values are not same, flip the gates in internal nodes of tree in such a manner such that result and expected values comes out to be equal.
    Do this in minimum number of flips possible.
    Also handle those cases where it is impossible to achieve the expected value.
    Write the code for above problem.
Then, there were some normal HR questions and that was it!! 

Friday, August 10, 2012

Thoughtworks Interview of Monika Bisla

1st round:
11 logical assessment question based on some flow charts.

2nd round:
Coding round.

Interview 1:
  • Tell us about yourself.
  • What all subjects in Computer science u like ??
  • Then they asked: Are u comfortable with OOPs? I said, yes.
    He asked "Have u seen movie avatar"? I said, No. He said..does not matter..
    Suppose there is a rocket , it contains a Spaceship.I want to send some people on Mars.People are there in the spaceship.Write a program to lend the spaceship on Mars planet. Make all the classes.
    Then, they said, Suppose tomorrow i change my requirements, i want to send 'N' number of things top Mars , Or i may also send rocket empty,just for testing. Incorporate all these things in your classes n show us the main program, How all these classes are related, how will u make the spaceship lend on Mars.
    It took around 20 mins in this question only.
  • Do u know about recursion. Write a program to print a given character 100 times.
  • 2 more coding problems:
    1. Write a program to find 1st and 2nd maximum from an array.
      I wrote it...I used swapping in the program at one place. Then they said..do it without swapping.
    2. Given Input :: x1y2z3 Output :: xxyyzzz
      I wrote the program Then they said, suppose input could be anything like
      Input:: abc3defgh1aa3 Output:: abcabcabcdefghaaaaaa
      Change your program accordingly.
  • Are u comfortable with DBMS ? What is normalization.
  • Do u use Twitter..?? I said, No, I use facebook. They asked, u make post on ur wall.Simulate a database for this.What all table will u make.??
    I made only 4 tables (since they were specifically asking about posts)
    • User's Table :: user_id , user_name , Place , d.o.b , rel_status
    • Friend's Table:: user_id , friend_id
    • Post Table:: Post_id , User_id , Likes , Post_text
    • Comments Table:: Post_id, Comment_text , Friend's Id(who made the comment)

    Then they gave me an SQL query:
    Write a query to retrieve all the comments made by USER 'X' on all of his friend's posts.
    I wrote the query using three nested sub-query.
    They asked, Is there any other way of doing this?
    I told it can be done using Views but I don't know how to do that.
  • Then, they asked , Have u heard about the sudoku game? Make a class for that and how will u solve the game , given some random values? What all data structure will u use? Give us the proper implementation.
  • Would u take a 9*9 grid or how will u do that ?
    I said i will make a class of 3*3 grid. N i will make 9 objects of that class.
    How will u do that?
     class sub_mat {  
       int a[3][3];  
       public:  
         . . .  
     }   
     int main() {  
       sub_mat sudoku[3][3];  
     }  
    

    Then , they asked me to do the initialization. I made a function for that. - Then , they asked me how would u solve it now? I told them my approach. - they asked me to show the syntax of that function n how would i call it? What all things will be used?
    I made a static function in the class, in which i passed the whole grid.. Then i calculated all the possible values for each cell.
Interview 2:
  • They again started with OOPS concepts.
    They asked," u must have travelled in DTC bus ". Write a class and its member functions.
    I made a class for vehicle..added data members (like model_no , price , serial_number , Type of vehicle , name..etc) then i added some functions like (start(),stop()...etc.)
    I made a class Bus, I made vehicle class public to it. I added data members and functions for bus class. They wanted to add more and more functions. 
  • Then, they said suppose there are three type of seats (Women, Senior citizen and conductor), how will u implement this thing in your class?
    I implemented it using a 3*3 array in which i stored type_id for a particular seat and then a range for that particular type.
  • Then, they said, Suppose we do not have any range , we can give any seat randomly to anyone, how will u implement it now, and there can be 'n' number of types of seat. -I made a hash table kind of thing. Then they said there is lot of pointer kind of things in this bus class. Make a separate class for this data-structure for seats. 
  • Then they said, "you have also done Java, Is there any data-structure available in java for this ?" Implement that also.
  • They asked.., shouldn't you categorize your vehicle class more,on the basis of type of vehicles. what all classes should be there and what all member functions should be in each class. (they spent half an hour on this question only.)
  • You have done compiler , So tell us what is a linker and what is a parser? How do they work? Who call them when a program gets executed and to whom they return their values?
  • Make a parser for a language in which i have data-types like :: tni a; taolf b;
  • Tell us about various scheduling algorithms.
    • How would u implement Remaining Time First ?? (I did it using min-heaps)
  • What is preemption?
  • What is Process Control Block? How does it gets implemented in memory?
  • U have done K-means algorithm , Let me ask u a puzzle.
    Suppose u have a Car , U have infinite amount of fuel , U have to go to some city "XYZ". U have never heard the name of the city, U dont know anything about it. U dont know in which direction it is and u cant get any information from any source. What strategy u will make to go to that city?
    I asked, Sir , can u tell me the distance. He said, no, It can be anywhere..it can be thousands miles away in any direction.
    My answer : I will first go straight from wherever i am , then i put a mark there, and take a circular round to ensure that place is not located in that radius.then , i again travel straight and take a circular round and so on until I find the place..
    then he asked, Is it a BFS or DFS ?? I said, first we go straight (i.e. DFS) and then we take a round (i.e. BFS) , so it is a mixture of both BFS and DFS.
    He said, Suppose now i am ready to tell u one hint, What will you ask for and what will be ur strategy? I said, tell me the distance.
    He said, it is 10,000 miles away.
    I answered, I will go straight 10,000 miles and take a circular round..:)
And that was it.
(Important part was that they wanted implementation of all things and you had to do everything on board.)

Friday, August 3, 2012

Google Written On Campus

Google visited our campus for the first time. The procedure consists of the following rounds:
  • Written test
  • Sets of Interviews
The Written Test
The written test consisted of 2 sections: 
  1. MCQs: There were 20 questions consisting of questions from OS, Algo, general logic etc. They covered all the things from basics of each subject to advanced concepts like NP Hard Problems etc.
  2. Coding Section: Coding section consisted of 2 programming problems:
    1. Problem 1: Two friends Atul and Vinay went for a picnic on an island. The island is a grid of m x n. While going back to home, Atul went and Vinay was left on the island. Now upon realizing this mistake, Atul is coming back to the island. In the meanwhile, Vinay will be wandering on the island. His probability of taking a step in any of the 4 direction (up, down, left, right) is equal. This means that he may fall into the sea as well and drown. Given the no of steps (k) he'll be taking before Atul arrives, size of the island (m x n) and his initial position (x,y), find the total probability that he'll be alive after Atul arrives.

      int ProbabilityOfBeingAlive(x,y,m,n,k)

    2. Problem 2: Write a code to multiply two integers.

      int Multiply(a,b)
Candidates shortlisted were called for the interviews in B'lore later.