Be ready to write code on a whiteboard. It's tough and requires some practice. You can find typical questions in list below. In general, you are expected to come up with optimal algorithm and implementation in 20 minutes. Quadratic run time is not good enough. Usually you need to come with O(N) or O(NlogN) solution.

Good luck!

General

Given two arrays, print all common elements. Small array size is M, and large array size is N (M << N)

Given a list, return the first pair of duplicates in the list

Given an array of N numbers, and a number T, find out whether there are two numbers from the N numbers sums up to the number T. Find out ALL solutions to the problem and analyze the run times.

Given 64K-1 numbers [0..64K-1] find one missing number.

You have unordered array X of N integers. Find the array M containing N elements where M* is the product of all integers in X except for X**. You may not use division. You can use extra memory. Solution faster than O(N^2)*

For a given sequence of numbers print all increasing subsequences.

Given an array of integers (both positive and negative) divide the array into two parts (sub-arrays) such that the difference between the sum of elements in each array is minimum?

Linked Lists

Implement basic operations for singly linked list: push_front, push_back, delete, tail, size, pop_front, find

Implement following operations for singly linked list: count, at, insert_at, insert_after

Reverse linked list in place

Find loop in linked list. Find length of the cycle. (Floyd's cycle-finding algorithm)

Write a function to find the middle node of the a singly-linked list

Write a function to copy list to new list and return pointer to head of the new list

Probability

You have a stream of infinite queries (i.e: real time search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.

Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

Write function to select random sample of size M from a stream of numbers.

Write function to select random sample of size M from a set of numbers of size N.

Write function to random shuffle array a.