Wednesday, 27 February 2013

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.


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)


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.

Monday, 11 February 2013

Breaking Into Wallstreet: Finance Interviews Prep

In this post, I will be focusing on preparation tips for Analyst-level finance jobs at major investment banks and other finance corporations. It's based on my experience with finance firms that recruited at IITB in 2012; so this post will make more sense for finance-enthusiasts at the IITs.

This post will not be focusing on Quant-finance profiles. If you need some fundae for preparing for Quant finance interviews, checkout Cracking Quant-Finance Interviews.

Integrating the following in your placement preparation routine should ideally help improve your chances of getting a finance job

Start reading a Financial daily
If you really want a financial markets role, you should know what's happening in the financial world and know it well. You should be able to answer questions based on important events that occurred in the financial markets over the recent years. For example, you might be asked 'Why did the 2008 crash occurred?', 'Tell me about what you think of Euro-zone crisis', 'What is Quantitative easing?' and so on. Reading financial news daily would help you answer above kind of questions. I suggest at least one of the following regularly:
  • The Economic Times: Focused on Indian markets. Highly recommended.
  • The Economist: It publishes some excellent finance and economics-oriented articles with interesting analysis and statistics. Recommended for those who absolutely love Economics.
  • Bloomberg/Reuters: Focused primarily on US and European markets. Read them once in a while to get an idea about stuff going on globally.

Getting your Finance concepts 'Right'
Do you know what are derivatives are? What about options? If these terms sound greek to you, I suggest reading them up from the following sources.
  • Investopedia: This is the wikipedia of finance. Read up the beginner's tutorials. Subscribe to Investopedia's daily word.
  • Vault Guide to Finance Interviews: This is an awesome handbook that gives introduction to almost all topics in finance starting from stocks & bonds to currency & interest rates. 
  • Vault Guide to Investment Banking: This one somewhat digs deeper into Investment Banking roles of Sales, Trading and Research and topics like Corporate Finance.

Financial Certifications 
  • Although certifications like CFA and FRM are way too expensive (at least by Indian standards, especially after the Rupee has eroded in comparison to Dollar), clearing them would put you in the favorites-list of recruiters. Also, they demonstrate interest and dedication that you have towards the field of Finance, thus giving you an extra cut over others in the competition. 
  • You can also pursue NCFM certification (National Stock Exchange's certification in financial markets)  for various finance modules.

Finance related Coursework 
  • Show-off some course-work in subjects related to Finance and Economics. You should try out Finance/Economics related courses running in your institute. 
  • You can pursue some from tons of Finance and Economics courses on Coursera like Game Theory, Introduction to Finance, Economics for Scientists etc. Here is the comprehensive list.

Internship in Finance
This is kind of mandatory. So try to get an internship in some role related to Financial markets if you are really interested in a long-term career in finance. 

CAT Practice
Give some mock CAT tests even if you are not going to appear for CAT. Most of the finance companies use aptitude test based shortlisting procedure and practice will help you get in the final interview shortlist. Practice Quantitative Aptitude and Data Interpretation sections from the CAT mocks, it will really help you do good on the tests.

Miscellaneous Websites I found the following websites to be great in terms of getting to know the Finance Industry and other interview tips. Do read them to know more. You can also ask your related doubts on the forums of some of these websites.

Firms that offer Financial Analyst profiles (IITB Placements, 2012)
  • Tier1: Deutsche Bank, JP Morgan, CitiGlobal, Credit Suisse, Optiver, American Express
  • Tier2: Capital One, Crisil, Finmechanics, Forefront Capital, FinIQ, Blufin, RAK Holdings

Thursday, 7 February 2013

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, 2)
(3, 1, 2)
(pushFront, pushFront, pushBack, popBack, pushBack, popBack) results in the following sequence of states and outputs:
(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:
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:
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

Output (note choice of pushBack over pushFront):

Output (pushFront is needed in some cases):

Output (some sequences are 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:
X1 Y1
X2 Y2
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):
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.

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 
2 100 200
3 110 190
4 105 145
1 90 150
5 102 198
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.

Tuesday, 5 February 2013

Credit Suisse: Quantitative Math Test

Following questions were asked for Strategic Risk Management profile of Credit Suisse at IIT-Bombay.

1) Value of E[|X|] where X ~ Normal(0,1)

2) Choose 3 points on circumference of a circle. What is the probability that the center will lie in the triangle?

3) There are 2 men who want to meet between 5pm and 6pm. Assuming arrival time is uniform and random, calculate the probability that 2nd arriving person has to wait less than 10 mins

4) What is the expected number of tosses needed to get 2 consecutive heads?

5) You are given a 6-sided fair die. Calculate expected number of throws of dice to see all the faces (values 1,2...6) at least once.

6) Solve: dy/dx + xy = x*(y^2)

7) Solve: dy/dx + 3y = e^x

8) Calculate Sum(Var(pow(Xi,2))), i = 1 to N, Xi are independent.

9) Calculate Var(XY) where X ~ Uniform(0,1) and Y ~ Normal(0,1)

10) There are 3 bulbs in a room. If we switched on all of them. What is the total expected time till the room remains lit? Assume the "on" time for each bulb is an exponential random variable with λ=1 hour.

11) There are N coins. Probability of kth coin to land up a head is 1/(2k+1). We toss all the N coins, calculate the probability that we get odd number of heads.

12) Dart thrown land up uniformly and random at a distance from centre of a unit circle. Distance from center is in the range [0,1]. One who lands up farther from the center loses and the loser pays amount equal to distance from the centre. What is the expected pay?

13) Calculate E[f(x)], where x ~ N(0,1) (For some function f).

14) Given X ~ Uniform(-π/2, π/2). Find probability distribution of Y = tan(X).

15) f(x,y) = (x^2 - y^2) / (x^2 + y^2). Comment on continuity of the function at (0,0)

16) We do M trials. In each trial the result is a uniform RV in [0,1]. What is the minimum no of tosses needed to be 90% sure of getting a value in range [0.8, 0.9].

Monday, 4 February 2013

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)