tag:blogger.com,1999:blog-12578783559086484942024-03-21T07:04:36.281-07:00Get that Job at Google!Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.comBlogger40125tag:blogger.com,1999:blog-1257878355908648494.post-11003312325312184702016-10-17T03:23:00.000-07:002016-10-17T03:31:00.610-07:00Grab is Hiring! <div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhGJmmA097b9Lb5BShymwetbwnJ_qbBY1nPfk1C2UlH0ITDXKuM4TM4kUtGxt1H3-V0t0ewGBqZNLs5f8mlm9CN3jO0PhXnL6RPmZGVF6Z3A2AUMBKfGeChVmSB96b4ccg9QYS0EIqZqB8/s1600/Screen+Shot+2016-10-17+at+6.22.38+pm.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="125" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhGJmmA097b9Lb5BShymwetbwnJ_qbBY1nPfk1C2UlH0ITDXKuM4TM4kUtGxt1H3-V0t0ewGBqZNLs5f8mlm9CN3jO0PhXnL6RPmZGVF6Z3A2AUMBKfGeChVmSB96b4ccg9QYS0EIqZqB8/s320/Screen+Shot+2016-10-17+at+6.22.38+pm.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
I'm finally posting on this blog after 3 long years. I've recently joined Grab in a Product Management role, and it's been an amazing ride so far!<br />
<br />
Grab raised a $750M round (<a href="https://techcrunch.com/2016/09/19/grab-raises-750-million/">https://techcrunch.com/2016/09/19/grab-raises-750-million/</a>) recently, and is looking to expand rapidly. We're hiring for Product Management, Engineering, Design, Data Science, Analytics, and other areas.<br />
<br />
I would welcome any talented folks to work for the biggest tech start-up in Southeast Asia, in the very interesting and competitive ride-hailing space.<br />
<br />
Checkout <a href="http://grab.careers/">http://grab.careers</a>, and send your profiles to <a href="mailto:chinmay.chauhan@grab.com">chinmay.chauhan@grab.com</a> if interested. Make sure to include your resume and the roles that you're interested in at Grab.<br />
<br />
<br /></div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com5tag:blogger.com,1999:blog-1257878355908648494.post-85214457110017295122013-09-06T02:05:00.000-07:002013-09-06T02:09:31.302-07:00Strand Life Sciences - Algorithm Test<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: center;">
<a href="http://t0.gstatic.com/images?q=tbn:ANd9GcQ_R5ObPA73j0bje0kTvDYpc5Ql8yMkueUQgv9EMiDujgslYIo7" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><br /></a><a href="http://t0.gstatic.com/images?q=tbn:ANd9GcQ_R5ObPA73j0bje0kTvDYpc5Ql8yMkueUQgv9EMiDujgslYIo7" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="91" src="http://t0.gstatic.com/images?q=tbn:ANd9GcQ_R5ObPA73j0bje0kTvDYpc5Ql8yMkueUQgv9EMiDujgslYIo7" width="200" /></a></div>
<br />
<br />
Strand Life Sciences offered work profile of software engineering in their Bangalore office, during 2012 placements at IITB. <br />
<i><br /></i>
<i>Duration</i>: 1 hour<br />
<i>Type</i>: Pen-and-paper based<br />
<br />
<br />
<b>1.</b> <span style="font-family: Courier New, Courier, monospace;">void star(int i) {</span><br />
<span style="font-family: Courier New, Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>if (i > 1) {</span><br />
<span style="font-family: Courier New, Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>star(i/2);</span><br />
<span style="font-family: Courier New, Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>star(i/2);</span><br />
<span style="font-family: Courier New, Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>}</span><br />
<span style="font-family: Courier New, Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>cout << "hello" << endl;</span><br />
<span style="font-family: Courier New, Courier, monospace;"> }<span class="Apple-tab-span" style="white-space: pre;"> </span></span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;"> int main() {<span class="Apple-tab-span" style="white-space: pre;"> </span></span><br />
<span style="font-family: Courier New, Courier, monospace;"><span class="Apple-tab-span" style="white-space: pre;"> </span>star(5);</span><br />
<span style="font-family: Courier New, Courier, monospace;"> }</span><br />
How many times does "hello" gets printed?<br />
<br />
<b>2.</b> Rank functions (3/2)^<i>n</i>, 2^<i>n</i>, <i>n</i>^3, <i>n</i>! in order of increasing Big-O<br />
<br />
<b>3.</b> Find maximum number of partitions in which the 2D-plane is divided by <i>n</i> lines. Extend this argument to V-shaped figures instead of lines. Assume the V-shaped figures extend infinitely<br />
<br />
<b>4.</b> Given 2 strings, check if they are anagrams<br />
<br />
<b>5.</b> Find all permutations of a string<br />
<br />
<b>6.</b> Find maximum sum contiguous sub-sequence in an array of +ve and -ve numbers<br />
<div>
<br /></div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com7tag:blogger.com,1999:blog-1257878355908648494.post-42748641991442866002013-08-31T01:32:00.000-07:002016-02-24T00:09:40.348-08:00Deutsche Bank - Analyst Interview<div dir="ltr" style="text-align: left;" trbidi="on">
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:-<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9_xS0RSeTuc6gfOMZSmfdt1htKHRb7aN-SCs33cNqhbUUMxHXzakX8QKRZ_I4Imx52GRSUjxRdFAVIn2udY0nv6bdomzlXxAtBGj1loaqR5KGg8yL9HgBgalhDA6tZbb1J0iWxKBMcFA/s1600/deutsche-bank-logo.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="84" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9_xS0RSeTuc6gfOMZSmfdt1htKHRb7aN-SCs33cNqhbUUMxHXzakX8QKRZ_I4Imx52GRSUjxRdFAVIn2udY0nv6bdomzlXxAtBGj1loaqR5KGg8yL9HgBgalhDA6tZbb1J0iWxKBMcFA/s320/deutsche-bank-logo.jpg" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<b>1)</b> <a href="http://mathforum.org/dr.math/faq/faq.monty.hall.html" target="_blank">Monty Hall</a> problem<br />
<br />
<b>2) </b>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: *<span style="color: white;">1/15</span>*)<br />
<br />
<b>3)</b> <span style="background-color: white;"><span style="font-family: inherit;">When you die, you see 2 doors. 1 leads into heaven and one leads into hell. </span></span><span style="background-color: white; font-family: inherit;">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?</span><br />
<span class="Apple-tab-span" style="white-space: pre;"> </span><br />
<b>4)</b> Compare Nested Queries vs Joins for SQL queries. Which would perform better and in what cases?<br />
<br />
<b>5) </b>About Dijkstra algorithm and it's complexity<br />
<br />
<b>6) </b> Minimum spanning tree algorithm<br />
<br />
<b>7)</b> About breadth first traversal algorithm (BFS)<br />
<br /></div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com3tag:blogger.com,1999:blog-1257878355908648494.post-40415272721213159192013-06-16T02:21:00.003-07:002013-06-16T02:48:10.409-07:00Twitter Interview Questions<div dir="ltr" style="text-align: left;" trbidi="on">
I came across some Twitter's personal interview questions asked for it's Software Engineering position during some discussion:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://zpolitics.com/wp-content/uploads/2013/05/twitter.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="120" src="http://zpolitics.com/wp-content/uploads/2013/05/twitter.png" width="320" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<span id="goog_370130847"></span><span id="goog_370130848"></span></div>
<b>1)</b> Find whether a string contains a contiguous palindromic substring in O(n) time. Can you solve the problem in O(1) time?<br />
<br />
<b>2)</b> 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.<br />
<br />
<b>3)</b> What is a distributed hashtable? How to make data persistent, prevent data loss, and still keep the access efficient?<br />
<br />
<b>4)</b> 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?<br />
<br />
<b>5)</b> 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?<br />
<div>
<br /></div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com5tag:blogger.com,1999:blog-1257878355908648494.post-60430669334689570902013-06-12T09:09:00.000-07:002016-02-24T00:04:01.644-08:00Must Watch Movies for Finance Enthusiasts<div dir="ltr" style="text-align: left;" trbidi="on">
<div>
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:</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
</div>
<div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjfumnTrGkxEO_b8jEOjH3jmTGV3RR-rCEHD1onpHdefxZEwUMRHMBg7uSSyv6yg5dP1rR8dIB-GlUqFjwIArgaQxz20Co2DVbhf06FRufQNVpOU89mi1sGqRSjwBfDw8Kb9jpwvf6Jqmw/s1600/wallstreet.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="396" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjfumnTrGkxEO_b8jEOjH3jmTGV3RR-rCEHD1onpHdefxZEwUMRHMBg7uSSyv6yg5dP1rR8dIB-GlUqFjwIArgaQxz20Co2DVbhf06FRufQNVpOU89mi1sGqRSjwBfDw8Kb9jpwvf6Jqmw/s640/wallstreet.png" width="640" /></a></div>
<br /></div>
<div>
<br /></div>
<div>
<b><u>Wallstreet </u></b><i>(1987)</i> </div>
<div>
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 <i>Gordon Gekko</i> in the movie:</div>
<div>
<i style="background-color: white; color: #444444; font-family: inherit;"><br /></i>
<i style="background-color: white; color: #444444; font-family: inherit;">"<span style="line-height: 18px;">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"</span></i></div>
<div>
<br /></div>
<div>
<b><u>Enron</u> </b><i>(2005)</i></div>
<div>
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. </div>
<div>
<br /></div>
<div>
<u style="font-weight: bold;">Too big to fail</u> <i>(2011)</i></div>
<div>
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 <i>Too big to fail.</i></div>
<div>
<br />
<u style="font-weight: bold;">Inside Job</u><span style="font-weight: bold;"> </span><i>(2010)</i><br />
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 <span style="line-height: 18px;">gone rogue and has corrupted politics, financial regulation and academia.</span><br />
<br />
<b><u>Overdose</u></b> <i>(2010)</i><br />
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.<br />
<br />
<b><u>Rogue Trader</u></b> <i>(1999)</i><br />
The real story of trader Nick Leeson, who singlehandedly led to the bankruptcy of Barings Bank, one of Britian's oldest and important bank.<br />
<br />
<b><u>Margin Call</u></b> <i>(2011)</i><br />
A fiction movie depicting key employees at a bank 24 hours before the financial crash.<br />
<u style="font-weight: bold;"><br /></u>
<u style="font-weight: bold;">Zeitgeist: Addendum</u> <i>(2008)</i><br />
<span style="background-color: white; line-height: 18px;"><span style="font-family: inherit;">This documentary is an excellent critique of our "fractional reserve" debt-money system and the "Federal Reserve System" that controls it.</span></span><br />
<u style="font-weight: bold;"><br /></u>
<u style="font-weight: bold;">Freakonomics</u> <i>(2010)</i><br />
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: <i>Can you improve students academically by awarding them cash prizes?</i> 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.<br />
<br />
<u style="font-weight: bold;">Capitalism: A love story</u> <i>(2009)</i><br />
<span style="background-color: white; line-height: 18px;"><span style="font-family: inherit;">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.</span></span><br />
<br />
<span style="line-height: 18px;"><i>Any additional suggestions for movies/documentaries/tv-shows/books are most welcome! </i></span></div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com4tag:blogger.com,1999:blog-1257878355908648494.post-53953106219854158942013-05-21T04:29:00.000-07:002013-05-31T01:31:11.213-07:00My Placement Story: Part I<div dir="ltr" style="text-align: left;" trbidi="on">
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.<br />
<br />
<b><u><br /></u></b>
<b><u>Resume uploading</u></b> starts around <i>mid-August</i> and you have to prepare your resumes and submit them till <i>mid-Sept. </i>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:<br />
<ul style="text-align: left;">
<li>Take a look at a few of your senior's resumes and use them as templates.</li>
<li>Make several drafts, and improve your resume incrementally; remember that every word on your resume is important.</li>
<li>Use simple English. Don't try to show-off your vocab skills, it might back-fire if the interviewer misinterprets!</li>
<li>After having a final draft ready, send it to a couple of your seniors asking them for advice. </li>
<li>Make necessary changes as per suggestions and upload!</li>
</ul>
<br />
<b><u><br /></u></b>
<b><u>Placement season structure at IITB</u></b><br />
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:<br />
<ol style="text-align: left;">
<li>Resume uploading (deadline in <i>mid-Sept</i>)</li>
<li>Pre-Placement talks <i>(Last week of Sept - Last week of Nov)</i></li>
<li>Preliminary Tests conducted for shortlisting <i>(First week of Oct - Last week of Nov)</i></li>
<li>Final Interviews for shortlisted students <i>(1st Dec - 15th Dec)</i></li>
</ol>
<div>
<i><br /></i>
<b><u>Which firms did I apply?</u></b></div>
<div>
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:</div>
<div>
<br /></div>
<div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://img842.imageshack.us/img842/9682/listfirms.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="332" src="http://img842.imageshack.us/img842/9682/listfirms.png" width="640" /></a></div>
<br />
<br />
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 <b>5</b> tests on <i>Nov 30th</i>, just a day before the <i>D-Day! </i>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.<br />
<br />
<b><u>Where was I shortlisted?</u></b><br />
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.<br />
<br />
<b><u>Day-1</u></b> <i>(Dec 1st)</i><br />
<ul style="text-align: left;">
<li>Google </li>
<li>Microsoft</li>
<li>Opera</li>
</ul>
<div>
<b><u>Day-2</u></b> <i>(Dec 2nd)</i></div>
<ul style="text-align: left;">
<li>Epic Systems</li>
<li>GREE</li>
<li>Works Applications</li>
<li>Informatica</li>
<li>Adobe</li>
<li>Chronus</li>
<li>Oracle</li>
<li>Mylikes</li>
<li>Walmart Labs</li>
<li>Myntra</li>
<li>Lexity</li>
<li>Strand Life Sciences</li>
<li>Dolat Capital</li>
<li>Finmechanics</li>
</ul>
<div>
<br /></div>
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!<br />
<br />
PS:<i> On after thought, this post seems to be very IIT-Bombay specific, but hopefully you may find some useful bits and pieces.</i></div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com2tag:blogger.com,1999:blog-1257878355908648494.post-54023437970370089512013-05-17T05:13:00.000-07:002013-05-17T05:59:21.615-07:00Microsoft Pre-Placement Offer Interview<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: center;">
<a href="http://upload.wikimedia.org/wikipedia/commons/c/c7/Windows_logo_-_2012.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="200" src="http://upload.wikimedia.org/wikipedia/commons/c/c7/Windows_logo_-_2012.png" width="181" /></a></div>
<br />
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).<br />
<br />
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:<br />
<b><u><br /></u></b>
<b><u><br /></u></b>
<b><u><br /></u></b>
<b><u><br /></u></b>
<b><u>Interview #1</u></b><br />
<b><u><br /></u></b>
<div class="separator" style="clear: both; text-align: center;">
</div>
<b>1) </b>Design classes and implement member functions for playing Tic-Tac-Toe on an <i>N*N </i>board. You win if you get <i>N</i><i> </i>pieces in a row, column or diagonal.<br />
<i>Follow Up: </i>Briefly explain how will you implement the AI<br />
<br />
<b>2)</b> Reverse every word in a string.<br />
<br />
<br />
<b><u>Interview #2</u></b><br />
<br />
<b>1)</b> You are given an <i>M*N</i> 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 <i>M*N</i> board. Also, give some heuristics that to speed up the algorithm.<br />
<br />
<b>2)</b> How would you test a blue marker?<br />
<br />
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com2tag:blogger.com,1999:blog-1257878355908648494.post-39647243484589976472013-05-04T13:08:00.001-07:002013-06-02T02:53:58.099-07:00Opera Solutions: Analytics Specialist Test<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: center;">
<a href="http://www.commendo.at/UserFiles/commendo/Image/Opera%20Logo%20grey.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="136" src="http://www.commendo.at/UserFiles/commendo/Image/Opera%20Logo%20grey.png" width="320" /></a></div>
<br />
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:<br />
<br />
<br />
<b style="text-decoration: underline;"><br /></b>
<b style="text-decoration: underline;">Objective Paper</b> <i>(20 questions, 45 minutes)</i><br />
Consisted of questions on probability theory and basic statistics. Also there were some questions on Data interpretation (similar to those asked in IIM-CAT).<br />
<br />
<b><u><br /></u></b>
<b><u>Subjective Paper</u> </b><i>(6 questions, 45 minutes)</i><br />
<b>1)</b> 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?<br />
<br />
<b>2)</b> <a href="http://tierneylab.blogs.nytimes.com/2009/03/23/the-puzzle-of-100-hats/" target="_blank">100 prisoners hat puzzle</a><br />
<br />
<b>3)</b> Prove that product of 4 consecutive numbers is always of the form <i>k^</i>2 - 1.<br />
<br />
<b>4)</b> Prove that there always exists a sequence of length <i>n</i> of composite numbers for all <i>n</i>.<br />
<br />
<b>5)</b> Geometry problem: 3 circles tangent to each other, find <i>c</i> in terms of <i>a</i>,<i>b.</i> (Sorry I don't remember the diagram)<br />
<br />
<b>6)</b> 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.</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com1tag:blogger.com,1999:blog-1257878355908648494.post-84398963960032189692013-05-02T11:07:00.001-07:002013-06-02T02:38:26.535-07:00Mylikes Coding Test<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: center;">
</div>
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.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiV3TbDzQcTGSNPFCl1U8jilZxV_xy8QrJAoikxaACAWxiBpyLL0zNpjm1Fu0dNOfMMwgTigJvdSpZjMm1LDKxcL52m8VjomrarDnLojQp67lsEtunpRX21CjQVMywk6Rvf9-iJWYySpbo/s1600/Screenshot+from+2013-06-02+14:43:39.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="134" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiV3TbDzQcTGSNPFCl1U8jilZxV_xy8QrJAoikxaACAWxiBpyLL0zNpjm1Fu0dNOfMMwgTigJvdSpZjMm1LDKxcL52m8VjomrarDnLojQp67lsEtunpRX21CjQVMywk6Rvf9-iJWYySpbo/s320/Screenshot+from+2013-06-02+14:43:39.png" width="320" /></a></div>
<span style="font-family: inherit;"><span style="background-color: white; color: #333333; line-height: 27px;"><br /></span></span>
<b style="font-family: inherit;">1)</b><span style="font-family: inherit;"> Find output of a C++ program: It was based on classes, so good knowledge of classes in C++ was required.</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><b>2)</b> 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.</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><b>3)</b> Given that you have a million URLs, give a method to store them so as to retrieve a URL efficiently.</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><b>4)</b> 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</span><br />
<span style="font-family: inherit;">Ex: "100.23632" -> "100.24"</span><br />
<span style="font-family: inherit;"> "10000" -> "10,000"</span><br />
<span style="font-family: inherit;"> "1000000.1234" -> "1,000,000.1234"</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><i>Follow up</i>: 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.</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><b>5)</b> Given 2 strings <i>a, b, </i>check whether <i>b</i> is a postfix of <i>a</i> that is <i>a</i> ends with <i>b</i>.</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><b>6)</b> Find all permutations of a string.</span><br />
<div>
<br /></div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com1tag:blogger.com,1999:blog-1257878355908648494.post-29771118977579245262013-04-15T21:50:00.000-07:002013-04-15T21:50:51.907-07:00Samsung Interview Experience<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="font-family: inherit;">Following questions were asked by Samsung for it's Software Engineering Labs (SEL) position.</span><br />
<span style="font-family: inherit;"><br /></span>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Samsung_Logo.svg/698px-Samsung_Logo.svg.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="108" src="https://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Samsung_Logo.svg/698px-Samsung_Logo.svg.png" width="320" /></a></div>
<span style="background-color: white; color: #222222; font-family: inherit;"><br /></span>
<span style="background-color: white; color: #222222; font-family: inherit;"><b>1)</b> What is the difference between a process and a thread?</span><br />
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit;"><br /></span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit;"><b>2)</b> Compare Merge sort and Heap sort. What are their time and space complexities? State the cases when one will perform better than the other.</span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit;"><br /></span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit;"><b>3)</b> What is <i>Page table</i>, <i>Address space</i>, and <i>Virtual memory</i>?</span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit;"><br /></span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit;"><b>4)</b> 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.</span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit;"><br /></span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit;"><b>5)</b> <span style="line-height: 19.439998626708984px;">Construct 2 stacks using a single array. <i>Follow Up</i>: Construct 3 stacks in a single array.</span></span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit; line-height: 19.439998626708984px;"><br /></span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit; line-height: 19.439998626708984px;"><b>6)</b> What is a deadlock? </span><br />
<span style="font-family: inherit; line-height: 19.439998626708984px;"><br /></span>
<span style="font-family: inherit; line-height: 19.439998626708984px;"><b>7)</b> What are function pointers? What is their significance?</span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit; line-height: 19.439998626708984px;"><br /></span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit; line-height: 19.439998626708984px;"><b>8)</b> Reverse each word of a string "in place" (that is without using additional memory)</span></div>
<div style="background-color: white; color: #222222;">
<span style="font-family: inherit;">Ex: "Ram and Shyam are friends" --> "maR dna mayhS era sdneirf</span><span style="font-family: inherit;">"</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">Source: Sravan Bodapati, CSE IIT-Madras</span></div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com0tag:blogger.com,1999:blog-1257878355908648494.post-42582342944848829162013-04-03T01:51:00.002-07:002013-04-03T01:59:35.959-07:00Samsung Design Labs: Technical Test<div dir="ltr" style="text-align: left;" trbidi="on">
Samsung Design Labs conducted a Technical test for their selection process. I've outlined the test below to the best of my memory.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Samsung_Logo.svg/698px-Samsung_Logo.svg.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="108" src="https://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Samsung_Logo.svg/698px-Samsung_Logo.svg.png" width="320" /></a></div>
<br />
There was an objective paper which had 20 questions related to CS topics like Algorithms, C++, Data structures.<br />
<br />
The 2nd paper was subjective which had 2 algorithm questions<br />
<br />
<b>1)</b> Given a set of points, develop an algorithm to find their convex hull. Write code in C++ or some other similar language.<br />
<b><br /></b>
<b>2) </b>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.<br />
<br />
Note: Assume that the convex hulls are for the points in 2D representation.</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com0tag:blogger.com,1999:blog-1257878355908648494.post-29978864660462812672013-03-21T05:45:00.000-07:002013-04-03T02:05:05.499-07:00Morgan Stanley QED: Round1<div dir="ltr" style="text-align: left;" trbidi="on">
Morgan Stanley organized a contest <a href="http://en.wikipedia.org/wiki/Q.E.D." target="_blank">Q.E.D</a> 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.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://www.gcu.ac.uk/careers/newsevents/events/eventsxml/Morgan%20Stanley%20Logo%20new.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="73" src="http://www.gcu.ac.uk/careers/newsevents/events/eventsxml/Morgan%20Stanley%20Logo%20new.JPG" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<b>Objective Section</b><br />
<b><br /></b>
<b>1)</b> Let P be a projection, so P*P = P. Compute inverse of (I - cP) given c = 1/2, where I is the identity matrix.<br />
<br />
<b>2)</b> 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?<br />
<br />
<span style="font-family: inherit;"><b>3)</b> Compute <span style="background-color: white; white-space: nowrap;">Σ </span><span style="white-space: nowrap;">( i^5 / 1000^6 ) over i = 1 to 1000, approximately.</span></span><br />
<br />
<b>4)</b> 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).<br />
<br />
<span style="font-family: inherit;"><b>5)</b> Compute <span style="background-color: white; line-height: 16px;"> </span><span style="background-color: white; line-height: 16px;">∫ (<i>dt</i>)^2</span><span style="background-color: white; line-height: 16px;">.</span></span><br />
<span style="font-family: inherit;"><span style="background-color: white; line-height: 16px;"><br /></span></span>
<span style="font-family: inherit;"><span style="background-color: white; line-height: 16px;"><b>6)</b> Let <i>I</i> be an n*n identity matrix and <i>J</i> be an n*n matrix of all ones. Find the rank of <i>I - </i>(1/n)<i>J</i>.</span></span><br />
<span style="font-family: inherit;"><span style="background-color: white; line-height: 16px;"><br /></span></span>
<span style="font-family: inherit;"><span style="background-color: white; line-height: 16px;"><br /></span></span>
<span style="line-height: 16px;"><b><br /></b></span>
<span style="line-height: 16px;"><b>Subjective Section</b></span><br />
<span style="line-height: 16px;"><b><br /></b></span>
<b>1)</b> 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?<br />
<br />
<b>2) </b>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 <i>E</i>[ number of maximas in a random permutation ].<br />
<br />
<b>3) </b>Prove that <i>E</i>[x] = <span style="background-color: white; line-height: 16px;">∫ (1 - <i>F(x)) dx </i>over the range [0, </span><span style="background-color: white; font-family: 'lucida grande', tahoma, verdana, arial, sans-serif; line-height: 20px; text-align: center;">∞</span>], where F is the cumulative distribution function.<br />
<br /></div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com1tag:blogger.com,1999:blog-1257878355908648494.post-89180708101288261522013-03-17T07:23:00.000-07:002013-03-17T07:24:33.380-07:00Walmart Labs Test<div dir="ltr" style="text-align: left;" trbidi="on">
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.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://www.lippincott.com/files/cache/walmart_casestudy_design_logo-1_959_487_cy_90.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="161" src="http://www.lippincott.com/files/cache/walmart_casestudy_design_logo-1_959_487_cy_90.jpg" width="320" /></a></div>
<br />
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.<br />
<br />
There was a subjective section too, which had 2 questions to be coded on a piece of paper.<br />
<br />
<br />
<br />
<b>1)</b> Given 2 additional members, <i>node* prev</i>, <i>node* next</i> in a binary tree node* struct. Initially <i>prev</i> and <i>next</i> 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.<br />
<br />
<b>2)</b> <i>BreakDown(K, S)</i>. Give an algorithm to calculate number of distinct ways in which you can break up amount <i>K</i> into denominations present in <i>S</i>, set of denominations. </div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com2tag:blogger.com,1999:blog-1257878355908648494.post-10496679400041245272013-03-10T00:42:00.002-08:002013-03-10T00:51:55.435-08:00Pocket Gems Coding Test<div dir="ltr" style="text-align: left;" trbidi="on">
<div>
Following coding questions were asked by Pocket Gems, a social gaming company based in San Francisco. Total duration was 1 hour.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://s3.amazonaws.com/UCBSF/media/24/media.png?1318372881" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="200" src="http://s3.amazonaws.com/UCBSF/media/24/media.png?1318372881" width="200" /></a></div>
<div>
<b><br /></b></div>
<div>
<b>1)</b> 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.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<b>2) </b>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.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
Source: Arun Chaudhary, DCE</div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com9tag:blogger.com,1999:blog-1257878355908648494.post-80721901669109548712013-03-01T00:10:00.000-08:002013-03-01T01:02:32.475-08:00Microsoft Internship Interview<div dir="ltr" style="text-align: left;" trbidi="on">
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.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://www-deadline-com.vimg.net/wp-content/uploads/2011/11/microsoft-logo__111129012732.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="96" src="http://www-deadline-com.vimg.net/wp-content/uploads/2011/11/microsoft-logo__111129012732.jpg" width="400" /></a></div>
<br />
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.<br />
<br />
<b>1)</b> <a href="http://www.algorithmist.com/index.php/Coin_Change" target="_blank">Coin-change</a> problem. Given unlimited denominations of 1$, 2$, 5$, 10$; find the total number of ways to make change for amount 100$.<br />
<br />
<b>2)</b> Given strings <i>a</i>, <i>b, c. </i>Replace all occurrences of string <i>b</i> in <i>a</i> with string <i>c</i>. Note that there is no restriction on lengths of <i>a</i>, <i>b</i>, <i>c.</i><br />
<i><br /></i>
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.<br />
<br />
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. :)<br />
<b><b><br /></b></b>
<b><b><br /></b></b>
<b><b>Key Takeaways</b></b><br />
<ul style="text-align: left;">
<li><b><span style="font-weight: normal;">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.</span></b></li>
<li><b><span style="font-weight: normal;">Do some dry runs of your code for some test-cases and check whether it's doing what it's supposed to do.</span></b></li>
<li><b><span style="font-weight: normal;"><b><span style="font-weight: normal;">You need to cross-check your code twice and look out for small mistakes that you might commit due to interview pressure.</span></b></span></b></li>
</ul>
<br />
<br /></div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com2tag:blogger.com,1999:blog-1257878355908648494.post-52223180992765132332013-02-27T05:49:00.000-08:002016-02-24T00:08:14.989-08:00Morgan Stanley Quant Test<div dir="ltr" style="text-align: left;" trbidi="on">
Morgan Stanley took a test for it's <b>Quantitative Analyst</b> profile. The test had 2 sections <i>"Easy" </i>and <i>"Difficult"</i> and total duration was about 2.5 hours.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://www.morganstanley.com/img/mslogo.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://www.morganstanley.com/img/mslogo.png" height="100" width="400" /></a></div>
<br />
<b>Easy</b><br />
<br />
1) Prove no square matrices A, B exists such that AB-BA = I. (Hint: use trace(X))<br />
<br />
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.<br />
<br />
3) Consider all strings composed of of {0, 1, 2}. Find number of strings such that no two 1s are consecutive in the string.<br />
<br />
4) Given X, Y are Uniform(0,1) random variables. Find distribution of X^2 + Y^2.<br />
<br />
5) Write algorithm to find <a href="http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-ii.html" target="_blank">lowest common ancestor</a> of 2 nodes in a binary tree.<br />
<br />
6) Solve the recurrence f(a, b) = f(a, b-1) + f(a-1, b-1) with base cases<br />
f(0, 0) = 1,<br />
f(0, k) = 0,<br />
f(k, 0) = 1. (Hint: Did you observe it's a <a href="http://en.wikipedia.org/wiki/Pascal's_rule" target="_blank">Pascal Identity</a>)<br />
<b><br /></b>
<b><br /></b>
<b><br /></b>
<b>Difficult</b><br />
<br />
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.<br />
<br />
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.<br />
<br />
3) You are given <i>w</i> white balls and <i>b</i> 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.<br />
<br />
4) Give a method to randomly choose any K-size subset from an N-size subset, however, N is not known to you.<br />
<br />
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.<br />
<br /></div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com41tag:blogger.com,1999:blog-1257878355908648494.post-37251198697682314562013-02-11T09:18:00.001-08:002013-03-18T21:47:40.855-07:00Breaking Into Wallstreet: Finance Interviews Prep<div dir="ltr" style="text-align: left;" trbidi="on">
In this post, I will be focusing on preparation tips for <b>Analyst-level</b> 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 <i>finance-enthusiasts</i> at the IITs.<br />
<br />
This post will <i>not</i> be focusing on Quant-finance profiles. If you need some fundae for preparing for Quant finance interviews, checkout <a href="http://get-that-job-at-google.blogspot.in/2013/01/cracking-quant-finance-interviews.html" target="_blank">Cracking Quant-Finance Interviews</a>.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgqJnmMypSL2GU-Dhg0c0IH7dLrXG6ovmlFulZJ7q656_iLH26rHPlaJrADV1HjIGVjyEsSnoWzvZih7qmbEIKqU6QPPzFeBO19SZqNG_hIPiuu6HYMWPZV7_I77fwDtU6TNPED7qFFOdE/s1600/wall-street-sign-pic.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="265" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgqJnmMypSL2GU-Dhg0c0IH7dLrXG6ovmlFulZJ7q656_iLH26rHPlaJrADV1HjIGVjyEsSnoWzvZih7qmbEIKqU6QPPzFeBO19SZqNG_hIPiuu6HYMWPZV7_I77fwDtU6TNPED7qFFOdE/s400/wall-street-sign-pic.jpg" width="400" /></a></div>
<br />
Integrating the following in your placement preparation routine should ideally help<b> </b>improve your chances of getting a finance job<br />
<br />
<br />
<b><u>Start reading a Financial daily</u></b><br />
If you really want a financial markets role, you should know what's happening in the financial world and know it <i>well. </i>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 <i>regularly</i>:<br />
<ul style="text-align: left;">
<li><a href="http://economictimes.indiatimes.com/" target="_blank">The Economic Times</a>: Focused on Indian markets. Highly recommended.</li>
<li><a href="http://www.economist.com/" target="_blank">The Economist</a>: It publishes some excellent finance and economics-oriented articles with interesting analysis and statistics. Recommended for those who absolutely love Economics.</li>
<li><a href="http://www.bloomberg.com/" target="_blank">Bloomberg</a>/<a href="http://in.reuters.com/" target="_blank">Reuters</a>: Focused primarily on US and European markets. Read them once in a while to get an idea about stuff going on globally.</li>
</ul>
<div>
<br />
<br /></div>
<div>
<b><u>Getting your Finance concepts 'Right'</u></b></div>
<div>
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.</div>
<ul style="text-align: left;">
<li><a href="http://www.investopedia.com/" target="_blank">Investopedia</a>: This is the wikipedia of finance. Read up the beginner's tutorials. Subscribe to Investopedia's daily word.</li>
<li><a href="http://www.flipkart.com/vault-guide-finance-interviews/p/itmdyjk9gqgvpchp?pid=9781581316773&affid=chinmaysch" target="_blank">Vault Guide to Finance Interviews</a>: This is an awesome handbook that gives introduction to almost all topics in finance starting from stocks & bonds to currency & interest rates. </li>
<li><a href="http://www.flipkart.com/vault-com-career-guide-investment-banking-3rd/p/itmdyjk8s9xgtnpj?pid=9781581311150&affid=chinmaysch" target="_blank">Vault Guide to Investment Banking</a>: This one somewhat digs deeper into Investment Banking roles of Sales, Trading and Research and topics like Corporate Finance.</li>
</ul>
<div>
<br />
<br /></div>
<div>
<b><u>Financial Certifications</u> </b></div>
<div>
<ul style="text-align: left;">
<li>Although certifications like <i><a href="https://www.cfainstitute.org/pages/index.aspx" target="_blank">CFA</a></i> and <i><a href="http://www.garp.org/frm/frm-program.aspx" target="_blank">FRM</a></i> 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. </li>
<li>You can also pursue NCFM certification (National Stock Exchange's certification in financial markets) for various finance <a href="http://www.nseindia.com/education/content/module_ncfm.htm" target="_blank">modules</a>.</li>
</ul>
</div>
<div>
<br /></div>
<div>
<div>
<b><u><br /></u></b></div>
<div>
<b><u>Finance related Coursework</u> </b></div>
<div>
<ul style="text-align: left;">
<li>Show-off some course-work in subjects related to Finance and Economics. You should try out Finance/Economics related courses running in your institute. </li>
<li>You can pursue some from tons of Finance and Economics courses on <a href="http://coursera.org/" target="_blank">Coursera</a> like Game Theory, Introduction to Finance, Economics for Scientists etc. Here is the <a href="https://www.coursera.org/category/economics" target="_blank">comprehensive list</a>.</li>
</ul>
</div>
</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<b><u>Internship in Finance</u></b></div>
<div>
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. </div>
<div>
<br /></div>
<div>
<b><br /></b></div>
<div>
<b><u>CAT Practice</u></b><br />
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 <i>practice</i> will help you get in the final interview shortlist. Practice <i>Quantitative Aptitude</i> and <i>Data Interpretation</i> sections from the CAT mocks, it will really help you do good on the tests.</div>
<div>
<br />
<b style="text-decoration: underline;">Miscellaneous Websites</b> 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.<br />
<ul style="text-align: left;">
<li><a href="http://wallstreetoasis.com/" target="_blank">Wallstreet Oasis</a></li>
<li><a href="http://www.mergersandinquisitions.com/" target="_blank">Mergers and Inquisitions</a></li>
<li><a href="http://theeconomiccollapseblog.com/">Economic Collapse</a></li>
</ul>
<br />
<br /></div>
<b><u>Firms that offer Financial Analyst profiles</u> </b>(IITB Placements, 2012)<br />
<ul style="text-align: left;">
<li><b>Tier1</b>: Deutsche Bank, JP Morgan, CitiGlobal, Credit Suisse, Optiver, American Express</li>
<li><b>Tier2</b>:<b> </b>Capital One, Crisil, Finmechanics, Forefront Capital, FinIQ, Blufin, RAK Holdings</li>
</ul>
<div>
<br /></div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com17tag:blogger.com,1999:blog-1257878355908648494.post-51009616150665713502013-02-07T03:34:00.000-08:002013-02-08T04:48:43.578-08:00RocketFuel Codesprint at IIT-Bombay<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: left;">
<a href="http://rocketfuel.com/" target="_blank">Rocketfuel</a> is a targeted digital advertising company. It offers the profile of <i>Rocket Scientist</i>, which involves doing work related to AI, Machine Learning and Big Data Analytics. The work location was <b>Redwood City, California</b>. 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. </div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://media.marketwire.com/attachments/201210/94338_HZ-LOGO-TAG-RGB-300x100.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://media.marketwire.com/attachments/201210/94338_HZ-LOGO-TAG-RGB-300x100.jpg" /></a></div>
<b style="background-color: white; line-height: 25px;"><span style="font-family: inherit;"><span style="background-color: transparent; color: #444444; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;"><u><br /></u></span></span></b>
<b style="background-color: white; line-height: 25px;"><span style="font-family: inherit;"><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;"><u>Problem #1</u></span></span></b><br />
<b id="internal-source-marker_0.9857903639785945" style="background-color: white; font-weight: normal; line-height: 25px;"><span style="font-family: inherit;"><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">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.</span><br /><br /><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">An ordinary deque is data structure that represents a list and supports the following four operations:</span><br /><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">pushFront(x): add x to the beginning of the list so that it becomes the first element of the list</span><br /><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">pushBack(x): add x to the end of the list so that it becomes the last element of the list</span><br /><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">popFront(): remove and return the first element of the list</span><br /><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">popBack(): remove and return the last element of the list</span></span></b><br />
<b style="background-color: white; font-weight: normal; line-height: 25px;"><span style="font-family: inherit;"><span style="white-space: pre-wrap;"><br /></span><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">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.</span><br /><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">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.</span></span></b><br />
<span style="background-color: white; line-height: 25px;"><span style="font-family: inherit;"><span style="font-weight: normal;"><span style="white-space: pre-wrap;"><br /></span></span><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">Consider the following examples:</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">(pushBack, pushBack, pushFront) results in the following sequence of list states:</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">(1)</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">(1, 2)</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">(3, 1, 2)</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">(pushFront, pushFront, pushBack, popBack, pushBack, popBack) results in the following sequence of states and outputs:</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">(1)</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">(2, 1)</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">(2, 1, 3)</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">(2, 1) output: 3</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">(2, 1, 4)</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">(2, 1) output 4</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">In the previous example, the output of the entire sequence of operations can be written as (3, 4).</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">Your program will receive exactly one line of input, a comma-separated list of integers with no spaces in the following format:</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">x_1,x_2,...,x_N</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">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).</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">Your program should produce exactly one line of output, a comma-separated list of operations with no spaces in the following format:</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">op_1,op_2,...,op_2N</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">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.</span><br /><br /><span style="white-space: pre-wrap;"><b>Sample Testcases</b></span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">Input:</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">3,2,1</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">Output:</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">pushBack,pushBack,pushBack,popBack,popBack,popBack</span><br /><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">Input:</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">1,2,3</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">Output (note choice of pushBack over pushFront):</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">pushBack,popBack,pushBack,popBack,pushBack,popBack</span><br /><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">Input:</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">4,1,5,2,3</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">Output (pushFront is needed in some cases):</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">pushBack,pushFront,pushFront,pushBack,popBack,popBack,pushBack,popBack,popBack,popBack</span><br /><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">Input:</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">5,1,4,2,3</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">Output (some sequences are impossible):</span><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">impossible</span><br /><br /><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">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:</span><br /><span style="background-color: transparent; font-weight: bold; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">1.</span><span style="background-color: transparent; font-weight: normal; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;"> 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.</span><br /><span style="background-color: transparent; font-weight: bold; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;">2.<span style="font-weight: normal;"> 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.</span></span></span></span><br />
<span style="background-color: white; line-height: 25px;"><span style="font-family: inherit;"><span style="background-color: transparent; font-weight: bold; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;"><span style="font-weight: normal;"><br /></span></span></span></span>
<span style="background-color: white; line-height: 25px;"><span style="font-family: inherit;"><span style="background-color: transparent; font-weight: bold; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;"><span style="font-weight: normal;"><br /></span></span></span></span>
<span style="background-color: white; line-height: 25px;"><span style="font-family: inherit;"><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;"><b><u>Problem #2</u></b></span></span></span><br />
<span style="background-color: white; font-family: inherit; line-height: 25px;">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.</span><br />
<br />
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;"><br /></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">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.</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;"><br /></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">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.</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;"><br /></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">"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.</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;"><br /></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">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.</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;"><br /></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">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:</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">N M K</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">X1 Y1</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">X2 Y2</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">.</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">.</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">.</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">XK YK</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">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:</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">5 5 4</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">0 2</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">0 3</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">2 2</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">3 1</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">represents the following board:</span></div>
<pre style="background-color: white; line-height: 25px;"><span style="font-family: inherit;">..@@.
.....
..@..
.@...
.....
</span></pre>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">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):</span></div>
<pre style="background-color: white; line-height: 25px;"><span style="font-family: inherit;">..7@1
.6.2.
5.3.9
.4.A.
..B..</span></pre>
<div style="background-color: white; line-height: 25px; margin: 0px 0px 1.2em; padding: 0px;">
<span style="font-family: inherit;">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.</span></div>
<br />
<b style="background-color: white; font-weight: normal; line-height: 25px;"><span style="font-family: inherit;"><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;"><br /></span></span></b>
<b style="background-color: white; line-height: 25px;"><span style="background-color: transparent; margin: 0px 0.3em 0px 0px; padding: 0px; vertical-align: baseline; white-space: pre-wrap;"><u><span style="font-family: inherit;">Problem #3</span></u></span></b><br />
<span style="background-color: white; font-family: inherit; line-height: 25px;">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.</span><br />
<div style="background-color: white; line-height: 25px;">
<strong><span style="font-family: inherit;">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.</span></strong></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">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).</span></div>
<div style="background-color: white; line-height: 25px;">
<br /></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">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:</span></div>
<div style="background-color: white; line-height: 25px;">
<br /></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">racerId startTime endTime</span></span></div>
<div style="background-color: white; line-height: 25px;">
<br /></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">where <span style="margin: 0px 0.3em 0px 0px; padding: 0px;">racerId</span> is an integer in the range [0,10^9] and <span style="margin: 0px 0.3em 0px 0px; padding: 0px;">startTime</span> and <span style="margin: 0px 0.3em 0px 0px; padding: 0px;">endTime</span> are both integers such that <span style="margin: 0px 0.3em 0px 0px; padding: 0px;">0 <= startTime < endTime <= 10^18</span>. Each <span style="margin: 0px 0.3em 0px 0px; padding: 0px;">racerId</span> will be distinct. Also, the collection of all start and end times will not contain any duplicate elements.</span></div>
<div style="background-color: white; line-height: 25px;">
<br /></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">Given such an input, you should print output in the following format:</span></div>
<div style="background-color: white; line-height: 25px;">
<br /></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">racerId score</span></span></div>
<div style="background-color: white; line-height: 25px;">
<br /></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">where <span style="margin: 0px 0.3em 0px 0px; padding: 0px;">score</span> is the score as defined above for racer <span style="margin: 0px 0.3em 0px 0px; padding: 0px;">racerId</span>. The output lines should be sorted in ascending order of<span style="margin: 0px 0.3em 0px 0px; padding: 0px;">score</span> with ties broken by sorting by <span style="margin: 0px 0.3em 0px 0px; padding: 0px;">racerId</span>, also in ascending order. This can be accomplished with a simple sort at the end.</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;"><strong><br /></strong></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;"><strong>Directions</strong>:</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">Please code this problem in Java, C, or C++. Your solution should run in less than O(N^2) on all inputs.</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;"><em>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 </em><em>(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</em><em>. 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.</em></span></div>
<div style="background-color: white; line-height: 25px;">
<strong><span style="font-family: inherit;"><br /></span></strong></div>
<div style="background-color: white; line-height: 25px;">
<strong><span style="font-family: inherit;">What We Are Looking For:</span></strong></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">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.</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;"><br /></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;"><b>Sample Testcases</b></span><span style="font-family: inherit;"> </span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">input:</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">5</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">2 100 200</span></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">3 110 190</span></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">4 105 145</span></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">1 90 150</span></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">5 102 198</span></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">output:</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">3 0</span></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">4 0</span></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">1 1</span></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">5 2</span></span></div>
<div style="background-color: white; line-height: 25px;">
<span style="margin: 0px 0.3em 0px 0px; padding: 0px;"><span style="font-family: inherit;">2 3</span></span></div>
<div style="background-color: white; line-height: 25px;">
<br /></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;">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.</span></div>
<div style="background-color: white; line-height: 25px;">
<span style="font-family: inherit;"><br /></span></div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com3tag:blogger.com,1999:blog-1257878355908648494.post-49884325822543343052013-02-05T19:51:00.000-08:002013-02-05T19:51:47.511-08:00Credit Suisse: Quantitative Math Test<div dir="ltr" style="text-align: left;" trbidi="on">
Following questions were asked for <b>Strategic Risk Management</b> profile of Credit Suisse at IIT-Bombay.<br />
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://union.ic.ac.uk/acc/hockey/wp-content/uploads/2011/01/creditsuisse.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="98" src="https://union.ic.ac.uk/acc/hockey/wp-content/uploads/2011/01/creditsuisse.jpg" width="400" /></a></div>
<br />
<br />
<b>1)</b> Value of E[|X|] where X ~ Normal(0,1)<br />
<br />
<b>2)</b> Choose 3 points on circumference of a circle. What is the probability that the center will lie in the triangle?<br />
<br />
<b>3)</b> 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<br />
<br />
<b>4)</b> What is the expected number of tosses needed to get 2 consecutive heads?<br />
<br />
<b>5)</b> 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.<br />
<br />
<b>6)</b> Solve: dy/dx + xy = x*(y^2)<br />
<br />
<b>7)</b> Solve: dy/dx + 3y = e^x<br />
<br />
<b>8)</b> Calculate Sum(Var(pow(Xi,2))), i = 1 to N, Xi are independent.<br />
<br />
<b>9)</b> Calculate Var(XY) where X ~ Uniform(0,1) and Y ~ Normal(0,1)<br />
<br />
<b>10)</b> 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 <span style="background-color: white; color: #333333; font-family: arial, helvetica, clean, sans-serif; font-size: 13px; line-height: 16px;">λ</span>=1 hour.<br />
<br />
<b>11)</b> 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.<br />
<br />
<b>12)</b> 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?<br />
<br />
<b>13)</b> Calculate E[f(x)], where x ~ N(0,1) (For some function f).<br />
<br />
<b>14)</b> Given X ~ Uniform(-<span style="background-color: white; font-family: 'Times New Roman', 'Nimbus Roman No9 L', Times, serif; font-size: 15px; line-height: 19.1875px; white-space: nowrap;">π</span>/2, <span style="background-color: white; font-family: 'Times New Roman', 'Nimbus Roman No9 L', Times, serif; font-size: 15px; line-height: 19.1875px; white-space: nowrap;">π</span>/2). Find probability distribution of Y = tan(X).<br />
<br />
<b>15)</b> f(x,y) = (x^2 - y^2) / (x^2 + y^2). Comment on continuity of the function at (0,0)<br />
<br />
<b>16)</b> 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].<br />
<div>
<br /></div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com1tag:blogger.com,1999:blog-1257878355908648494.post-72406924507791585452013-02-04T01:26:00.000-08:002013-02-04T01:26:23.856-08:00Yahoo! Programming Test<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="font-family: inherit;">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.</span><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://static.businessinsider.com/image/4fd8dcb7eab8eab648000004-1600-304/yahoo-logo.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="60" src="http://static.businessinsider.com/image/4fd8dcb7eab8eab648000004-1600-304/yahoo-logo.jpg" width="320" /></a></div>
<br />
<span style="font-family: inherit;">Coding test had the following 2 questions:</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><b>1) </b>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. </span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://s17.postimage.org/kt5hno3m7/tree.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://s17.postimage.org/kt5hno3m7/tree.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div>
<span style="font-family: inherit;">The path needed is 3->7->4->9 since it adds up to 3 + 7 + 4 + 9 = 23, which is the max possible value.</span></div>
<br />
<br />
<span style="font-family: inherit;"><b>2)</b> Given an array of strings, display all the strings that are not prefix of any other string in the array.</span><br />
<div>
<span style="font-family: inherit;">(Hint #1: Sorting; </span><span style="font-family: inherit;">Hint #2: </span><a href="http://www.geeksforgeeks.org/trie-insert-and-search/" style="font-family: inherit;" target="_blank">Trie</a>)<br />
<br /></div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com1tag:blogger.com,1999:blog-1257878355908648494.post-30540785041207870372013-01-30T10:07:00.000-08:002013-02-02T11:14:51.581-08:00Epic Systems Interview Experience<div dir="ltr" style="text-align: left;" trbidi="on">
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.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://upload.wikimedia.org/wikipedia/commons/2/26/Epic.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="123" src="http://upload.wikimedia.org/wikipedia/commons/2/26/Epic.png" width="320" /></a></div>
<br />
<br />
<b>Tech Round </b>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.<br />
<br />
<br />
<b>HR Round </b>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 <i>very </i>interested in the opportunity and would definitely join Epic after being selected.<br />
<br />
<br />
<b>Key Takeaways </b>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 <a href="http://get-that-job-at-google.blogspot.in/2012/12/epic-systems-test.html" target="_blank">Epic's Coding Test</a> 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.<br />
<b><br /></b>
<b><br /></b>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com3tag:blogger.com,1999:blog-1257878355908648494.post-24167858535176363602013-01-26T01:07:00.000-08:002013-02-01T07:37:57.807-08:00Google's Hiring Algorithm<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="color: #333333;"><span style="line-height: 20.796875px;">Found this infographic on <a href="http://www.jobvine.co.za/" target="_blank">Jobvine</a>, very interesting stuff. Gives a good insight on how complex and selective the process is!</span></span><br />
<span style="color: #333333;"><span style="line-height: 20.796875px;"><br /></span></span>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://s2.postimage.org/w92frby9l/jobvine_infographic_1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://s2.postimage.org/w92frby9l/jobvine_infographic_1.png" /></a></div>
<span style="color: #333333;"><span style="line-height: 20.796875px;"><br /></span></span>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com2tag:blogger.com,1999:blog-1257878355908648494.post-41861975632633928702013-01-24T02:45:00.001-08:002013-01-26T01:15:21.008-08:00How does one 'Get that job at Google'!<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
Following post is inspired from Steve Yegge's <a href="http://steve-yegge.blogspot.in/2008/03/get-that-job-at-google.html" target="_blank">legendary post</a> on prepping for Google Interviews.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipRRAmaAQrlh_hEp039eVUOC8g16sKwUZSzLGjA4Y1XXUYQgtdzk_-1IaADVJ9SZGfZh32GRuNzXAxpiADmj5ycU1FMT8_lf9XBcPGfVntIcQxMj_dy8TBeUB7XSaGiX6GEiXkGgz8H3U5/s1600/google.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="172" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEipRRAmaAQrlh_hEp039eVUOC8g16sKwUZSzLGjA4Y1XXUYQgtdzk_-1IaADVJ9SZGfZh32GRuNzXAxpiADmj5ycU1FMT8_lf9XBcPGfVntIcQxMj_dy8TBeUB7XSaGiX6GEiXkGgz8H3U5/s320/google.jpg" width="320" /></a></div>
<br />
<span style="font-family: inherit;"><b>Coding Knowledge</b> </span><span style="font-family: inherit; line-height: 1.5em;">C/C++</span><span style="font-family: inherit; line-height: 1.5em;"> </span><span style="font-family: inherit; line-height: 1.5em;">and</span><span style="font-family: inherit; line-height: 1.5em;"> </span><span style="font-family: inherit; line-height: 1.5em;">Java</span><span style="font-family: inherit; line-height: 1.5em;"> </span><span style="font-family: inherit; line-height: 1.5em;">are the preferred programming languages for Google Interviewers. You must know at least one of them <i>really well</i>. You will be expected to write code in the phone screen interviews and in the onsite interviews as well.</span><br />
<h3>
<span style="font-weight: normal;"><span style="font-family: inherit; font-size: small; line-height: 1.5em;"><br /></span></span></h3>
<h3>
<span style="font-weight: normal;"><span style="font-family: inherit; font-size: small; line-height: 1.5em;">Recommended books for CS interviews:</span><span style="font-family: inherit; font-size: small; line-height: 1.5em;"> </span></span></h3>
<h3>
<ul>
<li><a href="http://www.flipkart.com/introduction-algorithms-8120340078/p/itmczynzhyhxv2gs?pid=9788120340077&affid=chinmaysch" style="font-weight: normal;" target="_blank"><span style="font-family: inherit; font-size: small;">Introduction To Algorithms - By Cormen</span></a></li>
<li><span style="font-family: inherit; font-size: small; font-weight: normal;"><a href="http://www.flipkart.com/programming-interviews-exposed-secrets-landing-your-next-job-3nd/p/itmdgdhrgjtytvmf?pid=9788126539116&affid=chinmaysch" target="_blank">Programming Interviews Exposed</a><span style="color: #555599; line-height: 1.5em;"> </span></span></li>
<li><span style="font-family: inherit; font-size: small; line-height: 1.5em;"><a href="http://www.flipkart.com/cracking-coding-interview-150-programming-questions-solutions-5th/p/itmd34cf5ja6gdhs?pid=9780984782802&affid=chinmaysch" style="font-weight: normal; line-height: 1.5em;" target="_blank">Cracking the Coding Interviews</a></span></li>
<li><span style="font-size: small;"><a href="http://www.flipkart.com/algorithms-for-interviews/p/itmdygaemy4guvxg?pid=9788100005743&affid=chinmaysch" style="font-weight: normal;" target="_blank"><span style="font-family: inherit;">Algorithms for Interviews</span></a></span></li>
</ul>
</h3>
<h3>
<span style="color: #111111; font-family: inherit; font-size: small; font-weight: normal; line-height: 1.5em;">Recommended websites for coding practice:</span><span style="color: #111111; font-family: inherit; font-size: small; font-weight: normal; line-height: 1.5em;"> </span><span style="font-family: inherit; font-size: small; font-weight: normal; line-height: 1.5em;"><a href="http://interviewstreet.com/" style="line-height: 1.5em;" target="_blank">InterviewStreet</a>, <a href="http://www.topcoder.com/" target="_blank">Topcoder</a></span></h3>
<div>
<br />
<br /></div>
<h3 style="background-color: white; color: #111111;">
<span style="font-size: small;"><span style="font-family: inherit;">Big-O</span><span style="font-family: inherit;"> </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">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 <a href="http://www.flipkart.com/introduction-algorithms-3rd/p/itmczynzhyhxv2gs?pid=9788120340077&affid=chinmaysch" target="_blank">Data Structures and Algorithms</a> book.</span></span></h3>
<h3 style="background-color: white; color: #111111;">
<span style="font-family: inherit; font-size: small;"><br /></span></h3>
<div>
<span style="font-family: inherit;"><br /></span></div>
<h3 style="background-color: white; color: #111111;">
<span style="font-size: small;"><span style="font-family: inherit;">Sorting</span><span style="font-family: inherit;"> </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">You should be able to write algorithms O(n*lgn) like </span><span style="font-weight: normal;">QuickSort and</span> <span style="font-weight: normal;">MergeSort</span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;"> </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">with ease. Compare and understand the best, worst and average case complexities. </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">I found this <a href="http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms" target="_blank">table</a> on wiki to be very handy; it lists important properties of all </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">sorting algorithms. </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">Don’t neglect the </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">basic O(n^2) algorithms</span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;"> like </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">Bubble sort</span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;"> or </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">Insertion sort</span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">, since other algorithms improve over these</span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">. Interviews are more about improving a basic idea, sorting algorithms will help with this process.</span></span></h3>
<div>
<span style="font-size: small;"><span style="font-family: inherit; line-height: 1.5em;"><br /></span></span><span style="font-size: small;"><span style="font-family: inherit; line-height: 1.5em;"><br /></span></span><span style="font-family: inherit;"><span style="font-weight: bold; line-height: 1.5em;">Hash Tables </span></span><span style="background-color: white; color: #111111; font-family: inherit; line-height: 1.5em;">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 <i>caching</i> results.</span></div>
<div>
<br />
<br /></div>
<div>
<span style="font-size: small;"><br /></span></div>
<h3 style="background-color: white; color: #111111;">
<span style="font-size: small;"><span style="font-family: inherit;">Trees</span><span style="font-family: inherit;"> </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">Go through basic tree construction, traversal and manipulation algorithms. You should be able to implement algorithms based on binary search trees. </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">You should be familiar with balanced trees although you are not expected to write code for them in the interview: </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;"><span class="caps">AVL</span> trees, Red-Black trees, <a href="http://www.geeksforgeeks.org/trie-insert-and-search/" target="_blank">Trie</a>, n-ary trees</span><strong style="font-family: inherit; line-height: 1.5em;"> </strong><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">etc</span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">. </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">Thorough knowledge about </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">inorder, postorder and preorder</span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;"> traversals is necessary, because we can solve many tree problems by doing simple modifications to one of these traversals.</span></span></h3>
<div>
<br />
<h3 style="background-color: white; color: #111111;">
<span style="font-size: small;"><br /></span></h3>
<h3 style="background-color: white; color: #111111;">
<span style="font-size: small;"><span style="font-family: inherit;">Graphs</span><span style="font-family: inherit;"> </span></span></h3>
<h3 style="background-color: white; color: #111111;">
<ul>
<li><span style="font-size: small;"><span style="font-family: inherit;"><span style="font-weight: normal; line-height: 1.5em;">Graphs are a <i>very </i>important concept in Computer Science. Practice the three </span><span style="font-weight: normal; line-height: 1.5em;">basic representation of graphs</span><span style="font-weight: normal; line-height: 1.5em;"> (objects and pointers, matrix, and adjacency list) and familiarize yourself with their pros & cons. </span></span></span></li>
<li><span style="font-family: inherit; font-size: small; font-weight: normal; line-height: 1.5em;">There is not much time during the interview so you should not expect something very complex. However, basic graph traversal algorithms (</span><span style="font-size: small; font-weight: normal;"><span style="font-family: inherit; line-height: 1.5em;"><i>DFS</i></span><span style="font-family: inherit; line-height: 1.5em;"> and </span><span style="font-family: inherit; line-height: 1.5em;"><i>BFS</i></span></span><span style="font-family: inherit; font-size: small; font-weight: normal; line-height: 1.5em;">) are a must, you should implement them in all basic representations. </span></li>
<li><span style="font-family: inherit; font-size: small; font-weight: normal; line-height: 1.5em;">You should be able to implement the </span><span style="font-size: small;"><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;"><i>Dijkstra</i></span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;"> or </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;"><i>Floyd-Warshall</i></span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;"> algorithms as well as minimum spanning tree algorithms (</span><span style="font-weight: normal;"><span style="font-family: inherit; line-height: 1.5em;"><i>Kruskal</i></span><span style="font-family: inherit; line-height: 1.5em;"> and </span><span style="font-family: inherit; line-height: 1.5em;"><i>Prim</i></span></span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">). Learn about </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;"><i>topological</i> sorting, since it is surprisingly very useful in many ordering problems</span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">.</span></span></li>
</ul>
</h3>
<div>
<span style="font-size: small;"><span style="font-family: inherit; line-height: 1.5em;"><br /></span></span></div>
<br />
<span style="font-family: inherit; line-height: 1.5em;"><br /></span></div>
<h3 style="background-color: white; color: #111111;">
<span style="font-size: small;"><span style="font-family: inherit;">Dynamic Programming </span><span style="font-weight: normal;"><span style="font-family: inherit; line-height: 1.5em;">This is probably </span><span style="font-family: inherit; line-height: 1.5em;">the</span><em style="font-family: inherit; line-height: 1.5em;"> </em><em style="font-family: inherit; line-height: 1.5em;">most important</em><span style="font-family: inherit; line-height: 1.5em;"> 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.</span></span></span></h3>
<div>
<h3 style="background-color: white; color: #111111;">
<span style="font-size: small;"><br /></span></h3>
<div>
<span style="font-size: small;"><br /></span></div>
<h3 style="background-color: white; color: #111111;">
<span style="font-size: small;"><span style="font-family: inherit;">Operating Systems </span><span style="font-family: inherit; font-weight: normal; line-height: 1.5em;">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.</span></span></h3>
<div style="background-color: white; color: #111111; line-height: 1.5em;">
</div>
</div>
<h3 style="background-color: white; color: #111111;">
<span style="font-size: small;"><br /></span></h3>
<div>
<span style="font-size: small;"><br /></span></div>
<h3 style="background-color: white; color: #111111;">
<span style="font-size: small;"><span style="font-family: inherit;">Mathematics </span><span style="font-weight: normal;"><span style="font-family: inherit; line-height: 1.5em;">You should familiarize yourself with </span><span style="font-family: inherit; line-height: 1.5em;">counting, combinatorics and probability</span><span style="font-family: inherit; line-height: 1.5em;">.</span></span></span></h3>
<h3 style="background-color: white; color: #111111;">
<span style="font-family: inherit;"><span style="font-size: small;"><br /></span></span></h3>
<div>
<span style="font-family: inherit;"><br /></span></div>
<div style="background-color: white; color: #111111; line-height: 1.5em;">
<span style="font-family: inherit; line-height: 1.5em;"><b>Google's publications </b>Read up Google's <i>path-breaking</i> publications listed below if you have time.</span><br />
<div>
</div>
<ul>
<li><a href="http://research.google.com/archive/gfs.html" style="color: #555599; font-family: inherit; line-height: 1.5em;" target="_blank">Google File System</a></li>
<li><a href="http://research.google.com/archive/bigtable.html" style="color: #555599; font-family: inherit; line-height: 1.5em;" target="_blank">Google Bigtable</a></li>
<li><a href="http://research.google.com/archive/mapreduce.html" style="color: #555599; font-family: inherit; line-height: 1.5em;" target="_blank">Google MapReduce</a></li>
</ul>
</div>
<h3 style="background-color: white; color: #111111;">
<span style="font-size: small;"><br /></span></h3>
<h3 style="background-color: white; color: #111111;">
<span style="font-family: inherit; font-weight: normal; line-height: 1.5em;"><span style="font-size: small;">I hope you find the above article useful :) Enjoy!</span></span></h3>
</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com2tag:blogger.com,1999:blog-1257878355908648494.post-49941163284576780902013-01-19T07:41:00.002-08:002013-02-04T02:49:13.014-08:00Facebook Interview Experience<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: center;">
<a href="http://d34wpjv4rf3nwa.cloudfront.net/www1/wp-content/uploads/2010/04/Facebook-Survey-Integration.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="120" src="http://d34wpjv4rf3nwa.cloudfront.net/www1/wp-content/uploads/2010/04/Facebook-Survey-Integration.jpg" width="320" /></a></div>
<br />
You can find some general tips for interviewing with facebook <a href="https://www.facebook.com/notes/facebook-engineering/get-that-job-at-facebook/10150964382448920" target="_blank">here</a> (posted by a Facebook Engineer). Following questions are from Facebook's final interview rounds (for Software Engineer position):<br />
<b><br /></b>
<b><u>Round 1</u></b><br />
<b>1)</b> 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.<br />
Signature: <span style="font-style: italic;">bool</span><i> isPalindrome(char*, node*)</i><br />
<br />
<b>2)</b> Multiply two very large numbers given in the form of strings and return the result also as string.<br />
Signature: <i>char* multiply(char*, char*)</i><br />
<br />
<b><u>Round 2</u></b><br />
<b>3)</b> 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.<br />
Eg. class iterator{<br />
<b> public</b>:<br />
next();<br />
} T;<br />
<br />
Consider the following binary tree:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="166" src="http://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg" width="200" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
T.next() will print 2<br />
T.next() again will print 5<br />
T.next() again will print 11<br />
T.next() again will print 6 and so on.<br />
so, kth call to next() should print kth node in the postorder traversal.<br />
<br />
<b>4)</b> Given two arrays of integers find their intersection. <i>FollowUp:</i> 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.<br />
<br />
<b><u>Round 3</u></b><br />
<b>5)</b> Find the longest common contiguous substring of two given strings.<br />
<br />
<b><u>Round 4</u></b><br />
<b>6)</b> Given a binary tree write a function to join all the nodes at the same level. Consider each node to have a <i>next</i> pointer.<br />
<br />
<b>7)</b> HR Questions:<br />
<ul style="text-align: left;">
<li>Tell me about yourself</li>
<li>Projects & Internships</li>
<li>One conflict with team mates and how did u deal with it </li>
<li>Where would you like to work? India or US? Why? </li>
<li>One thing you would want to change on <a href="http://facebook.com/" target="_blank">facebook</a> </li>
<li>One thing about facebook that excites you the most</li>
</ul>
<br />
<br />
Source: Some student at IIT-Guwahati.</div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com0tag:blogger.com,1999:blog-1257878355908648494.post-52285961029230394322013-01-19T06:33:00.000-08:002013-01-26T01:15:21.015-08:00Facebook Programming Test <div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://d34wpjv4rf3nwa.cloudfront.net/www1/wp-content/uploads/2010/04/Facebook-Survey-Integration.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="120" src="http://d34wpjv4rf3nwa.cloudfront.net/www1/wp-content/uploads/2010/04/Facebook-Survey-Integration.jpg" width="320" /></a></div>
<br />
Facebook had conducted it's test on InterviewStreet in IITB. Total duration of test was 2 hours. The problem boiled down to following:<br />
<br />
Given an undirected graph, source node <i>s</i> and destination node <i>d</i>; find number of distinct nodes visited on all paths from <i>s</i> to <i>d</i> such that each node is visited exactly once while enumerating all the paths.<br />
<br />
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. </div>
Chinmayhttp://www.blogger.com/profile/05849000619156676678noreply@blogger.com0