[Interview]Zillow Coding Test

Question 1) Given a string, write a routine that converts the string to a long, without using the

built in functions that would do this. Describe what (if any) limitations the code has. 

Question 2) Implement insert and delete in a tri-nary tree. A tri-nary tree is much like a binary

tree but with three child nodes for each parent instead of two -- with the left node being values

less than the parent, the right node values greater than the parent, and the middle nodes values

equal to the parent.

都是以前做过题目的变形，第一题可以参考String to Integer，第二题参考Remove Node in BST。Trinary树删除的区别就是注意我们有duplicates尽量先删duplicates，没有duplicates才用BST删除的方法，deleteMin中也是一样的。

代码如下，包括自己写的test case：

String to Long

	/*
	* specification of StringToLong function:
	*
	* 1. The function will skip as many as white spaces as possible and then deal with '+' or '-',
	* if there is no such sign, the number will be regarded as positive by default.
	* 2. If there are invalid characters following a valid number, the function will stop and
	* return the result when encounter invalid characters.
	* 3. If the result exceed the limit of long number, the function will return Long.MAX_VALUE or
	* Long.MIN_VALUE, which depends on the sign of that number.
	* 4. If there is no valid conversion, the function will return 0;
	*
	* example:
	* " 3456" -> 3456
	* " -29456 a" -> -29456
	* "9223372036854775808" -> 9223372036854775807
	* " +" -> 0
	*/
	public class StringToLong {
	public long covert(String s) {
	if (s == null)
	return 0;
	int len = s.length();
	int start = 0;
	boolean isNeg = false;
	long res = 0;
	//empty string
	if (len == 0)
	return 0;
	//skip white spaces
	while (start < len && s.charAt(start) == ' ')
	start++;
	//if reach end, return 0
	if (start == len)
	return 0;
	//deal with optional sign '+' and '-'
	if (s.charAt(start) == '+' || s.charAt(start) == '-') {
	isNeg = s.charAt(start) == '-'? true: false;
	start++;
	}
	//if reach end, return 0
	if (start == len)
	return 0;
	for (int i = start; i < len; i++) {
	//if encounter invalid character
	if (!isNum(s.charAt(i)))
	return res;
	int add = s.charAt(i) - '0';
	//test overflow
	if (isOverflow(isNeg, res, add))
	return isNeg? Long.MIN_VALUE: Long.MAX_VALUE;
	else
	res = isNeg? res * 10 - add: res * 10 + add;
	}
	return res;
	}
	private boolean isOverflow(boolean isNeg, long base, int add) {
	if (!isNeg) {
	long upperBound = (Long.MAX_VALUE - add) / 10;
	return base > upperBound;
	} else {
	long lowerBound = (Long.MIN_VALUE + add) / 10;
	return base < lowerBound;
	}
	}
	private boolean isNum(char c) {
	return c - '0' <= 9 && c - '0' >= 0;
	}
	public static void main(String[] strs) {
	test1();
	test2();
	test3();
	test4();
	test5();
	test6();
	test7();
	}
	/*
	*
	* Test Cases
	*
	*/
	//test random string
	private static void test1() {
	Long num1 = (long) (Math.random() * Long.MAX_VALUE);
	Long num2 = -(long) (Math.random() * Long.MAX_VALUE);
	StringToLong sTL = new StringToLong();
	if (num1 == sTL.covert(num1 + "") && num2 == sTL.covert(num2 + ""))
	System.out.println("Test Case 1 passed!");
	else
	System.out.println("Test Case 1 failed...");
	}
	//test empty string
	private static void test2() {
	StringToLong sTL = new StringToLong();
	if (sTL.covert("") == 0)
	System.out.println("Test Case 2 passed!");
	else
	System.out.println("Test Case 2 failed...");
	}
	//test multiple spaces with "+/-" sign
	private static void test3() {
	StringToLong sTL = new StringToLong();
	String num1 = "09286539937";
	String num2 = " 9377498";
	String num3 = " +8274";
	String num4 = " -27668836789";
	if (sTL.covert(num1) == 9286539937L && sTL.covert(num2) == 9377498
	&& sTL.covert(num3) == 8274 && sTL.covert(num4) == -27668836789L)
	System.out.println("Test Case 3 passed!");
	else
	System.out.println("Test Case 3 failed...");
	}
	//test invalid character
	private static void test4() {
	StringToLong sTL = new StringToLong();
	String num1 = "00000978741 ";
	String num2 = " -00000234564abnckdsuoe i237497284";
	if (sTL.covert(num1) == 978741 && sTL.covert(num2) == -234564)
	System.out.println("Test Case 4 passed!");
	else
	System.out.println("Test Case 4 failed...");
	}
	//test Long.MAX_VALUE and Long.MIN_VALUE
	private static void test5() {
	StringToLong sTL = new StringToLong();
	String num1 = Long.MAX_VALUE + "";
	String num2 = Long.MIN_VALUE + "";
	if (sTL.covert(num1) == Long.MAX_VALUE && sTL.covert(num2) == Long.MIN_VALUE)
	System.out.println("Test Case 5 passed!");
	else
	System.out.println("Test Case 5 failed...");
	}
	//test overflow
	private static void test6() {
	StringToLong sTL = new StringToLong();
	String num1 = "9223372036854775808";
	String num2 = "923840981238974365921734";
	String num3 = "-9223372036854775808";
	String num4 = "-209384843578320938423890482304823";
	if (sTL.covert(num1) == Long.MAX_VALUE && sTL.covert(num2) == Long.MAX_VALUE
	&& sTL.covert(num3) == Long.MIN_VALUE && sTL.covert(num4) == Long.MIN_VALUE)
	System.out.println("Test Case 6 passed!");
	else
	System.out.println("Test Case 6 failed...");
	}
	//test invalid input
	private static void test7() {
	StringToLong sTL = new StringToLong();
	String num1 = " ";
	String num2 = "+";
	String num3 = " a ";
	String num4 = "anclajsdfkl";
	if (sTL.covert(num1) == 0 && sTL.covert(num2) == 0 &&
	sTL.covert(num3) == 0 && sTL.covert(num4) == 0)
	System.out.println("Test Case 7 passed!");
	else
	System.out.println("Test Case 7 failed...");
	}
	}

view raw string to long.java hosted with ❤ by GitHub

Trinary Tree

	public class TrinaryTree<T extends Comparable<T>> {
	private class Node {
	private T value;
	private Node left;
	private Node mid;
	private Node right;
	public Node(T value) {
	this.value = value;
	left = null;
	right = null;
	}
	}
	private Node root;
	public TrinaryTree() {
	root = null;
	}
	public void insert(T value) {
	root = insert(root, value);
	}
	private Node insert(Node node, T value) {
	if (node == null) {
	Node n = new Node(value);
	return n;
	}
	int comp = value.compareTo(node.value);
	if (comp < 0)
	node.left = insert(node.left, value);
	else if (comp > 0)
	node.right = insert(node.right, value);
	else
	node.mid = insert(node.mid, value);
	return node;
	}
	public void delete(T value) {
	root = delete(root, value);
	}
	private Node delete(Node node, T value) {
	if (node == null)
	return null;
	int comp = value.compareTo(node.value);
	if (comp < 0)
	node.left = delete(node.left, value);
	else if (comp > 0)
	node.right = delete(node.right, value);
	else {
	if (node.mid != null)
	node.mid = delete(node.mid, value);
	else {
	if (node.left == null)
	return node.right;
	if (node.right == null)
	return node.left;
	//if has both left and right children
	Node x = node;
	//find successor
	node = findMin(node.right);
	node.right = deleteMin(x.right);
	node.left = x.left;
	}
	}
	return node;
	}
	private Node findMin(Node node) {
	while (node.left != null)
	node = node.left;
	while (node.mid != null)
	node = node.mid;
	return node;
	}
	//when delete min, first find if there is duplicate key
	//if found, delete duplicate, otherwise, delete that node
	private Node deleteMin(Node node) {
	if (node.left == null)
	return deleteMid(node);
	node.left = deleteMin(node.left);
	return node;
	}
	//delete duplicates
	private Node deleteMid(Node node) {
	if (node.mid == null)
	return node.right;
	node.mid = deleteMid(node.mid);
	return node;
	}
	//for test use
	/*
	* specification of serialize:
	*
	* The function serialize the trinary tree by using level order traversal, # indicate null,
	* all nodes with less then 3 children will be followed by # for each null children, except
	* for nodes in deepest level
	*/
	public String serialize() {
	return serialize(root);
	}
	private String serialize(Node root) {
	String str = "";
	LinkedList<Node> parent = new LinkedList<Node>();
	parent.add(root);
	boolean end = false;
	while (!end) {
	end = true;
	int size = parent.size();
	for (int i = 0; i < size; i++) {
	Node temp = parent.removeFirst();
	str += temp == null? "#": temp.value;
	str += ",";
	if (temp == null)
	continue;
	if (!isLeaf(temp))
	end = false;
	parent.add(temp.left);
	parent.add(temp.mid);
	parent.add(temp.right);
	}
	}
	return str.substring(0, str.length() - 1);
	}
	private boolean isLeaf(Node node) {
	return node.left == null && node.right == null && node.mid == null;
	}
	public static void main(String[] args) {
	test1();
	test2();
	test3();
	test4();
	}
	/*
	*
	* Test Cases
	*
	*/
	//test insert without duplicate
	private static void test1() {
	TrinaryTree<Integer> t = new TrinaryTree<Integer>();
	t.insert(10);
	t.insert(5);
	t.insert(15);
	t.insert(3);
	t.insert(7);
	t.insert(8);
	t.insert(9);
	t.insert(13);
	t.insert(14);
	t.insert(18);
	t.insert(16);
	//expected result after insertion
	String res = "10,5,#,15,3,#,7,13,#,18,#,#,#,#,#,8,#,#,14,16,#,#,#,#,9,#,#,#,#,#,#";
	if (res.equals(t.serialize()))
	System.out.println("Test Case 1 passed!");
	else
	System.out.println("Test Case 1 failed...");
	}
	//test delete without duplicate
	private static void test2() {
	TrinaryTree<Integer> t = new TrinaryTree<Integer>();
	t.insert(17);
	t.insert(10);
	t.insert(22);
	t.insert(5);
	t.insert(13);
	t.insert(19);
	t.insert(27);
	t.insert(4);
	t.insert(11);
	t.insert(14);
	t.insert(18);
	t.insert(20);
	t.insert(29);
	t.insert(3);
	t.insert(28);
	//expected result after insertion
	String res = "17,10,#,22,5,#,13,19,#,27,4,#,#,11,#,14,18,#,20,#,#,29,"
	+ "3,#,#,#,#,#,#,#,#,#,#,#,#,#,#,28,#,#";
	if (!res.equals(t.serialize())) {
	System.out.println("Test Case 2 failed...");
	return;
	}
	t.delete(10);
	//expected result after delete 10
	res = "17,11,#,22,5,#,13,19,#,27,4,#,#,#,#,14,18,#,20,#,#,29,3,#,#,#,#,#,#,#,#,#,#,#,28,#,#";
	if (!res.equals(t.serialize())) {
	System.out.println("Test Case 2 failed...");
	return;
	}
	t.delete(28);
	//expected result after delete 28
	res = "17,11,#,22,5,#,13,19,#,27,4,#,#,#,#,14,18,#,20,#,#,29,3,#,#,#,#,#,#,#,#,#,#,#,#,#,#";
	if (!res.equals(t.serialize())) {
	System.out.println("Test Case 2 failed...");
	return;
	}
	t.delete(27);
	//expected result after delete 27
	res = "17,11,#,22,5,#,13,19,#,29,4,#,#,#,#,14,18,#,20,#,#,#,3,#,#,#,#,#,#,#,#,#,#,#";
	if (!res.equals(t.serialize())) {
	System.out.println("Test Case 2 failed...");
	return;
	}
	t.delete(5);
	t.delete(19);
	t.delete(17);
	//expected result after multiple deletions
	res = "18,11,#,22,4,#,13,20,#,29,3,#,#,#,#,14,#,#,#,#,#,#";
	if (!res.equals(t.serialize()))
	System.out.println("Test Case 2 failed...");
	else
	System.out.println("Test Case 2 passed!");
	}
	//test insert with duplicates
	public static void test3() {
	TrinaryTree<Integer> t = new TrinaryTree<Integer>();
	t.insert(27);
	t.insert(15);
	t.insert(33);
	t.insert(7);
	t.insert(22);
	t.insert(30);
	t.insert(39);
	t.insert(27);
	t.insert(27);
	t.insert(15);
	t.insert(7);
	t.insert(9);
	t.insert(22);
	t.insert(31);
	t.insert(35);
	t.insert(39);
	t.insert(8);
	t.insert(9);
	t.insert(22);
	t.insert(30);
	t.insert(30);
	//expected result after insertion
	String res = "27,15,27,33,7,15,22,#,27,#,30,#,39,#,7,9,#,#,#,#,22,#,#,#,#,#,30,31,35,39,"
	+ "#,#,#,#,8,9,#,#,22,#,#,30,#,#,#,#,#,#,#,#,#,#";
	if (!res.equals(t.serialize()))
	System.out.println("Test Case 3 failed...");
	else
	System.out.println("Test Case 3 passed!");
	}
	//test delete with duplicates
	public static void test4() {
	TrinaryTree<Integer> t = new TrinaryTree<Integer>();
	t.insert(27);
	t.insert(15);
	t.insert(33);
	t.insert(7);
	t.insert(22);
	t.insert(30);
	t.insert(39);
	t.insert(27);
	t.insert(27);
	t.insert(15);
	t.insert(7);
	t.insert(9);
	t.insert(22);
	t.insert(31);
	t.insert(35);
	t.insert(39);
	t.insert(8);
	t.insert(9);
	t.insert(22);
	t.insert(30);
	t.insert(30);
	//expected result after deletion
	String res = "27,15,27,33,7,15,22,#,27,#,30,#,39,#,7,9,#,#,#,#,22,#,#,#,#,#,30,31,35,39,"
	+ "#,#,#,#,8,9,#,#,22,#,#,30,#,#,#,#,#,#,#,#,#,#";
	if (!res.equals(t.serialize())){
	System.out.println("Test Case 4 failed...");
	return;
	}
	//delete 27
	t.delete(27);
	//expected result after delete 27
	res = "27,15,27,33,7,15,22,#,#,#,30,#,39,#,7,9,#,#,#,#,22,#,#,30,31,35,39,"
	+ "#,#,#,#,8,9,#,#,22,#,#,30,#,#,#,#,#,#,#,#,#,#";
	if (!res.equals(t.serialize())){
	System.out.println("Test Case 4 failed...");
	return;
	}
	//delete 7
	t.delete(7);
	//expected result after delete 7
	res = "27,15,27,33,7,15,22,#,#,#,30,#,39,#,#,9,#,#,#,#,22,#,#,30,31,35,39,"
	+ "#,8,9,#,#,22,#,#,30,#,#,#,#,#,#,#,#,#,#";
	if (!res.equals(t.serialize())){
	System.out.println("Test Case 4 failed...");
	return;
	}
	//multiple deletions
	t.delete(22);
	t.delete(27);
	t.delete(27);
	//expected result after delete 7
	res = "30,15,#,33,7,15,22,30,#,39,#,#,9,#,#,#,#,22,#,#,30,31,35,39,"
	+ "#,8,9,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#";
	if (!res.equals(t.serialize()))
	System.out.println("Test Case 4 failed...");
	else
	System.out.println("Test Case 4 passed");
	}
	}

view raw trinary tree.java hosted with ❤ by GitHub