一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3227|回复: 19
收起左侧

[其他] zillow coding test..挂了.求分析..自己写的test cases都能过的e...

[复制链接] |试试Instant~ |关注本帖
kelvinzhong 发表于 2014-11-5 01:38:44 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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:
  1. long stringToLong(String s)
  2. {
  3.     /* code goes here to convert a string to a long */
  4. }
  5. void test() {
  6.     long i = stringToLong("123");
  7.     if (i == 123)
  8.         // success
  9.     else
  10. // failure
  11. }
复制代码
My answer:
  1. //Limitations:
  2. //1. This function hasn't deal with the problem that the value stored in the string is larger than a long can hold.
  3. //2. This function hasn't deal with the situation that the value stored in the string is a decimal number.
  4. long stringToLong(string s){

  5.     //filter the white space at the end and the beginning.
  6.         int start = 0, end = s.length() - 1;
  7.         while(start < s.length()){
  8.                 if(s[start] == ' '){
  9.                         start += 1;
  10.                 }else{
  11.                         break;
  12.                 }
  13.         }
  14.         while(end > 0){
  15.                 if(s[end] == ' '){
  16.                         end -= 1;
  17.                 }else{
  18.                         break;
  19.                 }
  20.         }
  21.         //empty input, return 0
  22.         if(start > end){
  23.                 return 0;
  24.         }

  25.         //check the sign
  26.         int sign = 1;
  27.         if(s[start] == '+'){
  28.                 start += 1;
  29.         }else if(s[start] == '-'){
  30.                 start += 1;
  31.                 sign = -1;
  32.         }

  33.         //input validation
  34.         for(int i = start; i <= end; i ++){
  35.                 if((s[i] < '0') || (s[i] > '9'))
  36.                         return 0;
  37.         }

  38.         //convert the string into long
  39.         long ret = 0;
  40.         for(int i = start; i <= end; i ++){
  41.                 ret = ret * 10 + (s[i] - '0');
  42.         }
  43.         return ret * sign;
  44. }
  45. //Test Case:
  46. void test_q1(){
  47.         long i = stringToLong("");
  48.         cout<<i<<endl;
  49.         i = stringToLong("    ");
  50.         cout<<i<<endl;
  51.         i = stringToLong("123");
  52.         cout<<i<<endl;
  53.         i = stringToLong("-123");
  54.         cout<<i<<endl;
  55.         i = stringToLong("+123");
  56.         cout<<i<<endl;
  57.     i = stringToLong("-123123132132132");
  58.     cout<<i<<endl;
  59. }
复制代码
Question2:
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.

My answer:
  1. // Trinary Node Difinition
  2. class Node{
  3. public:
  4.     Node * right;
  5.         Node * left;
  6.         Node * mid;
  7.         int val;
  8.         Node(int x){
  9.                 val = x;
  10.                 left = NULL;
  11.                 right = NULL;
  12.                 mid = NULL;
  13.         }
  14. };

  15. //insert function
  16. void insert(Node * root, int x){
  17.         Node * newnode = new Node(x);
  18.         if(root == NULL){
  19.                 root = newnode;
  20.                 return;
  21.         }

  22.         //iterate to the leaf, then insert the new node.
  23.         Node * cur = root;
  24.         while(cur != NULL){
  25.                 //if current node's value is equal to x
  26.                 if(cur->val == x){
  27.                         if(cur->mid == NULL){
  28.                                 cur->mid = newnode;
  29.                                 break;
  30.                         }else{
  31.                                 cur = cur->mid;
  32.                         }
  33.                 }
  34.                 //if current node's value is bigger than x
  35.                 else if(cur->val > x){
  36.                         if(cur->left == NULL){
  37.                                 cur->left = newnode;
  38.                                 break;
  39.                         }else{
  40.                                 cur = cur->left;
  41.                         }
  42.                 }
  43.                 //if current node's value is smaller than x
  44.                 else if(cur->val < x){
  45.                         if(cur->right == NULL){
  46.                                 cur->right = newnode;
  47.                                 break;
  48.                         }else{
  49.                                 cur = cur->right;
  50.                         }
  51.                 }
  52.         }
  53. }

  54. //delete function
  55. //if there are multiple nodes with value x, iterate to the last one.
  56. Node * delete_node(Node * root, int x){
  57.         if(root == NULL){
  58.                 return NULL;
  59.         }
  60.         Node * cur = root;
  61.         Node * pre = root;
  62.        
  63.         //iterate to the node with value x;
  64.         while(cur != NULL){
  65.                 //if current node's value is equal to x
  66.                 if(cur->val == x){
  67.                         if(cur->mid != NULL){
  68.                                 pre = cur;
  69.                                 cur = cur->mid;
  70.                         }else{
  71.                                 break;
  72.                         }
  73.                 }
  74.                 //if current node's value is larger than x
  75.                 else if(cur->val > x){
  76.                         pre = cur;
  77.                         cur = cur->left;
  78.                 }
  79.                 //if current node's value is smaller than x
  80.                 else if(cur->val < x){
  81.                         pre = cur;
  82.                         cur = cur->right;
  83.                 }
  84.         }
  85.         //if there is no node with value x
  86.         if(cur == NULL){
  87.                 return root;
  88.         }

  89.         //if the desired deleted node is root
  90.         if(cur == root){
  91.                 //construct a temporary parent of the root for further process
  92.                 pre = new Node(0);
  93.                 pre->left = root;
  94.         }

  95.         //delete cur node and replace it with another node
  96.         //if cur node is a leaf
  97.         if(cur->left == NULL && cur->right == NULL){
  98.                 if(pre->left == cur){
  99.                         pre->left = NULL;
  100.                 }else if(pre->right == cur){
  101.                         pre->right = NULL;
  102.                 }else if(pre->mid == cur){
  103.                         pre->mid = NULL;
  104.                 }
  105.         }
  106.         //if cur node only have one node
  107.         else if(cur->left == NULL && cur->right != NULL){
  108.             if(pre->left == cur){
  109.                         pre->left = cur->right;
  110.                 }else if(pre->right == cur){
  111.                         pre->right = cur->right;
  112.                 }
  113.         }
  114.         else if(cur->right == NULL && cur->left != NULL){
  115.                 if(pre->left == cur){
  116.                         pre->left = cur->left;
  117.                 }else if(pre->right == cur){
  118.                         pre->right = cur->left;
  119.                 }
  120.         }
  121.         //if cur node have two nodes
  122.         else{
  123.                 Node * pre_leftmost = cur;
  124.                 Node * leftmost = cur->left;
  125.                 //iterate to the leftmost leave
  126.                 while(leftmost->right != NULL){
  127.                         pre_leftmost = leftmost;
  128.                         leftmost = leftmost->right;
  129.                 }

  130.                 //if cur->left is the right most node of the left branch of cur
  131.                 if(pre_leftmost != cur){
  132.                         pre_leftmost->right = leftmost->left;
  133.                         leftmost->left = pre_leftmost;
  134.                 }

  135.                 leftmost->right = cur->right;
  136.                 if(pre->left == cur){
  137.                         pre->left = leftmost;
  138.                 }else if(pre->right == cur){
  139.                         pre->right = leftmost;
  140.                 }
  141.         }

  142.         //if the desired deleted node is root
  143.         if(cur == root){
  144.                 root = pre->left;

  145.         }

  146.         return root;
  147. }

  148. //Test Case:
  149. void test_q2(){
  150.         Node * root = new Node(5);
  151.         insert(root,5);
  152.         insert(root,4);
  153.         insert(root,9);
  154.     insert(root,10);
  155.         insert(root,2);
  156.         insert(root,2);
  157.         insert(root,7);
  158.    
  159.     //level order should be 5,4,5,9,2,7,10,2
  160.     cout<<root->val<<endl;
  161.     cout<<root->left->val<<endl;
  162.     cout<<root->mid->val<<endl;
  163.     cout<<root->right->val<<endl;
  164.     cout<<root->left->left->val<<endl;
  165.     cout<<root->right->left->val<<endl;
  166.     cout<<root->right->right->val<<endl;
  167.     cout<<root->left->left->mid->val<<endl;
  168.    
  169.     cout<<endl;
  170.    
  171.     root = delete_node(root,5);
  172.     root = delete_node(root,5);
  173.     //level order should be 4,2,9,2,7,10
  174.     cout<<root->val<<endl;
  175.     cout<<root->left->val<<endl;
  176.     cout<<root->right->val<<endl;
  177.     cout<<root->left->mid->val<<endl;
  178.     cout<<root->right->left->val<<endl;
  179.     cout<<root->right->right->val<<endl;
  180.    
  181.     cout<<endl;
  182.    
  183.     root = delete_node(root,10);
  184.     root = delete_node(root,9);
  185.     //level order should be 4,2,7,2
  186.     cout<<root->val<<endl;
  187.     cout<<root->left->val<<endl;
  188.     cout<<root->right->val<<endl;
  189.     cout<<root->left->mid->val<<endl;
  190.    
  191. }
复制代码

评分

3

查看全部评分

daihao0310 发表于 2014-11-5 01:52:57 | 显示全部楼层
第一道题感觉楼主没有考虑大于max_value和小于min_value的情况吧,楼主在limitation里虽然说明这种情况。但在具体的实现中却没有体现出来。
另外,麻烦问一下楼主online交上去之后多久给了回信?
回复 支持 反对

使用道具 举报

 楼主| kelvinzhong 发表于 2014-11-5 01:55:58 | 显示全部楼层
daihao0310 发表于 2014-11-5 01:52
第一道题感觉楼主没有考虑大于max_value和小于min_value的情况吧,楼主在limitation里虽然说明这种情况。但 ...

e..因为我确实不知道long的max_value 和min_value是多少.....一个星期...
回复 支持 反对

使用道具 举报

kurtwang 发表于 2014-11-5 01:58:19 | 显示全部楼层
感觉他家coding test挂人是随机的。。。
回复 支持 反对

使用道具 举报

 楼主| kelvinzhong 发表于 2014-11-5 02:05:45 | 显示全部楼层
kurtwang 发表于 2014-11-5 01:58
感觉他家coding test挂人是随机的。。。

尊的吗?。。
回复 支持 反对

使用道具 举报

daihao0310 发表于 2014-11-5 02:14:56 | 显示全部楼层
kelvinzhong 发表于 2014-11-5 01:55
e..因为我确实不知道long的max_value 和min_value是多少.....一个星期...

那我觉得我应该也黑了……这么久zillow还不给我回复~和楼主共勉!加油!
回复 支持 反对

使用道具 举报

xujingcheng 发表于 2014-11-5 04:09:59 | 显示全部楼层
zillow的coding test我也交了好久没回复了
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-11-5 04:14:09 | 显示全部楼层
楼主注意下代码简洁和test全面性吧。
回复 支持 反对

使用道具 举报

mayingjie116 发表于 2014-11-5 04:38:21 | 显示全部楼层
感觉第一题写得太长了。。
回复 支持 反对

使用道具 举报

pazzaintermilan 发表于 2014-11-5 04:42:34 | 显示全部楼层
lz 怎么知道挂了? 收到thank you email 了?
回复 支持 反对

使用道具 举报

hakase 发表于 2014-11-5 06:26:36 | 显示全部楼层
按当时用java写的,注意了MAX_VALUE和MIN_VALUE,并且用regex matcher先validate输入,如果出问题抛异常,结果收到电面。
看看JDK里面的源码就知道怎么写了。
回复 支持 反对

使用道具 举报

kurtwang 发表于 2014-11-5 07:39:05 | 显示全部楼层

真的。。我第一个判断overflow的条件都写错了。。也给我面试了。。glassdoor上一大堆大牛挂了这个code test不知道为什么
回复 支持 反对

使用道具 举报

 楼主| kelvinzhong 发表于 2014-11-6 01:19:25 | 显示全部楼层
北美农民 发表于 2014-11-5 04:14
楼主注意下代码简洁和test全面性吧。

版主的意思是我的代码太冗长,就是一个for循环能做的事情就不要拆成两个for?, 然后test是指要注意coner case吗?
回复 支持 反对

使用道具 举报

guomin1314 发表于 2014-11-9 15:47:00 | 显示全部楼层
我也做的这两个题,收到了面试邀请
回复 支持 反对

使用道具 举报

MCwong 发表于 2014-11-15 13:19:31 | 显示全部楼层
hakase 发表于 2014-11-5 06:26
按当时用java写的,注意了MAX_VALUE和MIN_VALUE,并且用regex matcher先validate输入,如果出问题抛异常, ...

请问第一题charAt()可以用么?题目要求"without building in function", 它的本意是不让直接用parseLong吧?
回复 支持 反对

使用道具 举报

hakase 发表于 2014-11-16 00:14:10 | 显示全部楼层
MCwong 发表于 2014-11-15 13:19
请问第一题charAt()可以用么?题目要求"without building in function", 它的本意是不让直接用parseLong ...

没错。看看OpenJDK怎么写的。
回复 支持 反对

使用道具 举报

zhaoweigg 发表于 2014-11-16 02:07:14 | 显示全部楼层
lz第二题写的也太长了吧,除去test 写了一百多行,clean
回复 支持 反对

使用道具 举报

YJM1024 发表于 2014-11-30 08:49:45 | 显示全部楼层
我觉得应该几十行代码就可以了吧。也许对方是人工审核代码,这样就有点麻烦了。
回复 支持 反对

使用道具 举报

pazzaintermilan 发表于 2014-12-2 08:09:47 | 显示全部楼层
一个月之后才给了我phone interview....
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 14:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表