We Brought Snacks

Tree’s are one of the many fundamental data structures in Computer Science. Today we’ll be talking about a specific kind of tree called the binary search tree. But before I get into that, let me go over what a Binary Tree is first.

A Binary Tree is a data structure composed of nodes that have at most 2 children. A node is a point on the tree that generally has a value associated with it, though it does not have to. As an example, we’ll look at a binary tree composed of integer nodes.

In the above picture we have a binary tree with seven different nodes. The root node (top of the tree) is the node with the value of 7. The left child of 7 is 8 and the right child of 7 is 9. This relationship follows throughout the whole tree. So now that you’ve seen a binary tree lets look at what makes a binary search tree different.

A binary search tree is a special form of binary tree where starting from the root node, you can travel down the tree and the nodes you travel across must follow the following rules. The left child of any node must be less than or equal to the parent node. The right child of any node must be greater than their parent node. In this case, when we build the tree, it will look different depending on the order we insert the nodes. So lets build the previous tree inserting the nodes in the order of 7, 6, 2, 8, 12, 9, 10. We get…

Any x you see is a child node with a null value. The reason binary search trees are useful is that you can search for any node you want and be guaranteed to find it in O(logn) time, assuming that the tree we build ends up being mostly balanced.  There are ways to guarantee that the tree is built in a balanced way but I won’t get into that right now.  As a bonus I will provide some sample code that implements a binary search tree in java below.

public class BST {
	private Node root;
	
	public BST() {
		this.root = null;
	}
	
	public Node getRoot() {
		return this.root;
	}
	
	public void add(int value) {
		if(root == null)
			root = new Node(value);
		else
			insert(value, root);
	}
	
	private void insert(int value, Node n) {
		if(value <= n.getValue()) {
			if(n.getLeft() == null)
				n.setLeft(new Node(value));
			else
				insert(value, n.getLeft());
		} else {
			if(n.getRight() == null)
				n.setRight(new Node(value));
			else
				insert(value, n.getRight());
		}
	}
	
	public boolean find(int value) {
		Node n = this.root;
		while(n != null) {
			if(value < n.getValue())
				n = n.getLeft();
			else if(value == n.getValue())
				return true;
			else
				n = n.getRight();
		}
		return false;
		
	}
	
	

}

public class Node {
	private int value;
	private Node left;
	private Node right;
	
	public Node(int value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
	
	public Node getLeft() {
		return this.left;
	}
	
	public Node getRight() {
		return this.right;
	}
	
	public int getValue() {
		return this.value;
	}
	
	public void setLeft(Node left) {
		this.left = left;
	}
	
	public void setRight(Node right) {
		this.right = right;
	}
}

The following interview is NOT my interview experience but, a friend’s on site interview at Amazon.

My friend, who is currently pursuing a masters degree in Computer Science was contacted by an Amazon recruiter. He never applied to Amazon, but he thinks they found his resume through the University career services or his Monster.com listing. Either way, he was contacted and was flown up to Seattle for interviews. They allowed him to skip the phone interviews.

He was flown up the day before and they had a room reserved for him at a nearby hotel. The next morning he headed over to the Amazon campus where he would spend the rest of the day in technical interviews with 4 different people (about 45 minutes each). Three of the interviewers were part of the team he was interviewing with and the other interviewer was from outside the team whom they called the “bar raiser”. Below are the questions he was asked throughout the day.

1. Write a method with the following definition:
boolean containsSubstring(String input, String search) and returns true if the search string appears in the input string (obviously you can’t use .contains).

2. Write a method that takes a linked list and flips all the pairs. ex:
a->b->c->d
b->a->d->c
basically, every pair is flipped with the prev/next (but only like pair to pair).

3. Write a method that takes two sorted lists of ints and returns a sorted list with the combination of the lists.

4. Write a method that takes K sorted lists of ints and returns a sorted list with the combination of the lists.

5. Given a map with points and a location, find the closest point to the location.

6. Given a map with points and a location, find the closest K points to the location.

7. (This problem was just carried on for a bit with a lots of little alterations)

8. Write a method that would take an int[][] and return the transpose.

9. Write a method that would take an int[][], an (x, y) and an int value (basically the object of this is to design a paint bucket feature, where if you click anywhere in on solid color it changes them all to a new color).

The challenge for today has to do with prime numbers. The goal is to write a function that takes in an integer x and prints out all of the prime numbers that are less than x. First of all, what exactly is a prime number? A prime number is an integer that is only divisible by 1 and itself. As an example, what should this function print if we pass in the value of 10?

2,3,5,7    (Note that 1 is NOT a prime number)

So first, lets look at the obvious solution.

void printPrimes (int x) {
    for(int i = 2; i < x; i++) {
        if (isPrime(i))
            System.out.print(i + ",");
    }
}

boolean isPrime (int y) {
    int count = 2;

    while (count < y) {
        if (y % count == 0) {
            return false;
        }
        count++;
    }
    return true;
}

Each time, we will check if the integer we are about to print is prime or not. Every time we check if a number is prime or not, we divide it by all of the numbers below it and see if we get a remainder. If we do not get a remainder then the number is not prime. By doing this though, we repeat much of the work we’ve already done and get a worst case runtime of O(n) + [O(n) + O(n-1)+...+O(1)] (roughly). So, how can we make this more efficient? There is a rule that says that all composite numbers can be made by multiplying prime numbers together. By keeping track of the known primes, we can check if a number is prime by dividing it by all of the known primes below it. So here is what I came up with.

public ArrayList<Integer> primes;

void printPrimes (int x) {
    primes = new ArrayList<Integer>();
    addPrimes(x);
    for(int i = 0; i < primes.size(); i++) {
        System.out.print(primes.get(i) + ",");
    }
}

void addPrimes(int x) {
    int count = 3;
    while (count < x) {
        if(isPrime(count)) {
            primes.add(count);
        }
        count++;
    }
}
    
boolean isPrime(int x) {
    for(int i = 0; i < primes.size(); i++) {
        if (x % primes.get(i).intValue() == 0){
            return false;
        }
    }
    return true;
}

Instead of dividing by every integer below itself to check if a number is prime, we only check the primes we have already found. I’m sure there are more things we can do to optimize this further. If you have any suggestions let me know in the comments!