Friday 6 September 2013

Strand Life Sciences - Algorithm Test




Strand Life Sciences offered work profile of software engineering in their Bangalore office, during 2012 placements at IITB.

Duration: 1 hour
Type: Pen-and-paper based


1.  void star(int i) {
if (i > 1) {
star(i/2);
star(i/2);
}
cout << "hello" << endl;
  }

  int main() {
star(5);
  }
How many times does "hello" gets printed?

2. Rank functions (3/2)^n, 2^n, n^3, n! in order of increasing Big-O

3. Find maximum number of partitions in which the 2D-plane is divided by n lines. Extend this argument to V-shaped figures instead of lines. Assume the V-shaped figures extend infinitely

4. Given 2 strings, check if they are anagrams

5. Find all permutations of a string

6. Find maximum sum contiguous sub-sequence in an array of +ve and -ve numbers

Saturday 31 August 2013

Deutsche Bank - Analyst Interview

This interview was given for Analyst position for the Tradefinder desk at Deutsche Bank, Mumbai. Basically, this position involves developing trading models and working with data through coding in MATLAB. The following questions were asked across 2 interview rounds:-


1) Monty Hall problem

2) We toss 4 unbiased coins. We know that one of the 4 coins lands a head. What is the probability that all coins land a head ? (Ans: *1/15*)

3) When you die, you see 2 doors. 1 leads into heaven and one leads into hell. Both doors are guarded by 2 guards, there are no signs that say heaven or hell, you are allowed to ask 1 guard 1 question only. The guard guarding heaven always tells the truth the guard guarding hell always tells a lie. What question should you ask to figure out the door that leads to heaven?

4) Compare Nested Queries vs Joins for SQL queries. Which would perform better and in what cases?

5) About Dijkstra algorithm and it's complexity

6)  Minimum spanning tree algorithm

7) About breadth first traversal algorithm (BFS)

Sunday 16 June 2013

Twitter Interview Questions

I came across some Twitter's personal interview questions asked for it's Software Engineering position during some discussion:


1) Find whether a string contains a contiguous palindromic substring in O(n) time. Can you solve the problem in O(1) time?

2) In an array, find the element which appears more than 50% of the time. Find element which appears more than 33% of the time in the array.

3) What is a distributed hashtable? How to make data persistent, prevent data loss, and still keep the access efficient?

4) What are the key differences between the data structures: Hashtable, Array, LinkedList, BST. For what kind of queries would a BST perform better than Hashtable?

5) How will you find the most frequently searched queries on Google in the last minute/last hour/last day from among a dynamic stream of queries?

Wednesday 12 June 2013

Must Watch Movies for Finance Enthusiasts

Yes, you read it right! This post is going to be about movies that will entertain you as well as enhance your knowledge about the finance industry in specific and about capitalism in general. I've watched a good number of finance movies/documentaries purely out of interest and I find following 10 movies to be the best picks for my finance movies portfolio:



Wallstreet (1987) 
This is one of the first hollywood drama to be made about Wallstreet. The main theme of this oscar-winning movie is of insider trading and illegal means to get an edge in the stock markets. Here is one of the epic dialogues by protagonist Gordon Gekko in the movie:

"Greed is right, greed works. Greed clarifies, cuts through, and captures the essence of the evolutionary spirit. Greed, in all of its forms; greed for life, for money, for love, knowledge has marked the upward surge of mankind. And greed, you mark my words, will not only save Teldar Paper, but that other malfunctioning corporation called the USA"

Enron (2005)
This documentary depicts the collapse of the 7th largest US firm, Enron, to bankruptcy in less than a year. My favorite character in the documentary is Jeff Skilling, the CEO of Enron. He is shown as a person who takes risk, purely for the thrill of it. 

Too big to fail (2011)
Based on the events leading to the financial crisis of 2008. The movie has characters with actual names and real-life events. The movie gets it's name from the fact that US banks have grown so huge that their failure will lead to collapse of the global economic system i.e. they are Too big to fail.

Inside Job (2010)
It provides a comprehensive analysis of the global financial crisis of 2008. It presents exclusive research and interviews of key politicians, journalists, academics and finance people. The movie concludes that finance industry has gone rogue and has corrupted politics, financial regulation and academia.

Overdose (2010)
This documentary traces the origins of the financial crisis and explores the similarities in policy lapse of financially unstable states like Greece, Iceland and even the USA.

Rogue Trader (1999)
The real story of trader Nick Leeson, who singlehandedly led to the bankruptcy of Barings Bank, one of Britian's oldest and important bank.

Margin Call (2011)
A fiction movie depicting key employees at a bank 24 hours before the financial crash.

Zeitgeist: Addendum (2008)
This documentary is an excellent critique of our "fractional reserve" debt-money system and the "Federal Reserve System" that controls it.

Freakonomics (2010)
Freakonomics is a collection of documentaries that explores human behavior in various real-world scenarios using the science of economics. An example which is presented in the movie: Can you improve students academically by awarding them cash prizes? This movie analyses and provides conclusions to such out-of-the-box questions. This movie is inspired from the famous book that goes by the same name, you can read the book if it interests you.

Capitalism: A love story (2009)
This film examines the impact of corporate dominance on the everyday lives of Americans. It's a sarcastic and humorous movie that addresses a serious issue.

Any additional suggestions for movies/documentaries/tv-shows/books are most welcome! 

Tuesday 21 May 2013

My Placement Story: Part I

The year was 2012 and it was placement season for me. It was an important event and I knew it was going to be hectic. This post will summarize my experience with IITB's placement process. Due to it's length I've divided it among several posts.


Resume uploading starts around mid-August and you have to prepare your resumes and submit them till mid-Sept. Remember that resumes are very important, because some firms simply shortlist candidates based on their resumes; so it's essential that you give a good impression. And anyways, even if the respective firm doesn't shortlist based on resumes, they'll definitely have a look at it. So it's better to prepare a decent resume. My advice:
  • Take a look at a few of your senior's resumes and use them as templates.
  • Make several drafts, and improve your resume incrementally; remember that every word on your resume is important.
  • Use simple English. Don't try to show-off your vocab skills, it might back-fire if the interviewer misinterprets!
  • After having a final draft ready, send it to a couple of your seniors asking them for advice. 
  • Make necessary changes as per suggestions and upload!


Placement season structure at IITB
Placement season consists of 3 phases: Phase-1, Phase-2 and Phase-3. Below I list the important timelines involved in Phase-1, which is the most important phase:
  1. Resume uploading (deadline in mid-Sept)
  2. Pre-Placement talks (Last week of Sept - Last week of Nov)
  3. Preliminary Tests conducted for shortlisting (First week of Oct - Last week of Nov)
  4. Final Interviews for shortlisted students (1st Dec - 15th Dec)

Which firms did I apply?
I gave the tests of companies that I was interested in, and that must have numbered to around 35. Here is the  comprehensive list of firms with whom I was involved for the shortlisting process:



Tests started in the 1st week of Oct and the frequency of tests per week was around 2-3. But this frequency increased gradually as we approached November end. I remember precisely that I gave 5 tests on Nov 30th, just a day before the D-Day! It gets very hectic in the last week of November, and you don't get any time for preparing for final interviews. All I did was gave tests day-in and day-out in the last week of November; you simply don't get time for anything else.

Where was I shortlisted?
After going through the tests and other shortlisting methods of the above firms, I was shortlisted in the following firms for final rounds of interviews to be given on Day-1 and Day-2.

Day-1 (Dec 1st)
  • Google 
  • Microsoft
  • Opera
Day-2 (Dec 2nd)
  • Epic Systems
  • GREE
  • Works Applications
  • Informatica
  • Adobe
  • Chronus
  • Oracle
  • Mylikes
  • Walmart Labs
  • Myntra
  • Lexity
  • Strand Life Sciences
  • Dolat Capital
  • Finmechanics

That's it for this post, I'll post about the intricacies and my horror story of Day-1 and Day-2's interview experience in upcoming posts. Keep checking!

PS: On after thought, this post seems to be very IIT-Bombay specific, but hopefully you may find some useful bits and pieces.

Friday 17 May 2013

Microsoft Pre-Placement Offer Interview


At the end of my summer internship at Microsoft India Development Center (Microsoft IDC), I had the opportunity to go through interviews for getting a Pre-Placement Offer (commonly known as PPO).

IDC is Microsoft's largest development center outside US. The different groups here are involved in development of almost all of Microsoft's major products. In fact, there are some products that have originated here. I don't doubt that Microsoft IDC is the best place to do some good software development work in India. I went through 2 tech interviews:




Interview #1

1) Design classes and implement member functions for playing Tic-Tac-Toe on an N*N board. You win if you get N pieces in a row, column or diagonal.
Follow Up: Briefly explain how will you implement the AI

2) Reverse every word in a string.


Interview #2

1) You are given an M*N board. You are given blocks of different shapes as found in a Tetris game. You have to give an algorithm to check whether all the blocks mesh perfectly in the M*N board. Also, give some heuristics that to speed up the algorithm.

2) How would you test a blue marker?

Saturday 4 May 2013

Opera Solutions: Analytics Specialist Test


Opera solutions is a consulting firm which engages in management consulting and decision analytics. The role of Analytics Specialist that Opera offers requires thorough knowledge of Statistics and other topics like Machine Learning. The shortlisting procedure was done through 2 pen-and-paper tests:



Objective Paper (20 questions, 45 minutes)
Consisted of questions on probability theory and basic statistics. Also there were some questions on Data interpretation (similar to those asked in IIM-CAT).


Subjective Paper (6 questions, 45 minutes)
1) A and B play a game. They roll 2 dice every time and add the numbers that show up. If it's a 12, then A wins. If there are 2 consecutive 7's then B wins. With what probability does A win the game?

2) 100 prisoners hat puzzle

3) Prove that product of 4 consecutive numbers is always of the form k^2 - 1.

4) Prove that there always exists a sequence of length n of composite numbers for all n.

5) Geometry problem: 3 circles tangent to each other, find c in terms of a,b. (Sorry I don't remember the diagram)

6) There is a parking space of length 4. Cars come and randomly choose any position to park over the interval [0, 4]. Each car occupies a space of length 1. Calculate expected number of cars that can park.

Thursday 2 May 2013

Mylikes Coding Test

Mylikes is a content and social advertising platform. It is similar to Google Adsense, but promises to have a patented algorithm for targeted advertisements. It visited IITB and the following questions were asked in it's 1 hour pen-and-paper based test.


1) Find output of a C++ program: It was based on classes, so good knowledge of classes in C++ was required.

2) Find output of a C++ program: It was based on recursion in functions and function calls, so knowledge about functions in C++ and recursion was necessary.

3) Given that you have a million URLs, give a method to store them so as to retrieve a URL efficiently.

4) Insert commas into at appropriate positions in a number and rounding the number also, represented in the form of a string. Try to make sense of the question from the following test cases
Ex: "100.23632" -> "100.24"
      "10000" -> "10,000"
      "1000000.1234" -> "1,000,000.1234"

Follow up: Write code in such a way that positions where you put commas can be placed as per Indian currency system (instead of US system). I think the follow-up was to see whether you were able to write code that was easily generalized to Indian as well as US comma systems.

5) Given 2 strings a, b, check whether b is a postfix of a that is a ends with b.

6) Find all permutations of a string.

Monday 15 April 2013

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

Wednesday 3 April 2013

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.

Thursday 21 March 2013

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.

Sunday 17 March 2013

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. 

Sunday 10 March 2013

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

Friday 1 March 2013

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.


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.


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.

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

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)

Wednesday 30 January 2013

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.


Saturday 26 January 2013

Google's Hiring Algorithm

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




Thursday 24 January 2013

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: 

Recommended websites for coding practice: InterviewStreetTopcoder



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


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