Coding interview questions

In preparation for a coding interview I collected numerous coding questions from the internet. Since they might be useful for other job applicants as well, I post them here.

The question are not sorted in any way, of varying difficulty and there are probably some duplicates. I have fixed only a few typographical errors but the questions are largely as I found them. Don't hold me responsible for bad spelling or grammar ;-)

Two books that I also found quite useful for my preparation were "Cracking the Coding Interview" by Gayle Laakmann and "Programming Interviews Exposed" by John Mongan. Well, here comes the list of questions:

Find a string in a very long string - a needle in a haystack.

Given a binary search tree and an integer k, describe the most efficient way to locate two nodes of the tree that sum to k.

Please describe a data structure that accomplishes the functions INSERT and FIND-MEDIAN in the best possible asymptotic time.

If you have one billion numbers and one hundred computers, what is the best way to locate the median of the numbers?

Say you are implementing exponentiation for a certain processor. How would you minimize the number of multiplications required for this operation?

You are given a grid, with points on the intersections (think a map of streets, people are standing on random corners). Write code to calculate the point on the grid that is the shortest distance from every point on the grid.

Write a function that finds the median of a set of three numbers, also find the Big O. Can it be done with only 2 comparisons, or do you need 3? .

Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests.

Design and write a Sudoku solver.

How to computer the longest increasing sequence in an array with only one extra variable.

Implement core functionality of a skip list.

Given an array of different integers, print out all the inversion pairs. (i.e, a[i] > a[j] where i < j).

Given a 2D boolean array. Return the length of the biggest square where all elements inside it is true.

Get the two highest number in a binary search tree.

Find the maximum sum possible in an array of positive integers by selecting the elements in such a way that no two elements are next to each other.

Same as above but another one is taken out again. Find the two missing numbers.

Given a set of strings, a number 'n', and a function that takes a string and gives back a score, find the n largest scored strings in the set.

Given two numbers m and n, write a method to return the first number r that is divisible by both (e.g., the least common multiple.

You are given a text file too large to fit in memory and 3 strings A, B, C. For each string, you have a sorted array listing the positions of the string in the file (e.g., inverted indices). Find the smallest window containing the 3 strings. Order of appearance does not matter.

Given 2 numbers x and y, check if x is an integer power of y. For instance, x = 8, y = 2 would return true and x = 10 and y = 2 would return false since the first one is an integer power but the second isn't.

Suppose you have an arbitrarily connected graph with n nodes. Come up with an algorithm to identify each set of connected nodes (i.e. identify all the islands in the graph). What's the complexity? Can you find a solution in O(n log n)?

Implement a random number generator such that the random number generated is always in a particular range. Perform through time complexity analysis of it. How would you improve the solution.

Get the kth largest number from two sorted arrays.

Find median given two sorted arrays.

Write a function to convert a collection of strings into a single string and a function to convert it back.

Write a method which will remove any given character from a String.

Write a program to find all prime number up to a given numbers.

Write program for word-wrap which should work on any screen size.

Write code for Generate Random No in a range from min to max.

Describe the design and implementation of a Tic Tac Toe game.

Given a graph, find if it represents a tree.

You have a sorted array of real numbers drawn from the uniform distribution between 0 and 1. How can you quickly find a number in it?

If you have a ransom letter and magazines, can you construct the ransom letter from the words in the magazine.

Find the intersection of two integer lists.

Write a program that reads a file, randomizes it's lines and writes the output to another file.

Find the balance point in an array. (The index where the sum of the elements to the left it is the same as the sum of the elements to the right of it.) .

Implement iterator for a list of lists which may contain empty lists.

Given a list of sorted words, output the order of the letters used to sort them.

Given a base 10 number, print the hexidecimal (base 16) representation of that number.

Sort integer array in linear time.

Given a bunch of N random points in space, how would you draw a line such that N/2 of them were to the left of the line and N/2 to the right of it. Complexity.

In a sorted array, find the number closest to a given number .

Describe the algorithm for a depth-first graph traversal.

Given List of Strings. Return a list of lists of Strings where each to anagram Strings in the input list exist in the same list in the output list.

How would you calculate the number of 1's in a list of 10,000 integers.

Given a file consisting of names, what data structure would you use to valid if a name is in the list. What if now the we say a name is valid if the if it differs no more than one character against a name in the file?

Write a method that generates a random sequence of numbers of specific percentages.

If you have 10 bags of marbles with 10 marbles each and one bag has marbles that weigh differently than the others, how would you figure it out from one weighing.

Given a binary tree, print out the whole tree by levels.

Implement a function that takes a string with '?' marks and returns all possible values when '?' is replaced with '0' or '1.

Implement a hashmap.

Write function to compute n-th Fibonacci number? Both iterative and recursive?

How do you reverse a singly linked list?

How do you find depth of binary tree?

Write code to print Inorder traversal of a tree?

Print out all leaf node of a binary tree?

Write a program to sort numbers using quick sort?

Write a program to implement binary search algorithm.

In an array 1-100 exactly one number is duplicate how do you find it?

Given two arrays, 1,2,3,4,5 and 2,3,1,0,5 find which number is not present in the second array.

How will you determine two graphs are the same.

What is the strategy pattern in Java.

Find the number of connected components in a Graph.

Write code to find the second shortest path between two given nodes in an undirected graph.

Write a function to return if a number is a palindrome (eg, 113848311) .

Reverse the word order in a string.

Reverse bits of a digit.

Write a method that finds depth of a (non-balanced) binary tree.

Convert decimal number 99 to base 7.

Define an algorithm that converts a string to an integer without using a built in method like int() .

Write a program to find depth of binary search tree without using recursion.

Write an iterator over multiple collections.

Most phones now have full keyboards. Before there there three letters mapped to a number button. Describe how you would go about implementing spelling and word suggestions as people type.

Given a dictionary of English words, find sets of anagrams. For instance, “pots”, “stop”, and “tops” are all anagrams of one another because each can be found by permuting the letters of the others.

Although Quicksort uses only O(log n) stack space on the average, it can use linear space in the worst case. Explain why, then modify the program to use only logarithmic space in the worst case.

Print all permutation of String both iterative and Recursive way.

Write code to check a String is palindrome or not?

Write code to check whether a number is power of two or not?

Design an algorithm to find the frequency of occurrence of a word in an article?

Large data set, in memory sorting with limited RAM.

Implement a special type of integer iterator. It will be a wrapper over a regular integer iterator, except that this iterator will only iterate over negative numbers. Show how you'd write the next() and hasNext() functions to work with the next negative integer instead of just the next integer.

Sorting in general with big-O complexity, followed by partition sort (quick sort), followed by finding the k-th largest element without full sorting.

Implement peek() and pop() from java iterator(). for example [1,2,3,4,5], peek() = 1, pop() = 1, peek() = 2, peek() = 2, pop() = 2 .

Mutable, non mutable classes in Java.

Declaring constants in Java.

Count the number of set bits for an 32 bits integer. How to improve the process for the second time use if the memory is unlimited.

What is the complexity of Quicksort? (mean and worst case).

Find the minimum window in a string which contains a list of characters .

Implement a set class with the following method: get(), put(), getRandom() .

Given a graph node, write a code to return a copy of the sub-graph starting with that node.

Create a Java method that clones a DAG (Directed Acyclic Graph).

Describe preorder, inorder, postorder.

What's the difference between a hashtable and a hashmap (in Java).

Explain the difference between Array Lists, Linked Lists, Vectors, Hash Maps, (from Java's JDK) etc. and when one choice is better of another.

Delete an element from a singly linked list in Java.

Out of 10 coins, one weighs less then the others. You have a scale. How can you determine which one weighs less in 3 weighs? Now how would you do it if you didn't know if the odd coin weighs less or more?

Addition of 2 big numbers (represented by 2 int arrays, assuming each integer can only be 0-9) .

Compute all the intersections of two sets of segments in a line.

Given a set of cities, each with a given population, select randomly a city with a probability that is proportional to the population.

You have a collection of html documents grouped by a source web site . You need to count frequencies of bi-grams across all documents and present it in a sorted order (may be return top N frequent bi-grams). How would you approach it? How to filter out non-significant bi-grams? How to distribute and merge? What data structures to use to keep counters?

Write code to shift a string with rotation [a, b, c << 2 = 2 c, a, b].

Convert a one dimensional array of Strings containing [a,b,c, d,e ...z] to 2 dimensional array of a2[aa,bb,cc] .

Write a string splitting function that does not copy the string.

Partition an array in such way zeros to be moved on the left side of the array, other numbers on the right side of the array. Extra storage not allowed, only in-place.

Write an algorithm to test if n is power of 2.

How to replace a string in a templatized string where each placeholder starts with a specific delimiter, you are given a map that maps the placeholders to associated values.

Ref to the game, Boggle, given a 3x3 grid of letters represented as a char array, generate all possible word combinations. The legal character sequences are horizontally or vertically adjacent chars. So in [A, B, C; D, E, F; G, H, I], ABCFI is legal but DFH is illegal.

Write the code to determine if a 2D point is inside a 2D closed polygon.

Implement a blocking queue in Java.

Implement heap-based priority queues to run as quickly as possible; at what values of n are they faster than sequential structures.

Algorithm for converting uniformly distributed random numbers into a logarithmic distribution.

Given a picture of a skip list data structure, implement the algorithm to maintain skip lists (add, search, delete).

Base class has one method takes argument as Object and inherited class overrides it to pass String as parameter.If called with argument of Object whcih method will be called.

Design and implement a garbage collection algorithm in any programming language. also needed to give out run time analysis.

you have a sequence where each number is a multiple of 2 or 5 (so: 2^i * 5^j). he gave the beginning of the sequence as 1,2,3,4,5,8,10,16... and asked me to find an algorithm to calculate the next number in the sequence.

Write code to check whether every element of an array has been visited (you are given a starting position and each position stores a pointer to a subsequent position).

Sample uniformly on a circle centered at zero with radius 1.

Write algorithm to compute a Log to the base 2 of a number (integral results no need for floating point). Solution should not assume a particular size of integer .

Implement a base 3 adder which takes two strings as input and returns a string .

Quad tree bitmap: describe data structure and an algorithm.

For a n-node tree, you are given a left leaf node pointer and right leaf node pointer. Write a function to find the number of nodes between the leaves pointed by the left and the right pointer.

You have a simple search consisting of search terms that are OR'ed together, ie: Cats AND Dogs. You have a set of documents possibly containing those terms and you have the positions of those terms in each document. How would you search for Cats AND Dogs.

You're given a string, and you want to split it into as few strings as possible such that each string is a palindrome.

What are the issues with floating point calculation? For example, 1.0f + e-30, is there any issue with the statement.

Given a sorted array A[1..n] with n integers, and an integer t, find all pairs (x,y) of elements in A such that x+y is smaller than t.

You are given a huge stream of geo coordinates. Unordered. Return list of objects in a specified radius from some point X.

Write classes representing expression tree for a simple calculator. You care only about constants and basic binary operators. Write function evaluating expressions.

Suppose you have a set objects, identified by a unique name. How do you store them so that you can retrieve them easily?

Given a tree and leaf node, write the code to make the leaf node as root of tree.

Find the longest word in a dictionary, such that the word can be built one character at a time, and all substrings are words in the dictionary. A new character can be added anywhere.

You have a n number of cities. Lets say city 1 has some information that needs to be sent to all other n-1 cities using minimal cost. Cost between each pair of cities is given. any number of cities can transmit the information once they receive the information but the overall total cost should be minimum.

Write a function to modify a singly linked list, appending copies of the first N-1 elements to the end in reverse order. For example, ['A', 'B', 'C', 'D'] becomes ['A', 'B', 'C', 'D', 'C', 'B', 'A'].

Given an array of structs: write a function that finds equal values in all the structs in the array.

How to find the max number of a shift buffer queue. For instance, there is an array like 5, 6,8,11,1,2, how to find the max number, which is 11 in this example.

Given inputs from Google Search, you have K chunks. Each chunk is individually alphabetically ordered (apple, banana, cat) ... (*apple, *banan, *cat). You want to merge all chunks into a single list. How would you do it? What limitations are there to your approach?

What's the difference between finally, final and finalize in Java.

Can an abstract class be instantiated in Java? And does it have a constructor.

If we had a list of n nodes, what are the maximum number of edges there can be for a directed acyclic graph.

Write an algorithm for integer multiplication.

Design a class to serialize / deserialze a graph.

Describe a method to sift through dozens of emails and rank them based on 'importance'.

Given a list of integers of at least length 7, print the average of each consecutive 7 number long subsequence .

Write a memory manager oriented towards millions of very small allocations (less than 10 bytes).

Design an in memory word processor. Implement cut, copy, paste, formatting, recoverability.

What's the difference between a non-exclusive lock and an exclusive lock.

Generalized tower of Hanoi problem (n pegs).

5 stacks of coins that looks identical. each stack has 5 coins each. 4 of those stacks weigh the same, 1 stack has coins that weigh exactly 1 pound less. using a digital scale once, find out the position of the stack that is less weight.

Given standard 3x4 telephone touch pad, give all number combinations of letters you can make using only the chess "rook" move (ie, L shape: 3 down, 1 over). I think it was all 7 digit combinations. Letters are standard phone letters (2 button is "ABC", etc). * and # not valid.

Implement a program to play the battleship game.

Serialize and deserialize a collection of strings into a single one.

Design an iterator for a collection of collections in java. The iterator should hide the nesting, allowing you to iterate all of the elements belonging to all of the collections as if you were working with a single collection.

Millions of cache entries, each with a unique key, stored in several servers. how to sort all entries whose key falls within a specified range using Map Reduce? What if one server has a very small range of keys (say 1 to 100) and another server has a very large range of keys (say 100 to 1000000)? .

Rotate a one-dimensional vector of n elements left by i positions. For instance, with n=8 and i=3, the vector abcdefg is rotated to defghabc. Simple code uses an n-element intermediate vector to do the job in n steps. Can you rotate the vector in time proportional to n using only a few dozen extra bytes of storage?

Write functions for the following date problems: given two dates, compute the number of days between them; given a date, return it’s day of the week; given a month and year, produce a calendar of the month as an array of characters.

Build the fastest possible complete function to generate a sorted array of random integers without duplicates. (You need feel constrained to use any prescribed interface for set representation).

How do you sort Java object using Comparator?

Was asked how I would implement division without using division or mod operators. The answer should return in the form quotient r remainder.

Write a program to implement blocking queue in Java?

Write a program for producer-consumer problem?

Estimate the total storage size of GMAIL.

How to add a counter to www.google.com to track the billionth user.

You have a 64bit integer counter set to 0.

How long it will take to overflow the counter given that you are incrementing it at 4Ghz speed.

Quickly estimate 2^64 without using a pen/papar.

Given an integer, its digits are stored in the array, the very last digit is the very last element of the array. Write a function that adds one to this integer.

Given a large network of computers, each keeping log files of visited urls, find the top ten of the most visited urls. The result list must be exact, and the maps are too large to transmit over the network (especially sending all of them to a central server or using MapReduce directly, is not allowed.

A specific implementation of B-Tree when looked from one side.

You are given a sorted list of disjoint intervals and an interval, e.g. [(1, 5), (10, 15), (20, 25)] and (12, 27). Your task is to merge them into a sorted list of disjoint intervals: [(1, 5), (10, 27)].

Given a picture of pixels represented with RGB values, convert it to 256-colors (each pixel represented with an index from a 256-sized table holding the actual colors) .

Implement a counter with a method to retrieve the number of increments in the last 60 seconds.

How many ways can you make change given the following denominations? ie, if numCentsToMake is 6 and denominations is [25, 10, 5, 1], then it should return 2: either a nickel and a penny or 6 pennies. int numWaysToMakeChange(int numCentsToMake, int[] denominations) .

Implement a stack that pops out the most frequently added item.

Discuss and implementation of flattening a binary search tree into string representations.

How would you go about testing a distributed system such as Gmail, before releasing it to the public. How would you simulate realistic server load ?

We have m slots for ads and n ads, each ads will have different revenue on different slot, design an algorithm to find out the best fit (find m ads in n ads and order them so that they can make max money,.

Given a word that consists of two words such as "aman" give all the combination of valid two words. You are given a dictionary to test against. Example: aman--> a man, am an. watermelon--> water melo.

How to design a search engine? If each document contains a set of keywords, and is associated with a numeric attribute, how to build indices?

how many ways you can write n as N summation of other numbers 5 = 1+ 2 +2 = 2+ 2 + 1 = 1 + 3 +1 = 1 + 4 etc.

If a user types in a n digit number on the telephone, how do you write a function to deduce if the number constitutes a valid word. For example, if the user enters 123, then can a valid word be made out of (a/b/c) + (d/e/f) + (g/h/i) .

How to select a random sample of size K from a stream of numbers.

Implement a fast exponentiation function.

Write a function to calculate the angle between hour and minute hand on a clock.

Write a program to compute if one string is a rotation of another.

Given a set of integers from 1 to 100, find out the number of combination that sum up to 100. Each integers can only be used once.

You need to write a function to climb n steps you can climb either 1 step at a time or 2 steps a time, write a function to return number of ways to climb a ladder with n step.

How do you find middle element of a linked list in single pass. How do you find 3rd element from last in single pass.

How would you determine if someone has won a game of tic-tac-toe on a board of any size?

Given an array of integers which is circularly sorted, how do you find a given integer.

Find a loop in a linked list. How long is the loop.

Algorithm to get Index of a permutation when all permutations arranged in lexicographical order and its complexity.

Given two binary search trees, write function which tells if two such trees are the same – (i.e. same info in the nodes, same branching to left and right at every node.

Come out with an algorithm for getting the column number provided the column name in a excel sheet and vice versa. Excel has a naming convention of A,B..Z,AA,AB,AC..ZZ,AAA... This had to be converted to the column numbers. A will be 1 and AA will 27. Also the algorithm to find the name provided column number.

Write a function that computes the intersection of two arrays. The arrays are sorted. Then, what if one array is really larger than the other array.

Find the common numbers in two text files.

Given a list of integer e.g. (1,2,4,5,6,7,8...). Find a pair with a given sum.

Find 3 numbers in an array adding up to a given sum S.

In a sorted matrix (sorted by rows and columns), find an element.

Find kth largest element in unsorted array.

Given the pre-order and in-order traversing result of a binary tree, write a function to rebuild the tree.

Given two strings. Remove the letters in order from the first string that are in the second.

Create a function to return the angle between the clock hands if given the hours and minutes.

Giving a windows size K and an array of size N, find the minimum of each window as it slides through the array.

Write code for Fibonacci algorithm (iterative or recursive) and explain what's the performance.

For a given maze, how to write a function to check if there's a way from the top-left grid to bottom-right grid with obstacles in the middle.

Given an array of numbers, there is one number that has a duplicate. How would you find the number.

Find element in circular sorted array.

You are climbing a stair case. Each time you can either make 1 step or 2 steps. The staircase has n steps. In how many distinct ways can you climb the staircase.

Remove a node from a singly linked list without knowing the head node. All you have is the node itself.

Given a list of strings return the substring representing the longest common prefix .

Find longest common substring.

Write a priority queue<E> with three methods. Insert(E Element, int priority). E Pop(), update(E Element, int new_priority).

Describe what happens when making a google search, specifically with client and server .

Implement a binary tree iterator class .

Given search terms, find the minimum window containing all the terms in a string .

How would you find the power set of a set of numbers .

How would you implement a stack to achieve constant time for "push", "pop" and "find mininum" operations.

You are given a Binary-Search-tree. Find duplicated values.

How to reverse the words in a sentence in place.

If you have a computer with no division operator, how do you do it .

How to find two missing integers in an unsorted array.

You are given a number of coins, how can you generate the probability of 1/3, 2/3, etc.

How would you sort an array of one millions integers.

Given a grid that contains rectangles, write a function that will return all the rectangles that overlap with each other.

You have all of the prices for a given stock for the next year. You can buy once and sell once in that year. How do you determine when to buy and sell to maximize your profit?

Write an algorithm to sort and merge 2 LARGE data streams on a system where storage is essentially unlimited (but slow) and RAM is limited.

Find the median of a very large dataset distributed over several network nodes.

Given unsorted sequence of billions of numbers that cannot all fit in memory at the same time, find the median of these values.

Implement a method that matches an entire string with star wildcard pattern, e.g. returns true for ("*ogle", "Google"), but false for ("fragile*", "agile") - without using regular expression language support.

How to count frequencies of characters in a string. What if the string is too huge? When is it reasonable to distribute across machines? How to find the most frequent character in the distributed scenario with a minimum data exchange between machines?

Write a program for finding the kth-smallest element in the array x[0...n-1] in O(n) expected time. Your algorithm may permute the elements of x.

You are given two sets of integers, sizes M and N with M < N. Perform inner equal join on these two sets (i.e., find intersection of the two lists). How to perform it if both the lists are in files and the available memory is of size K < M < N.

You are a parking lot attendant in a lot that has one open spot, and you want to move the cars from their original positions into a new arrangement. Create a program that will print out instructions on how to move the cars most efficiently.

Given a sequential file that contains at most four billion 32-bit integers in random order, find a 32-bit integer that isn’t in the file (and there must be at least one missing...why?). How would you solve this with unlimited main memory? How would you solve it if you could use several external files but only a few bytes of main memory?

Given a file containing at most ten million 7-digit integers with no duplicates. What is an efficient way to print these numbers in ascending order using just 1.5Mb RAM and reading the data just once? What are the consequences of only having 1Mb of RAM and no other storage? How would your answer change if duplicates were permitted?

N pots, each with some number of gold coins, are arranged in a line. You are playing a game against another player. You take turns picking a pot of gold. You may pick a pot from either end of the line, remove the pot, and keep the gold pieces. The player with the most gold at the end wins.

Transmute one word to another by the shortest path of 1-letter changes through a path of actual words.

Create a cache with fast look up that only stores the N most recently accessed items (LRU policy). O(1) time complexity is expected.

Find the smallest window/substring in an string that contains all letters in a given string.

Write a function to find out longest palindrome in a given string.