业呼的fb店面面经

刚刚面完facebook面试，发上来攒人品，希望大家都有机会！
1. divide a/b without usi

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

05:52):
第一题是两个int，返回的也是int

第一题

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.             }
    
14.         }
    
15.         
    
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;
    
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. };

复制代码

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;
   
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++;
    
11.             i--;
    
12.             result += 1 << i;
    
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. 
   
9. int longestPath(Node *root) {
   
10.     int result = 0;
    
11.     helper(root, result);
    
12.     return result;
    
13. }

复制代码

第二题

1. class Solution {
   
2. 
   
3. public:
   
4. 
   
5. int max_len;
   
6. 
   
7. int height(TreeNode* root) {
   
8.         if(root == NULL) return 0;
   
9.        
   
10.         int l = height(root->left);
    
11.         int r = height(root->right);
    
12.        
    
13.         max_len = max(max_len, l + r + 1);
    
14. 
    
15.         return max(l, r) + 1;
    
16. }
    
17. 
    
18. int long_path(TreeNode* root) {
    
19.         max_len = 0;
    
20.         height(root);
    
21.         return max_len;
    
22. }
    
23. 
    
24. };

复制代码

第一题是两个int

一会儿也电面，好紧张( ▼-▼ )

第一题目测和快速幂差不多

请教楼主一下，第一题里的n是代表a的位数吗，谢谢！

sonicgu 发表于 2015-11-3 09:20
请教楼主一下，第一题里的n是代表a的位数吗，谢谢！

第一题里边儿n是a/b

haifengc 发表于 2015-11-2 20:34
第一题

既然不能用除法，右移应该也不能用吧

craiglin1992 发表于 2015-11-3 12:11
第一题里边儿n是a/b

了解，谢谢