May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1756|回复: 11
收起左侧

业呼的fb店面面经

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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


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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

haifengc 发表于 2015-11-3 08:42:22 | 显示全部楼层
第二题
  1. class Solution {.鏈枃鍘熷垱鑷1point3acres璁哄潧

  2. public:
  3. . 鍥磋鎴戜滑@1point 3 acres
  4. int max_len;
  5. . 1point 3acres 璁哄潧
  6. int height(TreeNode* root) {
  7.         if(root == NULL) return 0;
  8.        
  9.         int l = height(root->left);. from: 1point3acres.com/bbs
  10.         int r = height(root->right);
  11.         鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.         max_len = max(max_len, l + r + 1);

  13.         return max(l, r) + 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  14. }. 1point 3acres 璁哄潧

  15. int long_path(TreeNode* root) {
  16.         max_len = 0;
  17.         height(root);
  18.         return max_len;
  19. }

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

使用道具 举报

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;
  11.             } else {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12.                 return -dividend;
  13.             }.1point3acres缃
  14.         }
  15.         . 1point 3acres 璁哄潧
  16.         unsigned int div = dividend;
  17.         unsigned int dis = divisor;
  18.         
  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;
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  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 | 显示全部楼层

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

使用道具 举报

sonicgu 发表于 2015-11-4 09:11:12 | 显示全部楼层
craiglin1992 发表于 2015-11-3 12:11.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一题里边儿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) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  2.         if(dividend == 0) return 0;
  3.         if(divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;
  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) {.1point3acres缃
  9.             int i = 0;
  10.             while(x >= y << i) i++;
  11.             i--;
  12.             result += 1 << i;. 鍥磋鎴戜滑@1point 3 acres
  13.             x -= y << i;
  14.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.         
  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. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-25 02:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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