# Cracking The Coding Interview

From Software Engineers Wiki

## Chapter 1. Arrays and Strings

- 1.1 Determine if a string has all unique characters.
- 1.2 Reverse a null terminated string.
- 1.3 Check whether a string is a permutation of the other string.
- 1.4 Replace all spaces in a string with '%20'.
- 1.5 Perform basic string compression using the counts of repeated characters.
- 1.6 Given an image represented by an NxN matrix, rotate the image by 90 degrees.
- 1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and colum are set to 0.
- 1.8 Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using isSubstring().

## Chapter 2. Linked List

- 2.1 Remove duplicates from an unsorted linked list.
- 2.2 Find the kth to last element of a singly linked list.
- 2.3 Delete a node in the middle of a singly linked list, given only access to that node.
- 2.4 Write code to partition a linked list around a value x.
- 2.5 There are two numbers represented by a linked list. Write a function that adds the two numbers and returns the sum as a linked list.
- 2.6 Given a circular linked list, return the node at the beginning of the loop.
- 2.7 Check if a linked list is palindrome.

## Chapter 3. Stacks and Queues

- 3.1 Implement three stacks using an array.
- 3.2 Design a stack with function min() which returns the minimum element.
- 3.3 Implement a data structure SetOfStack which consists of multiple stacks with size limit.
- 3.4 Implement the Tower of Hanoi using stacks.
- 3.5 Implement a MyQueue class which implements a queue using two stacks.
- 3.6 Sort a stack in ascending order.
- 3.7 An animal shelter operating on a strictly "first in, first out" basis.

## Chapter 4. Trees and Graphs

- 4.1 Check if a binary tree is balanced.
- 4.2 N/A Find a route between two nodes in a directed graph.
- 4.3 N/A Create a binary search tree with minimal height out of a sorted array with unique integer elements.
- 4.4 Creates a linked list of all the nodes at each depth out of a binary tree.
- 4.5 Check if binary tree is a binary search tree.
- 4.6 Find the next node of a given node in a binary search tree.
- 4.7 Find the first common ancestor of two nodes in a binary tree.
- 4.8 N/A Given two binary trees T1 and T2, decide if T2 is a subtree of T1.
- 4.9 N/A Given a binary tree in which each node contains a value, print all paths which sum to a given value.

## Chapter 5. Bit Manipulation

- 5.1 Replace only bits[j:i] in a given integer N with M.
- 5.2 Print a binary representation of a real number between 0 and 1.
- 5.3 Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.
- 5.4 Meaning of
`((n & (n - 1)) == 0)`

. - 5.5 Determine that number of bits required to convert integer A to integer B.
- 5.6 Swap odd and even bits in an integer.
- 5.7 Find a missing integer in an array which contains all the integer from 0 to n, except for one number.
- 5.8 Given a black and white frame buffer, draw a horizontal line directly into the frame buffer.

## Chapter 6. Brain Teasers

- 6.1 Find a bottle with heavier pills out of 20 bottles of pills.
- 6.2 Can you cover an 8x8 chess board in which two diagonally opposite corners have been cut off with 2 square dominos?
- 6.3 With 5 quarts and 3 quarts of jugs, fill 4 quarts of water.
- 6.4 Evacuate blue-eyed people from an island when all people are logical and they know there is at least one blue-eyed, but not exactly how many.
- 6.5 Two Eggs 100 Floor Problem; There is a building of 100 floors. An egg breaks if it drops from Nth floor or above. Find N with two eggs.
- 6.6 There are 100 closed lockers. Each pass N, every N lockers are toggled, and this is repeated until 100th pass. How many lockers will be open?

## Chapter 7. Mathematics and Probability

- 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?
- 7.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? 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.
- 7.3 (N/A) Determine whether two line segments would intersect.
- 7.4 Write methods to implement the multiply, subtract, and divide operations for integers. Use only the add operator.
- 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.
- 7.6 Given a two-dimensional graph with points on it, find a line which passes the most number of points.
- 7.7 Design an algorithm to find the kth number such that the only prime factors are 3,5, and 7.

## Chapter 8. Object Oriented Design

- 8.1 Design the data structures for a generic deck of cards. Explain how you would subclass the data structures to implement blackjack.
- 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 escalate 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.
- 8.3 Design a musical jukebox using object-oriented principles.
- 8.4 Design a parking lot using object-oriented principles.
- 8.5 Design the data structures for an online book reader system.
- 8.6 Implement a jigsaw puzzle. Design the data structures and explain an algorithm to solve the puzzle. You can assume that you have a f itsWith method which, when passed two puzzle pieces, returns true if the two pieces belong together.
- 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 problems to solve?
- 8.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. 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.

## Chapter 9. Recursion and Dynamic Programming

- 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.
- 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)?
- 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.
- 9.4 Write a method to return all subsets of a set.
- 9.5 Write a method to compute all permutations of a string.
- 9.6 Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pairs of parentheses.
- 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
- 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.
- 9.10 You have a stack of n boxes, with widths w., heights hir and depths drThe 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.
- 9.11 Given a boolean expression consisting of the symbols 0,1, &, |, and A, and a desired boolean result value result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result.

## Chapter 10. Scalability and Memory Limits

- 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.
- 10.2 How would you design the data structures for a very large social network like Facebook or Linkedln? Describe how you would design an algorithm to show the connection, or path, between two people (e.g., Me -> Bob -> Susan -> Jason -> You).
- 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 1 GB of memory available for this task.
- 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?
- 10.5 If you were designing a web crawler, how would you avoid getting into infinite loops?
- 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.
- 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

- 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
- 11.2 Write a method to sort an array of strings so that all the anagrams are next to each other.
- 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 sorted in increasing order.
- 11.4 Imagine you have a 20 GB file with one string per line. Explain how you would sort the file.
- 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.
- 11.6 Given an M x N matrix in which each row and each column is sorted in ascending order, write a method to find an element.
- 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.
- 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 tox). 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).

## Chapter 12. Testing

- 12.1 Find the mistake(s) in the following code:
unsigned int i; for (i = 190; i >= 0; --i) printf("%d\n", i);

- 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?
- 12.3 We have the following method used 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 position (x, y). Explain howyou would test this method.
- 12.4 How would you load test a webpage without using any test tools?
- 12.5 How would you testa pen?
- 12.6 How would you test an ATM in a distributed banking system?

## Chapter 13. C and 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 and an STL map. How is a 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++?
- 13.4 What is the difference between deep copy and shallow copy? Explain how you would use each.
- 13.5 What is the significance of the keyword "volatile" in C?
- 13.6 Why does a destructor in base class need to be declared virtual?
- 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.
- 13.10 Write a function in C called my2DAlloc which allocates a two-dimensional array. Minimize the number of calls to malloc and make sure that the memory isaccessible by the notation arr[i] []].

## 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 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 15. Databases

- 15.1 Write a SQL query to get a list of tenants who a re 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.
- 15.5 What isdenormalization? Explain the pros and cons.
- 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

- 16.1 What's the difference between a thread and a process?
- 16.2 How would you measure the time spent in a context switch?
- 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 simulation of the dining philosophers problem that prevents deadlocks.
- 16.4 Design a class which provides a lock only if there are no possible deadlocks.
- 16.5 Suppose we have the following code:
public class Foo { public Foo() { ... } public void first() { ... } public void secondQ { ... } public void thirdQ { ... } }

The same instance of Foo will be passed to three different threads. ThreadA will call first, threads 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?

## Chapter 17. Moderate

- 17.1 Write a function to swap a number in place (that is, without temporary variables).
- 17.2 Design an algorithm to figure out if someone has won a game of tic-tac-toe.
- 17.3 Write an algorithm which computes the number of trailing zeros in n factorial.
- 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.
- 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 (that is, find the smallest such sequence).
- 17.7 Given any integer, print an English phrase that describes the integer (e.g., "One Thousand, Two Hundred Thirty Four").
- 17.8 You are given an array of integers (both positive and negative). Find the contiguous sequence with the largest sum. Return the sum.
- 17.9 Design a method to find the frequency of occurrences of any given word in a book.
- 17.10 Write code to print the encoded version of an XML element.
- 17.11 Implement a method rand7() given randSQ.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).
- 17.12 Design an algorithm to find all pairs of integers within an array which sum to a specified value.
- 17.13 Consider a simple node-like data structure called BiNode, which has pointers to two other nodes. node). Implement a method to convert a binary search tree (implemented with BiNode) into a doubly linked list.
- 17.14 Given a dictionary (a list of words), design an algorithm to find the optimal way of "unconcatenating"a sequence of words.

## Chapter 18. Hard

- 18.1 Write a function that adds two numbers. You should not use + or any arithmetic operators.
- 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.
- 18.3 Write a method to randomly generates set of m integers from an array of size n. Each element must have equal probability of being chosen.
- 18.4 Write a method to count the number of 2s that appear in all the numbers between 0 and n (inclusive).
- 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.
- 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.
- 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.
- 18.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.
- 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.
- 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.