Thursday, February 01, 2007

Favourite songs

Glory of Love (Peter Cetera)
Right here waiting (Richard Marx)
I will always love you (Witney Houston)
My heart will go on (Titanic)
True (Ryan Cabrera)
I just called to say I love you (Stevie Wonder)
Everything I do (Bryan Adams)
You are not alone (MJ)
Deborah Gibson (Lost in your eyes)
George Benson (Nothing's gonna change my love for you)
Kool & The Gang (Cherish)
Vanessa Williams(Save the best for last)
I honestly love you (Olivia)
Forever and ever, Amen (Randy Travis)
Please Remember Me (Tim Mcgraw)
Complicated (Avril Lavigne)

Wednesday, April 12, 2006

Wednesday, March 15, 2006

Microsoft Interview Questions - 2

When I went to Microsoft for the second time, the interview was more pressurizing.

Interview 1 - The interviewer asked me a lot of questions about my project and the disucssions started with a lunch, which my interviewer hosted in an nearby restaurant. After more than 30 mins discussion about my favorite project, he gave a design question, which was not hard.

Q 1. Given a data store and multiple getters & setters, write a program to maintain consistency.

I gave out a simple queue concept, where getters and setter are allowed one by one to access the data store and in this case it would be like a semaphore. However, this would make the system inefficient by killing parallelism. So, I gave optimization, by adding 2 points:

1. If there are consecutive getters in the queue, allow them all in parallel

2. If there are consecutive setters, throw out all but the last, as they dont make any useful change and simulate the exceptions. I left the exception simulation for hardware and did these two things to have the data store with high parallelism and consistency.

The interviewer seemed to be pleased by the design.

The next interview was slightly more abstract. The interviewer grilled me on team working and bothered about the team-aspects of my favorite projet - a distributed file systems project. Then she gave a question:

Q 2. There are a number of tasks and they have their dependencies. Design data structures to represent them and write a program to schedule the tasks such that the dependencies are not violated.

I asked about other questions, like time deadlines, etc, but the tasks didnt have time deadlines and if a task had all its dependencies satisfied it can execute.

I designed a Directed Acyclic Graph (DAG) as I believed that it has to be a graph as tasks can have many to many relationship, it has to be directed as dependencies are always unidirectional and it has to be acylic so that it can be scheduled. To represent the graph, initially I took the adjacency matrix format, but soon realized that the graph will be very dynamic as new tasks keep coming and existing taks are scduled and removed. So, I designed based on adjacency lists and wrote a program that would run through the graph to find a node without dependency, schdule it and traverse the entire graph to find out its dependents and breaking the links. The interviewer was satisfied with teh design and after a long discussion (I dont exactly remember the details) the interview ended.

Q 3. The interview had a simple question, on which I stumbled initially. I was given a long string of numerals and have to write a funtion that checks if it contained all numbers from 000 to 999 (numbers are represented in 3 digits).

I first created a 1000 element hash array one for number from 0 to 999 and set it to false initially. Then I read through the array from 0 to len - 2 & in each iteration I take out i, i+1, i+2 characters, convert to number N and setting the element in the hash array[N] to true. At the end if all the elements in hash arry are true, then all numbers are there in the given string and the function returns true. Then, I did the folloowing optimizations:

1. To check all the elements in the hash array to be true, I have to go through the entire array in O(N) operations. Instead, I could just keep track of number of true elements in the array with a simple counter. Thus, everytime I set an element in the array to true from false, I increment the counter. If the counter reaches 1000, then it means that the entire array has true values and I can stop the fuction there itself, instead of goin through the entire length of the string. I can also eliminate the O(N) checking at the end.

2. The minimum length of the string that could have all 1000 numbers is 1002. I took a minute or two to realize this fact. I saw that the loop has to run atleast 1000 times to set 1000 true values, and to run 1000 times, len has to be atleast 1002. So, if the string length is less than 1002, right at the start we can return false.

3. To go a step further, everytime I find a duplicate element (the array[N] has true already) I increement a duplicate counter. At anytime, the length of the string > 1002 + d. If it is less than 1002 + d, then it means it wont contain all the numbers. This can effectively, reduce teh possibility that the entire string has to be searched.

The interviewer was impressed with the design and so I consider that it was positive.

Q 4. It was the famous tic-tac toe problem. Given a large N * N tic-tac-toe board (instead of reguard 3*3 tic-tac toe), the fucntion has to determine whether any player is winning in the current round, given the board state. Create appropriate data structures to represent the board.

I started out from the simplest of solutions. Take the board as a N*N array, go through all the rows and columns and diagonals to see whether they have same player's coins (for efficiency we can represent the two players as true and false and ignoring the free spaces, and if we XOR all the rows and then columns and diagonal and if get Negative (and full row or column) , then one of them wins). It was simple but was a O(2*N*N+2*N) = O(N^2). I knew i could do better.

I then had sentinels for each row, column and diagnals (2N+2 sentinels) for each player. Every time, I place a coin in the board in (x,y), I increment the row_sentinel[x], column sentinal[y] & diagonal[1] if x == y or diagaonal[2] if x == N-y-1; If any of these elements equals N, then the corresponding player wins. It is cleaner and effecient and any point I need to check just the 2N+2 sentinals and it is a O(N) operation. I still could do better.

I created a super-sentinal for each player that keeps track of max value among sentinels. Thus, everytime I update the sentinals, I would check to see if it greater than the value of super sentianl and if yes, I would update teh super-sentinal. Thus, at anytime to see if a player is winning, I need to check (super-sentinal == N). It is extremely simple and highly efficient and is a O(1) operation.

The interviewer seemed to be very impressed. I clinched the job.

Q 5. Now the interview with the Product Manager (a person responsible for many core aspects of MSDN). Last interview with a head of the group, is always a positive sign and so I was upbeat. But, the question was extremely tricky and one of the stunning problems with a very simple solution.

There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers. The odd numbers are to be sorted in descending order and the even numbers in ascending order. You are not allowed to use any extra array and it has to use a conventional sorting mechanism and should not do any pre or post processing.

I'll give you a clue (which I had to secure after a painful 20 mins).. You can use operator overloading and write the solution in 5 lines.. If you solve now, it would still be great, because I solved it after 20 mins and with a lot of hints.

Friday, March 03, 2006

How I got into Microsoft

I hope you wud have seen my earlier post on Microsoft interview. I didnt update my blog, after that, due to so many events... Let me recount some of them.

After coming from the Microsoft interview - 1, I was totally confident and felt happier that the interview went well. I had more than 5 interviews and the interviewers gave a fell-good factor. So, I was pretty upbeat about the results. So, I started waiting for the results from Monday after the interview on Friday (10th Feb). But, as days started moving, I didnt get any results. I was panicked. I called up the recruiter and she asked me to wait further, while most others had gotten the negative results. By Friday, I felt pretty dejected and the recruiter called me up and conveyed her regrets that the team profiles didnt match with me and so they cudnt offer me. I knew exactly what she was talking, as in couple of interviews I gave a strong liking for distributed systems (the teams were dealing with security and subscription) and expressed my desired to change the teams, once I join Microsoft. I realised how politicially incorrect, that was. After all, it is the team that is goin to get you into Microsoft and if you dont show an interest in the team, the team wont be interested in you.

So, the Rule No. 1: Always show interest and passion in what you work. If you r interviewed for sweeping, convince the interviewer that sweeping and mopping are the best jobs in the world.

Rule No. 2: Never be too candid and open in your remarks. In business and politics, the art of 'sweet lies' have to be learnt.

That weekend, I was a bit moody, as the Microsoft 'rejection' came at the same time as rejections for my PhD admission from MIT & Stanford. Truly, I believed it is the end of the world. Not becaz, some big company kicked me out, but because I cant do much better on my interview and I wont know what to improve on to bring a success. On Monday, I took on the pre-planned trip to Virginia to interview with the company, where I interned. Its a really good one for my research and had very good pay package. I went and spoke to them, had a couple of interviews and the CEO (its a small company, after all) liked me and was upbeat in offering me a designer job. But, the only thing about the place was there was something that was bothering my intuition about that company. I associated it with a bit of damp air and without sun shine. Whereas Microsoft appeared fresh and sunny and it was a psychologically important factor for me to have sunlight at work. But, I was to seal the offer in a couple of days.

But, then on Tuesday, Microsoft got back to me and asked me about the team preference and in one not-so-usual case they were offering me a second interview and with a team closer to my interests - XML enterprise team (though the name didnt appear cool to me, their work on distributed tools and systems for MSDN interested me). And I wanted to interview immediately, as I had give the decision to the other company. So, tickets were booked urgently and within 2 days, I went back to Seattle. This time, I was not as much upbeat as I was last time.

Rule No. 3: Know what you like and dislike and we need not cheat ourselves on that. If stick to what you like, the doors of opportunity will open eventually.

I'm not goin 2 explain the interview process in much of detail. Its goin to be a separate post. But, this time the interview process were different. In general, it was more like kicking my ass. The interviews were deliberately pressurising.

The first interview needed me to explain clearly why I'm choosing distributed system rather than anything else. Second one, asked me why I'm choosing Software Designer position, though my interests suited me the Program Manager position. I argued that I'm not experienced enough to handle the post of a Program Manager, rightaway and eventually would like to become one. Third interview pressurised me on my team skills . Fourth one, with the development manager (who was the same person who interviewed me first, at my campus) I was asked about my research interests and why I wanted to get into Microsoft. The last interview, with the project manager was even more pressurizing. He told me all my negative reviews from the all the previous interviews. He told me that I might not be a good team player, I didnt listen to the interviewers, I made my problems harder.... I was smiling at him, as he said I think you have the abilities to become a computer scientist. This final interview gave me enormous confidence and a liking to work under such a person. I decided that I'm not goin 2 do a PhD for now, then and there, and to make my decision easier CMU sent a rejection in that same evening.

I appeared more confident, because interview by Product Manager at the end, is a positive sign. I told my recruiter that I wanted the result within the next 24 hours and true the word. She had it ready next day. The next morning, I was too late for the flight -- 50 min before the flight, I was at my hotel 30 min away from the airport. So, when I stopped over at Detroit, in the evening, I called her up and she gave me the good news. I GOT THROUGH.... Now, remaining is negotiation. I said, since I was at the airport, I would negotiate the offer the next day.

The next day (Wed, 1 March) I set up the time for negotiation. The package details have to be strictly confidential, by agreements, so I cant reveal any of that. The recruiter went in great detail in explaining all the benefits, including shares and relocation. I was not extremely satisfied with the base-salary, since the other company's salary was equally good. But, over the course of the week, the negotiation went well and I was convinced of the process and finally accepted it on 6th March. It was a great feeling... Now over to the legal processes...

Collected links about me

Sunday, February 12, 2006

An Interview with Microsoft

On Feb 10, 2006 I had my interview with Microsoft for the position of Software Design Engineer (SDE). I submitted my resume when they came to my campus (Univ. of Maryland, Baltimore County) last September and had an interview with them in October and got the on-site interview call. I went to interview totally unprepared, not knowing what to expect. People told me about famous puzzles and linked list questions that they usually ask. I was lazy and didnt prepare much. I just read a bit of "Programming Interviews Exposed" and did a few problems from the net. I also went through the various data structures from wikipedia.

Read more about preaparing for the interviews

Microsft takes due care of the intervieews. They book the flights, give 3days/2 nights at Marriot, pay for all your taxi and food expenses and make sure that you are totally comfortable with the process. I paid for the $50 for my cab from Seattle airport to Bellevue (where my hotel was) and the drivers there know well about Microsoft's interview process. I spent my evening of the first day, blogging, and at night went to a nearby Indian restaurant (near Bellevue there are a lot of Asian restaurants, including Taj Palace). It is highly advisable to spend the day before interview, in a less tensed fashion and I had a long sleep.

On the day of the interview, I went fully dressed (I counted the number of people wearing the suit, on the entire campus and still didnt get the count cross 5) to the Building 19 (the recruiting center for the Redmond Campus) at around 10am for the 10.30 interview. I registered at the front lobby and had a casual chat with other interviewees (around 100 interviewees come everyday). The place was bustling and at around 10.50 am (they are not famous for their punctuality) my recruiter met me. She explained me the entire process, and had a general interview for 30 minutes, where she asked me about the reason for liking Computer Science, reason for choosing to Microsoft, a major project done recently, interesting courses taken recently and other aspects of academics. She also asked me about other competing offers that I have and noted down other important aspects related to HR (like candidate's availability, future interests etc.). After that, she gave me the details of the teams that I'll be interviewing with (I was to interview with Security group and Subscription group) and indicated that there might be around 4-6 interviews on that day.

At around 11.30, they shuttled me to the office of Security group (I think building 25) and there I informed my arrival to the receptionist and a team lead had come to interview me. He took me to his office and had a hour long interview. Like all other interviewers on that day, he asked me about the reason for choosing Microsoft and had me explain about the distributed file systems project that I did recently. Then, he gave me a programming question and asked me to code the solution on the white board.

1. The question was: Finding maximum subsequence in an array of integers (containing positive and negative numbers).

The question is a standard question in many algorthmic courses and though I came across the problem, earlier, I didnt have the most efficient solution. I gave the O(n^2) overlapping window solution and gave an indication of the O(n) solution. He was moderately satisfied and gave the second question, which was a tougher design question.

2 A disk is partioned into two hemispheres colored in black and white and the disk is rotating.By appropriate positioning of sensors (A sensor can read the disk near it as black or white) we need to find the direction of the motion of the disk.

The problem was deceptive and I rushed into the solution, later realizing that the problem was not as simple as I thought it to be. It was an interesting design question and we had a brief talk about designing the algorithm. At the end of the interview, I knew I didnt have the best of the starts, but still it didnt go bad either and I hoped to catch up in the next interviews.

After this interview, there were confusions in their camp (few interviewers didnt turn up on that day) and the team lead found an alternative and the replacement guy reluctantly started interviewing. He was having problems with his system and didnt enjoy much of the intrusion. We started to get moving with the interview, when 10 minutes into the interview, the team lead found that the recruiter already made a replacement and he apologized for the confusion and lead me to another interviewer. He was a nice, young guy and after the 2 usual questions, (mentioned earlier) he gave me two more programming questions, after taking me for a lunch interview.

In the lunch, he asked generally about my preferences in working (client side/server side), team preferences and area preferences and we had a nice discussion about my career goals etc. After that he asked 2 programming questions in the office.

3 A sorted array has a number of elements repeated in it. I have to take this array and without using any extra memory, do in place copying to compact the array, so the resulting array would not have duplicates.

It was easier among the questions that I had in that day. I had my solution with two pointers - one to move with every unique item -p and other one moving for each item in the original array -i. Whenver a new item is encounterd by the i pointer, the data is copied on to the location of the p pointer and it is moved one step. The solution was cleaner and the interviewer was satisfied.

4 Given an n-ary tree represented as a list of items, containing a node and its parent, construct the n-nary tree from it.

I gave a recursive solution for this and kept reading from the list continously a node and its parent and moving to the node's parent and so on. I used a hash table to hash to the location of a node encountered in the list. Again the interviewer seemed to get pleased.

After the interview, I was waiting in the lobby for 20 minutes before they found a guy from MSN Messenger to interview me. I went to his office in Redwest campus, and he asked about the challenges that I faced in the distributed systems project and gave me a coding question:

5 Given 2 linked lists, merge them by alternating the elements on the two lists. If one of them is emty, join all the elements of the other list.

It was not pretty hard, but I did a few mistakes with the pointer. At the end I was able to give the solution, but the interview was not entirely satisfactory.

After this, I moved to Building 115 (I might not be exact, here) and I was to interview with the Subscription services group. One senior gentleman there, gave another coding question:

6 Given two nodes on a binary tree, find the smallest common ancestor. If the nodes are children of the same node, then the parent is least common ancestor, of the nodes are related by their grandparents, it is answer or if one node is the ancestor of another, it itself is the answer and so on.

My solution involved, building a new binary tree, with parent pointers and height information stored on every node. Then, the solution is very simple. Find the nodes in the binary tree, make both the nodes come to same level, by moving a lower node along its parents and till both the nodes have the same parent, continue moving both the nodes to their parents.

The solution is O(log n), though the other solution without involving parent pointers and height information (done recursively on the original tree) might take O(n). However, building the new tree takes O(n) and find step, if done by hash tables takes O(1), else can take O(n). The solution surprised the interviewer, and after a long look, he accepted the solution.

The last interview of the day was the best of the day. The interviewer was very good and he asked me on coding a simple board game.

7 In the board game battleships there are 1-d ships placed on the board and an enemy ship can be shot at. If we shoot at a position where a part of the ship is thee, it is counted as a hit and if he a shot at all the positions of the ship spread across the board, it is counted as a sunk, else it is taken as a miss. Construct data structures for representing the board and ships and write a function that takes a position as parameter and returns the result as miss, hit or sunk.

After changing my design for 2-3 times, I finally came up with a solution, where the ships are represented by an array, where each element stores the number of remaining parts of the ship. The board is a 2D array storing the refrences to the ship that a position contains, else an invalid value to indicate the absence of a ship. If the position shows invalid reference then I return a miss, else I goto the reference and decrement the ship's part count and if the part count is nil, I return sunk, else I returned hit.

The solution impressed the interviewer and asked me in detail, about group preferences and work styles etc. At around 6.30 the 8 hour interview 'ordeal' ended and I went back to my recruiter. She had her final comments and at 8 pm I returned back.

Looking back, it was a great day starting with a beautiful sun-shine and a hitch-free day. The interviewers were understanding and some of their design questions were challenging. Their in-depth questions about my distributed file systems project was intriguing and I liked the overall process.

Let me wait for few more days for the result!!!!

Wednesday, February 08, 2006

Tuesday, December 20, 2005

Recap of new things in 2005

  1. Taught class (lab course) for undergrads for ulmost an entire semester and got gud feedback
  2. Attended many interviews for big companies and worked for the first time in a company, in summer
  3. Performed some gud research and wrote a decent paper and got it published in AAMAS workshop
  4. Finished off the main courses in MS, with decent standing
  5. Got more of economic freedom
  6. Places Visited: Coolfront (west virginia), Pittsburgh, Atlantic City, Brussels, Antwerp (Belgium), Amsterdam, Utrecht (Netherlands), New York (to come)

What I did in 2005

Well... 2005 was indeed a great year for me, though not as great as 2003. Probably, this was the year I was expected to work, the most. I never had so many night-outs, so many times staring on the computer screens and bits of papers. I got used to sleeping at 2-3 am in the night and waking up at 9-10 am in the morning. Life was hard and I had to do things differently, than I was used to making in the first 21 years of my life.

Let me recap on few things I did this year ---

Jan - I spent almost the entire month on my research on Peacekeeping robots. I studied a lot about defence operations, robotics, swarm intelligence and multi-agent systems. I programmed a bit on Ant-Colony Optimization and got gud results for TSP. I read abt swarm intelligence in a couple of books and found it impressive.

Feb - Spend time on developing my research idea and coding the stuff. Spent a bit of time on learning Breve -a simulator for robotics, for my Advanced Robotics course. TA work for 201 took a big chunk of my time for FEb-March-Apr-May.

March - Went to coolfront - a resort in West Virginia and had a weekend of fun. Wrote my research paper and submitted to AAMAS workshop and the initial plan of 3 papers were cut to just 1. Did a bit of work for my Multiagents course. Spent sometime preparing for the Microsoft interview (which eventually got cancelled due to snow).

April - Did work on polishing my paper for the Basic Research Methods class. Presented the work in Graduate Research Conference and won 1st prize. Did some more work for my courses.

May - Applied to Cougaar and after a bit of preparation, got through it. Spent the last few days watching few movies, arranging my accomodation and stuff at virginia and booking for the Europe trip.

June - Went in Cougaar, spending most of my time learnign Java and Swing. I learnt some crucial lessons on design, over there.

July - Some more of the work at Cougaar. Went to the AAAI Summer school at Pittsburgh and had a nice presentation at CMU. I was impressed with the robotics institute. Went on to Amsterdam and Beligium for AAMAS conference and it was awesome.

August - Bit more of work at Cougaar. Spent time seeing the fight between developers and management at Cougaar. Spent time on thinking for my paper. Went to meet a research at Brookings.

September - Spent time on coding my research project. Started my applications and started working for my SOP. Spend time on working for selecting a topic for Algost project and did basic design for OS project.

October - Time went for preparing for OS exams, coding OS project, Algost Project/Homeworks and Exam. Did my SOP and prepared for Microsoft interview.

November - Coded up for Algos Project, wrote draft reports, wrote mid-terms, interviewed with Amazon.

December - Finished the exams, Algos and OS projects and having leisure time

Exams are over! Chill

The exams are over at last. Things are chilling down. This semester had been such a tough time for me, I wanted the semester to end, badly. I hope I'll be getting gud grades to take good memories from this semester. I've some grading stuff and some research stuff to finish. After that, I'll be having a great time in India.