FB onsite 挂经 非典型coding

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

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

5. design 记不清了， 好像是 news feed?

n2是n1少一位digit，输入s=n1 + n2, 求(n1, n2)的可能解

123456
   ^
   e
^^^ ^^
h   t

e为去掉的digit
h为前缀
t为后缀

s = 2 * t + (11 * h + e) * 10^r
= 2 * t + e * 10^r + h * 11 * 10^r

注意2 * t < 10^r, 0 <= e <= 9

尝试不同的r
h = s / (11 * 10^r)
e * 10^r + 2 * t = s % (11 * 10 ^ r)
e = (s % (11 * 10 ^ r)) / 10 ^ r
t = ((s % (11 * 10 ^ r)) % 10 ^ r) / 2

复杂度log(s)

1. def findn1n2(s):
   
2.     if s < 10: return [(s, 0)]
   
3.     rec = set()
   
4.     r = 0
   
5.     while s / (11 * 10 ** r):
   
6.         h = s / (11 * 10 ** r)
   
7.         m = s % (11 * 10 ** r)
   
8.         e = m / (10 ** r)
   
9.         t = (m % (10 ** r)) / 2
   
10.         n1 = h * 10 ** (r + 1) + e * 10 ** r + t
    
11.         n2 = h * 10 ** r + t
    
12.         rec.add((n1, n2))
    
13.         r += 1
    
14.     return list(rec)
    
15. 
    
16. print findn1n2(2) #[(2, 0)]
    
17. print findn1n2(39) #[(36, 3)]
    
18. print findn1n2(1246) #[(1133, 113), (1123, 123)]

复制代码

buaaroger 发表于 2017-5-20 07:26
给的提示是start with a simpler case where n2 is n1 without last digit

给的提示非常有意义，比如 sum = A + A'
A'是A去掉任意一位。那么可以看成是两部分相加：
sum = (A1 + A1')*(10^r) + 2*A2
其中，A1是A的左半部分，A2是A的右半部分。比如A1'则是A1去掉了最后一位。r则是截成左右两段的位数。
而如果A1'是A1去掉最后一位，则非常容易反推

例如：
1246 = 1223+123
1246 = (122+12)*10 + 3*2

依照这个方法实现了一下。初步测试有效。

1. 
   
2.         public static void extract(int sum){
   
3.                 int splitter = 1;
   
4.                 while(sum>splitter){
   
5.                         int right = sum/splitter;
   
6.                         int left = sum%splitter;
   
7.                         if(left%2==1) break;
   
8.                        
   
9.                         int extractedLeft = left/2;
   
10.                         Integer extractedRight = extractIfLast(right);
    
11.                         if(extractedRight!=null){
    
12.                                 System.out.print(extractedRight*splitter+extractedLeft + ", ");
    
13.                                 System.out.println((right-extractedRight)*splitter+extractedLeft);
    
14.                         }
    
15.                         if(splitter>1){
    
16.                                 extractedRight = extractIfLast(right-1);
    
17.                                 if(extractedRight!=null){
    
18.                                         System.out.print(extractedRight*splitter+extractedLeft+splitter/2+ ",     ");
    
19.                                         System.out.println((right-1-extractedRight)*splitter+extractedLeft+splitter/2);
    
20.                                 }
    
21.                         }
    
22.                         splitter *= 10;
    
23.                 }
    
24.                
    
25.         }
    
26.        
    
27.         //如果是去掉了最后一位
    
28.         public static Integer extractIfLast(int sum){
    
29.                 int small = sum/11;
    
30.                 int large = sum-small;
    
31.                 if(large/10==small) return large;
    
32.                 else return null;
    
33.         }

复制代码

补充内容 (2017-5-20 13:30):
代码会打印重复组合， 反正大概是这么个意思，大家将就看一下

两题design啊。看上去题目都还好，有什么feedback吗

这个如何破？
2.2. 给两个数 n1, n2. n2 is n1 without 1 digit, e.g. n1 = 123, then n2 can be 12, 13 or 23. 现在知道n1+n2的和是多少， 求n1 和 n2 的可能值

dlf1601 发表于 2017-5-20 06:27
这个如何破？
2.2. 给两个数 n1, n2. n2 is n1 without 1 digit, e.g. n1 = 123, then n2 can be 12, 13 o ...

暴力破解。。。对于 0 -  (n1 + n2)   排除一些显然不可能的， 每个数字都做计算。。。复杂度比价高。不知道楼主怎么回答的。

给的提示是start with a simpler case where n2 is n1 without last digit

dlf1601 发表于 2017-5-20 06:27
这个如何破？
2.2. 给两个数 n1, n2. n2 is n1 without 1 digit, e.g. n1 = 123, then n2 can be 12, 13 o ...

这个不是很直接吗，模拟所有的n1位就好了

补充内容 (2017-5-20 07:35):
呃一开始看错了没有想好，不过n2比n1少一位，所以sum的第一位肯定就是n1的最高位或者n1的最高位+1，然后接着慢慢推？

ecneralc 发表于 2017-5-20 07:33
这个不是很直接吗，模拟所有的n1位就好了

补充内容 (2017-5-20 07:35):

99 + 9 = 108

if it is last digit missing, it should be easy.

Just mod by 11; that is the missing digit.

buaaroger 发表于 2017-5-20 07:26
给的提示是start with a simpler case where n2 is n1 without last digit

再请教一下，第一题copy on write class是考thread safe吗？
是不是这样就行了？。。

class StringClass {

    public String str;
    public StringClass(String s) {
        str = s;
    }

    public synchronized StringClass write(String s) {
        return new StringClass(s);
    }

}

补充内容 (2017-5-20 13:33):
class Solution {

    public static void main(String[] args) {
        StringClass a = new StringClass("abc");
        StringClass b = a;
        a = a.write("bac");

        System.out.println(a.s...