脸昂赛

BabyShung 发表于 2017-3-18 22:27
lz好厉害 肯定大offer。想求一下第四轮系统设计的思路。。

谢谢，我的思路就是 typical 的 client-server system，然后把想到的说出来就好了，我觉得最好是你去 lead 整个 interview，有条理的把所有你知道的说出来，面试官如果有想知道的细节会问你的

求问楼主第三题, 怎么通过一个迭代器实现peek()方法啊. 一旦调用了next()挪动了位置就回不去了啊.. 我的想法就和原题差不多, 先找到第一个不相同的位置, 然后根据修改,插入,删除这三种情况看剩下的是不是一样. 对于每个情况, 需要建一个迭代器的copy.

lhh_NJU 发表于 2017-3-20 11:58
求问楼主第三题, 怎么通过一个迭代器实现peek()方法啊. 一旦调用了next()挪动了位置就回不去了啊.. 我的想 ...

第三题，用迭代器

1.         //稍作解释，我们对每个string 迭代器，存当前的char和之前的char
   
2.         //ca就是current a 的char, pa就是previous a 的char
   
3.         //one edit就三种情况，ca==cb || cb==pa || ca==pb
   
4.         static boolean oneEditDistanceIterator(StrIt a, StrIt b){
   
5.                 Character ca=a.next(), cb=b.next(), pa, pb;
   
6.                 while(ca==cb && ca!=null){
   
7.                         ca = a.next();
   
8.                         cb = b.next();
   
9.                 }
   
10.                 //如果完全相同不算true,就有这一句
    
11.                 if(ca==null && cb==null) return false;
    
12.                 //从这里开始验证三种不同的情况，如果都失败了，就返回false
    
13.                 boolean dela=true, delb=true, update=true;
    
14.                 while(ca!=null || cb!=null){
    
15.                         pa = ca;
    
16.                         pb = cb;
    
17.                         ca = a.next();
    
18.                         cb = b.next();
    
19.                         dela = dela && ca==pb;
    
20.                         delb = delb && cb==ca;
    
21.                         update = update && cb==ca;
    
22.                         if(!dela && !delb && !update) return false;
    
23.                 }
    
24.                 return true;
    
25.         }
    
26.        
    
27. 
    
28.         protected static class StrIt{
    
29.                 String s;
    
30.                 int p=0;
    
31.                 public StrIt(String ss){
    
32.                         s = ss;
    
33.                 }
    
34.                 public Character next(){
    
35.                         return p<s.length() ? s.charAt(p++) : null;
    
36.                 }
    
37.         }

复制代码

补充内容 (2017-4-12 01:59):
稍作解释，我们对每个string 迭代器，存当前的char和之前的char
ca就是current a 的char, pa就是previous a 的char
one edit就三种情况，ca==cb || cb==pa || ca==pb
在迭代的过程中只要handle住这三种情况就OK

翻滚吧豆子 发表于 2017-4-12 01:54
第三题，用迭代器

补充内容 (2017-4-12 01:59):

line20
多谢分享 line20 是不是因该是
delb = delb && cb==pa ?

say543 发表于 2017-4-14 09:54
line20
多谢分享 line20 是不是因该是
delb = delb && cb==pa ?

对对对对  打错啦

请问楼主最后一轮says design的面试官也是一个brown色的小哥吗？他会role play 装自己是白痴手下问你问题 挺有意思的。

请问是在menlo park还是seattle面的？

LZ 第三题的加二进制字符串, followup问怎么改能支持各种 base 这个follow up如何回答呀

LZ，您的两个设计都是好像client为主的，对于server端的要求很少呀

Q3: 看起来像是old C-style string char* :

1. bool oneEditDistance(char* a, char* b) {
   
2.     if (!a || !b) return false;
   
3.     bool foundDiff = false;
   
4.     int flag = 7; // bit0: delete a; bit1: delete b; bit2: replace
   
5.     for (char* pa, *pb; *a||*b; pa=a, a+=(*a!='\0'), pb=b, b+=(*b!='\0')) {
   
6.         if (foundDiff) {
   
7.             if (flag &= ((*a == *pb)+((*b == *pa) << 1) +((*a == *b)  << 2)) == 0) return false;
   
8.         }
   
9.         else foundDiff = (*a != *b);
   
10.     }
    
11.     return foundDiff;
    
12. }

复制代码