Interview Questions.md

Interview Questions: Stacks and Queues (ungraded)

TOTAL POINTS 3

Question 1

Queue with two stacks.

Implement a queue with two stacks so that each queue operations takes a constant amortized number of stack operations.

Question 2

Stack with max.

Create a data structure that efficiently supports the stack operations (push and pop) and also a return-the-maximum operation. Assume the elements are real numbers so that you can compare them.

Question 3

Java generics.

Explain why Java prohibits generic array creation.

Interview Questions: Elementary Sorts (ungraded)

TOTAL POINTS 3

Question 1

Intersection of two sets.

Given two arrays a[] and b[], each containing n distinct 2D points in the plane, design a subquadratic algorithm to count the number of points that are contained both in array a[] and array b[].

Question 2

Permutation.

Given two integer arrays of size n, design a subquadratic algorithm to determine whether one is a permutation of the other. That is, do they contain exactly the same entries but, possibly, in a different order.

Question 3

Dutch national flag.

Given an array of n buckets, each containing a red, white, or blue pebble, sort them by color. The allowed operations are:

• swap(i, j) : swap the pebble in bucket i with the pebble in bucket j.
  
• color(i) : determine the color of the pebble in bucket i.
  

The performance requirements are as follows:

• At most n calls to color().
  
• At most n calls to swap().
  
• Constant extra space.