一亩三分地论坛

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

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

业呼的fb店面面经

[复制链接] |试试Instant~ |关注本帖
craiglin1992 发表于 2015-11-3 05:51:49 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@Facebook - 校园招聘会 - 校园招聘会 |Otherfresh grad应届毕业生

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

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

x
刚刚面完facebook面试,发上来攒人品,希望大家都有机会!
1. divide a/b without using division operation, needs to be better than O(n). from: 1point3acres.com/bbs
2. longest path in a tree (between any two nodes)
希望帮到大家,祝大家成功!


补充内容 (2015-11-3 05:52):
第一题是两个int,返回的也是int
 楼主| craiglin1992 发表于 2015-11-3 05:52:12 | 显示全部楼层
第一题是两个int
回复 支持 反对

使用道具 举报

miss_snow 发表于 2015-11-3 07:21:50 | 显示全部楼层
一会儿也电面,好紧张( ▼-▼ )
回复 支持 反对

使用道具 举报

pacman 发表于 2015-11-3 07:59:41 | 显示全部楼层
第一题目测和快速幂差不多
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-3 08:42:22 | 显示全部楼层
第二题
  1. class Solution {

  2. public:

  3. int max_len;
  4. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  5. int height(TreeNode* root) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.         if(root == NULL) return 0;
  7.        
  8.         int l = height(root->left);
  9.         int r = height(root->right);. 1point 3acres 璁哄潧
  10.        
  11.         max_len = max(max_len, l + r + 1);

  12.         return max(l, r) + 1;. from: 1point3acres.com/bbs
  13. }

  14. int long_path(TreeNode* root) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15.         max_len = 0;. more info on 1point3acres.com
  16.         height(root);
  17.         return max_len;
  18. }

  19. };
复制代码
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-11-3 09:20:34 | 显示全部楼层
请教楼主一下,第一题里的n是代表a的位数吗,谢谢!
回复 支持 反对

使用道具 举报

 楼主| craiglin1992 发表于 2015-11-3 12:11:13 | 显示全部楼层
sonicgu 发表于 2015-11-3 09:20
请教楼主一下,第一题里的n是代表a的位数吗,谢谢!

第一题里边儿n是a/b
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-3 12:34:17 | 显示全部楼层
第一题
  1. class Solution {
  2. public:
  3.     int divide(int dividend, int divisor) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.         if(divisor == 0) {
  5.             return INT_MAX;
  6.         }
  7.         if(divisor == 1) return dividend;
  8.         if(divisor == -1){
  9.             if(dividend == INT_MIN) {
  10.                 return INT_MAX;-google 1point3acres
  11.             } else {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  12.                 return -dividend;
  13.             }
  14.         }
  15.         
  16.         unsigned int div = dividend;. 1point 3acres 璁哄潧
  17.         unsigned int dis = divisor;. 鍥磋鎴戜滑@1point 3 acres
  18.         . 1point 3acres 璁哄潧
  19.         if(dividend < 0) div = -div;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  20.         if(divisor < 0) dis = -dis;
  21.         
  22.         unsigned int ordis = dis;
  23.         int left = 0;
  24.         while(dis < div) {
  25.             dis <<= 1;
  26.             left++;
  27.         }
  28.         
  29.         int res = 0;
  30.         while(div >= ordis) {
  31.             if(div >= dis) {
  32.                 div -= dis;
  33.                 res += 1 << left;
  34.             }
  35.             dis >>= 1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  36.             left--;
  37.         }
  38.         
  39.         if(dividend < 0 && divisor > 0) return -res;
  40.         if(dividend > 0 && divisor < 0) return -res;
  41.         return res;
  42.     }
  43. };
复制代码
回复 支持 反对

使用道具 举报

pacman 发表于 2015-11-3 14:56:04 | 显示全部楼层
haifengc 发表于 2015-11-2 20:34
. from: 1point3acres.com/bbs 第一题

既然不能用除法,右移应该也不能用吧
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-11-4 09:11:12 | 显示全部楼层
craiglin1992 发表于 2015-11-3 12:11
第一题里边儿n是a/b

了解,谢谢
回复 支持 反对

使用道具 举报

plich 发表于 2015-11-4 09:21:44 | 显示全部楼层
pacman 发表于 2015-11-3 14:56
既然不能用除法,右移应该也不能用吧

个人理解,考的就是位运算
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-11-5 13:31:06 | 显示全部楼层
  1.     int divide(int dividend, int divisor) {
  2.         if(dividend == 0) return 0;
  3.         if(divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  4.         
  5.         int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
  6.         long x = labs(dividend), y = labs(divisor);
  7.         int result = 0;
  8.         while(x >= y) {
  9.             int i = 0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10.             while(x >= y << i) i++;. 鍥磋鎴戜滑@1point 3 acres
  11.             i--;
  12.             result += 1 << i;
  13.             x -= y << i;
  14.         }
  15.         . more info on 1point3acres.com
  16.         return result * sign;
  17.     }
复制代码
  1. int helper(Node *root, int &result) {
  2.     if(!root) return 0;
  3.     int l = helper(root->left, result);
  4.     int r = helper(root->right, result);
  5.     result = max(result, l + r + 1);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.     return max(l + 1, r + 1);
  7. }

  8. int longestPath(Node *root) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.     int result = 0;
  10.     helper(root, result);
  11.     return result;
  12. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 06:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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