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. 

Optiver Math Test: Subjective Questions

I have posted the subjective questions asked in Optiver's written test below. Do check out Optiver Objective Questions for objective questions asked in the test. Also, if you need more information on Optiver and it's selection procedure check About Optiver.

1) After a snail racing contest, the four contestants were congratulating each other. Only one snail wore the same number as the position it finished in. Alfred's snail wasn't painted yellow nor blue, and the snail who wore 3, which was painted red, beat the snail who came in third. Arthur's snail beat Anne's snail, whereas Alice's snail beat the snail who wore 1. The snail painted green, Alice's, came second and the snail painted blue wore number 4. Anne's nail wore number 1. Can you work out who's snail finished where, it's number and the colour it was painted?

2) At a certain time between 3pm and 4pm, the hour and the minute hands are at equal angles from the 6 mark, what time will it be exactly?

3) I lived in a city that held as much as it could,
    So I moved to another that repaid what what it should.
    The third had very little, with not much to be found,
    The fourth was very boring, with no change in the sound.
    The fifth was so foggy you could not see past the next face.
    The sixth was on the move; I could barely keep up the pace,
    The seventh was strange; bizzare character would people attain,
    So I settled in the eighth, because it was so plain. 
    What are the various cities?

4) Five youngsters entered a contest to guess how many marbles were in a bowl. Alice guessed 45, Betty guessed 39, Chuck guessed 49, Dan guessed 50, and Ed guessed 47. One was off by 6, one by 5, one by 2, and one by 4. One was right. Who was right?

5) A sheet of paper has statements numbered from 1 to 100. For each N, 1<=N<=100, Statement N says, "Exactly N of the statements in this sheet are false". Which statements are true?

6) You have normal 6-sided cube. I give you 6 different colors that you can paint each side of the cube with (one color to each side). How many different cubes can you make?

Optiver Math Test: Objective Questions

These are the questions asked in Optiver's Subjective Test. Do check Optiver's selection procedure for more information about shortlisting process of Optiver at IIT-Bombay.

1) What number comes next in this series: 1 11 21 1211 111221 312211 13112221 ?

• 12113331
• 1113213211
• 13221113
• 113211321

2) The following equation is wrong: 103 - 102 = 3. Move one numeral to make it correct. The numeral moved is ?

• 0
• 1
• 2
• 3

3) Imagine a 3*3*3 cube. How many cuts do we need to break it into 27 1*1*1 cubes ? (A cut may go through multiple pieces)

• 27
• 9
• 18
• 6

4) In a deck of 52 cards, what is the least number of cards you must take to be *guaranteed* at least one four-of-a-kind (eg: 4 queens) ?

• 4
• 16
• 28
• 40

5) Can you arrange the numerals 1 to 9 (1, 2, 3, 4, 5, 6, 7, 8 and 9) in a single fraction that equals 1/3 ? Example that doesn't work 7192/38456 = 0.187. The last 2 digits of the numerator of the above fraction are 

• 58
• 32
• 61
• 59

6) 5 pirates of different ages have a treasure of 50 gold coins. On their ship, they decide to split the coins using this scheme: The oldest pirate proposes how to share the coins, all of them will then vote for or against it. If 50% or more of the pirates vote for it, then the coins will be shared that way. Otherwise, the pirate proposing the scheme will be thrown overboard, and the process is repeated with the pirates that remain. Assuming that all 5 pirates are intelligent, rational, greedy and do not wish to die, how much will the 2nd youngest pirate get ?

• 97
• 98
• 0
• 20

I have posted the subjective section of the paper here.

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

Cracking Quant-Finance Interviews

Quantitative finance or Mathematical finance is one of the most lucrative (read high-paying) job profiles offered at IITs. This post is meant to be useful to people who are targeting quant-finance jobs. Below post is based on my experience at IIT-Bombay's placements, but I think it will be useful to everyone in general.

What is Quantitative Finance ?
Naively speaking, it involves using mathematical models for profit maximization and risk minimization in financial markets. The word quantitative is used because instead of qualitatively ranking assets, you try to figure out actual numbers and hence make good decisions and thus great profits. Quants generally code up mathematical models. Thus extensive knowledge of Computer Science is needed.

Example: One example is Algorithmic Trading. In naive terms, you give the computer a set of conditions and if some condition holds true, you execute some trades (buy or sell orders).

• Since you have a huge amount of market data about different assets available every second, you need to be able to store and retrieve the data efficiently. Knowledge of Databases helps us in managing the data efficiently.
• Also sometimes, the profit-making conditions may hold true only for a fraction of a second and your hardware and software developed should be very fast so as to execute the trades within that fraction of the second. Thus your systems must be time-optimized at hardware and software levels. Knowledge in Algorithm Design, Compilers and Networks helps us tackle this problem.

Here is a presentation that Mr. Ashwin Rao (MD, Morgan Stanley India) gave on Quantitative Finance; it might give you more perspective.

Why Quantitative Finance ?

• You might want to work as a quant simply because you love Mathematics and want to see it's application in the real-world financial markets.
• Quants get paid truck-loads of money! This is because they help make Wallstreet banks and hedge-funds make huge profits. So money is a factor that might excite you to work as a quant. 
• But, one thing to be noted is that the work hours are on the heavier side. So it turns out to be "more work for more money" policy. Yet the pay-per-hour ratio is well above other kinds of job profiles.
• Also there are performance related bonuses and believe me, the bonuses can be as much as your base salary or even more. This is where the finance sector beats all other sectors, in general.

What are the skills needed for Quant Finance Jobs ?

• CS major students have an edge over others for this profile. This is because of application of various CS based concepts on the job. Knowledge about Data Structures & Algorithms is essential.
• You are expected to have a solid programming background in C/C++ or Java.
• Generally you are not expected to have any prior knowledge/experience in finance.
• Solid background in Math topics like Probability Theory, Linear Algebra and Calculus.

How to do well on Quant Interviews/Tests ?
You need to be very good in Probability theory, Combinatorics and general Math topics like Linear Algebra and Calculus. Also having idea about Data Structures and Algorithms is essential. I recommend reading/practicing from the following resources:

Probability / Combinatorics / Math:

• FAQ in Quantitative Finance : Contains very good puzzles on probability and math along with solutions.
• Fifty Challenging Problems in Probability with Solutions 
• Mathematical Puzzles - A Connoisseur's Collection : For general math puzzles and combinatorics.
• Heard on the Street : Excellent quant puzzles and finance-based questions.

Data Structures and Algorithms:

• Introduction To Algorithms - By Cormen : If you have no idea about Data Structures and Algorithms, this book is an absolute must. It's considered to be a bible for Algorithms.
• Algorithms For Interviews : This book has a huge number of algorithmic puzzles classified as per different algorithm design paradigms. I recommend practicing from it if you have time.

Puzzle Blogs:

• CSE Blog : A puzzle blog by IITB alumnus. Contains most frequently asked puzzles in Quant Interviews along with solutions and interesting discussions.
• Me, Myself and Mathematics
• Rustan Lieno Collection

Also, I will be posting questions asked by various quant firms that appeared at IITB's 2012 placements. I suggest you to keep checking my blog from time to time.


Which kind of firms offer Quant Finance jobs ?
Generally investment banks and hedge-funds. Some recruiters at IIT-Bombay offering quant-finance profiles:

• Hedge Funds: WorldQuant, Tower Research Capital
• Investment Banks: Goldman Sachs, Morgan Stanley, Deutsche Bank, CitiGroup, Credit Suisse