Showing posts with label MSc 11-13. Show all posts
Showing posts with label MSc 11-13. Show all posts

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

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.

Saturday, July 7, 2012

Aricent Interview of Monika Bisla


Written exam was same for all. For details regarding written, click here.

Interview
My interview started with my resume. The interviewer had a look at my resume and asked about my recent projects. I told him briefly.

Then he started with C questions like

  • What will happen in this code :
main()
{
        main();
}
I replied with Segmentation Fault. Then he asked what is a segmentation fault? In which conditions segmentation fault can occur?
  • Which loops are used in C language? Difference between while and do-while?
  • Types of storage classes in C? Difference between auto, static, extern and global variables. What is their scope and where do they get stored in memory.
  • How can we write structures in a text file and then retrieve it?
  • Fopen and Fclose commands in C,  how they are implemented?
  • OOPS concepts, What is polymorphism and types of polymorphism? What is function Overloading?
  • Can we use sizeof() operator in #define preprocessors? If not, why?


After this he switched to Software Engg.

  • SDLC(S/w develoopement life-cycle.)
  • Various models? Why watrefall model is called waterfall? What is an Agile model?
  • When we do requirement analysis, which is the most basic step?
  • What is RISK? How do we do risk management? (he also asked, “Is joining Aricent a Risk”? :))
  • What are various kind of testings? Unit Testing , Integration Testing, Regression Testing?
  • When do we do all these testings during developement of software?


Switching to Operating Systems,

  • How do we implement Cache?
  • What is purging?
  • What is a page fault? How do we handle it?
  • What is a deadlock? Give an example.

After this, he asked about difference between Stack and queues and their applications? Which data structure do we use for recursion? Why stack is used for recursion?

Starting with Computer Networks,

  • What is the difference between TCP and UDP? where are they used?
  • Layers of ISO model, protocols used in application layer and transport layer.
  • What is the difference between packet switching and circuit Switching? TCP and UDP use what?
  • What is difference between http and https?
  • Port number of FTP, HTTP?
  • What is difference between a switch and a router? In which layer they are implemented? What are L2 and L3 switches?
  • What is a VPN? Is it implemented using internet?
  • What is VLAN?
  • How do we implement a WAN?
  • What is GSM? How it is implemented? Is it used for voice or data or both?
  • What is GPRS? how it is implemented? Can we send voice packets on GPRS?
That's it. 
Overall, he covered all the topics.