Samsung Interview Experience

Following questions were asked by Samsung for it's Software Engineering Labs (SEL) position.

1) What is the difference between a process and a thread?

2) Compare Merge sort and Heap sort. What are their time and space complexities? State the cases when one will perform better than the other.

3) What is Page table, Address space, and Virtual memory?

4) Given a binary tree, find the node containing a Minimum heap of maximum size below it. So the node will be the root of the min-heap of maximum possible size in the binary tree.

5) Construct 2 stacks using a single array. Follow Up: Construct 3 stacks in a single array.

6) What is a deadlock? 

7) What are function pointers? What is their significance?

8) Reverse each word of a string "in place" (that is without using additional memory)

Ex: "Ram and Shyam are friends" --> "maR dna mayhS era sdneirf"

Source: Sravan Bodapati, CSE IIT-Madras

Samsung Design Labs: Technical Test

Samsung Design Labs conducted a Technical test for their selection process. I've outlined the test below to the best of my memory.

There was an objective paper which had 20 questions related to CS topics like Algorithms, C++, Data structures.

The 2nd paper was subjective which had 2 algorithm questions

1) Given a set of points, develop an algorithm to find their convex hull. Write code in C++ or some other similar language.

2) You are given 2 convex hulls. Develop an algorithm to find all the common points; that is the points that lie in the intersection of these 2 convex hulls. Write code.

Note: Assume that the convex hulls are for the points in 2D representation.

Walmart Labs Test

Walmart Labs opened it's India division very recently. It has been on a hiring spree since then. The profile was Software engineering in the area of Machine Learning and Big Data.

It conducted a 1.5 hour test which consisted of 15 objective questions based on basic concepts in Networks, Data structures & Algorithms, some simple questions on Combinatorics.

There was a subjective section too, which had 2 questions to be coded on a piece of paper.



1) Given 2 additional members, node* prev, node* next in a binary tree node* struct. Initially prev and next are set to NULL. Populate these 2 pointers in the binary tree using inorder successor and predecessor of the respective node for all nodes in the tree.

2) BreakDown(K, S). Give an algorithm to calculate number of distinct ways in which you can break up amount K into denominations present in S, set of denominations. 

Pocket Gems Coding Test

Following coding questions were asked by Pocket Gems, a social gaming company based in San Francisco. Total duration was 1 hour.

1) Given an array of positive numbers. We can make any element of the array negative. We have to find the minimum positive sum after modifying numbers of array, by making some numbers negative.

2) Given an array of pairs of the form <a, b>. We have to find a sub-array such that the 1st element in the pairs are in increasing order and the sum of 2nd element of the pairs in the sub-array is maximum possible.

Source: Arun Chaudhary, DCE

Microsoft Internship Interview

It was August, 2011 and start of my 3rd year at IITB. It was internship season at IITB and I was desperately looking for a summer internship. Microsoft visited the campus and I was shortlisted (based on CPI) for interviews.

There were no personal interviews. Instead, every batch of 10 students was taken in a classroom and we were given to solve a couple of questions. We were asked the following questions and we had to write working-code on a piece of paper.

1) Coin-change problem. Given unlimited denominations of 1$, 2$, 5$, 10$; find the total number of ways to make change for amount 100$.

2) Given strings a, b, c. Replace all occurrences of string b in a with string c. Note that there is no restriction on lengths of a, b, c.

Somehow, I managed to code up the problems but not very neatly. I asked the interviewer to check my solutions. He stared at the code I had written for a couple of minutes and then asked me some questions and tried to confuse me. He then asked me about the complexity of my code and I was able to estimate it correctly. He then said that I was done with the process and could leave.

I thought that my interview performance was not up to the mark and didn't expect that I could get selected by Microsoft. However, later on, in the night I got a call saying that I had been selected by Microsoft for it's Summer Internship Program. Phew! I was relieved and my worries about getting an summer internship vanished all-together. :)


Key Takeaways

• You should be able to write neat code at one go. Practice writing actual code (C++/Java) on a piece of paper or white-board.
• Do some dry runs of your code for some test-cases and check whether it's doing what it's supposed to do.
• You need to cross-check your code twice and look out for small mistakes that you might commit due to interview pressure.

RocketFuel Codesprint at IIT-Bombay

Rocketfuel is a targeted digital advertising company. It offers the profile of Rocket Scientist, which involves doing work related to AI, Machine Learning and Big Data Analytics. The work location was Redwood City, California. Following questions were asked at Rocketfuel's codesprint for placements at IIT-Bombay. The interface used was InterviewStreet and the total duration of the sprint was 4 hours. 

Problem #1
In this problem your goal is to write a program to examine the outputs from a sequence of operations on a data structure called a single-output deque, and deduce the sequence of operations that produced that output.

An ordinary deque is data structure that represents a list and supports the following four operations:
pushFront(x): add x to the beginning of the list so that it becomes the first element of the list
pushBack(x): add x to the end of the list so that it becomes the last element of the list
popFront(): remove and return the first element of the list
popBack(): remove and return the last element of the list

In this problem, we are considering the behavior of a single-output deque, which is the same as a deque except that it supports only pushFront, pushBack, and popBack.
Furthermore, we modify pushFront and pushBack so that they do not accept an argument. Instead, pushFront and pushBack push the contents of a counter (whose initial value is 1) to the beginning or end of the deque and increment the counter.

Consider the following examples:
(pushBack, pushBack, pushFront) results in the following sequence of list states:
(1)
(1, 2)
(3, 1, 2)
(pushFront, pushFront, pushBack, popBack, pushBack, popBack) results in the following sequence of states and outputs:
(1)
(2, 1)
(2, 1, 3)
(2, 1) output: 3
(2, 1, 4)
(2, 1) output 4
In the previous example, the output of the entire sequence of operations can be written as (3, 4).
Your program will receive exactly one line of input, a comma-separated list of integers with no spaces in the following format:
x_1,x_2,...,x_N
where 1 <= N <= 100,000 and the sequence (x_1, x_2,..., x_N) is a permutation of the set of integers {1, 2,..., N} (i.e., the sequence is not empty, and there are no repeated or missing values).
Your program should produce exactly one line of output, a comma-separated list of operations with no spaces in the following format:
op_1,op_2,...,op_2N
where each op_i is a string from the set {pushFront, pushBack, popBack}. The output of the sequence of operations (op_1, op_2,..., op_2N) should be the sequence (x_1, x_2,..., x_N). If it is not possible to produce the output (x_1, x_2,..., x_N) with any sequence of single-output deque operations, simply print the string “impossible”. If there are multiple sequences of operations that result in the sequence received in the input, choose the output that is smallest lexicographically, ordered by standard alphabetical ordering.

Sample Testcases
Input:
3,2,1
Output:
pushBack,pushBack,pushBack,popBack,popBack,popBack

Input:
1,2,3
Output (note choice of pushBack over pushFront):
pushBack,popBack,pushBack,popBack,pushBack,popBack

Input:
4,1,5,2,3
Output (pushFront is needed in some cases):
pushBack,pushFront,pushFront,pushBack,popBack,popBack,pushBack,popBack,popBack,popBack

Input:
5,1,4,2,3
Output (some sequences are impossible):
impossible

To help with solving this problem in a timely manner, we provide the following hints that may help you work out one way of writing an efficient program to solve this problem:
1. Note that if the first element of the input sequence is 4, then the 5th element of the output must be popBack (unless the output is impossible). The reason for this is that at least 4 pushes must be executed to get 4 into the deque, and the 4th push must be a pushBack so that 4 is ready to be popped from the back of the deque. More than 4 pushes could be executed, but elements 5 and above must be pushed to the front, and this could easily be done after 4 was popped instead of before. Since popBack is lexicographically smaller than pushFront, we prefer to execute popBack as early as possible.
2. Consider simulating the deque as a way to efficiently determine which operations were performed on it. For example, as above, if the first element of the input is a 4, simulate a deque having the elements 1 through 4 pushed into it. Since you do not know whether each element was pushed to the front or the back, try pushing it on both sides and figuring out which side is correct later in the simulation.


Problem #2
After venturing into deep space to use your computer science skills on various projects at the frontier of civilization. You are abducted by the mafia, who had placed a losing bid for some contracts you won. Fortunately, you were able to hide your earnings in a secret location before you were taken away to the mafia headquarters to be questioned.

The mafia headquarters is situated on a space station orbiting the planet, and this particular space station houses a large zero-gravity amusement park. A single guard begins escorting you to the questioning room, and you quickly strike up a conversation. As you are walking past the arcade, the guard claims to be the top pinball player on the station, so you offer a challenge. If you can beat the guard in a single game of pinball, the guard will let you go, and if you lose, you will tell the guard where you stashed the money you received for the irrigation project on the planet below.

The guard accepts your challenge, but you now have another problem. You've never played the particular type of pinball that is played on the station, so you have to quickly learn how to play optimally so that you can achieve a higher score than the guard. Pinball games in this arcade have the following format. You can place a ball anywhere inside the rectangular playing area of the pinball machine and then bump the ball so that it travels in any of the 45 degree diagonal directions. You then allow the ball to bounce around the machine and the ball crosses over various lights that are situated randomly around the board. The goal is to cross as many lights as possible.

"This game isn't too difficult", you think, but the guard then explains that you are allowed to bump the ball one additional time, potentially changing the ball's direction, again in one of the 4 diagonal directions on the board. Thus, your strategy for the game, given the size of the board and the position of the lights, is to choose a starting position, starting direction, bump time, and bump direction so as to maximize the number of lights you cross.

Note that you can only get points for crossing each light once, so the game is over after you have bumped the ball twice (once to start, and once to redirect the ball) and it is clear that the ball will not cross any additional lights even if it is allowed to roll indefinitely. Further, the machine is frictionless and experiencing zero-gravity, so the ball travels in a straight line until it hits one (or two, simultaneously) sides of the rectangular pinball board in a perfectly elastic collision. You can only place the ball at integral coordinates on the board, and you can only bump the ball at integral coordinates.

Since you are an expert computer scientist, your job is to write a program to help you play optimally. Your program should accept input of the following form:

N M K

X1 Y1

X2 Y2

.

.

.

XK YK

where N is the number of rows on the pinball board, M is the number of columns on the pinball board, and K is the number of lights that are placed on the board. The values Xi and Yi represent, respectively, the row and column of the the ith light on the pinball board (0-indexed). Your program should simply output the number of lights that can be crossed using an optimal strategy. For example, the following input:

5 5 4

0 2

0 3

2 2

3 1

represents the following board:

..@@.
.....
..@..
.@...
.....

where each '@' symbol represents a light and each '.' symbol represents space in the interior of the pinball board. For this board, it is possible to cross up to 3 lights, depending on your strategy, so your program should output one line consisting of the number 3. For example, you could start the ball in the upper-right corner at position (0, 4) and then bump the ball up and to the left at position (3, 1) so that your ball follows the following pattern (the 1-indexed timestamp corresponding to the first time a position is reached by the ball is indicated by a single hexadecimal digit -- A == 10 and B == 11):

..7@1
.6.2.
5.3.9
.4.A.
..B..

You may assume that the input will be well-formed, so that the line N M K is followed by exactly K lines, each of which consists of a distinct ordered pair of integers Xi and Yi, such that 0 <= Xi < N and 0 <= Yi < M. All values on a single line will be separated by a single space. The values of N and M can be as large as 1600 and K can be as large as min(N * M, 10000). Points can be earned for test cases of increasing size up to the stated bounds.

Problem #3
Suppose you are a fan of auto-racing and want to figure out which drivers are likely to perform well in an upcoming race. Luckily you have access to a log of the times that each racer started and finished their test race the day before.

The particular rating algorithm you have chosen is to assign each racer R a score that equals the number of other racers who both started after R started and also finished before R finished.

Note that a lower score generally suggests that the racer is faster, and this rating algorithm keeps from penalizing fast racers who have slow times simply because they are stuck behind a crash or slow racer. Additionally, this rating algorithm does not reward fast racers who pass tons of slow racers in comparison to fast racers who race when there are not many slow racers on the track to pass (compare this with rating a racer based on the net number of passes).

More formally, you want to write a program that will read the test race log from standard input. The first line of the log contains a single integer n from 0 to 70,000 that represents the number of racers in the log. The next n lines of the test race log have the following format:

racerId startTime endTime

where racerId is an integer in the range [0,10^9] and startTime and endTime are both integers such that 0 <= startTime < endTime <= 10^18. Each racerId will be distinct. Also, the collection of all start and end times will not contain any duplicate elements.

Given such an input, you should print output in the following format:

racerId score

where score is the score as defined above for racer racerId. The output lines should be sorted in ascending order ofscore with ties broken by sorting by racerId, also in ascending order. This can be accomplished with a simple sort at the end.

Directions:

Please code this problem in Java, C, or C++. Your solution should run in less than O(N^2) on all inputs.

Hint: The naive brute force solution is too slow to run within the time limit. You will need to think of a faster solution. Specifically, we are looking for a solution that is guaranteed to be less than O(N^2) on all inputs. One possible way to accomplish this (there are several other acceptable methods) is to use a data structure with K buckets (e.g., K = 300), each of which is initially empty and is defined by two times. Each bucket  will eventually contain racers whose start time falls between the two times. The bucket boundaries should be chosen such that they ultimately will contain the same number of racers. Then iterate through the racers in end time order and, as you iterate over each racer, build up this bucketed data structure in such a way that you can use it to quickly count the number of racers that finished before him but started after him.

What We Are Looking For:

For this problem, we simply want to see that you can implement the algorithm correctly, without particular regard to principles of object orientation or modularity.  Do give us at least minimal documentation to help us understand what you are trying to accomplish in certain key places of the algorithm.

Sample Testcases 

input:

5

2 100 200

3 110 190

4 105 145

1 90 150

5 102 198

output:

3 0

4 0

1 1

5 2

2 3

Note in the above example that racer 3 has a score of 0 because no one starts after racer 3 (a drawback to this scoring system is the last racer always has a score of 0). Racer 4 also has a score of 0 because the only racer who starts after racer 4's start time (racer 3) has a later finish time. Racer 3 is listed ahead of racer 4 despite having a slower time because racer 3's id is lower. At the other end, racer 2 has a score of 3 because racers 3, 4, and 5 start after racer 2 and finish before racer 2 finishes.

Yahoo! Programming Test

Yahoo's technical test (at IIT-B, 2012 Placements) consisted of 25 objective questions and 2 coding questions. Total duration was around 1.5 hours. Objective questions mainly focused on Data Structures, Big-O, Sorting, C/C++ concepts and some general puzzles.

Coding test had the following 2 questions:

1) You have been given a triangle of numbers as shown below. You are supposed to start at the top and go to the base of the triangle by taking a path which gives the maximum sum. You have to print this maximum sum at the end. A path is formed by moving down 1 row at each step to either of the immediately diagonal elements. 

The path needed is 3->7->4->9 since it adds up to 3 + 7 + 4 + 9 = 23, which is the max possible value.

2) Given an array of strings, display all the strings that are not prefix of any other string in the array.

(Hint #1: Sorting; Hint #2: Trie)

Epic Systems Interview Experience

Epic systems recruited from IIT-B in 2012 for it's office in Wisconsin-Madison, USA. I was shortlisted by Epic Systems for final rounds of interviews at IIT-B's placements in 2012. The interviews were telephonic.

Tech Round The person conducting the interview asked me to give a brief introduction about myself. He asked me to explain about the project that I had done during my summer internship. Then he asked me to tell the difference between a full and a complete binary tree. After that, he asked about Quicksort algorithm. Later on, he asked if I had any questions for him. I queried him about Life at Epic and generally about Madison city.


HR Round The lady first introduced herself and then asked for my introduction. The interview consisted of standard HR questions like 'Why Epic ?', 'Why US?'? etc. She asked me how would I contribute to Epic and about my activities other than academics at IIT-Bombay. She was basically trying to make sure that I was very interested in the opportunity and would definitely join Epic after being selected.


Key Takeaways The telephonic interviews were not technical at all and were conducted just for sake of checking whether you had suitable technical aptitude, communication skills and necessary personality traits. Since the interviews were not very tech-oriented, I think that Epic's Coding Test conducted earlier had a considerable weight in the selection process. My suggestion is that you should perform well on the test to get shortlisted for final rounds of interviews and eventually get selected for the job. Also, having a good GPA (preferably 8.0+ on a scale of 10.0) benefits greatly.

Google's Hiring Algorithm

Found this infographic on Jobvine, very interesting stuff. Gives a good insight on how complex and selective the process is!

How does one 'Get that job at Google'!

Following post is inspired from Steve Yegge's legendary post on prepping for Google Interviews.

Coding Knowledge C/C++ and Java are the preferred programming languages for Google Interviewers. You must know at least one of them really well. You will be expected to write code in the phone screen interviews and in the onsite interviews as well.

Recommended books for CS interviews: 

• Introduction To Algorithms - By Cormen
• Programming Interviews Exposed 
• Cracking the Coding Interviews
• Algorithms for Interviews

Recommended websites for coding practice: InterviewStreet, Topcoder

Big-O This should be the starting point in preparing for an algorithmic interview. You must not struggle with basic complexity analysis, as it will guarantee not being hired. You should be familiar and understand the O, Θ and Ω notations. I recommend reading section on complexity analysis from Data Structures and Algorithms book.

Sorting You should be able to write algorithms O(n*lgn) like QuickSort and MergeSort with ease. Compare and understand the best, worst and average case complexities. I found this table on wiki to be very handy; it lists important properties of all sorting algorithms. Don’t neglect the basic O(n^2) algorithms like Bubble sort or Insertion sort, since other algorithms improve over these. Interviews are more about improving a basic idea, sorting algorithms will help with this process.

Hash Tables When in doubt, think of hash tables. They are useful in most of the problems and frequently help us improve the time complexity of some problems by caching results.

Trees Go through basic tree construction, traversal and manipulation algorithms. You should be able to implement algorithms based on binary search trees. You should be familiar with balanced trees although you are not expected to write code for them in the interview: AVL trees, Red-Black trees, Trie, n-ary trees etc. Thorough knowledge about inorder, postorder and preorder traversals is necessary, because we can solve many tree problems by doing simple modifications to one of these traversals.

Graphs 

• Graphs are a very important concept in Computer Science. Practice the three basic representation of graphs (objects and pointers, matrix, and adjacency list) and familiarize yourself with their pros & cons. 
• There is not much time during the interview so you should not expect something very complex. However, basic graph traversal algorithms (DFS and BFS) are a must, you should implement them in all basic representations. 
• You should be able to implement the Dijkstra or Floyd-Warshall algorithms as well as minimum spanning tree algorithms (Kruskal and Prim). Learn about topological sorting, since it is surprisingly very useful in many ordering problems.

Dynamic Programming This is probably the most important subject as the implementations are small. You should be able to implement 2-3 dynamic algorithms during a 35-40 minutes time. As you’ll check the resources on this blog or on the web, you’ll find that you should expect at least one dynamic programming question per interview.

Operating Systems Learn about processes, threads and concurrency issues. Know about mutexes, semaphores, monitors and how they work. Understand what deadlock and livelock are and how to avoid them. Learn about context switching, scheduling etc.

Mathematics You should familiarize yourself with counting, combinatorics and probability.

Google's publications Read up Google's path-breaking publications listed below if you have time.

• Google File System
• Google Bigtable
• Google MapReduce

I hope you find the above article useful :) Enjoy!

Facebook Interview Experience

You can find some general tips for interviewing with facebook here (posted by a Facebook Engineer). Following questions are from Facebook's final interview rounds (for Software Engineer position):

Round 1
1) Given a string and some characters in a linked list write a function to return if the string is a palindrome or not ignoring all the characters in the linked list.
Signature: bool isPalindrome(char*, node*)

2) Multiply two very large numbers given in the form of strings and return the result also as string.
Signature: char* multiply(char*, char*)

Round 2
3) Write an iterator for the postorder traversal of binary tree. The iterator should print elements in order of postorder traversal on every call to it.
Eg. class iterator{
       public:
       next();
} T;

Consider the following binary tree:

T.next() will print 2
T.next() again will print 5
T.next() again will print 11
T.next() again will print 6 and so on.
so, kth call to next() should print kth node in the postorder traversal.

4) Given two arrays of integers find their intersection. FollowUp: What if one of the arrays is very much bigger than the other. What if one of them is too big to be in the memory.

Round 3
5) Find the longest common contiguous substring of two given strings.

Round 4
6) Given a binary tree write a function to join all the nodes at the same level. Consider each node to have a next pointer.

7) HR Questions:

• Tell me about yourself
• Projects & Internships
• One conflict with team mates and how did u deal with it 
• Where would you like to work? India or US? Why? 
• One thing you would want to change on facebook 
• One thing about facebook that excites you the most

Source: Some student at IIT-Guwahati.

Facebook Programming Test

Facebook had conducted it's test on InterviewStreet in IITB. Total duration of test was 2 hours. The problem boiled down to following:

Given an undirected graph, source node s and destination node d; find number of distinct nodes visited on all paths from s to d such that each node is visited exactly once while enumerating all the paths.

The question above is fairly tricky to implement in an efficient manner. Surprisingly, the exact same coding question was also asked at other IITs as well as every other college in India where Facebook had gone for recruitment. 

Amazon Programming Tests

Amazon's technical test consisted of an objective section of 20 questions and a subjective section in which you need to write working code. The test was conducted on InterviewStreet. Following programming questions were asked at the various IITs in 2012:



IIT-B
1) Given Preorder traversal of a BST, implement a function to find its Postorder traversal.
2) Given some set of strings, print all the strings that are anagrams adjacent to each other.


IIT-R
1) Given a linked list with each node containing a character in A-Z, rearrange the list so that all the vowels are at the beginning and consonants are at the end.
2) Print all the unique triplets (a, b, c) in an array from which we can form a triangle whose sides are of lengths a, b, c.


IIT-KGP
1) You are given a tree with each node having an integer element. For each leaf-node, sum of integer elements on path from root to leaf is computed. Find the leaf node with a) maximum sum, b) minimum sum
Follow up: Print the path with min/max root to leaf path sum
2) Given an array of integers, find 2 elements having minimum difference in their absolute values.


IIT-K
1) You are given a linked list, and you have to swap every 2 consecutive nodes with each other.
eg. 1->2->3->4->5 will become 2->1->4->3->5
2) You are given an array of string and you have to print all the pairs which are anagram of each other. You should ignore the case of the characters in strings while checking for anagrams, so "Cat" and "Act" are anagrams of each other.


IIT-D
1) Given an array of +ve integers, join these integers in a way to maximize the resulting number formed.
Ex: [884 88] -> 88884
      [20 19 90] -> 902019
      [909 90] -> 90990
2) Given a tree and a value x, check if there exists a path in the tree with nodes that sum up to x. 
Note: The path has to start at any node and go down the tree.

Twitter Programming Test

Twitter conducted an online programming test at IIT-Bombay. Following questions were asked:

1) Given a string, check if there exists some anagram of the string which is a palindrome.
Function Signature: bool anagramPalindrome(string word)

Sample Testcases:
a) anagramPalindrome("rotate") returns false, no anagram of "rotate" is a palindrome
b) anagramPalindrome("hanna") returns true, since using letters from "hanna", we can form the palindrome "nahan"

2) Given a permutation which contains numbers in the range [1, N], return the length of the largest cycle in the permutation. Function Signature: int longestCycle(vector<int> perm)

Sample Testcases:
a) longestCycle([2 3 1]) returns 3, since only cycle is (1 2 3) whose length is 3
b) longestCycle([5 4 3 2 1]) returns 2, since the permutation can be decomposed into (1 5), (2 4), (3)



Somehow, I was also able to get hold of the questions asked at IIT-Delhi's twitter programming test:

1) Find the number of "visible" nodes in a binary tree. A node is a "visible" node if the path from root to that node does not encounter any node of value higher than that node.

2) In a 2D matrix of dimensions M*N, find number of "equilibrium" points.  A point (i, j) is said to be an "equilibrium" point only if all following conditions hold:
a) sum of rows 1...(i-1) =  sum of rows (i+1)...M
b) sum of columns 1...(j-1)  = sum of columns (j+1)...N

Flipkart Test

Flipkart conducted its test on Interviewstreet. There were 20 objective questions and 2 programming questions. Test was for 2 hours.

Here are the 2 programming questions :

1) You are given an array of integers. You need to find the minimum number of swaps necessary to make the array sorted.

Eg. [3,2,1] -> 3 swaps needed
      [1,2,3] -> 0 swaps needed

2) Snakes and ladders game. Find the smallest number of jumps (ie optimal no of dice throws) needed to win a snakes and ladders game. Assume you are given a board with all the necessary inputs like start/end positions of all ladders and snakes. (Hint: Think about the problem in terms of a graph)

Directi Test

Directi conducted a programming test at IIT-B for placements. The platform we used was CodeChef.
I personally found the interface on to be very non-intuitive as compared with InterviewStreet. Make sure you practice on codechef before appearing for the test, so as to not get stuck up on some trivial issues during the test. The total duration of the test was about 1.5 hours.


Here are the questions asked :

1) The question boiled down to this : Find the shortest path from source node S to destination node T in an un-directed graph where all the edges have equal weight. (Hint : Think BFS)

2) This one was non-trivial. I don't remember the question exactly but the idea was to enumerate all the cycles in some given permutation of {0,1,...,n-1}.

Eg: If p[] = {0,1,2} there are 3 cycles 0->0, 1->1, 2->2
      If p[] = {2,0,1} there is only 1 cycle, 2->1->0->2

Informatica Test - Subjective Round

This year Informatica participated in the placement process at IIT-B. They invited applications for India as well as their US Office for software engineering profiles!

Their process for shortlisting for final rounds of interviews consisted of two Rounds of testing.

First round had very simple objective questions on Data structures, Algorithms, Operating Systems, Database Queries and some other questions on basic CS concepts.

Out of the 60-70 people who sat for the first round, 30 made it to the shortlist for the second round, which was subjective. The duration of subjective round was 1 hour and it had the following questions :-


1) You are given an array of integers, say a. Find i, j, k in the array such that a[i] < a[j] < a[k]. Expected time complexity is O(n), and space complexity is O(1).

2) You are given a pointer to a node in a graph. You have to create a copy of the graph. The node structure is as follows.

class Node {
      int id;
      vector<Node*> neighbors;
}

3) Write a program to compute fibonacci numbers. Improve its efficiency.

4) You have a set of jobs j1, j2, ..., jN. There are some restrictions on the way the jobs can be executed, eg. j1 has to be executed before j2, j3 has to be executed before j1 etc. Give an algorithm to to schedule the   jobs given the constraints.

5) Design a 2-way HashTable

6) Given 2 very large arrays A and B. Find the common elements given that you have
                                          a) Unlimited Space
                                          b) Limited Space

7) In a store there are a million distinct items. You have to list the k most sold items at the end of day. Give the data structure/algorithm you will use for the following cases
                  a) You have to list the items in sorted order of number items sold,
                  b) Sorted order is not necessary, so just print the items in any order

8) How many times will "hello" be printed on executing the following program.

int main() {
      int tmp;      
      for (int i=0; i<7; i++) {
           tmp = fork();
           if (tmp > 0) break;
           cout << "hello" << endl;
      }
}

9) I don't remember this one exactly, but you are given a program with several declarations/definitions of variables. You have to say where will the memory be allocated for all the declarations, eg. Heap, Stack, Text Segment, etc.



Out of the 30 people who appeared for the subjective round, only 15 odd people were able to clear it, and shortlisting for final interviews was purely based on your performance in the test.

Google Interview Experience

I was shortlisted by Google for final rounds of interviews. Here are the questions asked to me during my face-to-face interviews. Each interview was for about 45 minutes.

Round1:

The interviewer started by asking me about myself and then about my projects. He asked questions like "Why Google", "Why not some other company like Eg. Microsoft", "How would you design a Self-controlling car", which I had to answer within 30 seconds.

1) Write code to multiply 2 matrices, check for corner cases, erroneous inputs etc.

2) Given a matrix M, check whether 2 rows are exactly equal in the matrix. Optimize time complexity.

Eg. M  =     1 2 3, then rows 1 and 3 are same.
                3 4 5
                1 2 3


Round2:

1) Given a N*N grid of characters, find all the words that can be made using by traversing in the eight possible directions in the grid. (similar to Boggle)

2) Find some local minima in an array of integers, assume that all the integers are distinct.

Local minima definition :
Given an array a[1], a[2], ... , a[n-1]

 if a[0] < a[1], then a[0] is a local minima
 if a[n-1] < a[n-2], then a[n-1] is a local minima
 if a[i] > a[i-1] && a[i] < a[i+1], then a[i] is a local minima

Google Test

Google's test conducted at IIT-Bombay consisted of 20 objective questions, which were of moderate difficulty level. It also had a subjective question which goes as follows.

You are given a number of dices n, each with a number of faces m. You roll all the n dices and note the sum of all the throws you get from rolling each dice. If you get a sum >= x, you win, otherwise you lose. Find the probability that you win.

Google's shortlist for final rounds of interviews consisted of only those people who had done relatively well on the test, and fortunately I was one of them. So now you know how important it is to do well on the test.