Tags: | Posted by Admin on 9/13/2009 11:11 AM | Comments (0)

Question: Binary Search Tree Validity

Write a function to determine whether a given binary tree of distinct integers is a
valid binary search tree. Assume that each node contains a pointer to its left child, a
pointer to its right child, and an integer, but not a pointer to its parent. You may use
any language you like.
Good Answer: Note that it's not enough to write a recursive function that just checks
if the left and right nodes of each node are less than and greater than the current
node (and calls that recursively). You need to make sure that all the nodes of the
subtree starting at your current node are within the valid range of values allowed by
the current node's ancestors. Therefore you can solve this recursively by writing a
helper function that accepts a current node, the smallest allowed value, and the
largest allowed value for that subtree. An example of this is the following (in Java):

boolean isValid(Node root) {
return isValidHelper(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
boolean isValidHelper(Node curr, int min, int max) {
if (curr.left != null) {
if (curr.left.value < min ||
!isValidHelper(curr.left, min, curr.value))
return false;
}
if (curr.right != null) {
if (curr.right.value > max ||
!isValidHelper(curr.right, curr.value, max))
return false;
}
return true;
}

The running time of this algorithm is O(n).

Question: Odd Man Out

You're given an unsorted array of integers where every integer appears exactly
twice, except for one integer which appears only once. Write an algorithm (in a
language of your choice) that finds the integer that appears only once.
Good Answer: Set up a hash set that we will put the integers from the array into.
Have a second variable that will keep a sum. Start going through the array and for
each integer, check to see if it's already in the hash set. If it is not, add that integer to
the sum and store that integer in the hash set. If it is in the hash set, subtract that
integer from the sum. When the algorithm finishes going through the array, the sum
variable should be equal to the integer we were looking for, since it is the only
number we never subtracted from the sum. This takes O(n) time and O(n) space.

int oddManOut(int[] array) {
HashSet<Integer> s = new HashSet<Integer>();
int sum = 0;
for (int i = 0; i < array.length; i++) {
if (s.contains(array[i])) {
sum = sum - array[i];
} else {
s.add(array[i]);
sum = sum + array[i];
}
}
return sum;
}

Really Awesome Answer: XOR all the values of the array together! Since XOR is
commutative and is its own inverse, each integer in the array that appears twice will
cancel itself out, and we'll be left with the integer we're looking for. This takes O(n)
time and O(1) space. We told you bitwise stuff was handy!

int oddManOut(int[] array) {
int val = 0;
for (int i = 0; i < array.length; i++) {
val ^= array[i];
}
return val;
}

Question: Design a Poker Game

(Don't ask all these questions at the same time; ask one after another, since they
build upon each other.) Without writing any actual code, describe as much as
possible how you would design a poker game program. What classes would you
have? What relationships would they have with each other? What would be the
basic flow of the program and how would those classes play a part? If you then
wanted to add a new type of poker game (such as Texas Hold 'em), how would that
fit into your design?
Answer: There are so many possible answers to this problem that it would be
difficult to say that one answer is the best. Look to make sure that they make
classes to simulate the basic parts of a poker game (perhaps a hand, the pot, a game
type or rules, a round, the deck, etc.). Using inheritance (subclassing in objectoriented
programming) where it makes sense is also good for reusability and
extendibility. Using design patters (such as Model‐View‐Controller,
Listener/Observer, or the Singleton pattern) is also a good thing. The main point is
for them to get used to thinking about how they would design a system. Most
importantly, they need to think about simplicity, reusability, and extendibility in
their design.

Question: Leader Election

Describe a technique to identify a "leader" among a group of 10 identical servers
that are all connected to every other server. There are no prior distinguishing
characteristics of any of them and the same program to identify the leader starts
running on all of them at the same time. After an answer is given, ask how much
network traffic it requires and, if "ties" are possible, ask how you can break ties.
Good Answer: Have each server wait a random amount of time and then say "I'm it."
The "I'm it" announcement is time‐stamped, and the computer that time‐stamped its
announcement first is elected the leader. This approach requires sending out 9
messages. If there is a tie, the computers can repeat the procedure.
Note that other answers are possible, but every correct answer will use randomness
in some way.

Question: Queue Using Stacks

Describe a queue data structure that is implemented using one or more stacks.
Don't worry about running time. Write the enqueue and dequeue operations for the
queue. You may use any language you like.
Good answer: You can use two stacks: an "incoming" stack and an "outgoing" stack.
The enqueue and dequeue operations would look like this (in Java):

Stack in;
Stack out;
void enqueue(int value) {
while (!out.isEmpty())
in.push(out.pop());
in.push(value);
}
int dequeue() {
while (!in.isEmpty())
out.push(in.pop());
return out.pop();
}

Question: Instant Messaging

Describe a design for an instant messaging program where there are several
servers, clients are connected to each server, and the servers communicate with
each other. Describe the classes, interfaces, and so on that you would use and how
you would organize them.
Answer: As in the previous design questions, there is no best answer. Good topics to
discuss are how each client communicates with a server, how the servers maintain
state with the other servers, how state information is communicated between
servers and clients, and the speed/reliability of their design.

Question: Maximal Subarray

Given an array, describe an algorithm to identify the subarray with the maximum
sum. For example, if the input is [1, ‐3, 5, ‐2, 9, ‐8, ‐6, 4], the output would be [5, ‐2,
9].
Good Answer: Observe that the sum of a subarray from element i to element j is
equal to the sum of the subarray from element 1 to element j minus the subarray
from element 1 to element i ‐ 1. Our algorithm will iterate through the array. The
algorithm keeps track of the sum x of the elements no later than the element. It will
also keep track of the minimum sum y of the subarray from the first element to an
element no later than the current element. Finally, It will also keep track of the
subarray z with the maximum sum so far. At each step, we update x by adding the
current element to it. We update y by checking whether x < y; if so, we set y to be x.
We update z by checking whether y ‐ x is greater than z; if so, we set z to be y ‐ x.
For example, with the sample input, our algorithm would do the following:
Current element | x | y | z
----------------------------------
1 | 1 | 0 | 1
-3 | -2 | -2 | 0
5 | 3 | -2 | 5
-2 | 1 | -2 | 5
9 | 10 | -2 | 12
-8 | 2 | -2 | 12
-6 | -4 | -4 | 12
4 | 0 | -4 | 12
Surprisingly, this problem is equivalent to the stock market problem described in
handout 3. Given an array a1, you can "convert" it to an array a2 for the stock
market problem by setting each element a2[i] to be a1[0] + a1[1] + ... + a1[i].

Question: Obstacle Avoidance

Given an n x n grid with a person and obstacles, how would you find a path for the
person to a particular destination? The person is permitted to move left, right, up,
and down.
Good Answer: Use the A* algorithm or another fast path‐finding algorithm. (It is
described on Wikipedia.)

Comments are closed