Monday, July 15, 2013

Aricent Interview Experience of Isha Aggarwal

Written : 
This time, Aricent had an online test instead of written test.
It comprised of 4 sections.

Section 1 :

Questions based on English and verbal ability were there.
Comprehension based questions were there.
Some other questions included : improve the italicized part of the sentence, or to select the synonym or antonym of the given word, to arrange the given sentences in an order, and so on..

Section 2:
This section was to judge your Quantitative aptitude. Questions on Logarithms,profit and loss, speed distance time, work, calculating cost of fencing, etc. type questions were there. Just revise your concepts and main formulas, and that would be enough.
During your mock tests, try making a note of formulas simultaneously.. It wont burden you in the end!

Section 3:
It was a mix of DS concepts and programming concepts. It was a simple section. Just be thorough with basic concepts. In some questions Pseudo codes were given, and output was asked. A few questions on C++ were also there. Only basic concepts.

Section 4:
It was the logical ability section.
Questions were simple in this section as well. Complete the series type, Given a para of information, and then answer the questions. Blood relations, a string encoded as another word, so what will be the code for another word. Notation of operators changed, and then answering the questions that follow. Data sufficiency questions were there.


People who cleared the written were asked to fill the
 Critical incidence form which consisted of questions like:
  • State a situation when you had too many tasks at one time and how did you handle it.
  • State a situation when you yourself was busy but still helped someone out.
  • When you were in a very difficult situation and you came out of it.
  • what was the most difficult decision you ever had to make.
  • Write an incidence when you stated an unpopular opinion.
  • State a task you completed of which you had very little/no knowledge.
For every question, you have to write what was the situation, how you handled it and what was the outcome!
This form will be discussed in detail during HR. So don't cook up stories.Try to think of real incidents..
Include 
We were then called for GD in a group of 10 or 12, and it was a non-eliminatory round.



INTERVIEW :

I was first asked about the programming language I am comfortable in and about some programs that I have done.
Then he asked me to write a factorial program optimally, I wrote both the recursive and iterative approach, and told him about the pros and cons of each.
Next he asked me to write a program to swap 2 numbers optimally. For this I wrote the program without using any temporary variable. I then told him about XOR method as well. He then asked me what is XOR operation and asked me to do swapping using XOR with an example.

Then he asked me to explain Quicksort with an example. He basically wanted complete dry run. Then he asked me the running time of quicksort. When I answered about worst case running time, he asked me to give a worst case input for QS.
Then he asked me differences between Insertion sort and Bubble sort, again with an example of each.

Next, he asked me to explain how to implement stack using Linked list.Where push and pop will be done, etc.
And then implementation of queue with linked list. etc.

Then he moved to OS :
Asked me what is a process, characteristics of a process. Structure of PCB. Difference between a thread and a process.What is a semaphore.Why is it used. Types of semaphore etc.

I guess that was all. He then discussed the critical incidence form in detail, so no seperate HR for me!

All the very best to all :)

Friday, June 14, 2013

Adobe Interview of Samarth Gupta

Written:
It consisted of 3 sections viz Apti and Quant, C and Engineering.
C paper consisted of 10 questions that were based on pointers and functions.
Check if an expression has valid parenthesis

Engineering Paper:
  1. Each instruction on JVM is in byte code. How many such instructions are possible?
  2. Some Memory and Process Scheduling based scenario was given along with 4 options.
  3. Synchronization of two processes using the following code:
     boolean lock;  
     while(lock) ;  
     lock = true;  
     /* critical section code */  
     lock = false;  
    
    Is it feasible?
  4. Reverse a Singly linked list
  5. Check if a number is palindrome without converting it to string
  6. Implement multiplication recursively
  7. A number has 3 on it's unit place if one of it's multiples has 1 on all it's places. e.g. 111 is a multiple of 3, 111111 is a multiple of 13. You need to find such multiple of a given number. The multiple may be very large and exceed the limits. Don't use any complex data structures.
  8. A matrix having 0s and 1s is there. Each row can not have a 1 followed by a 0. You need to find the row having maximum 1's.

Interview 1:
It started off with compilers. Explain Parsing, different types of parsing, LR(1), LALR(1). 
Steps of compilation, explain lexical analysis, linker, loader.
Examples of syntax error, semantic error, linker error, relocatable addressing.

OS:
Process management, memory management, process v/s thread, file descriptor, synchronization techniques etc.

C/C++:
Some questions for output, overloading v/s overriding, structures v/s classes, inheritance, virtual functions, can constructors and destructors be virtual? why or why not? diamond inheritance problem, and a lots of questions on pointers. Some statements were there and I had to read them properly i.e. 
 int *p;  
 P is a pointer to integer  
Complex ones were there.
In C, functions are evaluated right to left. Why, any benefit?

Data Structures and algorithms:
Convert an expression from infix to postfix and vice versa (code)
Merge two sorted linked lists removing duplicates.
Reverse a Linked List (any other method than the one I had written in the engineering paper)
Height of a tree (he asked me more than one method. I was able to give 3 solutions)
2 sorted lists, you have to find the element of rank k in their merger without actually merging them

Assembly code to generate factorial of a number (I assumed some basic instructions like ADD, SUB, JMP etc)


Interview 2:
Design a base 64 encoder for an infinite stream of data.
Implement cin and cout using printf and scanf
Implement LRU Cache
Design a class to give following 3 functions in O(1):
  • void insert(int data)
  • void delete(int data)
  • int getRandom()

Serialization and de-serialization of a binary tree.
What are smart pointers?
How garbage collection works in java?
Malloc and Free
Maps (Hash maps) and how they work?
Average of 4 unsigned integers (simple addition might result in overflow)


Interview 3:
It was with the director of the acrobat team. Started off with my intro, what I do in leisure time, and it continued for next 20 minutes on Online Gaming. Next 20 minutes were on my project in snapdeal and next 20 mins were on what Acrobat Team does and how acrobat helps adobe earn profit.
Then he moved to DS and Algo:
Reverse a Doubly Linked List (proper code)
You are given an infinite sequence of words. what you need to do is when a new word is there, store it. whenever a word is repeated, throw an exception. Make sure you do not spend too much time in searching. Give a solution using some DS and design an algo for the same. Then this moved to phrases, then he asked me to store the sequence as well.
That's it..

Interview 4 (HR Round):
This was a casual round where we discussed about adobe, job profile, facilities etc. 

Hope it helps!
All the best.. :)

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!!