Cracking The Coding Interview

• Microsoft wants smart people Geeks. People who are passionate about technology.
• You'll have a short interview with a recruiter where he or she will give you a sample question. Your recruiter is usually there to prep you, and not to grill you on techni- cal questions. Be nice to your recruiter. Your recruiter can be your biggest advocate, even pushing to re-interview you if you stumbled on your first interview. They can fight for you to be hired - or not!
• During the day, you'll do four or five interviews, often with two different teams Unlike many companies.
• Depending on the team, interviewers may or may not share their feedback on you with the rest of the interview loop.
• When you complete your interviews with a team, you might speak with a hiring manager. If so, that’s a great sign! It likely means that you passed the interviews with a particular team. It’s now down to the hiring manager’s decision.
• You might get a decision that day, or it might be a week. After one week of no word from HR, send them a friendly email asking for a status update.

Definitely Prepare: “Why do you want to work for Microsoft?”

In this question, Microsoft wants to see that you’re passionate about technology. A great answer might be, “I’ve been using Microsoft software as long as I can re- member, and I'm really impressed at how Microsoft manages to create a product that is universally excellent. For example, I’ve been using Visual Studio recently to learn game programming, and it’s APIs are excellent.” Note how this shows a passion for technology!

• Amazon’s recruiting process usually begins with one or two phone screens in which you in- terview with a specific team. The engineer who interviews you will usually ask you to write simple code and read it aloud on the phone They will ask a broad set of questions to explore what areas of technology you’re familiar with.
• Next, you fly to Seattle for four or five interviews with one or two teams which have selected you based on your resume and phone interviews. You will have to code on a whiteboard, and some interviewers will stress other skills. Interviewers are each assigned a specific area to probe and may seem very different from each other.
• They can not see other feedback until they have submitted their own and they are discouraged from discussing it until the hiring meeting.
• Amazon’s “bar raiser” interviewer is charged with keeping the interview bar high. If one interview seems significantly harder and different, that’s most like- ly the bar raiser This person has both significant experience with interviews and veto power in the hiring decision.
• While Amazon’s recruiters are excellent at following up with candidates, occa- sionally there are delays. If you haven’t heard from Amazon within a week, we recommend a friendly email.

Definitely Prepare:

• Amazon is a web-based company, and that means they care about scale. Make sure you prepare for questions in “Large Scale.” You don’t need a background in distributed systems to answer these questions. See our recommendations in the System Design and Memory Limits Chapter.
• Additionally, Amazon tends to ask a lot of questions about object oriented design. Check out the Object Oriented Design chapter for sample questions and suggestions.

• However, because Google HR can be a little disorganized, we recommend being proactive in com- munication.
• A Google engineer performs the first phone screen, so expect tough technical questions.
• On your on-site interview, you'll interview with four to six people, one of whom will be a lunch interviewer. Interviewer feedback is kept confidential from the other interviewers, so you can be assured that you enter each interview with blank slate. Your lunch interviewer doesn’t submit feedback, so this is a great opportunity to ask honest questions.
• Written feedback is submitted to a hiring committee of engineers to make a hire/no-hire recommendation. Feedback is typically broken down into four categories (Analytical Ability, Coding, Experience and Communication) and you are given a score from 1.0 to 4.0 overall.
• The hiring committee understands that you can’t be expected to excel in every interview, but if multiple people raise the same red flag (arrogance, poor coding skills, etc), that can disqualify you. A hiring committee typically wants to see one interviewer who is an “enthusiastic en- dorser”. In other words, a packet with scores of 3.6, 3.1, 3.1 and 2.6 is better than all 3.1s. Your phone screen is usu- ally not a strong factor in the final deci- sion.
• The Google hiring process can be slow. If you don’t hear back within one week, politely ask your recruiter for an up- date. A lack of response says nothing about your performance.

Definitely Prepare:

• As a web-based company, Google cares about how to design a scalable system. So, make sure you prepare for questions from “System Design and Memory Limits” Additionally, many Google interviewers will ask questions involving Bit Ma- nipulation, so please brush up on these questions.

• Much like the company itself, Apple’s interview process has minimal beaucracy.
• The inter- viewers will be looking for excellent technical skills, but a passion for the position and com- pany is also very important. While it’s not a prerequisite to be a Mac user, you should at least be familiar with the system.
• The interview process typically begins with a recruiter phone screen to get a basic sense of your skills, followed up by a series of technical phone screens with team members.
• Once you’re invited on campus, you'll typically be greeted by the recruiter who provides an overview of the process. You will then have 6-8 interviews with members of the team for which you’re interviewing, as well as key people with whom your team works.
• You can expect a mix of 1-on-1 and 2-on-1 interviews. Be ready to code on a whiteboard and make sure all of your thoughts are clearly communicated. Lunch is with your potential future manager and appears more casual, but is still an interview. Each interviewer is usually fo- cused on a different area and is discouraged from sharing feedback unless there’s something they want subsequent interviewers to drill into.
• Towards the end of the day, your inter- viewers will compare notes and if ev- eryone still feels you’re a viable candi- date, you'll interview with the director and then VP of the organization you’re applying to. While this decision is rath- er informal, it’s a very good sign if you make it. This decision also happens be- hind the scenes and if you don’t pass, you'll simply be escorted out of the building without ever having been the wiser (until now)
• If you made it to the director and VP interviews, all of your interviewers will gather in a conference room to give an official thumbs up or thumbs down The VP typically won’t be present, but can still veto the hire if they weren’t im- pressed.
• Your recruiter will usually fol- low up a few days later, but feel free to ping your recruiter for updates.

Definitely Prepare:

• If you know what team you’re interview- ing with, make sure you read up on that product. What do you like about it? What would you improve? Offering specific recommendations can show your passion for the job.
• Also, Apple employees are huge Apple fans. You should show this same passion in your interview.

• While Yahoo tends to only recruit at the top 10 – 20 schools, other candidates can still get interviewed through Yahoo’s job board (or – better yet – if they can get an internal referral). If you’re one of the lucky ones selected, your interview process will start off with a phone screen. Your phone screen will be with a senior employee (tech lead, manager, etc)
• You will typically interview with 6 – 7 people on the same team for 45 minutes each Each interviewer will have an area of focus. Interviews will often be composed as follows:
  • 5 minutes: General conversation Tell me about yourself, your projects, etc
  • 20 minutes: Coding question For example, implement merge sort
  • 20 minutes: System design For example, design a large distributed cache These ques- tions will often focus on an area from your past experience or on something your interviewer is cur-rently working on
• At the end of the day, you will likely meet with a Program Manag- er or someone else for a general con- versation (product demos, concerns about the company, your competing offers, etc). Meanwhile, your interview- ers will discuss your performance and attempt to come to a decision The hiring manager has the ultimate say and will weigh the positive feedback against the negative.
• If you have done well, you will often get a decision that day, but this is not always the case. There can be many reasons that you might not be told for several days – for example, the team may feel it needs to interview several other people.

Definitely Prepare:

• Yahoo, almost as a rule, asks questions about system design, so make sure you prepare for that. They want to know that you can not only write code, but that you can design software. Don’t worry if you don’t have a background in this - you can still reason your way through it!

Resume screeners look for the same things that interviewers do:

• Are you smart?
• Can you code?

That means that you should present your resume to show those two things. Your love of tennis, traveling, or magic cards won’t do much to show that, so it’s likely just wasting space.Keep in mind that recruiters only spend a fixed amount of time (about 20 seconds) looking at your resume. If you limit the content to the best, most impressive, most relevant items, they’ll jump out at the recruiter Weak items only dilute your resume and distract the re- cruiter from what you’d like them to see.

---

Writing Strong Bullets:

• For each role, try to discuss your accomplishments with the following approach: “Accom- plished X by implementing Y which led to Z” Here’s an example:
• “Reduced object rendering time by 75% by applying Floyd’s algo- rithm, leading to a 10% reduction in system boot time”
• “Increased average match accu- racy from 1.2 to 1.5 by implement- ing a new comparison algorithm based on windiff”

Not everything you did will fit into this approach, but the principle is the same: show what you did, how you did it, and what the results were Ideally, you should try to make the results “measurable” somehow.

---

Advice for Non-Native English Speakers and Internationals:

• Proofreading: Some companies will throw out your resume just because of a typo. Please get at least one native English speaker to proofread your resume.
• Personal Information: For US positions, do not include age, marital status, or nationality. This sort of personal information is not appreciated by companies, as it creates a legal liabil- ity for them However, you may want to include your current work authorization / visa status, particularly when applying to smaller companies who may be unable to sponsor candidates.

Behavioral questions are asked for a variety of reasons

• They can be asked either to get to know your personality,
• to more deeply understand your resume,
• or just to ease you into an interview Either way,

these questions are important and can be prepared for.

Behavioral questions are usually of the form “tell me about a time when you ”, and may ask for an example from a specific project or position. I recommend filling in the following “preparation grid” as shown below:

	Project1	Project2	Project3	Project4
Most Challenging
What You Learned
Most Interesting
Hardest Bug
Enjoyed Most
Conflicts with Teammates

In each cell, put the corresponding story. We recommend reducing each story to just a couple keywords that you can write in each cell This will make the grid easier to study

---

What questions should you ask the interviewer?

• Genuine Questions: These are the questions you actually want to know ideas of questions that are valuable to many candidates:
  • “How much of your day do you spend coding?”
  • “How many meetings do you have every week?”
  • “What is the ratio of testers to developers to product managers? What is the interac- tion like? How does project planning happen on the team?”
• Insightful Questions: These questions are designed to demonstrate your deep knowledge of programming or technologies.
  • “I noticed that you use technology X How do you handle problem Y?”
  • “Why did the product choose to use the X protocol over the Y protocol? I know it has benefits like A, B, C, but many companies choose not to use it because of issue D”
• Passion Questions: These questions are designed to demonstrate your passion for technol- ogy.
  • “I’m very interested in scalability Did you come in with a background in this, or what opportunities are there to learn about it?”
  • “I’m not familiar with technology X, but it sounds like a very interesting solution Could you tell me a bit more about how it works?”

• Memorizing or trying to learn specific questions won’t help you!
• Try to solve the problem on your own.
• Write the code for the algorithm on paper.
• Type your paper code as-is into a computer.
• *Do a mock interview. CareerCup offers a mock interview

Data Structures	Algorithms	Concepts
Linked Lists	Breadth First Search	Bit Manipulation
Binary Trees	Depth First Search	Singleton Design Pattern
Tries	Binary Search	Factory Design Pattern
Stacks	Merge Sort	Memory (Stack vs Heap)
Queues	Quick Sort	Recursion
Vectors / ArrayLists	Tree Insert / Find / etc	Big-O Time
Hash Tables

• Be Specific, Not Arrogant
• Limit Details
• Ask Good Questions
• Structure Answers Using S.A.R(Situation, Action, Response)

A technical interview question can be solved utilizing a five step approach:

1. Ask your interviewer questions to resolve ambiguity
2. Design an Algorithm
3. Write pseudo-code first, but make sure to tell your interviewer that you’re writing pseudo-code! Otherwise, he/she may think that you’re never planning to write “real” code, and many interviewers will hold that against you
4. Write your code, not too slow and not too fast
5. Test your code and carefully fix any mistakes

• Negotiating. It’s Always Negotiable! Ok, maybe not always, but usually an offer is negotiable even if a recruiter tells you otherwise. It helps if you have a competing offer But, don’t lie – Microsoft knows what Google offers, so it just won’t be realistic if you make up numbers. Also, technol- ogy is a small world, and people talk. Be honest.
• What’s the money like, really? Think about the full offer package Many companies will have impressive salaries, but small annual bonuses Other companies will have huge annual bonuses, but lower salaries Make sure you look at the full package (salary, signing bonus, health care benefits, raises, annual bonus, relocation, stock, promotions, etc) It’s very confusing, and it’s often not clear which company is offering more
• What about your career options? I can’t give you some magical formula to compute which offer to accept, but here’s what I’d recommend thinking about (in no particular order):
  • Career Path: Make a plan for your career What do you want to do 5, 10 and 15 years out? What skills will you need to develop? Which company or position will help you get there?
  • Promotion Opportunity: Do you prefer to move into management, or would you prefer to become an increasingly senior developer?
  • Money and Benefits: Of course, the money matters (but if you’re early in your career, it probably doesn’t matter much). As mentioned above, make sure you look at the full package.
  • Happiness: Did you like the people? The products? The location? It’s hard to tell, of course, before you work there. What are the options to change teams if you’re unhappy?
  • Brand Name: The company’s brand name can mean a lot for your future career Some company names will open doors, while others will not as much.
  • What about company stability? Personally, I think it matters much less than most people think. There are so many software companies out there. If you get laid off and need to find a new job, will it be difficult to find a new one? Only you can answer that.

• Practicing on a Computer
• Not Rehearsing Behavioral Questions
• Not Doing a Mock Interview
• Trying to Memorize Solutions
• Talking Too Much
• Talking Too Little
• Rushing
• Not Debugging
• Sloppy Coding
• Giving Up

Should I tell my interviewer if I know a question?

Yes! You should definitely tell your interviewer if you’ve previously heard the question This seems silly to some people - if you already know the question (and answer), you could ace the question, right? Not quite

Here’s why we strongly recommend that you tell your interviewer that you’ve heard the question:

1. Big honesty points. This shows a lot of integrity That’s huge. Remember that the interviewer is evaluating you as a potential teammate I don’t know about you, but I personally prefer to work with honest people!
2. The question might have changed ever-so-slightly. You don’t want to risk repeating the wrong answer
3. If you easily belt out the right answer, it’s obvious to the interviewer. They know how hard a problem is supposed to be. It’s very hard to “pretend” to struggle through a question, because you just can’t approach it the same way other candidates do.

• 1.1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
• 1.2 Write code to reverse a C-Style String. (C-String means that “abcd” is represented as five characters, including the null character.)
• 1.3 Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer.
• 1.4 Write a method to decide if two strings are anagrams or not.
• 1.5 Write a method to replace all spaces in a string with ‘%20’.
• 1.6 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees Can you do this in place?
• 1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
• 1.8 Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i e , “waterbottle” is a rotation of “erbottlewat”).

---

1.6

int m[N][N];
for(int k=0;k<N/2;k++) {
  int r = k;
  int last = n - 1 - r;
  for(int c = r; c <= last; c++) {
    // [r,c], [N-1-c,r], [N-1-r,N-1-c], [c,N-1-r]
    int tmp = m[r][c];
    m[r][c] = m[c][N-1-r];
    m[c][N-1-r] = m[N-1-r][N-1-c];
    m[N-1-r][N-1-c] = m[N-1-c][r];
    m[N-1-c][r] = tmp;
  }
}

Questions:

• 2.1 Write code to remove duplicates from an unsorted linked list. How would you solve this problem if a temporary buffer is not allowed?
• 2.2 Implement an algorithm to find the nth to last element of a singly linked list.
• 2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
• 2.4 You have two numbers represented by a linked list, where each node contains a sin- gle digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
• (x) 2.5 Given a circular linked list, implement an algorithm which returns node at the begin- ning of the loop.
  • Assume P,Q at head. P proceeds 1 step, and Q proceed 2 step. There is k nodes before entry node of the circular list. And they takes u step to meet each other at p in the circular list. So we have following equations.
    1. k + xn + p= 2u # Q position.
    2. k + yn + p = u # P position.
    3. u = zn # using 1 and 2.
    4. (k + p) = z'n # using 2 and 3.
    5. k % n = (n-p) # done.
  • see leetcode https://oj.leetcode.com/problems/linked-list-cycle/ and https://oj.leetcode.com/problems/linked-list-cycle-ii/

Questions:

• 3.1 Describe how you could use a single array to implement three stacks.
• 3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.
• 3.5 Implement a MyQueue class which implements a queue using two stacks.
• 3.6 Write a program to sort a stack in ascending order. You should not make any assump- tions about how the stack is implemented.

• Trees
  • Not all binary trees are binary search trees
  • In-Order: Traverse left node, current node, then right
  • Pre-Order: Traverse current node, then left node, then right node
  • Post-Order: Traverse left node, then right node, then current node
  • AVL Tree, RB Tree.
  • Construct Tree by using Orders
• Graphs
  • Depth First Search
  • Breadth First Search
  • Dijkstra,Floyd,Prim,Kruskal.

Questions:

• 4.1 Implement a function to check if a tree is balanced.
• 4.2 Given a directed graph, design an algorithm to find out whether there is a route be- tween two nodes.
• 4.3 Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.
• 4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists).
• 4.5 Write an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.
• 4.6 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure.
• 4.7 You have two very large binary trees: T1, with millions of nodes, and T2, with hun- dreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
• 4.8 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value.

---

4.6

TreeNode* ancestor(TreeNode* root,TreeNode* p,TreeNode* q,int& cond) {
  if(root == NULL) return NULL;
  if(root == p || root == q) {
    cond++; // root is p or q, find one.
  }
  // check left.
  int c = 0;
  TreeNode* t = ancestor(root->left, p, q, c);
  if(c == 2) {
    cond = 2;
    return t;
  }
  cond += c;  
  if(cond == 2) {
    return root;
  }
  // check right.
  c = 0;
  t = ancestor(root->right, p, q, c);
  if(c == 2) {
    cond = 2;
    return t;
  }
  cond += c;
  if(cond == 2) {
    return root;
  }
  // maybe cover one.
  return root;
}

TreeNode* ancestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  int cond;
  return ancestor(root, p, q, cond);
}

Questions:

• 5.1 You are given two 32-bit numbers, N and M, and two bit positions, i and j Write a method to set all bits between i and j in N equal to M. Input: N = 10000000000, M = 10101, i = 2, j = 6. Output: N = 10001010100
• 5.2 Given a (decimal - e g 3 72) number that is passed in as a string, print the binary rep- resentation If the number can not be represented accurately in binary, print “ERROR”
• 5.3 Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
• 5.4 Explain what the following code does: ((n & (n-1)) == 0).
• 5.5 Write a function to determine the number of bits required to convert integer A to integer B.
• 5.6 Write a program to swap odd and even bits in an integer with as few instructions as possible (e g , bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).

---

5.3

#include <cstdio>
#include <cassert>

int previous(int number) {
  int n = number;
  int c1 = 0;
  int c0 = 0;
  // find 0.
  while(n & 0x1) {
    n >>= 1;
    c1++;
  }
  // find 1.
  while(!(n & 0x1)) {
    n >>= 1;
    c0++;
  }
  // rearrange following 1 and 0.
  // 10 with c0-1{0} and c1{1}
  // change to 01 c1{1} c0-1{0}
  n = ((n >> 1) << 1) + 1;
  for(int i=0;i<c1;i++) {
    n = (n << 1) + 1;
  }
  for(int i=1;i<c0;i++) {
    n = (n << 1);
  }
  return n;
}

int next(int number) {
  int n = number;
  int c1 = 0;
  int c0 = 0;
  // find 1.
  while(!(n & 0x1)) {
    n >>= 1;
    c0++;
  }
  // find 0.
  while(n & 0x1) {
    n >>= 1;
    c1++;
  }
  // rearrrange following 1 and 0.
  // change to 1 c0+1{0} c1-1{1}.
  n += 1;
  for(int i=0;i<=c0;i++) {
    n = (n << 1);
  }
  for(int i=1;i<c1;i++) {
    n = (n << 1) + 1;
  }
  return n;
}

int main() {
  int n = (1 << 5) + (1 << 1) + 1;
  int m = (1 << 4) + (1 << 3) + (1 << 2);
  assert(previous(n) == m);
  assert(next(m) == n);
  return 0;
}

• Don’t panic when you get a brain teaser. Interviewers want to see how you tackle a problem; they don’t expect you to immediately know the answer. Start talking, and show the inter- viewer how you approach a problem
• In many cases, you will also find that the brain teasers have some connection back to funda- mental laws or theories of computer science.
• If you’re stuck, we recommend simplifying the problem. Solve it for a small number of items or a special case, and then see if you can generalize it.

Questions:

• 6.1 Add arithmetic operators (plus, minus, times, divide) to make the following expres- sion true: 3 1 3 6 = 8. You can use any parentheses you’d like.
• (x) 6.2 There is an 8x8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board?
• 6.3 You have a five quart jug and a three quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water?
• (x) 6.4 A bunch of men are on an island. A genie comes down and gathers everyone to- gether and places a magical hat on some people’s heads (i e , at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those(and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat.
• (x) 6.5 There is a building of 100 floors If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs Find N, while minimizing the number of drops for the worst case.
  • dp[t][s][e] = 1 + min{ i=[s,e], max(dp[t-1][s][i-1], dp[t][i+1][e]) }. if(s>e) 0 else if(t==0) e-s+1
  • note(dirlt): not easy to deduce actions from dp
  • note(dirlt): and only one step can be decided. I've attached the code below.
• (x) 6.6 There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e g , he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?
  • only n = p * p have been flipped with odd number and final status is open.

---

6.5

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100;
const int R = 2;
int dp[R][N+1][N+1];

int get(int t,int s,int e) {
  if(s>e) return 0;
  if(dp[t][s][e] != 0) {
    return dp[t][s][e];
  }
  int v = -1;
  for(int i=s;i<=e;i++) {
    int r = 1 + max(get(t,i+1,e),dp[t-1][s][i-1]);
    if(v == -1 || r < v) {
      v = r;
    }
  }
  dp[t][s][e] = v;
  return v;
}

void foo() {
  memset(dp,0,sizeof(dp));
  for(int i=1;i<=N;i++) {
    for(int j=i;j<=N;j++) {
      dp[0][i][j] = (j-i+1);
    }
  }
  for(int t=1;t<R;t++) {
    for(int s=1;s<=N;s++) {
      for(int e=1;e<=N;e++) {
        get(t,s,e);
      }
    }
  }
}

void reverse() {
  int t = R-1;
  int v = dp[t][1][N];
  printf("%d\n",v);

  int s = 1;
  int c = 1;
  bool changed = true;
  while(changed) {
    changed = false;
    for(int i=s;i<=N;i++) {
      // search first point that egg breaks.
      // and to my intuition, there will be only one point.
      if(v == (c + dp[t-1][s][i-1])) {
        printf("below %d\n",i);
        s = i+1;
        c++;
        changed = true;        
        break;
      }
    }
  }
}

int main() {
  foo();
  reverse();
  return 0;
}

• All problems that can be solved recursively can also be solved iteratively (though the code may be much more complicated). Before diving into a recursive code, ask yourself how hard it would be to implement this algorithm iteratively. Discuss the trade-offs with your interviewer.
• Recursive algorithms can be very space inefficient. Each recursive call adds a new layer to the stack, which means that if your algorithm has O(n) recursive calls then it uses O(n) memory Ouch! This is one reason why an iterative algorithm may be better.

Questions:

• 8.2 Imagine a robot sitting on the upper left hand corner of an NxN grid The robot can only move in two directions: right and down How many possible paths are there for the robot?
  • Imagine certain squares are “off limits”, such that the robot can not step on them Design an algorithm to get all possible paths for the robot
• 8.3 Write a method that returns all subsets of a set.
• 8.4 Write a method to compute all permutations of a string.
• 8.5 Implement an algorithm to print all valid (e g , properly opened and closed) combi- nations of n-pairs of parentheses.
• 8.7 Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.
• 8.8 Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.

• Bubble Sort
• Selection Sort
• Merge Sort
• Quick Sort
• Bucket Sort
• Binary Search

Questions:

• (x) 9.1 You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B Write a method to merge B into A in sorted order.
• 9.3 Given a sorted array of n integers that has been rotated an unknown number of times,give an O(logn) algorithm that finds an element in the array. You may assume that the array was originally sorted in increasing order. EXAMPLE: Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14) Output: 8 (the index of 5 in the array)
• 9.4 If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?
• 9.5 Given a sorted array of strings which is interspersed with empty strings, write a meth- od to find the location of a given string
  • Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
  • Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1
• 9.6 Given a matrix in which each row and each column is sorted, write a method to find an element in it.
• 9.7 A circus is designing a tower routine consisting of people standing atop one anoth- er’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of peo- ple in such a tower. EXAMPLE: Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

---

9.3

#include <vector>
#include <cstdio>
using namespace std;

int BS(int A[],int n,int x) {
  int s = 0;
  int e = n-1;
  while(s <= e) {
    int m = (s + e) / 2;
    if(A[m] == x) return m;
    if(A[m] > x) {
      if(A[s] <= x) {
        e = m - 1;
      } else {
        s = m + 1;
      }
    } else {
      if(A[e] >=x) {
        s = m + 1;
      } else {
        e = m - 1;
      }
    }
  }
  // insert position.
  // return s;
  return -1;
}

int main() {
  int A[] = {15,16,19,20,25,1,3,4,5,7,10,14};
  int n = sizeof(A) / sizeof(int);
  printf("%d\n",BS(A,n,5));
  return 0;
}

---

9.5

#include <vector>
#include <string>
using namespace std;

int BS(const vector<string>& A,const string& x) {
  int n = A.size();
  int s = 0;
  int e = n - 1;
  while(s <= e) {
    int m = (s + e) / 2;
    if(A[m] == "") {
      int u = m;
      while(u>=0 && A[u] == "") u--;
      if(u >= 0) {
        if(A[u] == x) return u;
        else if(A[u] > x) {
          e = u - 1;
          continue;
        }
      }
      u = m;
      while(u<=e && A[u] == "") u++;
      if(u <= e) {
        if(A[u] == x) return u;
        else if(A[u] < x) {
          s = u + 1;
          continue;
        }
      }
      return -1;
    } else if(A[m] == x) {
      return m;
    } else if(A[m] > x) {
      m = e - 1;
    } else {
      s = e + 1;
    }
  }  
}

int main() {
  const char* ss[] = {"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", "", NULL};
  vector<string> A;
  for(int i=0;ss[i];i++) {
    A.push_back(ss[i]);
  }
  printf("%d\n",BS(A,"ball"));
  printf("%d\n",BS(A,"ballcar"));
  return 0;
}

Questions:

• 10.1 You have a basketball hoop and someone says that you can play 1 of 2 games
  • Game #1: You get one shot to make the hoop
  • Game #2: You get three shots and you have to make 2 of 3 shots
  • If p is the probability of making a particular shot, for which values of p should you pick one game or the other?
• 10.2 There are three ants on different vertices of a triangle What is the probability of colli- sion (between any two or all of them) if they start walking on the sides of the triangle? Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon
• 10.4 Write a method to implement *, - , / operations You should use only the + operator.
• (x) 10.5 Given two squares on a two dimensional plane, find a line that would cut these two squares in half.
• (x) 10.6 Given a two dimensional graph with points on it, find a line which passes the most number of points.
• (x) 10.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

---

10.7

#include <queue>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

int kth(int k) {
  priority_queue<int,vector<int>,std::greater<int> > Q3; // 3,5,7
  priority_queue<int,vector<int>,std::greater<int> > Q5; // 5,7
  priority_queue<int,vector<int>,std::greater<int> > Q7; // 7
  Q3.push(3);
  Q5.push(5);
  Q7.push(7);
  for(;;) {
    int x = min(min(Q3.top(),Q5.top()),Q7.top());
    k--;
    if(k == 0) return x;
    if(x == Q3.top()) {
      Q3.pop();
      Q3.push(x * 3);
      Q3.push(x * 5);
      Q3.push(x * 7);
    } else if(x == Q5.top()) {
      Q5.pop();
      Q5.push(x * 5);
      Q5.push(x * 7);
    } else {
      Q7.pop();
      Q7.push(x * 7);
    }
  }
}

int main() {
  printf("%d\n",kth(13));
  return 0;
}

Questions:

• 11.1 If you were integrating a feed of end of day stock price information (open, high, low, and closing price) for 5,000 companies, how would you do it? You are responsible for the development, rollout and ongoing monitoring and maintenance of the feed. De- scribe the different methods you considered and why you would recommend your approach. The feed is delivered once per trading day in a comma-separated format via an FTP site. The feed will be used by 1000 daily users in a web application.
• 11.2 How would you design the data structures for a very large social network (Facebook, LinkedIn, etc)? Describe how you would design an algorithm to show the connec- tion, or path, between two people (e g , Me -> Bob -> Susan -> Jason -> You).
• (x) 11.3 Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory. What if you have only 10 MB of memory?
  • note(dirlt): The solution provided by the book should be with a restriction that integers are not repeated. But anyway, the solution is inspiring
• 11.4 You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4KB of memory available, how would you print all duplicate elements in the array?
• 11.5 If you were designing a web crawler, how would you avoid getting into infinite loops?
• 11.6 You have a billion urls, where each is a huge page How do you detect the duplicate documents?
• 11.7 You have to design a database that can store terabytes of data It should support ef- ficient range queries How would you do it?.

Questions:

• 16.1 Explain the following terms: virtual memory, page fault, thrashing.
• (x) 16.2 What is a Branch Target buffer? Explain how it can be used in reducing bubble cycles in cases of branch misprediction.
• (x) 16.3 Describe direct memory access (DMA). Can a user level buffer / pointer be used by kernel or drivers?
• (x) 16.4 Write a step by step execution of things that happen after a user presses a key on the keyboard Use as much detail as possible.
• 16.5 Write a program to find whether a machine is big endian or little endian.
• 16.6 Discuss how would you make sure that a process doesn’t access an unauthorized part of the stack.
• 16.7 What are the best practices to prevent reverse engineering of DLLs?.
• (x) 16.8 A device boots with an empty FIFO queue In the first 400 ns period after startup, and in each subsequent 400 ns period, a maximum of 80 words will be written to the queue Each write takes 4 ns A worker thread requires 3 ns to read a word, and 2 ns to process it before reading the next word What is the shortest depth of the FIFO such that no data is lost?
• 16.9 Write an aligned malloc & free function that takes number of bytes and aligned byte (which is always power of 2).
• 16.10 Write a function called my2DAlloc which allocates a two dimensional array. Minimize the number of calls to malloc and make sure that the memory is accessible by the notation arr[i][j].

Questions:

• 17.1 Explain what happens, step by step, after you type a URL into a browser. Use as much detail as possible.
• 17.2 Explain any common routing protocol in detail For example: BGP, OSPF, RIP
• 17.3 Compare and contrast the IPv4 and IPv6 protocols.
• (x) 17.4 What is a network / subnet mask? Explain how host A sends a message / packet to host B when: (a) both are on same network and (b) both are on different networks Explain which layer makes the routing decision and how.
• (x) 17.5 What are the differences between TCP and UDP? Explain how TCP handles reliable delivery (explain ACK mechanism), flow control (explain TCP sender’s / receiver’s win- dow) and congestion control.

Questions:

• 18.1 What’s the difference between a thread and a process?
• 18.2 How can you measure the time spent in a context switch?
• 18.3 Implement a singleton design pattern as a template such that, for any given class Foo, you can call Singleton::instance() and get a pointer to an instance of a singleton of type Foo. Assume the existence of a class Lock which has acquire() and release() methods. How could you make your implementation thread safe and exception safe?.
• 18.4 Design a class which provides a lock only if there are no possible deadlocks.
• 18.5 You are given a class with synchronized method A, and a normal method C If you have two threads in one instance of a program, can they call A at the same time? Can they call A and C at the same time?

Questions:

• 19.1 Write a function to swap a number in place without temporary variables.
• (x) 19.3 Write an algorithm which computes the number of trailing zeros in n factorial.
• 19.4 Write a method which finds the maximum of two numbers. You should not use if- else or any other comparison operator.
• 19.6 Given an integer between 0 and 999,999, print an English phrase that describes the integer (eg, “One Thousand, Two Hundred and Thirty Four”).
• 19.7 You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.
• 19.8 Design a method to find the frequency of occurrences of any given word in a book.
• (x) 19.10 Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5 (i e , implement rand7() using rand5()).
• 19.11 Design an algorithm to find all pairs of integers within an array which sum to a speci- fied value.

---

19.3

int zeros(int n) {
  int c = 0;
  for(int k = 5; n >= k; k *= 5) {
    c += n / k;
  }
  return c;
}

---

19.6

#include <cstdio>
#include <string>
using namespace std;

static const char* s1[] = {"Zero","One","Two","Three","Four","Five",
                           "Six","Seven","Eight","Nine","Ten",
                           "Eleven","Twelve","Thirteen","Fourteen",
                           "Fifteen","Sixteen","Seventeen","Eighteen",
                           "Nineteen"};
static const char* s2[] = {"","","Twenty","Thirty","Fourty","Fifty",
                           "Sixty","Seventy","Eighty","Ninety"};

string speak(int n) {
  if(n <= 19) {
    return s1[n];
  } else if(n < 100) {
    int m = n % 10;    
    string s = s2[n / 10];
    if(m != 0) {
      s += " ";
      s += s1[m];
    }
    return s;
  } else if(n < 1000) {
    int m = n % 100;
    string s = s1[n / 100];
    s += " Hundred";
    if(m != 0) {
      s += " and ";
      s += speak(m);
    }
    return s;
  } else {
    int m = n % 1000;
    string s = speak(n / 1000);
    s += " Thousand";
    if(m != 0) {
      s += ", ";
      s += speak(m);
    }
    return s;
  }
}

void print(int n) {
  printf("%s\n",speak(n).c_str());
}

int main() {
  print(101);
  print(1001);
  print(1010);
  print(999100);
  return 0;
}

Questions:

• (x) 20.1 Write a function that adds two numbers You should not use + or any arithmetic op- erators.
• (x) 20.2 Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.
• (x) 20.3 Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen.
• (x) 20.4 Write a method to count the number of 2s between 0 and n.
• 20.5 You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. Can you make the searching operation in O(1) time? What about the space complexity for your solu- tion?
• (x) 20.6 Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. As- sume that the computer memory can hold all one billion numbers.
• (x) 20.7 Write a program to find the longest word made of other words.
• (x) 20.8 Given a string s and an array of smaller strings T, design a method to search s for each small string in T.
  • note(dirlt): I got suffix tree:)
• (x) 20.9 Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.
• (x) 20.10 Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.
• (x) 20.11 Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
• (x) 20.12 Given an NxN matrix of positive and negative integers, write code to find the sub- matrix with the largest possible sum.
• (x) 20.13 Given a dictionary of millions of words, give an algorithm to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom).

---

20.1

#include <cstdio>

int add2(int a,int b) {
  int sum = a ^ b;
  int carry = (a & b) << 1;
  if(carry == 0) return sum;
  return add2(sum,carry);
}

int main() {
  printf("%d\n",add2(190,70));
  return 0;
}

---

20.4

#include <cstdio>

int c2(int n);
int c2r(int n, int pow) {
  if(n == 0) return 0;
  int x = n / pow;
  int y = n % pow;
  int res = 0;
  if(x == 2) {
    res += (y + 1);
  } else if(x > 2) {
    res += pow;
  }
  res += x * c2r(pow-1,pow / 10) + c2(y);
  return res;
}

int c2(int n) {
  int pow = 1;
  while((pow * 10) <= n) pow *= 10;
  return c2r(n,pow);
}

int main() {
  printf("%d\n",c2(279));
  return 0;
}

---

20.9

#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

class Median {
 private:
  priority_queue< int, vector<int>, less<int> > Q0;
  priority_queue< int, vector<int>, greater<int> > Q1;

 public:
  void insert(int x) {
    if(Q0.empty()) {
      if(Q1.empty()) {
        Q1.push(x);
      } else {
        int y = Q1.top();
        if(x < y) {
          Q0.push(x);
        } else {
          Q1.pop();
          Q0.push(y);
          Q1.push(x);
        }
      }
      return ;
    }

    int x0 = Q0.top();
    int x1 = Q1.top();
    if(Q0.size() == Q1.size()) {
      if(x <= x0) {
        Q0.pop();
        Q0.push(x);
        Q1.push(x0);
      } else {
        Q1.push(x);
      }
    } else {
      if(x >= x1) {
        Q1.pop();
        Q1.push(x);
        Q0.push(x1);
      } else {
        Q0.push(x);
      }
    }
  }

  double median() {
    if(Q0.size() == Q1.size()) {
      return (Q0.top() + Q1.top()) * 0.5;
    } else {
      return Q1.top();
    }
  }
};

int main() {
  Median m;
  m.insert(1);
  m.insert(2);
  printf("%g\n",m.median());
  m.insert(3);
  printf("%g\n",m.median());
  m.insert(-3);
  printf("%g\n",m.median());
  return 0;
}

---

20.11

int m[N][N];
for(int n=N;n>=1;n--) {
  for(int r=0;(N-r)>=n;r++) {
    for(int c=0;(N-c)>=n;r++) {
      if(bound(r,c,n)) {
        return n;
      }
    }
  }
}

---

20.12

int m[N][N];
int dp[N][N]; // dp[s][e] = sum from (0,0) to (s,e).
for(int r=0;r<N;r++) {
  for(int c=0;c<N;c++) {
    int s = 0;
    for(int i=0;i<c;i++) {
      s += m[r][i];
    }
    dp[r][c] = s;
    if(r != 0) {
      dp[r][c] += dp[r-1][c];
    }
  }
}

int v = INT_MIN;
for(int rs=0;rs<N;rs++) {
  for(int re=rs;re<N;re++) {
    for(int cs=0;cs<N;cs++) {
      for(int ce=0;ce<N;ce++) {
        int u = sum(rs,cs,re,ce);
        if(u > v) v = u;
      }
    }
  }
}

int X(int a,int b) {
  if(a < 0 || b < 0) return 0;
  return dp[a][b];
}

int sum(int rs,int cs,int re,int ce) {
  int a = X(rs-1,cs-1);
  int b = X(rs-1,ce) - X(rs-1,cs-1);
  int c = X(re,cs-1) - X(rs-1,cs-1);
  int d = X(re,ce);
  return d - a - b - c;
}