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.

Morgan Stanley QED: Round1

Morgan Stanley organized a contest Q.E.D in 2012 to promote Mathematics in Finance among the students of IITB. It kicked off with a talk on Quantitative Finance by Ashwin Rao (Managing Director, Morgan Stanley India). For the contest, there were 3 elimination rounds. Round #1 had the following questions.

Objective Section

1) Let P be a projection, so P*P = P. Compute inverse of (I - cP) given c = 1/2, where I is the identity matrix.

2) Two creepers, C1 and C2, are both climbing up and round a cylinder. C1 twists clockwise and C2 anticlockwise, both start at the same point at the bottom. Before they reach the top of the cylinder C1 had made 5 complete twists and C2 had made 3 complete twists. Not counting the bottom and the top, how many times do their paths intersect?

3) Compute Σ ( i^5 / 1000^6 ) over i = 1 to 1000, approximately.

4) For strings of length m + n, with m 0's and n 1's. Find the expected number of switches from 0 to 1 (a switch can be thought of as presence of '01' in the given string).

5) Compute  ∫ (dt)^2.

6) Let I be an n*n identity matrix and J be an n*n matrix of all ones. Find the rank of I - (1/n)J.



Subjective Section

1) You have N cars that are all travelling the same direction on an infinitely long one-way highway. Unfortunately, they are all going different speeds, and cannot pass each other. Eventually the cars will clump up in one or more traffic jams. In terms of N, what is the expected number of clumps of cars?

2) Say a[1], a[2], a[3], ... a[N] be a permutation of first N natural numbers. a[i] is a maxima if a[i-1] < a[i] > a[i+1]. Find E[ number of maximas in a random permutation ].

3) Prove that E[x] = ∫ (1 - F(x)) dx over the range [0, ∞], where F is the cumulative distribution function.

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.

Morgan Stanley Quant Test

Morgan Stanley took a test for it's Quantitative Analyst profile. The test had 2 sections "Easy" and "Difficult" and total duration was about 2.5 hours.

Easy

1) Prove no square matrices A, B exists such that AB-BA = I. (Hint: use trace(X))

2) Each amoeba my transform to 0 amoeba (means that it's dead), 1 amoeba (stays itself) or 2 amoebas (reproduces a child). We initially have 1 amoeba. Find probability of the process up with 0 amoeba in the end.

3) Consider all strings composed of of {0, 1, 2}. Find number of strings such that no two 1s are consecutive in the string.

4) Given X, Y are Uniform(0,1) random variables. Find distribution of X^2 + Y^2.

5) Write algorithm to find lowest common ancestor of 2 nodes in a binary tree.

6) Solve the recurrence f(a, b) = f(a, b-1) + f(a-1, b-1) with base cases
    f(0, 0) = 1,
    f(0, k) = 0,
    f(k, 0) = 1. (Hint: Did you observe it's a Pascal Identity)



Difficult

1) Give an algorithm to find longest alternating subsequence in an array of numbers. The sequence need not be continuous. Alternating means that 1st term is greater than 2nd term, 2nd term is smaller than 3rd term and so on OR 1st term is smaller than 2nd term, 2nd term is greater than 3rd term and so on.

2) You are given a stream of numbers. Give an efficient data structure to find median of the numbers read so far from the stream in O(1) time.

3) You are given w white balls and b black balls initially in a box. Each time we randomly draw a ball from the box and remove it.We continue until no white ball is left in the box. Find the expected number of black balls in the box in the end.

4) Give a method to randomly choose any K-size subset from an N-size subset, however, N is not known to you.

5) Find all functions f, such that f(mA+nB) = mf(A) + nf(B), f(AB) = f(BA), where A, B are square matrices, find f in terms of a matrix M.