Cracking the Interview Code

Strings and Arrays

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

LinkedLists

[ ] 2.1 Write code to remove duplicates from an unsorted linked list.

How would you solve this problem if a temporary buffer is not allowed?

[ ] 2.2 Implement an algorithm to find the nth to last element of a singly linked list.
[ ] 2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: 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 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.
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.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C

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 function min which returns the minimum element? Push, pop and min should all operate in O(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 exceeds some threshold.
[ ] 3.4 In the classic problem of the Towers of Hanoi, you have 3 rods 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 (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.
(C) A disk can only be placed on top of a larger disk.
[ ] 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 that should be used to write this program: push | pop | peek | isEmpty.

$ 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 distance from 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 with minimal height.
[ ] 4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (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 in a binary search tree where each node has a link to its parent.
[ ] 4.6 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree.Avoid storing additional nodes in a data structure.NOTE: This is not necessarily a binary search tree.
[ ] 4.7 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds 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.

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

FOLLOW 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?

Data Structures

[]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++.

[ ] 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 NxN grid.The robot can only move in two directions: right and down.How many possible paths are there for the robot?
FOLLOW UP
Imagine certain squares are “off limits”, such that the robot can not step on them.Design an algorithm to get all possible paths for the robot.
[ ] 8.3 Write a method that returns all subsets of a set.
[ ] 8.4 Write a method to compute all permutations of a string.
[ ] 8.5 Implement an algorithm to print all valid (e.g., properly opened and closed) 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 many image editing programs.That is, given a screen (represented by a 2 dimensional array of Colors), a point, and a new color, fill in the surrounding 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 the number of ways of representing n cents.
[ ] 8.8 Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.

[ ] You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B.Write a method to merge B into A in sorted order.
[ ] 9.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 unknown number of times, give an O(log n) algorithm that finds an element in the array.You may assume that the array was originally sorted in increasing order.
EXAMPLE:
Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
Output: 8 (the index of 5 in the array)
[ ] 9.4 If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?
[ ] 9.5 Given a sorted array of strings which is interspersed with empty strings, write a 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 a method to find an element in it.
[ ] 9.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.
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)

[ ] 10.1 You have a basketball hoop and someone says that you can play 1 of 2 games.
Game #1: You get one shot to make the hoop.
Game #2: You get three shots and you have to make 2 of 3 shots.
If p is the probability of making a particular shot, for which values of p should you pick one game or the other?
[ ] 10.2 There are three ants on different vertices of a triangle.What is the probability of 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.

[ ] 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?

[ ] 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 they differ 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 query to return a list of the honor roll students (top 10%), sorted by their grade point average.