L phone interview

/**
* Sample input:
*
* 1
* / \
* 3 5
* / / \
* 2 4 7
* / \ \
* 9 6 8

*
* Expected output:
* 1
* 3 5
* 2 4 7
* 9 6 8
* ==========
*/

class TreePrinter {

static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}

public void printTree(Node root) {
// implementation here
if (root == null)
return;
Queue queue = new LinkedList();
queue.push(root);
queue.push(null);
while(!queue.isEmpty()) {
while(!queue.isEmpty() || queue.peek() != null) {
Node t = queue.remove();
System.out.println(t.value);
if (t.left != null)
queue.add(t.left);
if (t.right != null)
queue.add(t.right);
}
if (queue.peek() == null)
queue.remove();
if (queue.isEmpty())
return;
System.out.println();
queue.push(null);
}
}
}

/**
* Return the smallest character that is strictly larger than the search character,
* @param sortedStr : sorted list of letters, sorted in ascending order.
* @param c : character for which we are searching.
* Given the following inputs we expect the corresponding output:
* [‘c’, ‘f’, ‘j’, ‘p’, ‘v’], ‘a’ => ‘c’
* [‘c’, ‘f’, ‘j’, ‘p’, ‘v’], ‘c’ => ‘f’
* [‘c’, ‘f’, ‘j’, ‘p’, ‘v’], ‘k’ => ‘p’
* [‘c’, ‘f’, ‘j’, ‘p’, ‘v’], ‘z’ => ‘c’ // The wrap around case
* [‘c’, ‘f’, ‘k’], ‘f’ => ‘k’
* [‘c’, ‘f’, ‘k’], ‘c’ => ‘f’
* [‘c’, ‘f’, ‘k’], ‘d’ => ‘f’ e = 0, s = 0// mid = 0 s = 0
* [‘c’, ‘f’, ‘k’], ‘k’ => ‘c’
*/

public char firstSmallest(char[] array, char target) {
if (array.length == 0)
return null;
int s = 0;
int e = array.length – 1;
while(s <= e) {
int mid = (s + e)/2;
if (array[mid] == target){
if (mid == array.length – 1)
return array[0];
return array[mid + 1];
}
if (array[mid] < target)
s = mid + 1; //s = 1 e = 0
else
e = mid – 1;
}
if (s == array.length)
return array[0];
return array[s]; //return f
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s