interview

Of all the blockers of dynamism, I have known comfort zone to be the deadliest. For it gives us a false hope that the place and position we are in, is perfect. A poison for growth mindset I would say.
Once we stay somewhere for 5+ years, it becomes a home for us. Home is hard to leave. For it renders us with a feeling of fulfillment.

Being a creature of habit, my behavior lately exhibits every sign of a person in comfort zone. I have never been quite fond of change. I am staying in the same flat for the last five years, driving the same car to work through the same route. Every person at the restaurant I visit knows my taste buds and all I have to say is, “The same cuisine I order always, please”. Microsoft has been my home for close to six years now.

This has greatly distanced me from the real world. Silent contemplation in lonely nights on these aspects renders me anxious. The Tech world is changing and so are the requirements. Not having slightest of clue on how the water tastes outside and where I stand, I said yes when an opportunity knocked my door tenth time since my college days.

When it all started?

It was a lazy friday noon. Winds blew hot, burning skin of people it touched. Sitting idle, my eyes alighted on a mail from a recruiter at the company. As usual, I responded that I was content with my work and things were going well for me. She asked me to just have a phone conversation and if things looked fascinating, we could move forward.
I said, “Yes”. After all, what harm could one phone call have done. Must I say, she was very convincing.

1 Informational (35 minutes) + 1 Screening (20 minutes) + 2 Skype (45 minutes each) + 5 F2F onsite rounds

Informational

This was supposed to be just a phone call until it became really interesting. Things like fantastic opportunities, work culture, smart engineers and location preferences were presented. In exchange, I talked about the work I have been doing at Microsoft.

Screening

Being no different from screening rounds of other companies, the focus was mainly to judge if my skills are worth time of their great engineers. Call it a first level of check.
Basic questions to test Algorithmic + Coding + Mathematical skills — Quick sort, Merge sort, Hashing, Powers of 2, Tree traversals etc.
I got a call next day that they can move to the interview process.

Video call – Round #1

The first DP problem on the face gave me sweats I find myself unable to pen in words even today. A simple problem, anyone with decent practice could have solved in 5 minutes.

Count number of ways to divide an array of n balls in k non-empty subsets.

After few failed attempts, I came up with a working recurrence relation:
Number of ways would be:
Put (k – 1) balls in n sunsets and remaining one in any of n sunsets +
Put (k – 1) balls in (n – 1) subsets and remaining one in the empty subset
f(n, k) = f(n, k – 1) * kC1 + f(n – 1, k – 1)

I didn’t do very well in this round as my first few formulae didn’t work and I took few hints to come up with the right solution. However, I was able to write the working code very fast, which turned to my advantage.
The feedback was shared in 2 hours that I exhibited good potential. My coding was fast. But I needed to practice more. Since it was an onsite opportunity, they asked for another round.

Video call – Round #2

A fairly simple problem to find a missing character in two words. They kept on tweaking the problem, adding more constraints and complexity along the way.
I wrote code for three approaches.

Onsite (Finally), phew…

Emirates

I wasn’t quite sure if I would be able to make to onsite. I was disappointed of my performance and I needed a break to get over frustration. A visit to hometown seemed to be the most logical decision, which I later regretted after wasting thousands of bucks on flight tickets.
One lazy Friday evening in office, when I was doing some code review, my recruiter informed me over call that they can move ahead with the onsite process. I was wildly surprised. She mentioned that she didn’t want me to spend the weekend in worry and hence, shared the happy news as soon as she could.

They booked my flight and hotel tickets. We talked for several days about my travel arrangements, preparation and any queries I had in mind.

The D day

Time flies. The D day arrived sooner than I had anticipated. I landed in the evening, checked in to the hotel, had a lavish dinner and slept like a baby to prep myself for the next big day.

Round #1

In order to avoid last minute rush, especially in a place I had never been before, I arrived an hour early. The lobby was decor’ed with statues of slim geeks in skinny jeans holding mobile phones in their hands, emphasizing the direction the current generation is going and the core focus of the company. Beside me was a digital display with an array of tiles which flipped every couple of seconds showcasing that the company cares about Diversity and Inclusion.
There wasn’t a slightest of fear on what’s gonna happen next. Instead my mind was puzzled with how the tiles were working. Ah! So they have multiple threads delivering the content to the tiles sitting in UI. The threads may never be sitting idle as the text appearing the those tiles as keyboard inputs. Or may be this is an illusion of parallelism as the context switch is so fast.

A guy in his early 30s, wearing a broad smile and a pony hanging on his back broke my reverie.
“Are you Aashish?”, his voice was as fresh as morning dew.
Having done some research about him on LinkedIn, “Yes”, I knew who I was talking to.
“Hi! I am sorry I’m late by 30 seconds. I took a wrong turn. Hope you didn’t have to wait long.”, he smiled, “Let us walk to the interview room, shall we?”. There was a passion in his tone of voice. A passion that I have seen in very few people I have interacted with in my life so far.

We walked in a small meeting room. A white board was walled on the left, a table for 4 positioned in the center and a laptop connected to a projector on the right.
We spent the first few minutes knowing about his background, his work and his team.
“You’ve been given two words A and B. How many minimum concatenations of word A is needed to form subsequence B?”, he explained the problem with one example.
Despite solving few problems on subsequences in the past, I had never heard of this pattern of problem before. It wasn’t a surprise. The company was wildly famous for asking new problems. And if not, they would tweak it to the extent it becomes new.

I started with asking questions to understand the scope of the problem.
“Will the words contain only ASCII characters How long can be the words? Can they fit in one machine? What do we return if no concatenation can make a desired subsequence? etc”
The first approach that popped up my mind was to put all characters of word A in a set and check if it contains every character from word B. Once it’s certain that a solution exists, I played with two pointers pointing to words A and B and wrapping around pointer to word A to the beginning when we fall short of characters. The minimum concatenation is the count of wrapping done.
The time complexity of this solution is O(lenA x lenB).

While the above approach worked fine, the time complexity wasn’t great. I proposed another solution to create a map of characters to their indices (unordered_map<char, list<int>>) in word A. Now instead of linearly looking for a character from word B in A, a binary search in the map would reduce the time complexity to logA. One key point to take care was to make sure we are picking the next index from where we left of and increment the count of minimum concatenation at right time. upper_bound method worked like a charm. The time complexity reduced to O(log(lenA) x lenB).

“Sounds great. Do you want to code it?”, he seemed fine with the approach.
The code was pretty straight forward to write. He took a look at the implementation, went through various corner cases and finally said, “Great, we have 5 more minutes. If you have any question about the company, the team or anything else, fire at me.”
The company being a leader in Scalability, I was curious to know how they dealt with various challenges they faced and learning from it. Work-life balance, company culture, healthy environment, quality of work were other topics we discussed. He wished me good luck for the next round and left.

Round #2

Ralf isn’t a Computer Scientist. But his quote holds true for every aspect of engineering I know of. The beauty of the world lies in design. But we are not here to talk about how Lamborghini design is better than its rivals or why Tesla is winning over the world. Well, not today.

System Design has been a hype for quite long and for all the right reasons. It’s the core of every business & technical strategy and the success behind every company.

I only got time to gulp some water before a guy with notebook in his hand walked in. Bald, mature & experienced look, he seemed like the kind of person people would want to go for seeking expert opinions.
“So how did your first round go?”, he broke the ice.
“It was great”, I said cheerfully.
“Well, that’s rare here. I usually hear responses like, it was okay or I don’t know.”, he said, “Hope it went as good as you said”, he further added.
“Are you aware of what a System Design is.”, he asked, “Have you ever used FaceBook or Yelp checkin system? I want you to design that.”, he continued without waiting for my answer. Guess it was a rhetorical question.
“Before we start, let me tell you that I would most probably not ask you to write any code. So feel free to fire all complex and advanced data Structures that pop in your mind. “

As all design discussions start, I began with understanding the scope of the system. Users would tap on the Add location and it would show the list of 10 nearest location to choose from. The check in status would then be saved on the server. Delivering the status to user’s friends was out of scope. It’s good to have high availability and low latency for good user experience in a system like this. Availability can have an edge over Consistency. If a user doesn’t see a newly added location for sometime, it should be okay.
He wanted me to come up with numbers. It was important, especially when you design something of FB scale. How many people, how many daily active users, how many locations, the size of database, number of machines, network bandwidth etc.
So, there are 2.2 billion users. Let’s say we have 70% (1.5 billion) DAU and 30% of them checkin at least once a day. There can be hot users as well. Let’s worry about them later.
The locations can be anything from coffee shops to hospitals to parks to big shopping complexes. All locations can be stored in a database.
“How many locations do you think there can be?”, he chimed in.
Umm, there are around ‘X’ places in the world and each place can have an average of ‘Y’ locations…
“Don’t you think that it would make more sense to calculate the number of locations based on the world population rather than geographical area?”
Ah, yes! The world population is 7 billion and there can be one location on an average per hundred people. We agreed upon 700 millions locations.
“Which type of database will you use to store the locations? How many machines do you need?”
I calculated the size of data to deal with and explained sharding can be done over LocationId in NoSQL. Calculation of network bandwidth with that data and machine config I was given (128 Gig, Octa core) gave an idea on the number of machines needed. Performance numbers talked by Jeff Dean was of great help.
When the user taps on the search location, latitude and longitude will be send to the server…
“Okay! How would you fetch the 10 nearest locations of a user?”
Well, locations can be added to a Graph in memory and…
“What if there is no node in Graph corresponding to user location? What if a user is standing in the middle of a street?”
Umm… The whole structure can be seen as a 2D plane with four quadrants. Locations can be read from DB and organized in memory in Quad tree. Nodes at each level would be connected through a Linked List. Looking for nearest location would boil down to Quad-nary search based on user location where we discard three children at each level as we narrow down the search. If a node doesn’t have enough locations, we would check its siblings/cousins, maintain a max heap of size 10 and return the result.
“Can you improve it further?”
I think we can use K Dimensional tree as well. Unlike Quad tree, we don’t need to fork exactly in the middle.
“So how does the whole flow look like?”
I drew a high level design on the white board where the user location is sent from client to an Application server. The App server then passes the location to a NearestLocationFinder engine. Result is passed back to user. User checks in. The checkin data is sent to another Application server. Since the checkin data can contain huge bits like images and videos, the App server would put the checkin data in a Message Queue. We would spin off few workers to pick entries from Message Queue and write to a Database. We would need two Load Balancers. One for each Application server.

We further discussed on dealing with SPOF (Single Point of Failure) through replica, pros & cons of Master – Master and Master – Slave models. A caching mechanism in place (something like Memcached) for low latency to display user checkin history.

Forty minutes just flew. As usual, the interview ended up with me asking few questions around Scalability.
Having realized many things that can go wrong in a design of humongous scale, “How often do you calculate these numbers? Are they very accurate?”, I asked in wonder.
“We do work with numbers. But they aren’t always correct. It takes a lot of experience”, he replied, “Good luck with your next interview”, and he left.

Round #3

The interviews so far had been a breeze. Discussing interesting problems is always fascinating and mind boggling.
In no time, the third interviewer walked in, introduced himself, the team he was working on and other cool stuffs.
A simple problem on expression evaluation, except it had a twist on how Compilers work. State Automata quickly struck my mind like a bolt of lightning. I drew few states to parse and switch between the states based on input. He mostly emphasized on why I used Data Structure ‘X’ over ‘Y’. Coding was simple and I had to use map and Stack. That’s the beauty of state machine. Once there is a working diagram, coding doesn’t take much efforts.

“Let’s try to break the code”, he smiled while going through the code.
I looked for every possible corner case that crossed my mind and each one of them seemed to be covered.
“What if one of the numbers is 0?”, he looked at me.
“Damn!”
In the heat of discussing big things, I missed to handle critical divide by zero error. Albeit I fixed it quickly, I think the harm was done.

Lunch break

A person with no expression on his face was waiting outside to take me to lunch. He looked very well acquainted with the environment and the work place, probably because of spending many years there. We quickly rushed to the cafeteria. An array of delicious cuisines, varying from Indian to Italian to Mediterranean to every other I could think of, accompanied with drinks and deserts. I wish it weren’t an interview day and I were there with an empty belly & mind void of any thought.
While taking a stroll in the beautiful campus post lunch, we crossed meditation room, music hall decor’ed with Grand Piano & other instruments, very strange shaped offices fostering creativity. Filled with awe, we entered a room that looked like forest. Trees peeking from the left, tiny waterfall gliding softly in the corner, birds chirping over the branches. In the center was lying a young girl doing something on her laptop. I was amazed and blown away.

Round #4

A glimpse of the amazing campus pushed me to give my best. I met another cool guy who asked a problem on finding nearest favorite city of a user.
“I am not, in particular, looking for a solution. I am looking for ideas”, he added.

I asked few questions to understand the scale at play — How many cities can there be? Can we fit all of them in one machine?
I threw some Algorithm (which I don’t remember) in the beginning. While I was explaining on the board, a variation of Dijkshtra’s popped up my mind which seemed to work well. He was fine with it. I also added some preprocessing to optimize the Algorithm as the cities don’t change very frequently. Writing code took another 5 minutes.
“How often would you preprocess the data?”,he asked.
In the times when there is less load on the server, like once every 24 hours.
“Don’t you think it will hamper accuracy?”.
Yes, it’ll. But not very far. It will help users get data in reasonable time window. User experience matters. The error in system exists even today. Maps wasn’t able to detect the new U turn for weeks.

I was happy and content until he added the twist.
“How would you improve it?”, he smiled.
This was the most optimal solution that crossed my mind there. Luckily while skimming through my FB newsfeed few months back, I watched a video on comparison of Djikshtra’s and heuristics based A* Algorithm.
“We can use some heuristics to scope the search instead of going haywire. I remember reading about A* Algorithm in my graduation days.”, I felt relaxed.
I could see him smiling. It looked like this was what he was looking for.
So if the direction of favorite city of the user lies South, we can bail out the Algo and not explore the North. There can be a possibility that we have a rocky road in the direction we are looking and there is a faster way if we take the opposite direction and use a newly constructed flyover.
“This is a good practical solution. Not everytime we want the perfect accurate result. There is a careful balance between accuracy and latency”, he smiled.
We discussed few other practical approaches, few things on and collection of data and ML.

The best interview of the day, I could feel it from the conversation with him. He was widely impressed.
“So tell me about the things you do at Microsoft. I went through your resume and it was pretty impressive”, he said.
“Microsoft is a great company. Smart people, awesome culture. To be honest, I don’t find anything bad there. If I had, I won’t have stayed 5 years there”, I responded. We discussed some of the work I was doing without violating any NDA.

Round #5 — The final battle

There is a saying, “All is well that ends well”.
No matter what I do, I can’t seem to annihilate those 45 minutes of my life. Rooted deep inside the neurons of my brain, it hurts even today and makes me wonder how I could have done it any better.

DP has always been my nightmare. No matter how many problems I solve, a new one still surprises me.
I was greeted by an Indian guy in the last round. Unlike other interviewers, he, without any talk, rushed to a problem which had some made up story on Cargo, men and packages.
I recognized it in an instant. It was a complex version of famous Painter Partition problem. A fairly difficult problem for people who haven’t practiced DP well. I gave a brute force exponential solution and explained on the white board followed by for-for-for DP solution. I, then with some example, pictured on the board how the table would be filled. He seemed fine with the approach and asked to code.
That’s where things went south. A recursive solution was easier and straight forward. I could have just written the brute force solution I had explained in the beginning and stored the result in a table to optimize. It was a win-win situation. But No! I had to cripple myself to death.

Beaming with confidence, I started writing for-for-for iterative solution and explaining what each line of code was supposed to do along the way. I made critical off-by-one error and another error in calculation where a column was being added the way I didn’t want to. I also felt irritated that even after explaining Algo twice — Once on the white board, later while writing code, he was wasting time in asking things I had already explained. This didn’t happen in any other round and I would never expect it from someone working at a company of that stature.
I, however was able to correct one of the errors and was close to fixing second when he asked me to write the recursion solution. Something I could have done in the first place without suffering any agony.
“Let bygones be bygones”, I sighed, took a deep breath and wrote the perfect working solution in single attempt, all within 3 minutes. I just needed another minute to store the result in a table. But the time was over. If only he had cooperated more, I had performed better.
And as I had guessed, he, without any talk, took me out of the building.

If I do an assessment of my performance, I did good in first, not sure about second, okay in third, great in fourth and not good in fifth. Interview process was a breeze and as smooth as butter. I was pretty impressed with how well organized everything was.

Please feel free to ask any question, except the name of the company 🙂

You may also like:

Copyright © 2019, Aashish Barnwal,  All rights reserved.

Read more

I am a CSE Graduate from KIIT University. I joined Microsoft straight out of college. Usually, Microsoft doesn’t visit there, but that year I got lucky.

2 written tests + 3 F2F technical interviews + 1 Skype technical interview

 

Written test 1 (Objective), 30 minutes

First written test was conducted by some third party company. It consisted of 15 objective questions from C, Sorting, Data Structures, Big O, compiler and state machine. We were given 30 minutes. Cut off was 12 out of 15 questions. 77 out of 400 students made it.

Written test 2 (Coding), 60 minutes

Three problems to be solved in 60 minutes with no use of compiler. One problem on Linked List, second on heap and third on array. I coded all problems from scratch including main method. I also wrote flexible methods that could work on any kind of inputs (instead of deleting nodes from 4 to 6, it would delete nodes between ‘M’ and ‘N’ ) and handle all corner cases. The result was announced after 20 days. 30 out of 77 made it.

F2F Interview #1, 60 minutes

We were interviewed in groups of 6. Each one of us in a group was given same problem to solve. I couldn’t code the perfect solution in an hour. All I had discussed 6 different ways to solve the problem. I was afraid that I might be rejected in first round. The interview lasted for 60 minutes.

14 out of 30 were selected.

Continue reading My interview experience at Microsoft

Read more

My contribution on Quora on cracking technical interviews:

 

  1. What should I do in the next 6 months to get into a company like Amazon/Google?
  2. How do I go about preparing for interviews on GeeksforGeeks?
  3. What are the top 20 websites for interview preparation?
  4. What are some useful websites for a CS student?
  5. How does one become good at problem solving?
  6. Career Cup or GeeksforGeeks?
  7. Should I do competitive programming or learn GeeksforGeeks, from a placement point of view?
  8. Which is the best book to start learning algorithms?
  9. Which books should I refer for data structures in C?
  10. I suck in competitive programming but I wish to make a mark there. I’m improving my skills by practicing on GeeksforGeeks. Is this the right approach?
  11. Should I learn algorithms and data structures in my vacation or learn any other thing? See details.
  12. How many academic projects should be mentioned in the resume while appearing for big companies like Amazon, MS, Adobe by a fresher?
  13. What are your reviews of Data structures and Algorithm made easy by Narasimha Karumanchi? Should it be used and when?
  14. Is it neccessary to put subjects of interest in our resume, we dont get good job at big tech companies if not added?
  15. Do we have to mention our Data structures skills in our resume in subjects of interest part ?
  16. Does the bloggers get paid when they write article on geeksforgeeks?
  17. How can one contribute to GeeksforGeeks and become one of the moderators?
  18. Studying Algorithms and data structures cover similar topics in c,c++ and Java languages?
  19. What is the difference between dynamic programming and recursion?
  20. What is easiest approach to tackle Dynamic programming problems?
  21. How should I explain dynamic programming to a 4-year-old?

Copyright © 2017, Aashish Barnwal,  All rights reserved.

Read more

My interview with GeeksforGeeks: Geek on the top – Aashish Barnwal

My contribution on GeeksforGeeks over the years:

  1. How to prepare for top MNCs?
  2. Implementing Iterator pattern of a single Linked List
  3. Curiously recurring template pattern (CRTP)
  4. Opaque pointer
  5. Factory design pattern
  6. K Dimensional Tree | Set 1 (Search and Insert)
  7. Design an efficient data structure for given operations
  8. Ternary Search Tree
  9. Print unique rows in a given boolean matrix
  10. Implement LRU Cache
  11. Sort numbers stored on different machines
  12. Find the k most frequent words from a file
  13. Given a sequence of words, print all anagrams together | Set 1
  14. Given a sequence of words, print all anagrams together | Set 2
  15. Generate integer from 1 to 7 with equal probability
  16. Graph and its representations
  17. Median of two sorted arrays of different sizes
  18. Iterative Quick Sort
  19. Magic Square
  20. Comparator function of qsort() in C
  21. Copy elision in C++
  22. Playing with Destructors in C++
  23. Casting operators in C++ | Set 1 (const_cast)
  24. DFA based division
  25. Counting Sort
  26. Space and time efficient Binomial Coefficient
  27. Efficient program to calculate e^x
  28. Greedy Algorithms | Set 2 (Kruskal’s Minimum Spanning Tree Algorithm)
  29. Greedy Algorithms | Set 3 (Huffman Coding) – GeeksforGeeks
  30. Greedy Algorithms | Set 4 (Efficient Huffman Coding for Sorted Input)
  31. Greedy Algorithms | Set 6 (Prim’s MST for Adjacency List Representation)
  32. Dynamic Programming | Set 27 (Maximum sum rectangle in a 2D matrix)
  33. Dynamic Programming | Set 28 (Minimum insertions to form a palindrome)
  34. Dynamic Programming | Set 30 (Dice Throw)
  35. Dynamic Programming | Set 31 (Optimal Strategy for a Game)
  36. Dynamic Programming | Set 34 (Assembly Line Scheduling)
  37. Find minimum elements after considering all possible transformations – GeeksforGeeks
  38. Check whether a given graph is Bipartite or not
  39. Maximum of all subarrays of size k (Added a O(n) method)
  40. Linked complete binary tree & its creation
  41. Print all permutations in sorted (lexicographic) order
  42. Lexicographic rank of a string
  43. Union-Find Algorithm | Set 1 (Detect Cycle in a an Undirected Graph)
  44. Measure one litre using two vessels and infinite water supply
  45. Random number generator in arbitrary probability distribution fashion
  46. Iterative Postorder Traversal | Set 1 (Using Two Stacks)
  47. Iterative Postorder Traversal | Set 2 (Using One Stack)
  48. Boundary Traversal of binary tree
  49. An in-place algorithm for String Transformation
  50. Morris traversal for Preorder
  51. Construct Full Binary Tree from given preorder and postorder traversals
  52. Two nodes of a BST are swapped, correct the BST
  53. Check if each internal node of a BST has exactly one child
  54. Largest subarray with equal number of 0s and 1s
  55. Check if a number is Palindrome
  56. Given a number, find the next smallest palindrome
  57. Construct BST from given preorder traversal | Set 1
  58. Construct BST from given preorder traversal | Set 2
  59. Flattening a Linked List
  60. Find the largest multiple of 3
  61. Count numbers that don’t contain 3
  62. Check divisibility by 7
  63. To find sum of two numbers without using any operator
  64. Find a pair with the given difference
  65. Add two numbers represented by linked lists | Set 2
  66. Longest Palindromic Substring | Set 1
  67. Longest Palindromic Substring | Set 2
  68. Count the number of possible triangles
  69. Find the number of islands
  70. Pascal’s Triangle
  71. Stack | Set 1 (Introduction)
  72. Heap Sort

Mentions:

  1. Find a pair with the given difference
  2. Sliding Window Maximum (Maximum of all subarrays of size k)
Copyright © 2017, Aashish Barnwal,  All rights reserved.
Read more

This post was residing in my draft for quite long. I finally got some time out of my busy schedule to refine it.

The first question quickly pops up on why am I writing this post at all. There are already tens of hundreds of similar compilations on web that talks about this.

Well, following reasons compelled me to do so:

  1. Being a GFG moderator, I’ve been getting many requests from readers through various social media (FB, LinkedIn, Quora, InstaGuide) and various mail clients asking for mentorship and guidance on how to prepare for top MNCs like Microsoft, Amazon, Google etc
  2. Having gone through similar journey and witnessing many of my friends succeeding, I feel knowledge should be shared. My experience might be useful for newer generations who happen to chase the same goal as once was mine

Please note that this article is purely a reflection of my learnings, what I followed through the years and my experience. This is NOT the only way to improvise on what is needed – your coding skills, strengthening DS & Algorithms and boosting problem solving skills. I repeat, this is NOT the only way. There are things I couldn’t follow because of time constraints or didn’t follow because I was just not aware. Please comment if I missed anything which is worth mentioning here.

Language

Language has been a topic of debate between aspirants since years. It’s always good to master one language, knowing ins and out of it rather than hopping from one language to other. Why?  Because sometimes it might happen to you that when you get a problem, you start wondering what language you should choose and your focus is compromised. When you should really concentrate on problem solving, Implementation comes later. Then while you are coding, you plan to change the language in between. This won’t serve you good in interviews. If you’re able to solve a problem in language ‘X’, eventually you will also solve it in language ‘Y’. Learning a new language is just a matter of time. A language might not be as widely used after 5 years as it is being used now. Your ability to solve a problem will what matter in the long run.

I usually switch between C and C++. If time is at its crunch, I prefer to use STL (standard library functions) instead of writing my own version of Linked List. If I want to develop a project, an android app for instance, I go for a managed language because it is easier. If I want to automate something to save my time, like replying and liking my birthday wishes, a python script is the saving grace. You got the point, right? Master one language and learn others as per requirements.

Data Structures and Algorithms

Data Structures and Algorithms is very important and serves as the backbone of problem solving.

For beginners, Fundamentals of Data Structures in C by Sahni Horowitz is good. After reading it, you should be able to understand basic Data Structures, how they are implemented and fewer examples where they can be used. Don’t expect to learn advanced DS through this. After your basic concepts are clear and you are comfortable implementing them in a language of your choice, you can work on learning algorithms and solving problems.

Many sites (including GeeksforGeeks) present problems in a very adhoc manner with no order of difficulty level. This makes things difficult for beginners because they don’t know the difficulty level of the problem they are attempting. Data Structures and Algorithms made easy by Narasimha Karumanchi is a good read after you are comfortable with the basics. It has pretty good collection of problems organized by difficulty level. Just make sure to try to solve problems on your own instead of rushing for the solution. Once you have a fair understanding of DS and have got some confidence in solving problems, jump to online portals and start solving problems from topic of your choice. GeeksforGeeks is good to start with.

For Algorithms, Introduction to Algorithms by Cormen is a must read.

Advanced Data Structures

Sometimes, basic DS don’t serve the purpose to solve problems and you need to know advanced DS. Day to day problems like implementing a prefix based search for a phone contact list to finding the dictionary word from a jumbled sequence of characters need special kind of DS. There are many of them – TST, Trie, Suffix tree, Suffix array, Fibonacci heap, Segment tree, Gap buffer, Rope, Skip list, K Dimensional tree and so on. While it is good to know the implementation of these DS, I would suggest to also know when to use one.

Problem solving

So you got a gun, understand how to use it, probably have used it before. If you are going to fight a war, you won’t like to rely upon your amateur experience. You would prefer to practice hard to save your ass. Now try to think it in perspective of problem solving. You know what DS are. But you also need to know when to use one. Welcome to the world of problem solving. You are given a problem and you are asked to solve it. That problem can be anything starting from a simple puzzle to implementing a user scenario. You must have noticed degree of connection feature in LinkedIn. How will you implement it? Does your approach take care of scalability? Will your code crumble when user base increases ten folds? This is the most important skill top MNCs usually look for. How do you approach a problem? How do  you divide it into modules? How do you solve each of them and then combine them?

Dynamic Programming

I separated out DP because it is one monster which is difficult to master upon. No matter how many problems did you solve in the past, a new DP problem can always surprise you. The more you will practice, higher the chances will be to find out patterns. Google is peculiar about DP. You should expect at least one DP problem per interview round  if you are preparing for Google. Practice DP section from:

Competitive Programming

Competitive Programming plays a very important role in boosting problem solving skills and ability to perform under time pressure. Do participate in various online portals like TopCoder, CodeChef, SPOJ. Here is a post on Getting started in sport of programming.

Design and testing

So you are good in DS and Algos. You are probably good in problem solving as well and you come up with different approaches with varying time and space complexity. The problem which you solve in Competitive Programming is well defined and has to work under an environment which nobody will probably use. What if you are asked to implement a user scenario. The problem statement is usually vague and you need to discuss a lot to resolve ambiguities. This is where design comes into picture. How will you design a redo-undo feature? What data structures will you use to store history in a web browser? How will you implement auto-complete feature in address bar? Let’s say Amazon wants to build a feature that would resume a video stored in cloud from any device. What data structures will you use? How will you scale up things? Does your design take care of concurrency issues? What about the performance? What if you and your girlfriend share the same cloud account and are trying to play the same video from different devices?

Now you have thought through the design well, have come up with different data structures to use with pros and cons in mind. While implementing, you must take care of corner cases. You must be aware about the integer overflow issue in Youtube video view count. While implementing, they never really thought that the view count can exceed what an integer variable can hold and BOOM, the view count cycled back to zero.

Before a feature goes live, it must be tested well. It is good to practice some test questions as well. How will you test a Insert image feature in MS Word? What about a cut-copy-paste feature? How will you test Temple Run game? Try to write all the possible test cases and how you are going to handle this in your code. Writing a robust code is very important. If you take care of these things at an earlier stage, you can avoid silly bugs (and boost your chances of getting selected in interviews).

What else?

Have a sound understanding of Operating System. The dinosaur book by Galvin is a good read. Know how networking works and have insights on DBMS.

Resume building

First impression is the best. Resume is the first thing that HR will use to decide whether to call you for interview or not. And they have got hundreds of them. So they will usually scan it for 20 seconds to 2 minutes. It should be clean, concise and elegant. Each word mentioned should worth the space it eats. The rule of thumb is if you have less than one year of experience, the size of resume should not exceed a page (with few exceptions).

Few points to note:

  • Maintain a header to fit info like name, email id, address and contact number
  • Mention level of expertise corresponding to each language. Example: Proficient in C and good at Java
  • If you are mentioning a project, write your key learning, impact in the team and . If this project is online (an app), don’t forget to include the link. This will show that you built something that is being used by people . Guess what, this is what companies do, building a product, stabilizing it as per user feedback, taking in new feature requests and so on.

Here are few useful tips from Gayle – What are common mistakes that applicants make when writing their resumes for tech companies?

How to apply for Microsoft?

I get many messages asking me for a favour to refer them. When I ask them how much comfortable they are with DS and Algos, they say good enough. Then I rephrase my question to how do they feel when they solve interview experiences at GeeksforGeeks. Either they haven’t heard of GeeksforGeeks or they never read. This is not a surprise. GeeksforGeeks is still growing. But when I ask them a problem on DS by tweaking already existing famous ones, all they say is they haven’t solved this problem before. Please do NOT do that. It’s one thing to yearn for something. But quite other to put efforts to make it a reality.

If you are not able to clear the interviews, you will have wait again for 6-12 months depending on the company policy before you can apply again. Now coming to the point,  you can apply for a position at Microsoft either through Careers page or through referral. Referral usually bumps chances of getting an interview call because your resume gets to the system through a person Microsoft trusts to be a good engineer. How do you ask for a referral? It’s simple. Forward your resume to someone you know working there. No one will say NO unless your resume is filled with something which doesn’t fit company requirements. Rule of thumb is we believe in solving problems and if you are good at it, we would love to see you here. Remember, everyone wants to work with a smart person. And this is usually true for any company, not just for Microsoft.

Do’s and Don’ts

  • Practice, practice and practice
  • Make a habit of writing clean and readable code (avoid variables names like i, j)
  • Make sure to handle all corner cases
  • Use pen and paper to practice code. In interviews you have NO access to a compiler
  • Don’t mug up the solutions. Try to solve on your own
  • Think of different ways of solving a problem and thoughts on why one should be preferred over the other

Resources

I have answered few questions related to interview preparation on Quora. You might find some content missing here in blog and it is intentional to avoid the duplication of efforts. Please read my technical answers here.

Resources (which I haven’t talked about):

  • Cracking the coding interview by Gayle Laakmann: A must read once before interviews. It covers aspects like what interviewers expect from you, how to deal with behavioral questions and few interesting problems. It will change your thoughts about design and test problems for good
  • GeeksforGeeks: A bible of problems (with well explained solutions). Make sure you do NOT rush for solutions. Try to solve problems on your own no matter how much time does it take. With time and honest practice, you should get better
  • CareerCup: A huge collection of problems. Though you can’t rely upon solutions, it provides a rich community for discussing problems. I found it good for discussing design problems
  • Project Euler: A heaven for mathematics lovers. You solve the problems using some formulas on paper and then write code to get the final solution. Solve at least 40 problems from this site.

You might like following write ups:

PS: This blog is published on GeeksforGeeks.

Good luck!

Copyright © 2016, Aashish Barnwal,  All rights reserved.

Read more
Bitnami