Zillow
Question 1
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. For
example:
long stringToLong(String s)
{
/* code goes here to convert a string to a long */
}
void test()
{
i = stringToLong("123");
if (i == 123)
// success
else
// failure
}
related
- Java中的long型数据
long型数据是primitive data type中的一种
-》64 bit的integer
-》signed long: -2^63 ~ 2^63-1
-》unsigned long: 0 ~ 2^64-1
- Java中的Long class里有能够实现将String转成long型的build-in method
//Parses the string argument as a signed decimal long.
static long parseLong(String s)
solution
3. 如果要转的数大于或小于long的范围：抛异常
如何比较？ 1）直接比string－－－》不好 2）先转成数再比
需要转成一个超过long的上下限的数：BigInteger class
//class BigInteger
//constructor
//Translates the decimal String representation of a BigInteger into a BigInteger.
BigInteger(String val)
//method
//Compares this BigInteger with the specified BigInteger.
int compareTo(BigInteger val)
Long class 中long型数据上下限
//A constant holding the maximum value a long can have, 2^63-1.
static long MAX_VALUE
//A constant holding the minimum value a long can have, -2^63.
static long MIN_VALUE
Code
static long parseLong(String str) throws Exception {
//corner case
if(str.length() == 0 || str == null) throw new Exception("Not a valid string!");
//long
long res = 0;
long base = 1;
char digitChar;
//convert from the lowest digit to highest digit according base
for(int i = str.length()-1; i >= 1; i-- ) {
digitChar = str.charAt(i);
//if invalid digit, throw exception
if(digitChar < '0' || digitChar > '9') {
throw new Exception("Not a valid string!");
}
else {
res = res + base*(digitChar - '0');
base = base*10;
}
}
//check the 1st string
digitChar = str.charAt(0);
//if '+'
if(digitChar == '+') {
//check if bigger than Long.MAX_VALUE
BigInteger bigInt = new BigInteger(str);
String maxLongStr = Long.toString(Long.MAX_VALUE);
BigInteger maxLong = new BigInteger(maxLongStr);
if(bigInt.compareTo(maxLong) > 0) throw new Exception("Max limit exceed!");
}
//if '-'
else if(digitChar == '-') {
//check if smaller than MIN.MAX_VALUE
BigInteger minInt = new BigInteger(str);
String minLongStr = Long.toString(Long.MIN_VALUE);
BigInteger minLong = new BigInteger(minLongStr);
if(minInt.compareTo(minLong) < 0) throw new Exception("Min limit exceed!");
res = -1*res;
}
//if '0'~'9'
else if(digitChar >= '0' && digitChar <= '9') {
//check if bigger than Long.MAX_VALUE
BigInteger bigInt = new BigInteger(str);
String maxLongStr = Long.toString(Long.MAX_VALUE);
BigInteger maxLong = new BigInteger(maxLongStr);
if(bigInt.compareTo(maxLong) > 0) throw new Exception("Max limit exceed!");
res = res + base*(digitChar - '0');
}
//else
else throw new Exception();
return res;
}
Question 2
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.
For example, suppose I added the following nodes to the tree in this order: 5, 4, 9, 5, 7, 2, 2.
The resulting tree would look like this:
5
/ | \
4 5 9
/ /
2 7
|
2
Code
public void insert(int val) {
//before insert, we need to find where to insert. e.g Node n's left Node
if(root == null) root = new Node(val);
else insertHelper(root, val);
}
private void insertHelper(Node root, int val) {
//recursion
if(root.val > val) {
if(root.left == null) {
root.left = new Node(val);
return;
}
else insertHelper(root.left, val);
}
else if(root.val == val) {
if(root.mid == null) {
root.mid = new Node(val);
return;
}
else insertHelper(root.mid, val);
}
else {
if(root.right == null) {
root.right = new Node(val);
return;
}
else insertHelper(root.right, val);
}
}
/*
* Please complete this method.
* Deletes only one instance of val from the tree.
* If val does not exist in the tree, do nothing.
*/
public void delete(int val) {
if(root == null) return;
else {
deleteHelper(root, val);
}
}
private Node parent = null;
private static final int L = 0;
private static final int R = 1;
private static final int Mid = 2;
private int whichChild = L;
private void deleteHelper(Node root, int val) {
//we need to find the a Node (let's call it n) with valur val first
//base
if(root == null) {
//Node with value val doesn't exsit, do nothing
return;
}
//recursion
if(root.val > val) {
//n may be in sub left branch
if(root.left != null) {
//record parent & which child info
parent = root;
whichChild = L;
}
deleteHelper(root.left, val);
}
else if(root.val < val) {
//n may be in sub right branch
if(root.right != null) {
//record parent & which child info
parent = root;
whichChild = R;
}
deleteHelper(root.right, val);
}
if(root.val == val) {
//delete n, reconstruct the tree
//1.if root has mid child
if(root.mid != null) {
//record parent & which child info
parent = root;
whichChild = Mid;
deleteHelper(root.mid, val);
}
//2.if root has right child
else if(root.right != null) {
//record parent & which child info
parent = root;
whichChild = R;
//find the smallest of right sub tree
int min = minNodeVal(root.right);
root.val = min;
//delete smallest of sub tree
deleteHelper(root.right, min);
}
//3.if root has only left child
else if(root.left != null){
root = root.left;
}
//4. if root has no child
else {
if(whichChild == L) parent.left= null;
if(whichChild == Mid) parent.mid= null;
if(whichChild == R) parent.right= null;
}
}
}
private int minNodeVal(Node root) {
if(root.left != null){
return minNodeVal(root.left);
}
else
return root.val;
}