登录
  • #刷题

zi‌‌‍‍‌‍‍‌‍‌‍‍‌‍‍‍‍‍‍‍‌‌‌‌‌‌‌‍‌‌‍‌llow coding test..挂了.求分析..自己写的test cases都能过的e...

kelvinzhong
5126
18
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)[br][/br][br][/br]{[br][/br][br][/br]    /* code goes here to convert a string to a long */[br][/br][br][/br]}[br][/br][br][/br]void test() {[br][/br][br][/br]    long i = stringToLong("123");[br][/br][br][/br]    if (i == 123)[br][/br][br][/br]        // success[br][/br][br][/br]    else[br][/br][br][/br]// failure[br][/br][br][/br]}
My answer:
//Limitations:[br][/br][br][/br]//1. This function hasn't deal with the problem that the value stored in the string is larger than a long can hold.[br][/br][br][/br]//2. This function hasn't deal with the situation that the value stored in the string is a decimal number.[br][/br][br][/br]long stringToLong(string s){[br][/br][br][/br]    //filter the white space at the end and the beginning.[br][/br][br][/br]	int start = 0, end = s.length() - 1;[br][/br][br][/br]	while(start < s.length()){[br][/br][br][/br]		if(s[start] == ' '){[br][/br][br][/br]			start += 1;[br][/br][br][/br]		}else{[br][/br][br][/br]			break;[br][/br][br][/br]		}[br][/br][br][/br]	}[br][/br][br][/br]	while(end > 0){[br][/br][br][/br]		if(s[end] == ' '){[br][/br][br][/br]			end -= 1;[br][/br][br][/br]		}else{[br][/br][br][/br]			break;[br][/br][br][/br]		}[br][/br][br][/br]	}[br][/br][br][/br]	//empty input, return 0[br][/br][br][/br]	if(start > end){[br][/br][br][/br]		return 0;[br][/br][br][/br]	}[br][/br][br][/br]	//check the sign[br][/br][br][/br]	int sign = 1;[br][/br][br][/br]	if(s[start] == '+'){[br][/br][br][/br]		start += 1;[br][/br][br][/br]	}else if(s[start] == '-'){[br][/br][br][/br]		start += 1;[br][/br][br][/br]		sign = -1;[br][/br][br][/br]	}[br][/br][br][/br]	//input validation[br][/br][br][/br]	for(int i = start; i <= end; i ++){[br][/br][br][/br]		if((s[i] < '0') || (s[i] > '9'))[br][/br][br][/br]			return 0;[br][/br][br][/br]	}[br][/br][br][/br]	//convert the string into long[br][/br][br][/br]	long ret = 0;[br][/br][br][/br]	for(int i = start; i <= end; i ++){[br][/br][br][/br]		ret = ret * 10 + (s[i] - '0');[br][/br][br][/br]	}[br][/br][br][/br]	return ret * sign;[br][/br][br][/br]}[br][/br][br][/br]//Test Case:[br][/br][br][/br]void test_q1(){[br][/br][br][/br]	long i = stringToLong("");[br][/br][br][/br]	cout<<i<<endl;[br][/br][br][/br]	i = stringToLong("    ");[br][/br][br][/br]	cout<<i<<endl;[br][/br][br][/br]	i = stringToLong("123");[br][/br][br][/br]	cout<<i<<endl;[br][/br][br][/br]	i = stringToLong("-123");[br][/br][br][/br]	cout<<i<<endl;[br][/br][br][/br]	i = stringToLong("+123");[br][/br][br][/br]	cout<<i<<endl;[br][/br][br][/br]    i = stringToLong("-123123132132132");[br][/br][br][/br]    cout<<i<<endl;[br][/br][br][/br]}Question2:[br][/br][br][/br]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.[br][/br][br][/br]My answer:[code]// Trinary Node Difinition[br][/br][br][/br]class Node{[br][/br][br][/br]public:[br][/br][br][/br]    Node * right;[br][/br][br][/br]	Node * left;[br][/br][br][/br]	Node * mid;[br][/br][br][/br]	int val;[br][/br][br][/br]	Node(int x){[br][/br][br][/br]		val = x;[br][/br][br][/br]		left = NULL;[br][/br][br][/br]		right = NULL;[br][/br][br][/br]		mid = NULL;[br][/br][br][/br]	}[br][/br][br][/br]};[br][/br][br][/br]//insert function[br][/br][br][/br]void insert(Node * root, int x){[br][/br][br][/br]	Node * newnode = new Node(x);[br][/br][br][/br]	if(root == NULL){[br][/br][br][/br]		root = newnode;[br][/br][br][/br]		return;[br][/br][br][/br]	}[br][/br][br][/br]	//iterate to the leaf, then insert the new node.[br][/br][br][/br]	Node * cur = root;[br][/br][br][/br]	while(cur != NULL){[br][/br][br][/br]		//if current node's value is equal to x[br][/br][br][/br]		if(cur->val == x){[br][/br][br][/br]			if(cur->mid == NULL){[br][/br][br][/br]				cur->mid = newnode;[br][/br][br][/br]				break;[br][/br][br][/br]			}else{[br][/br][br][/br]				cur = cur->mid;[br][/br][br][/br]			}[br][/br][br][/br]		}[br][/br][br][/br]		//if current node's value is bigger than x[br][/br][br][/br]		else if(cur->val > x){[br][/br][br][/br]			if(cur->left == NULL){[br][/br][br][/br]				cur->left = newnode;[br][/br][br][/br]				break;[br][/br][br][/br]			}else{[br][/br][br][/br]				cur = cur->left;[br][/br][br][/br]			}[br][/br][br][/br]		}[br][/br][br][/br]		//if current node's value is smaller than x[br][/br][br][/br]		else if(cur->val < x){[br][/br][br][/br]			if(cur->right == NULL){[br][/br][br][/br]				cur->right = newnode;[br][/br][br][/br]				break;[br][/br][br][/br]			}else{[br][/br][br][/br]				cur = cur->right;[br][/br][br][/br]			}[br][/br][br][/br]		}[br][/br][br][/br]	}[br][/br][br][/br]}[br][/br][br][/br]//delete function[br][/br][br][/br]//if there are multiple nodes with value x, iterate to the last one.[br][/br][br][/br]Node * delete_node(Node * root, int x){[br][/br][br][/br]	if(root == NULL){[br][/br][br][/br]		return NULL;[br][/br][br][/br]	}[br][/br][br][/br]	Node * cur = root;[br][/br][br][/br]	Node * pre = root;[br][/br][br][/br]	[br][/br][br][/br]	//iterate to the node with value x;[br][/br][br][/br]	while(cur != NULL){[br][/br][br][/br]		//if current node's value is equal to x[br][/br][br][/br]		if(cur->val == x){[br][/br][br][/br]			if(cur->mid != NULL){[br][/br][br][/br]				pre = cur;[br][/br][br][/br]				cur = cur->mid;[br][/br][br][/br]			}else{[br][/br][br][/br]				break;[br][/br][br][/br]			}[br][/br][br][/br]		}[br][/br][br][/br]		//if current node's value is larger than x[br][/br][br][/br]		else if(cur->val > x){[br][/br][br][/br]			pre = cur;[br][/br][br][/br]			cur = cur->left;[br][/br][br][/br]		}[br][/br][br][/br]		//if current node's value is smaller than x[br][/br][br][/br]		else if(cur->val < x){[br][/br][br][/br]			pre = cur;[br][/br][br][/br]			cur = cur->right;[br][/br][br][/br]		}[br][/br][br][/br]	}[br][/br][br][/br]	//if there is no node with value x[br][/br][br][/br]	if(cur == NULL){[br][/br][br][/br]		return root;[br][/br][br][/br]	}[br][/br][br][/br]	//if the desired deleted node is root[br][/br][br][/br]	if(cur == root){[br][/br][br][/br]		//construct a temporary parent of the root for further process[br][/br][br][/br]		pre = new Node(0);[br][/br][br][/br]		pre->left = root;[br][/br][br][/br]	}[br][/br][br][/br]	//delete cur node and replace it with another node[br][/br][br][/br]	//if cur node is a leaf[br][/br][br][/br]	if(cur->left == NULL && cur->right == NULL){[br][/br][br][/br]		if(pre->left == cur){[br][/br][br][/br]			pre->left = NULL;[br][/br][br][/br]		}else if(pre->right == cur){[br][/br][br][/br]			pre->right = NULL;[br][/br][br][/br]		}else if(pre->mid == cur){[br][/br][br][/br]			pre->mid = NULL;[br][/br][br][/br]		}[br][/br][br][/br]	}[br][/br][br][/br]	//if cur node only have one node[br][/br][br][/br]	else if(cur->left == NULL && cur->right != NULL){[br][/br][br][/br]    	if(pre->left == cur){[br][/br][br][/br]			pre->left = cur->right;[br][/br][br][/br]		}else if(pre->right == cur){[br][/br][br][/br]			pre->right = cur->right;[br][/br][br][/br]		}[br][/br][br][/br]	}[br][/br][br][/br]	else if(cur->right == NULL && cur->left != NULL){[br][/br][br][/br]		if(pre->left == cur){[br][/br][br][/br]			pre->left = cur->left;[br][/br][br][/br]		}else if(pre->right == cur){[br][/br][br][/br]			pre->right = cur->left;[br][/br][br][/br]		}[br][/br][br][/br]	}[br][/br][br][/br]	//if cur node have two nodes[br][/br][br][/br]	else{[br][/br][br][/br]		Node * pre_leftmost = cur;[br][/br][br][/br]		Node * leftmost = cur->left;[br][/br][br][/br]		//iterate to the leftmost leave[br][/br][br][/br]		while(leftmost->right != NULL){[br][/br][br][/br]			pre_leftmost = leftmost;[br][/br][br][/br]			leftmost = leftmost->right;[br][/br][br][/br]		}[br][/br][br][/br]		//if cur->left is the right most node of the left branch of cur[br][/br][br][/br]		if(pre_leftmost != cur){[br][/br][br][/br]			pre_leftmost->right = leftmost->left;[br][/br][br][/br]			leftmost->left = pre_leftmost;[br][/br][br][/br]		}[br][/br][br][/br]		leftmost->right = cur->right;[br][/br][br][/br]		if(pre->left == cur){[br][/br][br][/br]			pre->left = leftmost;[br][/br][br][/br]		}else if(pre->right == cur){[br][/br][br][/br]			pre->right = leftmost;[br][/br][br][/br]		}[br][/br][br][/br]	}[br][/br][br][/br]	//if the desired deleted node is root[br][/br][br][/br]	if(cur == root){[br][/br][br][/br]		root = pre->left;[br][/br][br][/br]	}[br][/br][br][/br]	return root;[br][/br][br][/br]}[br][/br][br][/br]//Test Case:[br][/br][br][/br]void test_q2(){[br][/br][br][/br]	Node * root = new Node(5);[br][/br][br][/br]	insert(root,5);[br][/br][br][/br]	insert(root,4);[br][/br][br][/br]	insert(root,9);[br][/br][br][/br]    insert(root,10);[br][/br][br][/br]	insert(root,2);[br][/br][br][/br]	insert(root,2);[br][/br][br][/br]	insert(root,7);[br][/br][br][/br]    [br][/br][br][/br]    //level order should be 5,4,5,9,2,7,10,2[br][/br][br][/br]    cout<<root->val<<endl;[br][/br][br][/br]    cout<<root->left->val<<endl;[br][/br][br][/br]    cout<<root->mid->val<<endl;[br][/br][br][/br]    cout<<root->right->val<<endl;[br][/br][br][/br]    cout<<root->left->left->val<<endl;[br][/br][br][/br]    cout<<root->right->left->val<<endl;[br][/br][br][/br]    cout<<root->right->right->val<<endl;[br][/br][br][/br]    cout<<root->left->left->mid->val<<endl;[br][/br][br][/br]    [br][/br][br][/br]    cout<<endl;[br][/br][br][/br]    [br][/br][br][/br]    root = delete_node(root,5);[br][/br][br][/br]    root = delete_node(root,5);[br][/br][br][/br]    //level order should be 4,2,9,2,7,10[br][/br][br][/br]    cout<<root->val<<endl;[br][/br][br][/br]    cout<<root->left->val<<endl;[br][/br][br][/br]    cout<<root->right->val<<endl;[br][/br][br][/br]    cout<<root->left->mid->val<<endl;[br][/br][br][/br]    cout<<root->right->left->val<<endl;[br][/br][br][/br]    cout<<root->right->right->val<<endl;[br][/br][br][/br]    [br][/br][br][/br]    cout<<endl;[br][/br][br][/br]    [br][/br][br][/br]    root = delete_node(root,10);[br][/br][br][/br]    root = delete_node(root,9);[br][/br][br][/br]    //level order should be 4,2,7,2[br][/br][br][/br]    cout<<root->val<<endl;[br][/br][br][/br]    cout<<root->left->val<<endl;[br][/br][br][/br]    cout<<root->right->val<<endl;[br][/br][br][/br]    cout<<root->left->mid->val<<endl;[br][/br][br][/br]    [br][/br][br][/br]}[/code][/i][/i][/i]
18条回复
热度排序

发表回复