The book - cracking the coding interview has list of questions. The list of questions and solutions is not comprehensive, but I guess that is the point. Coding interviews are about judging your approach to problems rather than specific solutions. I found that some of the problems were quite simple compared to the difficulty level currently in force at various companies. In particular would like to see more dynamic programming problems, but I think the author covers all the main questions, which sharpens our mind to focus on the problem solving, and is a very good starting point, which covers almost 80-90% problem solving exercises.
You can purchase the book from here:
Now lets see the index, covered in blog. Its in no way is as good as book, but I have logged these posts as my notes and faster web access.
Chapter 1 | Arrays and Strings
1.1 Implement an algorithm to determine if a string has all uniquecharacters. 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 stringwithout using any additional buffer. NOTE: One or two additional variables are fine.An extra copy of the array is not.FOLLOW UP Write the test cases for this method.
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 4bytes, 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 andcolumn is set to 0.
1.8 Assume you have a method isSubstring which checks if one word is a substring ofanother. 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”).
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?
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, givenonly access to that node.EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->eResult: nothing is returned, but the new linked list looks like a->b->d->e
2.4 You have two numbers represented by a linked list, where each node contains a singledigit. The digits are stored in reverse order, such that the 1’s digit is at the head ofthe list. Write a function that adds the two numbers and returns the sum as a linkedlist.EXAMPLE Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)Output: 8 -> 0 -> 8
2.5 Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.DEFINITIONCircular linked list: A (corrupt) linked list in which a node’s next pointer points to anearlier node, so as to make a loop in the linked list.EXAMPLE input: A -> B -> C -> D -> E -> C (the same C as earlier)output: C
Chapter 3 | Stacks and Queues
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 functionmin which returns the minimum element? Push, pop and min should all operate inO(1) time.
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 exceedssome threshold. Implement a data structure SetOfStacks that mimics this.SetOfStacks should be composed of several stacks, and should create a new stack oncethe previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() shouldbehave identically to a single stack (that is, pop() should return the same values as itwould if there were just a single stack).FOLLOW UP Implement a function popAt(int index) which performs a pop operation on a specificsub-stack.
3.4 In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of differentsizes which can slide onto any tower. The puzzle starts with disks sorted in ascendingorder of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints:(A) Only one disk can be moved at a time.(B) A disk is slid off the top of one rod onto the next rod.© A disk can only be placed on top of a larger disk.Write a program to move the disks from the first rod to the last using Stacks.
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 assumptions about how the stack is implemented. The following are the only functions thatshould be used to write this program: push | pop | peek | isEmpty.
Chapter 4 | Trees and Graphs
4.1 Implement a function to check if a tree is balanced. For the purposes of this question,a balanced tree is defined to be a tree such that no two leaf nodes differ in distancefrom the root by more than one.
4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
4.3 Given a sorted (increasing order) array, write an algorithm to create a binary tree withminimal height.
4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists).
4.5 Write an algorithm to find the ‘next’ node (i.e., in-order successor) of a given node ina 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 nodesin a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is notnecessarily a binary search tree.
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. Note that it can be any path in the tree - it does not have to start at the root.
Chapter 5 | Bit Manipulation
5.1 You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write amethod to set all bits between i and j in N equal to M (e.g., M becomes a substring ofN located at i and starting at j).EXAMPLE:Input: N = 10000000000, M = 10101, i = 2, j = 6Output: N = 10001010100
5.2 Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binaryrepresentation. 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 samenumber 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. Input: 31, 14 Output: 2
5.6 Write a program to swap odd and even bits in an integer with as few instructions aspossible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).
5.7 An array A[1…n] contains all the integers from 0 to n except for one numberwhich is missing. In this problem, we cannot access an entire integer in A witha single operation. The elements of A are represented in binary, and the onlyoperation we can use to access them is “fetch the jth bit of A[i]”, whichtakes constant time.Write code to find the missing integer. Can you do it in O(n) time?
Chapter 6 | Brain Teasers
6 1 Add arithmetic operators (plus, minus, times, divide) to make the following expression true: 3 1 3 6 = 8 You can use any parentheses you’d like
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? Prove your answer (by providing an example, or showing why it’s impossible)
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?NOTE: The jugs are oddly shaped, such that filling up exactly ‘half’ of the jug would be impossible
6 4 A bunch of men are on an island A genie comes down and gathers everyone together 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 hatFOLLOW UP Prove that your solution is correct
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
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?
Chapter 7 | Object Oriented Design
7.1 Design the data structures for a generic deck of cards Explain how you would subclass it to implement particular card games
7.2 Imagine you have a call center with three levels of employees: fresher, technical lead (TL), product manager (PM) There can be multiple employees, but only one TL or PM An incoming telephone call must be allocated to a fresher who is free If a fresher can’t handle the call, he or she must escalate the call to technical lead If the TL is not free or not able to handle it, then the call should be escalated to PM Design the classes and data structures for this problem Implement a method getCallHandler()
7.3 Design a musical juke box using object oriented principles
7.4 Design a chess game using object oriented principles
7.5 Design the data structures for an online book reader system
7.6 Implement a jigsaw puzzle Design the data structures and explain an algorithm to solve the puzzle
7.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 problems to solve?
7.8 Othello is played as follows: Each Othello piece is white on one side and black on the other When 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, and the win is assigned to the person with the most pieces Implement the object oriented design for Othello
7.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
7.10 Describe the data structures and algorithms that you would use to implement a garbage collector in C++
Chapter 8 | Recursion
8.1 Write a method to generate the nth Fibonacci number.
8.2 Imagine a robot sitting on the upper left hand corner of an NxNgrid. The robot can only move in two directions: right and down. Howmany possible paths are there for the robot?FOLLOW UP Imagine certain squares are “off limits”, such that the robot cannot 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 openedand closed) combinations of n-pairs of parentheses.EXAMPLE:input: 3 (e.g., 3 pairs of parentheses)output: ()()(), ()(()), (())(), ((()))
8.6 Implement the “paint fill” function that one might see on manyimage editing programs. That is, given a screen (represented by a 2dimensional array of Colors), a point, and a new color, fill in thesurrounding area until you hit a border of that color.
8.7 Given an infinite number of quarters (25 cents), dimes (10 cents),nickels (5 cents) and pennies (1 cent), write code to calculate thenumber of ways of representing n cents.
8.8 Write an algorithm to print all ways of arranging eight queens ona chess board so that none of them share the same row, column or diagonal.
Chapter 9 | Sorting and Searching
9.1 You are given two sorted arrays, A and B, and A has a large enoughbuffer at the end to hold B. Write a method to merge B into A insorted order.
9.2 Write a method to sort an array of strings so that all the anagrams are next to each other.
9.3 Given a sorted array of n integers that has been rotated an unknownnumber of times, give an O(log n) algorithm that finds an element inthe array. You may assume that the array was originally sorted inincreasing 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 sortingalgorithm would you use to sort the file and why?
9.5 Given a sorted array of strings which is interspersed with emptystrings, write a method to find the location of a given string.Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”,“”, “”, “dad”, “”, “”] will return 4Example: 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 amethod to find an element in it.
9.7 A circus is designing a tower routine consisting of people standingatop one another’s shoulders. For practical and aesthetic reasons,each person must be both shorter and lighter than the person belowhim or her. Given the heights and weights of each person in thecircus, write a method to compute the largest possible number ofpeople 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)
Chapter 10 | Mathematical
10 1 You have a basketball hoop and someone says that you can play 1 of 2 gamesGame #1: You get one shot to make the hoopGame #2: You get three shots and you have to make 2 of 3 shotsIf 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 collision (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.3 Given two lines on a Cartesian plane, determine whether the two lines would intersect
10.4 Write a method to implement *, - , / operations You should use only the + operator
10.5 Given two squares on a two dimensional plane, find a line that would cut these two squares in half
10 6 .Given a two dimensional graph with points on it, find a line which passes the most number of points
10.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7
Chapter 11 | Testing
11.1 Find the mistake(s) in the following code:1 unsigned int i;2 for (i = 100; i <= 0; --i)3 printf(“%d\n”, i);
11.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?
11.3 We have the following method used in a chess game: boolean canMoveTo(int x, int y) x and y are the coordinates of the chess board and it returns whether or not the piece can move to that position Explain how you would test this method
11.4 How would you load test a webpage without using any test tools?
11.5 How would you test a pen?
11.6 How would you test an ATM in a distributed banking system?
Chapter 12 | System Design and Memory Limits
12.1 If you were integrating a feed of end of day stock priceinformation (open, high, low,and closing price) for 5,000companies, how would you do it? You are responsible forthe development, rollout and ongoing monitoring and maintenanceof the feed. Describe the different methods you considered andwhy you would recommend your approach. The feed is delivered onceper trading day in a comma-separated format via an FTP site. Thefeed will be used by 1000 daily users in a web application.
12.2 How would you design the data structures for a very largesocial network (Facebook,LinkedIn, etc)? Describe how you woulddesign an algorithm to show the connection, or path, between twopeople (e.g., Me -> Bob -> Susan -> Jason -> You).
12.3 Given an input file with four billion integers, provide analgorithm to generate an integer which is not contained in thefile. Assume you have 1 GB of memory.FOLLOW UP What if you have only 10 MB of memory?
12.4 You have an array with all the numbers from 1 to N, where N isat most 32,000. The array may have duplicate entries and you donot know what N is. With only 4KB of memory available, how wouldyou print all duplicate elements in the array?
12.5 If you were designing a web crawler, how would you avoid getting into infinite loops?
12.6 You have a billion urls, where each is a huge page. How do you detect the duplicate documents?
12.7 You have to design a database that can store terabytes of data.It should support efficient range queries. How would you do it?
Chapter 13 | C++
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 vs. an STL map. How is a hashtable implemented?If the number of inputs is small, what datastructure options can be used instead of a hash table?
13.3 How do virtual functions work in C++?
13.4 What is the difference between deep copy and shallow copy? Explainhow you would use each.
13.5 What is the significance of the keyword “volatile” in C?
13.6 What is name hiding in C++?
13.7 Why does a destructor in base class need to be declared virtual?
13.8 Write a method that takes a pointer to a Node structure as aparameter and returns a complete copy of the passed-in datastructure. The Node structure contains two pointers to other Nodestructures.
13.9 Write a smart pointer (smart_ptr) class.
Chapter 14 | Java
14.1 In terms of inheritance, what is the effect of keeping a constructor private?
14.2 In Java, does the finally block gets 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 Suppose you are using a map in your program, how would you count the number of times the program calls the put() and get() functions?
Chapter 15 | Databases
15.1 Write a method to find the number of employees in each department.
15.2 What are the different types of joins? Please explain how theydiffer and why certain types are better in certain situations.
15.3 What is denormalization? Explain the pros and cons.
15.4 Draw an entity-relationship diagram for a database with companies,people, and professionals (people who work for companies).
15.5 Imagine a simple database storing information for students’ grades.Design what this database might look like, and provide a SQL queryto return a list of the honor roll students (top 10%), sorted bytheir grade point average.
Chapter 16 | Low Level
16.1 Explain the following terms: virtual memory, page fault, thrashing.
16.2 What is a Branch Target buffer? Explain how it can be used in reducing bubble cycles in cases of branch misprediction
16 3 Describe direct memory access (DMA) Can a user level buffer / pointer be used by kernel or drivers?
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 littleendian.
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?
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)EXAMPLEalign_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
16.10 Write a function called my2DAlloc which allocates a two dimensionalarray. Minimize the number of calls to malloc and make sure that thememory is accessible by the notation arr[i][j].
Chapter 17 | Networking
17.1 Explain what happens, step by step, after you type a URL into abrowser. 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.
17.4 What is a network / subnet mask? Explain how host A sends amessage / packet to host B when: (a) both are on same networkand (b) both are on different networks.Explain which layer makes the routing decision and how.
17.5 What are the differences between TCP and UDP? Explain how TCPhandles reliable delivery (explain ACK mechanism), flow control(explain TCP sender’s / receiver’s window) and congestion control.
Chapter 18 | Threads and Locks
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, forany 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 Suppose we have the following code:…i) Can you design a mechanism to make sure that B is executed after A, and C is executed after B?ii) Suppose we have the following code to use class Foo. We do not know how the threads will be scheduled in the OS.Can you design a mechanism to make sure that all the methods will be executed in sequence?
18.6 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?
Chapter 19 | Moderate
19.1 Write a function to swap a number in place without temporary variables.
19.2 Design an algorithm to figure out if someone has won in a game of tic-tac-toe.
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 shouldnot use if-else or any other comparison operator.
19.5 The Game of Master Mind is played as follows:The computer has four slots containing balls that are red ®,yellow (Y), green (G) or blue (B). For example, the computer mighthave RGGB (e.g., Slot #1 is red, Slots #2 and #3 are green, Slot #4is blue).You, the user, are trying to guess the solution. You might, forexample, guess YRGB. When you guess the correct color for thecorrect slot, you get a “hit”. If you guess a color that exists butis in the wrong slot, you get a “pseudo-hit”. For example, theguess YRGB has 2 hits and one pseudo hit.For each guess, you are told the number of hits and pseudo-hits.Write a method that, given a guess and a solution, returns thenumber of hits and pseudo hits.
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.
EXAMPLE
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i e , {3, -2, 4} )
19.8 Design a method to find the frequency of occurrences of any givenword in a book.
19.9 Since XML is very verbose, you are given a way of encoding it where each tag gets
mapped to a pre-defined integer value The language/grammar is as follows:
Element --> Element Attr* END Element END [aka, encode the element
tag, then its attributes, then tack on an END character, then
encode its children, then another end tag]
Attr --> Tag Value [assume all values are strings]
END --> 01
Tag --> some predefined mapping to int
Value --> string value END
Write code to print the encoded version of an xml element (passed in as string)
FOLLOW UP
Is there anything else you could do to (in many cases) compress this even further?
19.10 Write a method to generate a random number between 1 and 7, given amethod 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 specified value.
Chapter 20 | Hard
20.1 Write a function that adds two numbers. You should not use + or anyarithmetic operators.
20.2 Write a method to shuffle a deck of cards. It must be a perfectshuffle - in other words, each 52! permutations of the deck has tobe equally likely. Assume that you are given a random numbergenerator which is perfect.
20.3 Write a method to randomly generate a set of m integers from anarray of size n. Each element must have equal probability of beingchosen.
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) betweenthem in the file. Can you make the searching operation in O(1) time?What about the space complexity for your solution?
20.6 Describe an algorithm to find the largest 1 million numbers in 1billion numbers. Assume that the computer memory can hold all onebillion numbers.
20.7 Write a program to find the longest word made of other words in alist of words.EXAMPLE Input: test, tester, testertest, testing, testingtester Output: testingtester
20.8 Given a string s and an array of smaller strings T, design a methodto search s for each small string in T.
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.
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.
EXAMPLE
Input: DAMP, LIKE
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE
20.11 Imagine you have a square matrix, where each cell is filled witheither black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
20.12 Given an NxN matrix of positive and negative integers, write codeto find the submatrix with the largest possible sum.
You can purchase the book from here:
Now lets see the index, covered in blog. Its in no way is as good as book, but I have logged these posts as my notes and faster web access.
Chapter 1 | Arrays and Strings
1.1 Implement an algorithm to determine if a string has all uniquecharacters. 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 stringwithout using any additional buffer. NOTE: One or two additional variables are fine.An extra copy of the array is not.FOLLOW UP Write the test cases for this method.
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 4bytes, 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 andcolumn is set to 0.
1.8 Assume you have a method isSubstring which checks if one word is a substring ofanother. 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”).
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?
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, givenonly access to that node.EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->eResult: nothing is returned, but the new linked list looks like a->b->d->e
2.4 You have two numbers represented by a linked list, where each node contains a singledigit. The digits are stored in reverse order, such that the 1’s digit is at the head ofthe list. Write a function that adds the two numbers and returns the sum as a linkedlist.EXAMPLE Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)Output: 8 -> 0 -> 8
2.5 Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.DEFINITIONCircular linked list: A (corrupt) linked list in which a node’s next pointer points to anearlier node, so as to make a loop in the linked list.EXAMPLE input: A -> B -> C -> D -> E -> C (the same C as earlier)output: C
Chapter 3 | Stacks and Queues
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 functionmin which returns the minimum element? Push, pop and min should all operate inO(1) time.
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 exceedssome threshold. Implement a data structure SetOfStacks that mimics this.SetOfStacks should be composed of several stacks, and should create a new stack oncethe previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() shouldbehave identically to a single stack (that is, pop() should return the same values as itwould if there were just a single stack).FOLLOW UP Implement a function popAt(int index) which performs a pop operation on a specificsub-stack.
3.4 In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of differentsizes which can slide onto any tower. The puzzle starts with disks sorted in ascendingorder of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints:(A) Only one disk can be moved at a time.(B) A disk is slid off the top of one rod onto the next rod.© A disk can only be placed on top of a larger disk.Write a program to move the disks from the first rod to the last using Stacks.
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 assumptions about how the stack is implemented. The following are the only functions thatshould be used to write this program: push | pop | peek | isEmpty.
Chapter 4 | Trees and Graphs
4.1 Implement a function to check if a tree is balanced. For the purposes of this question,a balanced tree is defined to be a tree such that no two leaf nodes differ in distancefrom the root by more than one.
4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
4.3 Given a sorted (increasing order) array, write an algorithm to create a binary tree withminimal height.
4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists).
4.5 Write an algorithm to find the ‘next’ node (i.e., in-order successor) of a given node ina 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 nodesin a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is notnecessarily a binary search tree.
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. Note that it can be any path in the tree - it does not have to start at the root.
Chapter 5 | Bit Manipulation
5.1 You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write amethod to set all bits between i and j in N equal to M (e.g., M becomes a substring ofN located at i and starting at j).EXAMPLE:Input: N = 10000000000, M = 10101, i = 2, j = 6Output: N = 10001010100
5.2 Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binaryrepresentation. 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 samenumber 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. Input: 31, 14 Output: 2
5.6 Write a program to swap odd and even bits in an integer with as few instructions aspossible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).
5.7 An array A[1…n] contains all the integers from 0 to n except for one numberwhich is missing. In this problem, we cannot access an entire integer in A witha single operation. The elements of A are represented in binary, and the onlyoperation we can use to access them is “fetch the jth bit of A[i]”, whichtakes constant time.Write code to find the missing integer. Can you do it in O(n) time?
Chapter 6 | Brain Teasers
6 1 Add arithmetic operators (plus, minus, times, divide) to make the following expression true: 3 1 3 6 = 8 You can use any parentheses you’d like
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? Prove your answer (by providing an example, or showing why it’s impossible)
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?NOTE: The jugs are oddly shaped, such that filling up exactly ‘half’ of the jug would be impossible
6 4 A bunch of men are on an island A genie comes down and gathers everyone together 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 hatFOLLOW UP Prove that your solution is correct
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
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?
Chapter 7 | Object Oriented Design
7.1 Design the data structures for a generic deck of cards Explain how you would subclass it to implement particular card games
7.2 Imagine you have a call center with three levels of employees: fresher, technical lead (TL), product manager (PM) There can be multiple employees, but only one TL or PM An incoming telephone call must be allocated to a fresher who is free If a fresher can’t handle the call, he or she must escalate the call to technical lead If the TL is not free or not able to handle it, then the call should be escalated to PM Design the classes and data structures for this problem Implement a method getCallHandler()
7.3 Design a musical juke box using object oriented principles
7.4 Design a chess game using object oriented principles
7.5 Design the data structures for an online book reader system
7.6 Implement a jigsaw puzzle Design the data structures and explain an algorithm to solve the puzzle
7.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 problems to solve?
7.8 Othello is played as follows: Each Othello piece is white on one side and black on the other When 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, and the win is assigned to the person with the most pieces Implement the object oriented design for Othello
7.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
7.10 Describe the data structures and algorithms that you would use to implement a garbage collector in C++
Chapter 8 | Recursion
8.1 Write a method to generate the nth Fibonacci number.
8.2 Imagine a robot sitting on the upper left hand corner of an NxNgrid. The robot can only move in two directions: right and down. Howmany possible paths are there for the robot?FOLLOW UP Imagine certain squares are “off limits”, such that the robot cannot 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 openedand closed) combinations of n-pairs of parentheses.EXAMPLE:input: 3 (e.g., 3 pairs of parentheses)output: ()()(), ()(()), (())(), ((()))
8.6 Implement the “paint fill” function that one might see on manyimage editing programs. That is, given a screen (represented by a 2dimensional array of Colors), a point, and a new color, fill in thesurrounding area until you hit a border of that color.
8.7 Given an infinite number of quarters (25 cents), dimes (10 cents),nickels (5 cents) and pennies (1 cent), write code to calculate thenumber of ways of representing n cents.
8.8 Write an algorithm to print all ways of arranging eight queens ona chess board so that none of them share the same row, column or diagonal.
Chapter 9 | Sorting and Searching
9.1 You are given two sorted arrays, A and B, and A has a large enoughbuffer at the end to hold B. Write a method to merge B into A insorted order.
9.2 Write a method to sort an array of strings so that all the anagrams are next to each other.
9.3 Given a sorted array of n integers that has been rotated an unknownnumber of times, give an O(log n) algorithm that finds an element inthe array. You may assume that the array was originally sorted inincreasing 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 sortingalgorithm would you use to sort the file and why?
9.5 Given a sorted array of strings which is interspersed with emptystrings, write a method to find the location of a given string.Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”,“”, “”, “dad”, “”, “”] will return 4Example: 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 amethod to find an element in it.
9.7 A circus is designing a tower routine consisting of people standingatop one another’s shoulders. For practical and aesthetic reasons,each person must be both shorter and lighter than the person belowhim or her. Given the heights and weights of each person in thecircus, write a method to compute the largest possible number ofpeople 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)
Chapter 10 | Mathematical
10 1 You have a basketball hoop and someone says that you can play 1 of 2 gamesGame #1: You get one shot to make the hoopGame #2: You get three shots and you have to make 2 of 3 shotsIf 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 collision (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.3 Given two lines on a Cartesian plane, determine whether the two lines would intersect
10.4 Write a method to implement *, - , / operations You should use only the + operator
10.5 Given two squares on a two dimensional plane, find a line that would cut these two squares in half
10 6 .Given a two dimensional graph with points on it, find a line which passes the most number of points
10.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7
Chapter 11 | Testing
11.1 Find the mistake(s) in the following code:1 unsigned int i;2 for (i = 100; i <= 0; --i)3 printf(“%d\n”, i);
11.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?
11.3 We have the following method used in a chess game: boolean canMoveTo(int x, int y) x and y are the coordinates of the chess board and it returns whether or not the piece can move to that position Explain how you would test this method
11.4 How would you load test a webpage without using any test tools?
11.5 How would you test a pen?
11.6 How would you test an ATM in a distributed banking system?
Chapter 12 | System Design and Memory Limits
12.1 If you were integrating a feed of end of day stock priceinformation (open, high, low,and closing price) for 5,000companies, how would you do it? You are responsible forthe development, rollout and ongoing monitoring and maintenanceof the feed. Describe the different methods you considered andwhy you would recommend your approach. The feed is delivered onceper trading day in a comma-separated format via an FTP site. Thefeed will be used by 1000 daily users in a web application.
12.2 How would you design the data structures for a very largesocial network (Facebook,LinkedIn, etc)? Describe how you woulddesign an algorithm to show the connection, or path, between twopeople (e.g., Me -> Bob -> Susan -> Jason -> You).
12.3 Given an input file with four billion integers, provide analgorithm to generate an integer which is not contained in thefile. Assume you have 1 GB of memory.FOLLOW UP What if you have only 10 MB of memory?
12.4 You have an array with all the numbers from 1 to N, where N isat most 32,000. The array may have duplicate entries and you donot know what N is. With only 4KB of memory available, how wouldyou print all duplicate elements in the array?
12.5 If you were designing a web crawler, how would you avoid getting into infinite loops?
12.6 You have a billion urls, where each is a huge page. How do you detect the duplicate documents?
12.7 You have to design a database that can store terabytes of data.It should support efficient range queries. How would you do it?
Chapter 13 | C++
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 vs. an STL map. How is a hashtable implemented?If the number of inputs is small, what datastructure options can be used instead of a hash table?
13.3 How do virtual functions work in C++?
13.4 What is the difference between deep copy and shallow copy? Explainhow you would use each.
13.5 What is the significance of the keyword “volatile” in C?
13.6 What is name hiding in C++?
13.7 Why does a destructor in base class need to be declared virtual?
13.8 Write a method that takes a pointer to a Node structure as aparameter and returns a complete copy of the passed-in datastructure. The Node structure contains two pointers to other Nodestructures.
13.9 Write a smart pointer (smart_ptr) class.
Chapter 14 | Java
14.1 In terms of inheritance, what is the effect of keeping a constructor private?
14.2 In Java, does the finally block gets 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 Suppose you are using a map in your program, how would you count the number of times the program calls the put() and get() functions?
Chapter 15 | Databases
15.1 Write a method to find the number of employees in each department.
15.2 What are the different types of joins? Please explain how theydiffer and why certain types are better in certain situations.
15.3 What is denormalization? Explain the pros and cons.
15.4 Draw an entity-relationship diagram for a database with companies,people, and professionals (people who work for companies).
15.5 Imagine a simple database storing information for students’ grades.Design what this database might look like, and provide a SQL queryto return a list of the honor roll students (top 10%), sorted bytheir grade point average.
Chapter 16 | Low Level
16.1 Explain the following terms: virtual memory, page fault, thrashing.
16.2 What is a Branch Target buffer? Explain how it can be used in reducing bubble cycles in cases of branch misprediction
16 3 Describe direct memory access (DMA) Can a user level buffer / pointer be used by kernel or drivers?
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 littleendian.
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?
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)EXAMPLEalign_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
16.10 Write a function called my2DAlloc which allocates a two dimensionalarray. Minimize the number of calls to malloc and make sure that thememory is accessible by the notation arr[i][j].
Chapter 17 | Networking
17.1 Explain what happens, step by step, after you type a URL into abrowser. 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.
17.4 What is a network / subnet mask? Explain how host A sends amessage / packet to host B when: (a) both are on same networkand (b) both are on different networks.Explain which layer makes the routing decision and how.
17.5 What are the differences between TCP and UDP? Explain how TCPhandles reliable delivery (explain ACK mechanism), flow control(explain TCP sender’s / receiver’s window) and congestion control.
Chapter 18 | Threads and Locks
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, forany 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 Suppose we have the following code:…i) Can you design a mechanism to make sure that B is executed after A, and C is executed after B?ii) Suppose we have the following code to use class Foo. We do not know how the threads will be scheduled in the OS.Can you design a mechanism to make sure that all the methods will be executed in sequence?
18.6 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?
Chapter 19 | Moderate
19.1 Write a function to swap a number in place without temporary variables.
19.2 Design an algorithm to figure out if someone has won in a game of tic-tac-toe.
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 shouldnot use if-else or any other comparison operator.
19.5 The Game of Master Mind is played as follows:The computer has four slots containing balls that are red ®,yellow (Y), green (G) or blue (B). For example, the computer mighthave RGGB (e.g., Slot #1 is red, Slots #2 and #3 are green, Slot #4is blue).You, the user, are trying to guess the solution. You might, forexample, guess YRGB. When you guess the correct color for thecorrect slot, you get a “hit”. If you guess a color that exists butis in the wrong slot, you get a “pseudo-hit”. For example, theguess YRGB has 2 hits and one pseudo hit.For each guess, you are told the number of hits and pseudo-hits.Write a method that, given a guess and a solution, returns thenumber of hits and pseudo hits.
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.
EXAMPLE
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i e , {3, -2, 4} )
19.8 Design a method to find the frequency of occurrences of any givenword in a book.
19.9 Since XML is very verbose, you are given a way of encoding it where each tag gets
mapped to a pre-defined integer value The language/grammar is as follows:
Element --> Element Attr* END Element END [aka, encode the element
tag, then its attributes, then tack on an END character, then
encode its children, then another end tag]
Attr --> Tag Value [assume all values are strings]
END --> 01
Tag --> some predefined mapping to int
Value --> string value END
Write code to print the encoded version of an xml element (passed in as string)
FOLLOW UP
Is there anything else you could do to (in many cases) compress this even further?
19.10 Write a method to generate a random number between 1 and 7, given amethod 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 specified value.
Chapter 20 | Hard
20.1 Write a function that adds two numbers. You should not use + or anyarithmetic operators.
20.2 Write a method to shuffle a deck of cards. It must be a perfectshuffle - in other words, each 52! permutations of the deck has tobe equally likely. Assume that you are given a random numbergenerator which is perfect.
20.3 Write a method to randomly generate a set of m integers from anarray of size n. Each element must have equal probability of beingchosen.
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) betweenthem in the file. Can you make the searching operation in O(1) time?What about the space complexity for your solution?
20.6 Describe an algorithm to find the largest 1 million numbers in 1billion numbers. Assume that the computer memory can hold all onebillion numbers.
20.7 Write a program to find the longest word made of other words in alist of words.EXAMPLE Input: test, tester, testertest, testing, testingtester Output: testingtester
20.8 Given a string s and an array of smaller strings T, design a methodto search s for each small string in T.
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.
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.
EXAMPLE
Input: DAMP, LIKE
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE
20.11 Imagine you have a square matrix, where each cell is filled witheither black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
20.12 Given an NxN matrix of positive and negative integers, write codeto find the submatrix with the largest possible sum.
We run five races with five horses. The five winners race in a sixth race while the 4th and fith place finishers are eliminated from further consideration, as we have to anyways take first 3.
Now we are left with 15 horses.
6th race
Take all the fastest horses from each group and race them. The sixth race show horse is faster than all the horses that participated in the preliminary races where the 4th and 5th place horses participated and they are eliminated from further consideration. So, now we have 12 horses left, because we know who is the fastest horse, and 4th and 5th horses are removed, so 15 - 1 -2 = 12.
The other horses in the preliminary race where the 6th race show horse participated are also eliminated.
The slow horses in the preliminary race in competition of 4th and 5th horse in the 6th race are also eliminated since there are at least three remaining horses that are faster.
So, horses who lost to 4th and 5th horse of race 6 are removed, so 12 - 4 = 8
Throw the last one horse of the second fast group. 7 horse left