Arrays

• Sort an array such that odd numbers are in front of even numbers and their relative order does not change.
• Given an array, write a function to check if any two elements sum up to a third.
• Given an array with all elements sorted on each individual row and column, find the kth smallest number.
• Given an array of words, find the longest common substring between two words in the array.
• Implement binary search on a sorted array that has been rotated once.
• Given two unsorted arrays of integers, merge them into one sorted array.
• Given an array of integers, find whether there is a sub-sequence that sums up to 0. Return it.
• Write a function that fins the minimum and maximum values in an unsorted array.
• You are given a read only array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing. Find A and B using less than O(n) space in O(n) time.
• You're given a read only array of n integers. Find out if any integer occurs more then n/3 times in the array in linear time and constant additional space.
• There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.
• Given an integer array, find the maximum sum of consecutive elements.
• Rotate a one-dimensional array of n elements to the right by k steps. For instance, with n=7 and k=3, the array {a, b, c, d, e, f, g} is rotated to {e, f, g, a, b, c, d}.

Bits

• Reverse the bits of an unsigned integer.
• How do you quickly count the number of set bits in a 32-bit integer in linear time? In constant time?

Linked Lists

• Write code to remove duplicates from an unsorted linked list.
• Write an algorithm to find the nth to last element of a singly linked list.
• Implement an algorithm to delete a node from a single linked list, given only access to that node.
• Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.
• Given two numbers represented as a linked list, calcuate and return their sum represented as a linked list.
• Given a circular linked list, derive an algorithm which returns the node at the start of the loop.
• Find a pair of elements from two sorted lists for which the sum of the elements is a certain value.
• Implement a linked list recursively.
• Implement a linked list iteratively.
• Write a function to determine if a singly linked list is a palindrome.
• Write a function to determine if a singly linked list has a loop.
• Print all of the elements in an array that has occured an odd number of times.
• Given an array of stock prices, where the increasing indexes of the array signify increase in time, return a good time to buy and sell such that profit is maximized.
• Given a linked list of integers, split the list into two lists such that one list contains only odd numbers and the other contains only even numbers.
• Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
• Given a linked list with unknown length, randomly select one node with equal probability for every node in the list.
• Two singly linked-lists intersect at a node and merge into a single linked-list. The size of each is unknown and the number of nodes prior to the intersection node can vary in each list. Write a function to find the intersecting node.
• Given only a pointer to the middle node of a singly linked list, write a function to delete that node.

Sets

• Write a function that prints out all subsetes of a given set of numbers.

Stacks

• Find the element in the middle position of a stack. Optimize for space.

Strings

• Given a N different open and close braces in a string "( { [ } ] )", write a function to check whether the string has matching braces.
• Given a list of strings, produce a list of the longest common suffixes.
• Determine whether or not a given string is a palindrome.
• Reverse all the words in a given sentence.
• Print all permutations of a word.
• You're given a string with numbers from 1 to 250 in random order but missing one number. Find the missing number.
• Write a program that can print out the text form of the numbers from 1 to 1000. For example, 20 prints out as "twenty".
• Write a function that switches the positions of two words.
• Given a number as a string, write an algorithm to map to its oral description. For example, "1" -> "11" (there is one one). "21" -> "1211" (there is one two and one one).
• Write a function that prints the integer equivalent of a given Roman numeral.
• Write a function that takes in two binary strings and returns their sum, which is also a binary string.
• Find the number of unique strings in a collection of strings.
• Implement regular expression matching with support for ‘.’ and ‘*’.
• Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
• Replace all occurrence of the given pattern to ‘X’.For example, given that the pattern=”abc”, replace “abcdeffdfegabcabc” with “XdeffdfegX”.

Trees and Graphs

• 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.
• Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
• Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.
• 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).
• Implement a function to check if a binary tree is a binary search tree.
• 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.
• 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.
• 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.
• 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.
• Find a common ancestor of two different leaf nodes.
• Clone an undirected graph. How do you make sure you create the same branches and don't have loops?
• Create a balanced b-tree given an unsorted array.
• Convert a tree to a doubly linked list.
• Implement a binary search tree for floating point values.
• Find the height of a binary tree.
• Convert a BST to a sorted circular doubly-linked list in-place.
• Implement a red black tree.
• Write a function that prints a binary tree level by level.
• Find the nth element of a binary tree in an in-order traversal.
• Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node in the list.
• Find the nearest leaf node from given node in binary tree.
• Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Each node contains a parent pointer which links to its parent.
• Given preorder and inorder traversal of a tree, construct the binary tree.
• Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Grab Bag (figure out what to use and implement it!)

• Given a series of words written using a scrambled alphabet, figure out what order the letters of the alphabet are in.
• Print the shortest path from start to end of a maze.
• List all possible combinations of a phone number where each number can be represented by numbers. For example, 1 = [A|B|C].
• Implement a calculator.
• You are on a point on Google Maps (longitude, latitude). Write a function that returns a list of places within a given radius.
• Find the square root of a number.
• Find all valid answers in a Boggle game.
• Find the angle between the hour hand and minute hand on an analog clock.
• Find the closest path between two landmarks.
• You have an incoming infinite stream of integers. Write a function where, at any time, returns the largest k integers.
• Implement the Fibonacci sequence with O(n).
• Find the N most frequently occurring words in a billion lines of text.
• Given two axis-aligned rectangles A and B. Write a function to determine if the two rectangles overlap.
• Given a function which generates a random integer in the range 1 to 7, write a function which generates a random integer in the range 1 to 10 uniformly.
• Write a function to divide a number by 3 without using +, -, *, / or % operators.
• Write a function to determine if a number is a power of two.
• Write a function to determine whether or not an input integer is prime.
• Write a function that takes an integer ( >= 1 ) and returns "true" if the integer is even and "false" if odd. You cannot use any conditional operators or switch statements.

Design/Thoughts

• How would you design a distributed ID generation system?
• How would you represent a graph with a million nodes?
• How do you implement the auto-complete feature when people are typing on a search box?
• What is the most efficient (memory) way to store on emillion phone numbers?
• Build a recommendation system for restaurants on Yelp.