Design an algorithm to flatten a binary tree into a linked list, breadth-first. Implement this with constant storage.

Devise an algorithm which takes an input array and divides it into three sets: negatives, zeros, and positives. Implement the sort in place and keep the numbers' relative sequence.

Given an array A[n] of n numbers, create an output array such that Out[i] is equal to the product of all the elements of A[n] except A[i]. Ex. Out[4] assuming n >= 5 will be the product of the numbers from A[0] through A[3] and the numbers from A[5] through A[n - 1]. Solve this without using the division operator and in O(n).

Divide a number by 3 without using +, -, *, / or % operators.
The number may be signed or unsigned.

Given a stream of numbers, write an algorithm to print the average (mean) of the stream at any point.

Ex. 10, 20, 30, 40...
Average after 1 number = 10
Average after 2 numbers = 15
Average after 3 numbers = 20
Average after 4 numbers = 25
...

Given N pairs of integers, write an algorithm to sort the pairs so that the first number in each pair is sorted increasingly whle the second number in each pair is sorted decreasingly. The first and second numbers in each pair can be swapped. Sometimes there will be no solution, in that case throw an exception.

Examples:

Input:
1 5
7 1
3 8
5 6
Output:
1 7 <- Swapped
1 5
6 5 <- Swapped
8 3 <- Swapped

Input:
1 5
6 9
Output:
Not Possible Exception

A singly linked list is filled a character in each node. Write a function to determine if the linked list is a palindrome.

Given a triangle of numbers as below, devise an algorithm to determine the maximum sum traveling from the top of the triangle to the base made by moving from one row to the next by adjacent cells.

		          5
		       6     3
		    2     8     6
		 9     5     4     7
		

In this example the route of maximum sum (24) from top to bottom is: 5 -> 6 -> 8 -> 5. Make sure your algorithm is scalable to larger triangles.

Today's question is actually just a puzzle to stimulate your mind. Move 3 matches to make exactly 4 squares of equal size. All matches must be used. Though not required, think of how you would solve this puzzle in code given Match objects.

Given two strings, an input and a mask, remove all characters from the input string present in mask.

Given the top-left and bottom-right coordinates of two axis-aligned rectangles, write a conditional statement to determine if they overlap.

You are on an island with an airport. The airport is home to an unlimited number of identical planes. Each plane has enough fuel capacity to fly half way around the world. The planes can refuel in-flight, instantly, from another planes' fuel tank. The island has unlimited fuel.

What is the fewest number of planes necessary to get one plane around the world assuming all planes need to return safely to the island?

Please attempt part 1 of this question if you haven't tried it yet.

An array is filled with the numbers from 1 through 1,000,000 (inclusive), with the exception of two missing numbers. The array has been filled randomly with each number used only once. Determine the two missing numbers in one pass through the data.

The factorial of 10 is 3628800. The last non-zero digit is 8. Write a function to compute the last non-zero digit of (10⁹!). Can you calculate (10¹⁰⁰!)?

A mathematician purchases four items from a convenience store. He notices that the sum and product of the prices of the four items comes out to $7.11. Write a function to determine the prices of the four items.

You are given 2 identical eggs and access to a 100-story building. If an egg is dropped from a story and broken then it cannot be used again. But if the egg does not break, then it will not break for every story below and can be considered undamaged.

Devise a strategy to determine the highest floor from which the eggs can be dropped without breaking while minimizing the number of egg drops to find the solution. What if you were given 3 eggs? 4 eggs? etc.

P.S. This question is commonly used by Google/Microsoft in interviews

Given the values of two nodes in a binary search tree, write a function to find the lowest common ancestor. Assume both values exist in the tree.

ex. In the BST below the LCA of 15 and 25 is 20.

Given a range of positive integer numbers [a,b], write a function that returns the count of integers which have a prime number of 1 bits set in their binary representation.

P.S. This was originally a Facebook programming puzzle.

Given a 2D matrix sorted in increasing order from left-to-right and top-to-bottom, devise an algorithm to search for a target number.

Given a stack, find an element in the middle position of the stack. Optimize for space.

Given a linked-list with unknown length, randomly select one node with equal probability for every node in the list.

Given a NxN matrix filled with 0s and 1s, set every row that contains a 0 to all 0's and every column that contains a 0 to all 0's. Optimize for space and passes.

ex.
0 1 0 1 0
1 1 1 1 1
1 1 1 1 1
0 1 1 1 0
0 1 0 1 0

Results in
0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 0 0 0 0
0 0 0 0 0

Sort an array in ascending order filled with 0's and 1's. Traverse the array once ex. O(n).

How can you implement 3 Stacks with 1 Array? Optimize for space.

You have a gold bar and need to pay a worker for 7 days at the end of each day. You can only make 2 breaks in the gold bar. How do you pay the worker assuming he works the same amount every day?

Implement a queue using two stacks.

How many distinct binary tree shapes exist for n nodes?

ex. For 3 nodes there are 5 distinct shapes:

How many ping pong balls can fit into a school bus?

Don't worry about the exact answer, the method of how you get to an answer is more important for this question.

You are given an array containing odd and even numbers. Sort the array so that all the odd numbers are before the even numbers. Also, the odd half of the array should be sorted in descending order while the even half should be sorted in ascending order. You cannot use an additional array and the sorts must be done in-place. Additionally, you cannot do any pre/post processing.

ex. An input array: [14, 12, 3, 10, 11, 1, 7, 26, 8]
    returns: [11, 7, 3, 1, 8, 10, 12, 14, 26]

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. Devise an algorithm to find the intersecting node.

In other words, two singly linked-lists meet at some point, find the node at which they meet.

Given an array filled with integers that appear exactly twice, with the exception of one integer that appears once, find the unique integer.


ex. findUnique([1, 2, 6, 9, 9, 1, 3, 6, 2])
    returns: 3
ex. findUnique([12, 45, 32, 65, 32, 65, 45])
    returns: 12

Given a single dimension array, find the sum of the largest contiguous subarray.


ex. largestSubarraySum([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])
    returns: 187
    Largest subarray starts from 59 and ends with 97

Given only a pointer to the middle node of a singly linked list, devise an algorithm delete that node.

Devise an algorithm to compute the nearest number that is a palindrome and greater than the input.

ex. nextPalindrome(10)
    returns: 11

ex 2. nextPalindrome(18457)
    returns: 18481

Given an integer, write a function to find the number of trailing zeros of its factorial.

ex. factorialZeroCount(10)
    10! = 3,628,800
    returns: 2

ex 2. factorialZeroCount(27)
    27! = 10,888,869,450,418,352,160,768,000,000
    returns: 6

Find three ways to modify the code below to print exactly 20 '-' characters by changing or inserting one character.

int i, n = 20;
for (i = 0; i < n; i--)
{
   print("-");
}

For this question be sure to check out the hint before the answer!

Write a function to reverse the words of an input string in place.

ex. reverseWords("the quick brown fox jumps over the lazy dog")
returns "dog lazy the over jumps fox brown quick the"

Devise an algorithm to find the first character that occurs only once in an input string.

ex. firstUniqueCharacter("chickenhi")
returns 'k'
Note: Email incorrectly displayed 'i'

Write a function to determine if a number is a power of two.

Create a method that checks whether an input integer is prime or not. For this question we will take a look at a simple algorithm for determining primes and optimize it.

Devise an algorithm to determine if two strings of letters are anagrams.

ex. isAnagram(Debit Card, Bad Credit)
returns true

ex 2. isAnagram(Eleven Plus Two, Twelve Plus One)
returns true

ex 3. isAnagram(Hello, World)
returns false

How many points are there on the globe that by walking one mile South, one mile East, and one mile North, (in this precise sequence) you reach the point at which you started?

Devise an algorithm to check if a binary tree is a binary search tree.

Given a singly linked list and its head node, find the node one-fourth of the way to the end of the list.

ex. If there are n nodes, return the node at floor(n / 4). If n <= 4 return the first node.

How can you cut a rectangular cake, with a rectangular slice (of any size/orientation) taken out, into two equal halves? You can only make one straight cut from the top of the cake (ex. cutting the cakes' height in half is not allowed).

Create a method 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.

ex. isEven(22) returns true

ex 2. isEven(1) returns false

Create a method that checks if an input integer is a palindrome without using an array or converting it to a String.

ex. isPalindrome(1234) returns false

ex 2. isPalindrome(12321) returns true

Devise an algorithm to find the number of 'pairs' in an input string. A 'pair' for this question can be defined as a situation in which two instances of the same character are separated by a single other character.

ex. "ZaZ" has one pair made of Z's

ex 2. "ZaZa" has 2 pairs

You are given 10 jars of pills. One jar is filled with contaminated pills. Regular and contaminated pills are identical - only to be differentiated by their weight. Regular pills weigh 10 grams while contaminated ones weigh 1.1 grams. You are provided a scale and allowed only one measurement. How do you identify which jar is contaminated?

Given an array of integers, devise an algorithm to find the largest number possible from a concatenation of the integers in the array. Each number must be used exactly once.

ex. An input array: [1, 3, 2, 4]
     returns: 4,321
     order of #'s: [4, 3, 2, 1]

ex. 2: [59, 58, 5, 1, 2]
     returns: 5,958,521
     order of #'s: [59, 58, 5, 2, 1]

ex. 3: [54, 5, 55, 6, 7, 56, 120, 560, 540, 505, 9, 57, 0, 1, 45, 65]
     returns: 976,655,756,560,555,545,405,054,512,010
     order of #'s: [9, 7, 6, 65, 57, 56, 560, 55, 5, 54, 540, 505, 45, 120, 1, 0]

You are given a 3-quart bucket, a 5-quart bucket, and an unlimited supply of water. How can you measure out exactly 4 quarts?

Write a recursive power function without using any external libraries.

ex. power(3, 4) should return 3⁴ which equals 81

What is the angle between the minute and hour hand of an analog clock at a quarter past 3?

An array is filled with the numbers from 1 through 100 (inclusive), with the exception of one missing number. The array has been filled randomly with each number used only once.

What is the fastest way to determine the missing number?