V. Behavioral Questions

• Purpose: know your personality, understand resume more deeply, or ease you into interview.
• Important chart (4 projects each): Most challenging, what you learned, most interesting, hardest bug, enjoyed most, conflicts with teammates
  • “softer questions”:
    • conflicts on a team
    • failures
    • times you had to persuade someone
  • think deeply about what each story communicates about you.

• What are your weaknesses?
  • Give a legitimate weakness and emphasize how you worked to overcome it.
  • There is always a struggle in my mind when answering questions like this. I don’t want to fear giving the wrong answer, in turn that makes me sounds fake.
  • When I am focusing on school or research, I tend to get tunnel vision about the big picture. For example, I always hear about new technologies like Flask and Django, but don’t see the common connection between all of these. CRT and RSA.
• What was the most challenging part of that project?
  • Cop out answer: “Had to learn languages and technologies”
• What questions should you ask the interviewer? The issue here is that I need to get over the fear of sounding disingenuous, but at the same time, not be disingenuous!
  • Genuine:
    • How much of your day do you spend coding?
    • How many meetings do you have per week?
    • What is the ratio of testers to developers to program managers?
    • What is the interaction like? How does project planning happen on the team?
  • Insightful, demonstrate deep knowledge of programming or technologies, and demonstrate your passion for the company or product:
    • 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, demonstrates passion for technology. Show interest in learning and will be strong contributor to the company.
    • 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?
• The way to brag without sounding arrogant is to be specific.
  • Limit the details but touch on the key points
• Give structured answers
  • Nugget first: Starting your response with a “nugget” that succintly describes what your response will be about.
  • S.A.R. (Situation, Action, Result)
    • Situation and result should be succinct. The action part is the bread and butter, and will allow the interviewer to easily identify how you made an impact and why it mattered.

“Soft” Questions

• Tell us about a technical project you worked on that didn’t go well. What did you learn from working on that project?
  • I attempted to make a Facebook Messenger chatbot once, set up the Flask server and Django API endpoint, with a SQLite database. The goal of the chatbot was to learn user’s dining menu preferences, message users whenever the school’s dining hall is serving that. However, the issue was that my app could not hold up to Facebook’s rigorous testing. They would send in a number of gibberish requests, and I would have to not send the same amount of responses back.
• What is your engineering philosophy? (Bombed this question, IXL Learning final stage)

VI. Technical Questions

• How to practice a question
  • Try to solve the problem on your own
  • Write the code for the algorithm on paper
  • Test your code, on paper.
  • Type your paper code as-is into a computer. Write down a list of the errors
• CareerCup.com or mock interviews with friends
• Absolute, must have knowledge
  • Data structures: Linked Lists, Binary Trees, Tries, Stacks, Queues, Vectors/ArrayLists, Hash Tables
  • Algorithms: BFS, DFS, Binary Search, Merge Sort, Quick Sort, Tree Insert / Find / e.t.c.
  • Comcepts: Bit Manipulation, Singleton Design Patter, Factory Design Patter, Memory (Stack vs. Heap), Recursion, Big-O Time.
• Hash tables extremely important!
• Powers of two table. 2^10 is roughly a thousand. 2^20 roughly a million. etc etc
• The smaller the company, the more important specific technologies are.
• Five steps to a technical question
  • Ask interviewer questions to resolve ambiguity
    • What are the data types? How much data is there? What assumptions do you need to solve the problem? Who is the user?
  • Design an algorithm
    • Space and time complexity? What happens if a lot of data? Can design cause other issues? Did you make the right trade offs? Have you leveraged properties of the data? Completely ok to first do brute force, and the optimize.
  • Write pseudocode first, but make sure to tell your interviewer that you’ll eventually write “real” code
    • Move quick.
  • Write your code at a moderate pace
    • Use data structures generously. Don’t crowd your coding
  • Test your code and carefully fix any mistakes.
    • Extreme cases, user error, general cases. If algorithm is complicated or highly numerical, consider testing while you’re writing the code rather than just at the end.
    • Find and understand the source of bugs, don’t just blindly fix.
• Five algorithm approaches
  • Approach 1: Exemplify. Use specific examples and work them out by hand.
  • Approach 2: Pattern Matching. Try and reduce this to a simpler, already solved problem
  • Approach 3: Simplify and generalize.
    • Shaky about how to use this! Find a specific example of when this applies.
  • Approach 4: Base case and build! Inductively solve the problem. Dynamic programming, etc.
  • Approach 5: Data Strucutre Brainstorm. Hacky, run through all data structure and sees which one works. I use this approach, but don’t like to admit it. Makes me feel dumb, but actually a useful technique.
• What is good, clean, code?
  • Correct: should operate correctly on all expected and unexpected inputs.
  • Efficient: Time and space. Both big-O and real life efficiency.
  • Simple: Be as quick as possible
  • Readable: Other developers should be able to read. Fancy code is not necessarily good code.
  • Maintainable: Should be easy to adapt during life cycle of product.
• To this end, we should:
  • Be generous with data structures, be purposeful, not hacky.
  • Write general methods that can be reusable.
  • Write modular code that can be tested individually
  • Flexible and robust. In general, more general is better. But if a specific case will do the trick, then do that.
  • Error checking. Good programmers do not make assumptions about the input.

I have a phone interview with Mixpanel on Monday. I do really bad on these so I need to practice. I am okay on implementing algorithms once I know the “critical insight”, but a lot of times I get stuck on finding that insight. So I figured the best way to practice would be to write down the “critical insight” to each problem, but only actually implement the ones that I believe are tricky to code up. Just in the interest of time.

Red text means that I have not solved it.

Brown text means that I am unsure if this is the fastest or most space efficient way to do it.

Purple text means that I have written the test cases for this problem.

Orange text means that I think I have it somewhat figured it out and would value greatly from actually implementing.

Green text means solved and implemented completely.

No color means that I solved almost completely and don’t feel that I’d gain much from implementing.

Chapter 1: Strings

1.1 Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures? Go through the entire string and keep track of characters using a set. If you cannot use additional data structures, then I can think of no faster way than just comparing each of the characters with all the previous characters, leading to a $O(n^2)$ runtime.

• Ask is it Unicode or Ascii. If it was Unicode, we would have to increase the storage size.
  • ASCII uses an 8-bit encoding while Unicode uses a variable bit encoding.
  • Unicode is standardized while ASCII isn’t. - Unicode represents most written languages in the world while ASCII does not. - ASCII has its equivalent within Unicode.
• Missed optimization: Check to see if the length of the string is more than the number of unique characters. If so, automatically return false.
• CTCI Solution: Use array whose ith index is true of that character appears.
• Alternative bitwise solution that has better space complexity but I don’t understand it.
• Sort it then see if there are any adjacent identicals.
• $O(n^2)$ compare to every other character in the string.

1.2 Implement a function void reverse(char* str) in C or C++ which reverses a null-terminated string. My C is rusty but I’m assuming that we want to do this in place. We could first find the length of the string and then do $\frac{n}{2}$ swaps using a temp variable. Can you do this without a temp variable?

• They said you can also implement it recursively but only if you are crazy. Fun to try I guess.
• If not doing in Python, then need to be careful of the null terminator.

1.3 Given two strings, write a method to decide if one is a permutation of the other. We could sort both strings and check to see if they are equal, with time complexity $O(n\log{n})$. If we put both into a dictionary and then compare the key-counts, then this would take time … roughly $O(n)$, but then this depends on the dictionary implementation.

• Always ask for the encoding scheme, ASCII or Unicode. This is less important for Python.
• Sort the strings is the classic approach.
• Tracking character counts is a more efficient way.

1.4 Write a method to replace all spaces in a string with ‘%20’. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the “true” length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place.). Go through the string. Whenever a space is found, put all “misplaced” characters towards the end of the array.

• Pattern: Start from the end and work backwards.
• Failed a problem of this sort on Google interview. Critical insight is to start from the end and move backwards.
• Intuition Failures. How do we know that we will not overlap indices?

1.5 Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the “compressed” string would not become smaller than the original string, your method should return the original string. Keep a running count of the number of characters “saved”. Doing this in place might be tricky.

• String concatenation takes time $O(n^2)$.
• The solution does not do this in place. Not sure how tough it would be to do that.
• Doing it not in place seems too easy

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? If you didn’t need to do it in place, then you could do a matrix multiplication by constructing the rotation matrix and then doing the mulitiplication. If we wanted to do this in place, we would have to go “ring by ring”. The indexing is tricky for this one.

• Ebay/Stubhub coding challenge, this one ate up a lot of time
• Moral of the story: find a pattern by drawing a picture, and be very careful with indices.
• Worthwhile to explore group symmetries between rotation, and reflection along the two diagonals.
• Probably the toughest problem for me from this section.

1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0. Traverse the entire matrix, and keep track of the rows and columns that will eventually get zeroed out. When finished, perform the zeroing.

• Got correct

1.8 Assume that 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. Don’t know how to do this one…

• Deceptively simple.
• Might be good practice to write the isSubstring method.

Chapter 2: Linked Lists

2.1 Write code to remove duplicates from an unsorted linked list. Follow up, how would you solve this problem if a temporary buffer is not allowed? With a temporary buffer, just keep track of duplicates and do some pointer stuff. But if you do not have access to a temporary buffer…then as you traverse the list, you need to traverse the rest of the remaining list to check for duplicates, slow $O(n^2)$ time complexity.

2.2 Implement an algorithm to find the kth to last element of a singly linked list. You could easily do this with two passes, but I’m assuming the question wants to do it in one. We could keep track of the elements that are k before the current one, and update it every time that we go forward. This has a space complexity of $\theta(k)$, but I don’t see how you could do it any faster.

• You can do this either recursively or iteratively, with the iterative solution being more optimal in terms of space.
• Guess I could do it recursively for practice.
• Be careful with off by one errors.

2.3 Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node. Take the given middle node, and then change the value to the next node, and then change the pointer to the next next node.

• Got this correct, except that I did not consider the edge case of when the node to be deleted is the last node of the linked list.
  • But that’s okay, because this case is impossible anyways.
  • But wait, why is this case impossible?

2.4 Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. Do we have to do this in place? Keep a pointer to the head of the beginning partition, and the partitioning node will be the head to the second partition. Traverse the list and update as necessary.

• This problem becomes much harder with an array.
• Doing this in place is harder.
• Ensure that you null out pointers so you don’t create a circular linked list!

2.5 You have two numbers represented by a linked list, where each node contains a single 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. Keep a “carry” variable, and use one of the agrument linked lists as the result linked list.

• Need to pad for the forward order case
• Modularize the different functions
• For our implementation, we go the easy route and assume low significance numbers come first.

2.6 Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop. Keep track of the set of already seen nodes. But this would require a buffer. Not sure if you could do this without a buffer. Can’t modify the instance variables of the linked list.

• Use the fast runner slow runner approach for detecting a loop in a linked list.
• Elegant solution
• More important to understand how the solution was arrived at.
• Key Insight: Carefully define variables and methodically reason to the solution.
• I like this problem
• The code is super simple, but need to know how to derive it.
• The easier version of this problem is to detect whether or not there is a loop in a linked list.
• How would one come up with this.

2.7 Implement a function to check if a linked list is a palindrome. Not sure how to do this.

• Reverse and compare. Reverse the linked list, then compare the first halves of the original and the reversed.
• There are also crazy recursive and iterative solutions.

Chapter 3: Stacks and Queues

3.1 Describe how you could use a single array to implement three stacks. Use a modulo 3.

• Trickier than you’d think.
• CTCI solutions does it differently, but would my way work?
• Fancier solution allows for varying divisions of the array. Too complex for an interview. Perhaps worthwhile to take a look at.

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. Keep an instance variable that keeps a linked list of the minimum element of the stack up to a new element push, update accordingly. Is there a way to make this use less than $O(n)$ space?

• Use additional stack to keep track of mins intelligently.
• Tricky to use a stack inside of a stack implementation
  • Defining a subclass is the best way I can think of to work around.
    • A lot of redundant code though

3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack). Follow up: Implement a function popAt(int index) which performs a pop operation on a specific sub-stack. Would this not just entail creating a linked list or an array of stacks?

• Just a bunch of modularized code, I don’t think this would show up in an interview.
• The CTCI solution for the follow up did “rollover” for the “popAt” method, which I neglected to do. Makes it less efficient but technically more correct, as all stacks will operate at full capacity.

3.4 In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (i.e., each disk sits on top of an even larger one). You have the following constraints: (1) Only one disk can be moved at a time. (2) A disk is slid off the top of one tower onto the next tower. (3) A disk can only be placed on top of a larger disk. Write a program to move the disks from the first tower to the last using stacks. Do some type of recursive branching…

• Base case and build approach.

3.5 Implement a MyQueue class which implements a queue using two stacks. Each stack would be responsible for pushing and popping respectively. If you want to push, then push to the push stack. If you want to pop, then you need to unload the push stack to the pop stack, and pop from the pop stack. This would effectively take $\theta(n)$ time per alternating push and pop operation…this is definitely not the most efficient way.

• After looking at the solutions, this was actually the right way to do it.

3.6 Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek and isEmpty. No idea how to do this.

• Pretty clever solution. Not sure how I would’ve come up with it.
• Honestly a pretty cool problem
• Do runtime analysis on this
• Basically a really inefficient insertion sort
• Pretend you are stacking plates in two bins in real life.
• If you were allowed unlimited stacks, then you can do a modified quicksort or mergesort.

3.7 An animal shelter holds only dogs and cats, and operates on a strictly “first in, first out” basis. People must adopt either the “oldest” (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create a data stucture to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat. You may use the built in LinkedList data structure. Have some data structure to tell which stack has the older oldest element. Just create a wrapper class that has a timestamp. This is almost trivial!

Chapter 4: Trees and Graphs

Keys: Binary tree vs binary search tree, balanced vs unbalanced, full and complete, binary tree traversal, tree balancing with RB and AVL, Trie, Graph Traversal, DFS, BFS <- use a queue.

• Know the ins and outs of tree traversal
  • With recursion, with stack, without recursion without stack

4.1 Implement a function to check if a binary tree is balanced, For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one. Return the conjunction of two recursive calls. Base cases are leaf nodes which are vacuously balanced.

• Got this right

4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes. Do DFS from both nodes and check if at least one of them can reach the other.

• Can also use BFS as well. Worthwhile to discuss the trade offs between BFS and DFS. DFS easy to implement, but BFS can find the shortest path efficiently, where DFS may go very deeply into some path first.

4.3 Given a sorted (increasing order) array with unqiue integer elements, write an algorithm to create a binary search tree with minimal height. Use recursion, have two cases, even and odd length arrays.

• Even and odd cases make this a little tricky

4.4 Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you’ll have D linked lists). Do an iterative level order traversal.

• Critical insight: you can traverse the tree in any way that you want, provided that you know what level you are at.
• Can simply modify the preorder traversal algorithm.
  • Wow, so simple.

4.5 Implement a function to check if a binary tree is a binary search tree. Should be a textbook algorithm, recursion and base cases. Good problem to practice with. Need to first write a binary tree class first.

• Critical insight: need all elements on the left to be smaller than the split key, not just the root’s key.
• Gotcha! Got caught with only testing the immediate left and right root values, instead of the entire subtrees.
• Use the min/max approach. The inorder approach might have simpler code, but has higher space complexity.

4.6 Write an algorithm to find the “next” node (i.e., in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.

• Failed a variant of this problem on Mixpanel first round phone interview. Actually this problem is slightly different.
• I used a recursive solution, you can actually just use in order traversal
• Maybe you don’t even need Morris traversal…
• Using Morris Traversal seems way more elegant.

4.7 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. NOTE: This is not necessarily a binary search tree. Do two recursive calls…base case etc. etc.

• Trickier than I thought, especially the optimized version.
• Todo: handle the optimization!

4.8 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide of T2 is a subtree of T1. A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical. Do two recursive calls with base cases etc etc.

• Complex problem with much subtlety.

4.9 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path does not need to start or end at the root or a leaf. Should be able to use recursion to solve this relatively easily.

4.10 Amazon interview question that stumped me: Morris traversal to do inorder traversal of a binary tree.

4.11 Non-recursive implementations of tree traversals. - Preorder, inorder, postorder

Extra questions for Chapter 4: 10.2, 10.5, 11.8, 17.13, 17.14, 18.6, 18.8, 18.9, 18.10, 18.13

Chapter 5: Bit Manipulation

Notes

• Sometimes, they explicitly ask for bit manipulation. Other times, it’s an optimization in your code.
• Should be very comfortable, need to be very careful. Test code thoroughly during and after.
• I am actually so weak in this
• Brush up on two’s complement and the like?

5.1 You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space to fit all of M. That is, if M=10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j=3 and i=2, because M could not fully fit between bit 3 and bit 2. Not really sure what the insight to this problem is…

• Use a bit mask, thoroughly test for off by one errors
• A bunch of edge cases that you need to check the input for.
• Definitely should do some input checking.

5.2 Given a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with at most 32 characters, print “Error”. Forgot how to represent real numbers in binary form.

• Recall the binary representation of doubles.
• No special bit operations needed for this one.
• “You should make sure to prepare thorough test cases for this problem, and actually go through them during your interview.” What test cases tho.
• There are very few doubles that can be represented with exactly 32 bits.

5.3 Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in the binary representation. Next smallest: take least significant 1 bit with 0 bits to the right, and swap the 1 with the least significant 0 bit to the right. Flip. Next largest: take least significant 0 bit with 1 bits to the right. Take the most siginificant 1 bit on the right, and flip it with the 0 bit.

• The beef of the problem is to flip two bits of a bitstring.

5.4 Explain what the following code does: ((n & (n-1)) == 0). This code checks to see if n is a power of 2.

• Or if $n == 0$.

5.5 Write a function to determine the number of bits required to convert integer A to integer B. Use XOR.

• Are there bit manipulation operators in Python?
• The code becomes much shorter when you are in C or C++.
• My code is rather inefficient
• There is a Pythonic way to do it, my code is very very not Pythonic

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, and so on)

• Iterate through the bitstring and make the appropriate mask.

5.7 An array A contains all the integers from 0 to n, except for one number which is missing. In this problem, we cannot access an entire integer A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in $O(n)$ time? Doing this in $O(nlogn)$ time is easy, just manually check all the bits to see which number is missing. Not sure how to do this in linear time though…

5.8 A monochrome screen is stored as a single array of bytes, allowing eight consecutive pixels to be stored in one byte. The screen has width w, where w is divisible by 8 (that is, no byte will be split across rows). The height of the screen, of course, can be derived by the length of the array and the width. Implement a function drawHorizontalLine(byte[] screen, int width, int x1, int x2, int y) which draws a horizontal line from (x1, y) to (x2, y). Is this not trivial…? I must be missing something.

5.9 (HRT C++ Examination) Add two bit strings to base -2, and have the result be the minimal such result of the sum.

Chapter 6: Brain Teasers

6.1 You have 20 bottles of pills. 19 bottles of 1.0 gram pills, but one has pills of weight 1.1 grams. Given a scale that provides an exact measurement, how would you find the heavy bottle? You can only use the scale once. Do we have any other assumptions?

• Got stumped grr.
• Key insight that was not mentioned in the posing of the question: there are effectively an infinite amount of pills in each bottle.
• The trick: remove a 1 pill from bottle 1, 2 pills from bottle 2,…
• Annoying question, if you know it you know it. Not many takeaways…
  • Takeaway: Be clever

6.2 There is an 8x8 chessboard 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?

• Ugh, the quintessential problem.
• Use induction. Effectively, each row is going to have an odd number of “protrusions”. Induct until the last layer.
• Key insight: There is no other way to solve this other than to use induction. I believe…

6.3 You have a five-quart jug, a three-quart jug, and an unlimited supply of water. How would you come up with exactly four quarts of water? Node that the jugs are oddly shaped, such that filling up exactly “half” of the jug would be impossible. Fill the three from the five, leaving 2 in the 5. pour the 2 into the three. Fill the 5 and dump 1 into the 3 until full, leaving 4 in the 5.

• Corollary (Interesting followup): As long as the two jug sizes are relatively prime, you can find a pour sequence for any value between one and the sum of the jug sizes.
  • Prove this!

6.4 A bunch of people are living on an island, when a visitor comes with a strange order: all blue-eyed people must leave the island as soon as possible. There will be a flight out at 8pm every evening. Each person can see everyone else’s eye color, but they do not know their own (nor is anyone else allowed to tell them). Additionally, they do not know how many people have blue eyes, although they do know that at least one person does. How many days will it take the blue-eyed people to leave? Let n be the number of blue eyed people that I see. There are two cases, I am either blue or not blue. In the simplest case, if I am the only blue eyed person, then I will leave in 1 day, because I see no other blue eyed people. If there are two blue eyed people, I will see 1 other blue eyed person, wait 1 day, and see that he has not left. In that case, I must leave, because he sees me. So it will take the total number of blue eyed people days to clear the island of blue eyed people.

6.5 There is a building of 100 floors. If an egg drops from the Nth floor or above, it will break. If it is dropped from any floor below, it will break. You’re given two eggs. Find N, while minimizing the number of drops for the worst case. The worst case is when N = height/2 - 1.

• I was bamboozled by this problem.

6.6 There are 100 closed lockers in a hallway A man begins by opening all 100 lockers. Next, he closes every second locker. Then, on his third pass, he toggles every third locker. This process continues for 100 passes, such that on each pass i, the man toggles every ith locker. After his 100th pass in the hallway, in which he toggles only locker #100, how many lockers are open? Count the parity for the number of factors.

• Stopped solving the problem a step too early.

Chapter 7: Mathemathics and Probability

Do NOT sleep on this section. Probably the toughest section of the book.

7.1 You have a basketball hoop and someone says that you can play one of two games. Game 1: You get one shot to make the hoop. Game 2: You get three shots and you have to make two of three shots. If p is the probability of making a particular shot, for which values of p should you pick one game or the other? $p$ vs. $3p^2(1-p)+p^3$. Solve for $p$.

7.2 There are three ants on different vertices of a triangle. What is the probability of collision (between any two of them) if they start walking on the sides of the triangle? Assume that each ant randomly picks a direction, with either direction being equally likely to be chosen, and that they walk at the same speed. Similarly, find the probability of collision with n ants on an n-vertex polygon. $1-(\frac{1}{2})^n$. The problem becomes more difficult if you have a 3d shape that is not a polygon.

• Off by one error, should be $1-(\frac{1}{2})^{n-1}$

7.3 Given two lines on a Cartesian plane, determine whether the two lines would intersect. Just check their slope … ?

• Ask a lot of questions, a lot of unknowns. Clarify them. How is the line represented?
  • Don’t assume that the slope and y-intercepts are integers, and design the class using object oriented design.
  • Consider trade offs between data structures
  • Include an error tolerance, which is an epsilon

7.4 Write methods to implement the multiply, subtract, and divide operations for integers. Use only the add operator. Multiply but adding in a for loop. How do you multiply by a negative number though?

• Really important question
• Divide is very tricky

7.5 Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis.

• Detail oriented question, practice this

7.6 Given a two-dimensional graph with points on it, find a line which passes the most number of points.

• Tough question, remember doing it for the Google foo.bar challenge.

7.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7. I’m assuming that there’s a better way than to just use brute force.

• What a tricky problem…

Chapter 8: Object-Oriented Design

• I am extremely weak and unconfident in this.
• Handle ambiguity. Ask clarifying questions and leave nothing to interpretation. Ask who is going to use it and how they are going to use it. The six W’s who, what, where, when, how, why. Define the core objects. Analyze relationships. Which objects are members of which other objects?
• Inheritance? many to many or one to many? Investigate Actions. What actions will the objects do?
• Design Patterns: Singleton and Factory Method design patterns especially useful for interviews.
• Singleton class: singleton pattern ensures that a class has only one instance and ensures access to the instance through the application.
• Factory method: The Factory Method offers an interface for creating an instance of a class, with its subclasses deciding which class to instantiate.

8.1 Design the data structures for a generic deck of cards. Explain how you would subclass the data structures to implement blackjack. What does it mean to “subclass the data structures?”. Need to have an array that represents the deck. Have an inner class Card, which tells you the suite and rank of a card. Also have a class Hand, which is a collection of Card objects. The Deck object needs to have a Deal function, and a Shuffle function. I think that should be the basic functionality of the Deck class. For blackjack, we need to have a deck, and Players that represent a game. Player objects will have a Hand and an integer representing their bet side and their amount of money left. The Blackjack object will have an integer representing the table stakes. One player will be designated as the dealer, and Player objects will have hit and stand functions.

• Clarify what the interviewer means by “generic”
• Enums in Python?

8.2 Imagine you have a call center with three levels of employees: respondent, manager, and director. An incoming telephone call must be first allocated to a respondent who is free. If the respondent can’t handle the call, he or she must excalate the call to a manager. If the manager is not free or not able to handle it, then the call should be escalated to a director. Design the classes and data structures for this problem. Implement a method dispatchCall() which assigns a call to the first available employee. Create a “master” class and call it Dispatcher. Create three classes Respondent, Manager, and Director. Have three queues in the Dispatcher class, and pull from the front of each queue in the hierarchy that is described. When an employee is finished with his/her call. Maybe have an Employee class as well that all three types of Employees inherit from.

• Singleton class
• Other methods are possible too.

8.3 Design a musical jukebox using object-oriented principles. Have a circularly linked list that stores pointers to the mp3 files. Have a Jukebox class with a scroll() method. Have a waitForPayment() method.

• This one seems easy, seems boring to implement though because it’s tough to play music through Python.
• About a hundred different questions you could ask about the specific design of the jukebox, this is important!
• Forgot about queueing up the song.
• You could also introduce users.

8.4 Design a parking lot using object-oriented principles.

• Have a parking lot class
• Keep track of cars entering using a dictionary, and who has paid
• Keep track of capacity
• Keep track of empty parking spots
  • Idea is you want to fill up spaces closer to the entrance/exit before you go into deeper storage.
• Consider different types of vehicles and what spots they can take.
  • Entails creating a vehicle class
• Have polymorphism and extending classes

8.5 Design the data structures for an online book reader system.

• Store the books
• Store the pages of the books
• Have readers request pages.
• Membership system
• Allow for page turning, removing books, etc.

8.6 Implement a jigsaw puzzle Design the data structure and explain an algorithm to solve the puzzle. You can assume that you have a fitsWith method in which when passed two puzzle pieces, returns true of the two pieces belong together.

• Such a tedious and difficult problem

8.7 Explain how you would design a chat server. In particular, provide details about the various backend components, classes, and methods. What would be the hardest problem to solve?

• Sweet mother of pearl …

8.8 Othello is played as follows: Each Othello piece is white on one side and black on the other. Whne a piece is surrounded by its opponents on both the left and right sides, or both the top and bottom, it is said to be captured and its color is flipped. On your turn, you must capture at least one of your opponent’s pieces. The game ends when either user has no more valid moves. The win is assigned to the person with the most pieces. Implement the object-oriented design for Othello.

8.9 Explain the data structures and algorithms that you would use to design an in-memory file system. Illustrate with an example in code where possible.

8.10 Design and implement a hash table which uses chaining (linked lists) to handle collisions. How is this object oriented design though?

• This one seems pretty doable

Chapter 9: Recursion and Dynamic Programming

Know how and when to use Bottom-up recursion vs Top-down recursion. Before diving into recursive code, ask yourself how hard it would be to implement it iteratively, and discuss the trade-offs with your interviewer.

9.1 A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. Create the subproblem $F(n)$, which is defined as the number of ways that the child can reach the end starting $n$ steps from finish.

• They said that $n=100$ should give us overflow, but I haven’t experienced that.

9.2 Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0,0) to (X,Y)? Follow up: Imagine certain spots are “off limits”, such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right. You can use the binomial theorem, but for the follow up, you need to use dynamic programming. Define the subproblem as $F(a,b)$ as the number of ways that you can get to $(x,y)$ starting from $(a,b)$ without using the forbidden set.

• Might want to brush up on binomial coefficients.

9.3 A magic index in an array $A[0,…,n-1]$ is defined to be an index such that $A[i]=i$. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A. Follow up: What if the values are not distinct?

9.4 Write a method to return all subsets of a set. Define the subproblem $F(n)$ as all subsets using the elements up to element $n$. Is there a way to do this that isn’t brute force? Maybe clever caching?

• It seems that all these combinatorics questions are just done the brute force way.
• My solution is extremely space inefficient.
  • But then again this does take exponential space anyways.
• This only works if the structure passed in is actually a set.
  • Interesting followup on how to remove duplicates in an array.
• Tricky to get the duplicates correct.

9.5 Write a method to compute all permutations of a string. Is there any good way to do this other than brute forcing it? Clever caching perhaps?

• CTCI solution does not account for duplicate permutations
  • Somewhat challenging to get those.

9.6 Implement an algorithm to print all valid combinations of n-pairs of parentheses.

• After two iterations, found a solution, but not the most efficient because had to check for duplicates.
• Catalan numbers
• CTCI solution is really elegant, but need to understand why this one doesn’t have to check for duplicates.
• Grok the CTCI solution and reimplement it.
• Great question.

9.7 Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.

9.8 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. FFT, generating polynomials, look at coefficient. We could possibly use dynamic programming.

• They used dynamic programming, nothing to do with FFT
• Good challenge to do with FFT
• Dynamic programming
• Can easily extend to give you all possible ways, instead of just counting.
• The FFT is used when you have a fixed amount of each denom.

9.9 Write an algorithm to print all ways of arranging eight queens on an 8x8 chess board so that none of them share the same row, column, or diagonal. In this case, “diagonal” means all diagonals, not just the two that bisect the board. Not sure about this one.

9.10 You have a stack of n boxes, with widths $w_i$, heights $h_i$, and depths $d_i$. The boxes cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly larger than the box above it in width, height, and depth. Implement a method to build the tallest stack possible, where the height of a stack is the sum of the heights of each box. Order the boxes in terms of strictly increasing size. Boxes with no strict relationship can be ordered arbitrarily. Then, this becomes the knapsack problem.

9.11 Given a boolean expression consisting of the symbols 0, 1, &, |, and ^, and a desired boolean result value result, implement a function to count the number of ways of paranthesizing the expression such that it evaluates to result.

9.12 CodeSignal Ebay/Stubhub coding challenge. Alice Bob play the remove pairs game.

Chapter 10: Scalability and Memory Limits

Can be among the easiest questions.

• Step 1:
  • Make believe. Pretend that all the data can all fit on one machine and there are no memory limitations. Use this solution as the outline.
• Step 2: Get real.
  • How much data can you fit on one machine, and what problems will occur when you split the data up?
• Step 3: Solve problems.
  • Think about how to solve the issues in step 2. The important metrics: Hard drive space, memory, internet transfer latency. Divide up large amounts of data can be done by order of appearance, by hash value, by actual value, or arbitrarily.

10.1 Imagine you are building some sort of service that will be called by up to 1000 client applications to get simple end-of-day stock price information (open, close, high, low). You may assume that you already have the data, and you can store it in any format you wish. How would you design the client-facing service which provides the information to client applications? You are responsible for the development, rollout, and ongoing monitoring and maintenance of the feed. Describe the different methods you considered and why you would recommend your approach. Your service can use any technologies you wish, and can distribute the information to the client applications in any mechanism you choose. I only have 4 doubles per stock, and we can safely say that there are not more than 10,000 stocks. For that reason, an in memory key value store would suffice…? No way it’s that simple…

• The Framework
  • Client ease of use: want the service to be easy for the clients to implement and useful for them.
  • Ease for ourselves: Cost of implementation as well as cost of maintenance.
  • Flexibility for future demands: Need to consider future costs
  • Scalability and Efficiency: Don’t want to overly burden our service.
• Completely missed everything on this question

10.2 How would you design the data structures for a very large social network like Facebook or LinkedIn? Describe how you would design an algorithm to show the connection, or path, between two people (e.g Me -> Bob -> Susan -> Jason -> You).

• Simply find the adjacency matrix based on who knows who.
  • Edges would not be directed, as “knowing someone” is symmetric
  • Then can run a simple Bellman-Ford, many times.
  • The solution says to use BFS instead
• However, the “millions of users” part is the key insight of the problem. You would have to divide up the problem onto different machines.
• Follow up questions:
  • In the real world, servers fail. How does this affect you?
  • How could you take advantage of caching?
  • Do you search the end of the graph (infinite)? How do you decide when to give up?
  • In real life, some people have more freinds of friends than others, and are therefore more likely to make a path between you and someone else. How could you use this data to pick where you start traversing?

10.3 Given an input file with four billion non-negative integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1GB of memory available for this task. Follow up: What if you have only 10MB of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers.

• I’m assuming it’s dumb to just keep track of the largest integer seen so far.
• Completely missed the spirit of this question.
• The follow up solution is quite clever.

10.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 4 kilobytes of memory available, how would you print all duplicate elements in the array?

• Just use a bit vector?
• Key insight, need to design the intricacies of a bit vector.

10.5 If you were designing a web crawler, how would you avoid getting into infinite loops?

• Assign each page a sequence number
  • Never go to the same sequence number twice
• Missed the key insight: How do you define if two pages are different or the same?

10.6 You have 10 billion URLs. How do you detect the duplicate documents? In this case, assume that “duplicate” means that the URLs are identical.

• How much memory do you have? Couldn’t you just do it the brute force way.
• Otherwise, you would have to use recursive hashing.
  • Brush up on recursive hashing!
• Completely missed this problem.

10.7 Imagine a web server for a simplified search engine. This system has 100 machines to respond to search queries, which may then call out using processSearch(string query) to another cluster of machines to actually get the result. The machine which responds to a given query is chosen at random, so you can not guarantee that the same machine will always respond to the same request. The method processSearch is very expensive. Design a caching mechanism for the most recent queries. Be sure to explain how you would update the cache when data changes.

Chapter 11: Sorting and Searching

• Radix sort
• Bubble sort
• Selection sort
• Merge sort
  • Know the in place implementation!
• Quick sort
• Binary search
  • Careful with the indices!
  • Does this change when we allow for duplicates?

11.1 You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. Do some fancy swapping thing to do it in place. Start from the ends of A and B, and merge them, putting the result in the end of A. However, this requires you to know where A ends, which should be given.

• Do we know for sure that A can exactly fit B?
• Follow up question, how would you modify this if A has maybe even more than enough space.

11.2 Write a method to sort an array of strings so that all the anagrams are next to each other. Write a comparator that compares strings based on the counts of letters.

• Wildly inefficient with current implementation.
• Need to know the character set a priori.
• Interesting discussion on why __cmp__ was deprecated, because certain structures, such as sets, don’t have strict orderings. Natural orderings…
• CTCI does a modification of bucket sort. Checking for anagramicity by sorting is inefficient. Mapping a word to its anagrams might be cool.

11.3 Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally stored in increasing order. With some fancy indexing, you could modify binary search to work on this rotated array. However, it is algorithmically/conceptually much easier via reshifting the array to be ordered.

• Off by one errors
• Create a function that transform the indexes after you find the number of offsets.
• Finding the rotation index is stupid.

11.4 Imagine you have a 20GB file with one string per line. Explain how you would sort the file. You would have to do an out of memory sorting algorithm, which sorts chunks of the file into “runs”, and then iteratively merges the runs to create a final single sorted file.

• Yay CS186!

11.5 Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string. Do binary search, but have a special case that takes care of when you hit an empty string.

11.6 Given a $MxN$ matrix in which each row and each column is sorted in ascending order, write a method to find an element. If we are at index $(i,j)$, we know that all elements to the left or top of it will be smaller, and all elements to the right and bottom of it will be larger. Traverse the diagonal and find the sliver of the matrix that you have to search the element for. $O(n)$ runtime.

• Are there duplicate elements?

11.7 A circus is designing a tower routine consisting of people standing atop one another’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 people in such a tower. This reminds me of the stacking boxes problem. Seems to be the same idea. Create a new order relation, where if both weight and height are not satisfied, then you say that they are equal. Then sort the array.

• This is a perfect example of where comparators (__cmp__) and rich comparators differ.
• Great problem
• The Schwartzian Transform
• Longest Increasing Subsequence
• Simple solution: Sort the array on heights, and then do the longest increasing subsequence on weights. $O(n^2)$
• My solution is actually better, but Python abstracts away the mechanics of the Schwartzian Transform.

11.8 Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number x (the number of values less than or equal to x). Implement the data structures and algorithms to support these operations. That is, implement the method track (int x), which is called when each number is generated, and the method getRankOfNumber(int x), which returns the number of values less than or equal to x (not including x itself). A binary search tree is my first idea, except that you track the “multiplicity” of an element, because a vanilla BST would not support duplicate elements. I sense there may be a more efficient way.

• Handle the case where you don’t find the number x.
• Can actually cache the number of elements to the left, don’t need to computer recursively.

Chapter 12: Testing

Four categories: (1) Test a real world object (like a pen) (2) Test a piece of software (3) Write test code for a function (4) Troubleshoot an existing issue.

What the interviewer is looking for:

• Big picture understanding. Do you understand what the software is really about? Can you prioritize the test cases properly? i.e. Amazon cares more about reliability of payment as opposed to placement of images.
• Knowing how the pieces fit together. Do you understand how software works, and how it might fit into a greater ecosystem? e.g. Testing Google spreadsheets requires you to test integration with gmail…etc.
• Organization. Do you approach the problem in a structured manner, or do you just spout off anythign that comes to your head? i.e. When testing a camera, break down the test cases into Taking Photos, Image Management, Settings, etc.
• Practicality. Can you actually create reasonable testing plans? Testing plans need to be feasible and realistic for a company to implement.

Steps for testing

• Step 1: Who will use it? And why?
• Step 2: What are the use cases?
• Step 3: What are the bounds of use?
• Step 4: What are the stress/failure conditions?
• Step 5: How would you perform the testing?
• Step 6: What are the test cases? How would you perform the testing?

Testing a Piece of Software

• Manual vs. Automated Testing
• Black Box Testing vs. White Box Testing
• Step 1: Define the test cases. The normal case, the extremes, nulls and “illegal” input, and strange input.
• Step 2: Define the expected result.
• Step 3: Write test code

Troubleshooting Questions

• Step 1: Understand the Scenario
• Step 2: Break down the problem
• Step 3: Create Specific, Manageable Tests

12.1 Find the mistake(s) in the following code:

• Yeah yeah yeah, code reviews, and what to look for.

12.2 You are given the source to an application which crashes when it is run. After running it ten times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

• Random variable
• Uninitialized variable
• Memory leak
• External dependencies
• To Debug
  • Who is running it?
  • What are they doing with it?
  • What kind of application is it?
• Maybe specific components or scenarios crash it.
• Process of elimination
  • Close down all other applications on the system.
  • Track resource usage carefully
  • Run it on a different machine
• Use tools to check for specific situations
  • cgdb
• Do you approach this in a calm, methodical way?

12.3 We have the following method ued in a chess game: boolean canMoveTo(int x, int y). This method is part of the Piece class and returns whether or not the piece can move to a position (x,y). Explain how you would test this method.

• Look up a game of chess, and at each stage, print the output of canMoveTo
• Pass in negative integers for x and y
• Check to see if returns true for occupied spaces
• If accounts for check, checkmate, en passant, castling, rules regarding castling
• Extreme case validation
  • Negative numbers
  • Numbers greater than height and width
  • Completely full board
  • Empty or nearly empty board
  • Far more white pieces than black, vice versa.
• General testing
  • Check the most important cases
  • Impossible to enumerate them all

12.4 How would you load test a webpage without using any test tools?

• Criteria
  • Response time
  • Through put
  • Resource utilization
  • Max load that the system can bear
• Write a multithreaded program w/ thousands of threads, where each thread acts asa real-world user loading the page. For each use, programmatically measure response time, data I/O etc.

12.5 How would you test a pen?

• Who will be using the pen?
• What will they be doing with it?
• Specify…
• What kind of tip does it have?
• The key here is “structure”
• Fact check
• Intended use
• Safety
• Unintended uses

12.6 How would you test an ATM in a distributed banking system?

Chapter 13: C and C++

• All data members are private by default in C++, you can change that using the “public” keyword.
• Constructor, default constructor, deconstructor
• Because functions are resolved at compile time, and are statically binded, we need to explicitly state virtual functions in child class methods.
• In another case, when you want a superclasses’ method to be left for implementation in a subclass, then you declare that method to be virtual.
  • But making the method a “pure virtual function” does not allow you to instantiate it.
• Virtual destructor: Define a destructor to be virtual if we also want the subclass to be cleaned up.
• Default values work the same as in Python
• Operator overloading allows you to perform operations on two classes that would otherwise not allow it.
• Pointer: holds the address of a variable
• Reference (&): An alias for an object and does not have memory of its own. Changing it will change the “reference”
  • References cannot be set to null and cannot be reassigned.
• Pointer arithmetic
• Templates: Apply the same class to different data types.

Notes from cplusplus.com’s tutorial

• cout is part of the standard library, and all the elements in the standard library are declared within what is called a namespace: the namespace std.

GeeksForGeeks commonly asked C++ interview questions

Set 1

What the difference between declaration and definition of a variable/function?

What are different storage class specifiers in C?

What is scope of a variable? How are variables scoped in C?

How would you print “Hello World?” without semicolon?

When should we use pointers in a C program?

What is a NULL pointer?

What is Dangling pointer?

What is memory leak? Why should it be avoided?

What are local static variables? What is their use?

What are static functions? What is their use?

Set 2

What are main characteristics of C language?

What is difference between i++ and ++i?

What is l-value?

How to write your own sizeof operator?

How will you print numbers from 1 to 100 without loop?

What is volatile keyword?

Can a variable be both const and volatile?

Set 3

Write down the smallest executable code?

What are entry control and exit control loops?

Why pre-processor directive does not have a semi-colon at last?

What is the difference between the header file within angular braces <> and double quotes ""?

What is the difference between near, far, and huge pointers?

Why does “type demotion” exist replacing “type promotion”? Also, would it consume less space/resources compared to type promotion?

What are stack and heap areas?

Difference between #include in C and import in Java?

Difference between ++*p, *p++, and *++p?

Explain deep copy and shallow copy with examples?

13.1 Write a method to print the last K lines of an input file using C++.

13.2 Compare and contrast a hash table and an STL map. How is hash table implemented? If the number of inputs is small, which data structure options can be used instead of a hash table?

13.3 How do virtual functions work in C++?

• Used with inheritance
• Called according to the type of object pointed or referred, not according to the type of pointer or reference.
• Resolved late, at runtime.
• You need to following for C++ run-time polymorphism:
  • Base class and derived class
  • Function with the same name in base class and derived class
  • Pointer or reference of base class type pointing or referring to an object of derived class.
• Depends on a “vtable” or “Virtual Table”. If any function of a class is declared to be virtual, a vtable is constructed which stores addresses of the virtual functions of this class.
• The compiler also adds a hidden vptr variable in all such classes which points to the vtable of that class.
• If a virtual function is not overridden in the derived class, the vtable of the derived class stores the address of the function in its parent class.
• The vtable is used to resolve the address of the function when the virtual function is called.
• Dynamic binding in C++ is performed through the vtable mechanism.
• Thus, when we assign the derived class object to the base class pointer, the vptr variable points to the vtable of the derived class. This assignment ensures that the most derived virtual function gets called.

13.4 What is the difference between deep copy and shallow copy? Explain how you would use each.

• Shallow copy copies all the member values from one object to another. A deep copy does all this and also deep copies any pointer objects.
• Shallow copy may cause a lot of programming runtime errors, especially with the creation and deletion of objects.
• Shallow copy is mostly used when there is a need to pass information about a complex structure without actual duplication of data.
  • Careful with the destruction of objects in shallow copy.
• IRL, shallow copy is rarely used. Deep copy should mainly be used, especially when the size of the copied object is small.

13.5 What is the significance of the keyword “volatile” in C?

• Informs the compiler that the value of the variable it is applied to can change from the outside, without any update done by the code.
  • Can be changed by the OS, hardware, or another thread
• Thus, compiler will need to reload the value each time from memory.
• Volatile variables are not optimized, which can be very useful.
• To prevent the compilers from doing optimizations, we can use the volatile keyword.

13.6 Why does a destructor in base class need to be declared virtual?

• We want the destructor of the most derived class is called.

13.7 Write a method that takes a pointer to a Node structure as a parameter and returns a complete copy of the passed in data structure. The Node data structure contains two pointers to other Nodes.

13.8 Write a smart pointer class. A smart pointer is a data type, usually implemented with templates, that simulates a pointer while also providing automatic garbage collection. It automatically counts the number of references to a SmartPointer<T*> object and frees the object of type T when the reference count hits zero.

13.9 Write an aligned malloc and free function that supports allocating memory such that the memory address returned is divisible by a specific power of two. Example: align_malloc(1000,128) will return a memory address that is a multiple of 128 and that points to memory of size 1000 bytes. aligned_free() will free memory allocated by align_malloc.

13.10 Write a function in C called my2DAlloc which allocates a two-dimensional array. Minimze the number of calls to malloc and make sure that the memory is accessible by the notation arr[i][j].

Chapter 14: Java

• The final keyword in Java has different meanings depending on whether it is applied to a variable, class, or method.
  • variable: the value cannot be changed once it is initialized
  • method: the method cannot be overwritten by a subclass
  • class: this class cannot be sublclassed
• finally keyword is used in with a try/catch block to ensure that a final piece of code is executed.
• finalize: The automatic garbage collector calls finalize before finally destroying the object.
• Method overloading: A method is overloaded when there are different versions of the method each with differing arguments.
• Method overriding: A method is overrided when a method is a redefinition of a method in the superclass.
• Collection Framework:
  • ArrayList
  • Vector: A synchronized ArrayList
  • LinkedList: Good demonstration of iterators
  • HashMap

14.1 In terms of inheritance, what is the effect of keeping a constructor private?

14.2 In Java, does the finally block get executed if we insert a return statement inside the try block of a try-catch-finally?

14.3 What is the difference between final, finally, and finalize?

14.4 Explain the difference between templates in C++ and generics in Java.

14.5 Explain what object reflection is in Java and why it is useful.

14.6 Implement a CircularArray class that supports an array-like data structure which can be efficiently rotated. The class should use a generic type, and should support iteration via the standard for (Obj o : circularArray) notation.

Chapter 14.a Python

• Namespaces
• Threading and locks
• PriorityQueues

Chapter 15: Databases

• Denormalized vs. Normalized Databases
  • Normalized databases: minimize redundancy
    • Relational databases
  • Denormalized databases: optimize read time
    • Store the data in multiple tables, commonly used to create highly scalable systems
• A bunch of SQL syntax stuff
• Small database design
  • Step 1: Handle ambiguity.
  • Step 2: Define the Core Objects
  • Step 3: Analyze relationships
  • Step 4: Investigate Actions
• Large database design
  • Need to think query about how to denormalize data.

15.1 Write a SQL Query to get a list of tenants who are renting more than one apartment.

15.2 Write a SQL Query to get a list of all buildings and the number of open requests (Requests in which status equals Open.)

15.3 Building #11 is undergoing a major renovation. Implement a query to close all requests from apartments in this building.

15.4 What are the different types of joins? Please explain how they differ and why certain types are better in certain situations.

• Inner Join
• Cartesian Join
• Outer Join
• Grace Hash Join
• Sort Merge Join

15.5 What is denormalization? Explain the pros and cons.

• Having duplicate data in tables in order to make joins more efficient

15.6 Draw an entity relationship diagram for a database with companies, people, and professionals (people who work for companies).

15.7 Imagine a simple database storing information for students’ grades. Design what this database might look like and provide a SQL query to return a list of the honor roll students (top 10%), sorted by their grade point average.

Chapter 16: Threads and Locks

A bunch of Java specific stuff that I am too lazy to learn.

• Every thread in Java is created and controlled by a unique object of the java.lang.Thread class. When a standalone application is run, a user thread is automatically created to execute the main() method. This thread is called the main thread.
• Can implement threads in one of two ways:
  • Implement the java.lang.Runnable interface
  • Extending the java.lang.Thread class
• Blah blah a bunch of Java stuff
• Deadlock, all four of these conditions must be met
  • Mutual exclusion: Only one process can access a resource at a given time. (Or, more accurately, there is limited access to a resource.)
  • Hold and Wait: Processes already holding a resource can request additional resources, without relinquishing their current resources.
  • No preemption: One process cannot forcibly remove another process’ resource.
  • Circular wait: Two or more processes form a circular chain where each process is waiting on another resource in the chain.

16.1 What’s the difference between a thread and a process?

• Related but fundamentally different
• Process is an instanfe of a program in execution.
  • Independent entity to which system resources are allocated. (CPU and Memory)
  • Each process is executed in a separate address space, one process cannot access the variables and data structures of another process.
  • If a process wishes to access another process’ resources, inter-process communications have to be used. These include pipes, files, sockets, and other forms.
• A thread exists within a process and shares the process’ resources (including its heap space).
  • Multiple threads exists within a process will share the same heap space.
  • Very different from processes, who cannoy directly access the memory of another process.
  • Each thread has its own registers and stack, but other threads can read and write heap memory.
• A thread is a particular execution path of a process. When one thread modifies a process resource, the change is immediately visible to sibling threads.

16.2 How would you measure the time spent in a context switch?

• Hard problem

16.3 In the famous dining philosophers problem, a bunch of philosophers are sitting around a circular table with one chopstick between each of them. A philosopher needs both chopsticks to eat, and always picks up the left chopstick before the right one. A deadlock could potentially occur if all the philosophers reached for the left chopstick at the same time. Using threads and locks, implement a simultion of the dining philosophers problem that prevents deadlocks.

16.4 Design a class which provides a lock only if there are no possible deadlocks.

• Implement deadlock detection algorithm, check for cycles and stuff in dependency graph.
• Wait-kill protocol

16.5 Suppose we have the following code:

public class Foo { 
	public Foo() {...}
	public void first() {...}
	public void second() {...}
	public void third() {...}
}

The same instance of Foo will be passed to three different threads. ThreadA will call first, threadB will call second, and threadC will call third. Design a mechanism to ensure that first is called before second and second is called before third.

16.6 You are given a class with synchronized method A and a normal method B. If you have two threads in one instance of a program, can they both execute A at the same time? Can they execute A and B at the same time?

• They can access A and B at the same time, but not both access A.

Chapter 17: Moderate

17.1 Write a function to swap a number in place (that is, without temporary variables). Classic problem, store sum, and the decompose.

• Such a simple solution that I couldn’t come up with on my own.
• There is also a solution that uses bit manipulation.

17.2 Design an algorithm to figure out if someone has won a game of tic-tac-toe. You want to check in a 3x3 grid, if there are any straight up and down lines and diagonals. Seems like a pretty straightforward problem.

• Critical: Understanding tradeoffs between the solutions based on the use cases, and being able to code in a clean and maintainable way.

17.3 Write an algorithm which computes the number of trailing zeros in n factorial. You want to count the number of twos and fives in the prime factorization of n. But because we are bottlenecked by the number of fives in the prime factorization, we just need to count those.

• First count the multiples of 5, then count the multiples of 25, etc.
• Trivial to do brute force, tough to do elegantly

17.4 Write a method which finds the maximum of two numbers. You should not use if-else or any other comparison operator.

17.5 The Game of Master Mind is played as follows: The computer has four slots, and each slot will contain a ball that is red (R), yellow (Y), green (G), or blue (B). For example, the computer might have RGGB (Slot #1 is red, Slots #2 and #3 are green, Slot #4 is blue). You, the user, are trying to guess the solution. You might, for example, guess YRGB. When you guess the correct color for the correct slot, you get a “hit”. If you guess a color that exists but is in the wrong slot, you get a “pseudo-hit”. Note thta a slot that is a hit can never count as a psuedo-hit. Write a method that, given a guess and a solution, returns the number of hits and pseudo-hits. Isn’t this trivial? First look for all hits, and then remove that color from the guess array. Then, look for all pseudo hits by having a “contains” set, or other data structure.

• Simple algorithm, but really really easy to make small mistakes.

17.6 Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n-m.

17.7 Given any integer, print an English phrase that describes the integer (e.g., “One Thousand, Two Hundred Thirty Four”) Define special rules for the tens place, and that’s it.

• Tedious, need to consider all of the special cases

17.8 You are given an array of integers (both positive and negative). Find the contiguous subsequence with the largest sum. Return the sum.

• I feel like I’ve seen this problem, and then gotten it wrong, at least 5 times.
• Make sure to account for the case of all negatives (detail oriented)
• Algorithm is simple, deriving it is not.
• There is a simple $O(n)$ linear time solution, but there is also a divide and conquer approach, which is more subtle.
• Also, need to clarify with the interviewer if a length 0 subarray is allowed.
• Tricky case of all negative numbers, the solution of this problem actually assumes the existence of positive numbers in the array, which is in neccesary.
• In Python, use sys.maxint to get the maximum integer representable, int is unbounded in Python.

17.9 Design a method to find the frequency of occurences of any given word in a book. Can’t we just use a dictionary? Is there any way to do this without a dictionary?

• Easy problem, but the interviewing will be checking for handling of null inputs.

17.10 Since XML is very verbose…

17.11 Implement a method rand7() given rand5(). That is, given a method that generates a random number between 0 and 4 inclusive, write a method that generates a random number between 0 and 6 inclusive. Have 7 variables, and keep adding the random output of rand5() until there is a clear absolute maximum. Proof by symmetry.

• Relatively prime proofs for fixed number of calls.
• They use a range and discard approach, but I think my code still works, albeit slightly less efficient.

17.12 Design an algorithm to find all pairs of integers within an array which sum to a specified value. Use two dictionaries.

• Need to clarify, does this problem allow for use of a single element twice?
• If the array is sorted, then we can do this in a more space efficient way, without the extra dictionary. However, we don’t have this guarantee in general.

17.13 Consider a simple node-like data structure called BiNode, which has pointers to two other nodes. The data structure BiNode could be used to represent both a binary tree (where node1 is the left node and node2 is the right node) or a double linked list (where node1 is the previous node and node2 is the next node). Implement a method to convert a binary search tree (implemented with BiNode) into a doubly linked list. The values should be kept in order and the operation should be performed in place (that is, on the original data structure).

public class BiNode{
	public BiNode node1, node2;
	public int data;
}

17.14 Oh, no! You have just completed a length document when you have an unfortunate Find/Replace mishap. You have accidentally removed all spaces, punctuation, and capitalization in the document. A sentence like “I reset the computer. It still didn’t boot!” would become “iresetthecomputeritstilldidntboot”. You figure that you can add back in the punctuation and capitalization later, once you get the individual words properly separated. Most of the words will be in a dictionary, but some strings, like proper names, will not. Given a dictionary (a list of words), design an algorithm to find the optimal way of “unconcatenating” a sequence of words. In this case, “optimal” is defined to be the parsing which minimizes the number of unrecognized sequences of characters. For example, the string “jesslookedjustliketimherbrother” would be optimally parsed as “JESS looked just like TIM her brother”. This parsing has seven unrecognized characters, which we have capitalized for clarity.

Chapter 18: Hard

18.1 Write a function that adds two numbers. You should not use + or any arithmetic operators. I have a feeling that this has to do with bit manipulation.

18.2 Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each of the 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect. What is the representation of the cards? Why not just actually shuffle the cards as you would in the physical world? Is there a way to shuffle it provably perfectly? Take the RNG, and use it to randomly generate to an index that has not yet been populated by a card. Repeat until no slots remaining.

• Shuffle a subarray, and swap the unshuffled element
• Need to motivate the answer, prove it rigorously
• DJPIOOYA (Don’t just pull it out of your ass)

18.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. Do you have access to a RNG? If so, trivial, flip a coin for each element.

• Think in a way similar to problem 18.2

18.4 Write a method to count the number of 2s that appear in all the numbers between 0 and n (inclusive) Iteratively keep increasing until you hit $n$. Order by “all numbers you can make with 2 in the ith most significant digit”.

• Start with a brute force solution, thoroughly test your code.

18.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. If the operation will be repeated many times for the same file (but different pairs of words), can you optimize your solution?

18.6 Describe an algorithm to find the smallest one million numbers in one billion numbers. Assume that the computer memory can hold all one billion numbers. Do a quick select type algorithm where you randomly select a pivot.

• Sorting is the slowest
• Use heaps
• Selection Rank is the fastest

18.7 Given a list of words, write a program to find the longest word made of other words in the list.

18.8 Given a string s and an array of smaller strings T, design a method to search s for each small string in T. The brute force way wouldn’t be too bad.

18.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.

• Continually rebalance trees.

18.10 Given two words of equal length that are in a dictionary, write a method to transform one word to another word by changing only one letter at a time. The new word you get in each step must be in the dictionary. Create a graph whose nodes are words and who are connected via edges, and connected if and only if there is one flip distance from the two words. Then do BFS or DFS on this graph.

18.11 Imagine you have a square matrix, where each cell (pixel) is either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels. Don’t really even understand the problem.

18.12 Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.

18.13 Given a list of millions of words, design an algorithm to create 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). The words need not be chosen consecutively from the list, but all rows must be the same length and all columns must be the same height.