11/23 狗家 onsite

应该跪得妥妥的了
一面中国姐姐：decode string, given "a3b2" return "aaabb", given "a234" return "aa3333", assume input valid

follow up1: given "a0b2c3" return "bbccc"
foilow up2: the input is the iterator-> implement your iterator with next() and has next()
follow up3: validate the input

二面中国哥哥：
面经题，然而我并没有做出来orz，given arraylist<Node>, return the number of component

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

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

时有两个线程对它进行+1操作，假设两个都是循环加一百次，问最后cnt的结果是什么？
follow up:如果是3个，5个...n个多线程，它们的结果又是啥

虽然有两题没有做出来，但狗家永远是我dream！
ps.每题必问time and space complexity!


补充内容 (2016-12-12 14:50):
被recruiter给了application engineer岗的面试【・_・?】心累orz...

1. #define MAXN 5000+5
   
2. short dp[MAXN][MAXN];
   
3. 
   
4. 
   
5. int intervalDP(string &s) {
   
6.         int n = s.length();
   
7.         for(int i=n-1;i >= 0; i--) {
   
8.                 for(int j=i+1;j<n;j++) {
   
9.                         if(s[i] == s[j]) {
   
10.                                 dp[i][j] = dp[i+1][j-1];
    
11.                         }else {
    
12.                                 dp[i][j] = min(dp[i+1][j],dp[i][j-1]) + 1;
    
13.                         }
    
14.                 }
    
15.         }
    
16.         return dp[0][n-1];
    
17. }
    
18. 
    
19. int lcs(string &s,string &t) {
    
20.         int n = s.length();
    
21.         for(int i=1;i<=n;i++) {
    
22.                 for(int j=1;j<=n;j++) {
    
23.                         if(s[i-1] == t[j-1]) {
    
24.                                 dp[i][j] = dp[i-1][j-1] + 1;
    
25.                         }else {
    
26.                                 dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
    
27.                         }
    
28.                 }
    
29.         }
    
30.         return dp[n][n];
    
31. }
    
32. 
    
33. int dfs(int l,int r,string &s) {
    
34.         if(l >= r) return 0;
    
35.         if(dp[l][r] != -1) return dp[l][r];
    
36.         if(s[l] == s[r]) {
    
37.                 dp[l][r] = dfs(l+1,r-1,s);
    
38.         }
    
39.         else {
    
40.                 dp[l][r] = min(dfs(l+1,r,s),dfs(l,r-1,s)) + 1;
    
41.         }
    
42.         return dp[l][r];
    
43. }
    
44. 
    
45. int main(){
    
46.         string s;
    
47.         while(cin>>s) {
    
48.                 int n = s.length();
    
49.                 // solution 1 区间dp
    
50.                 memset(dp,0,sizeof(dp));
    
51.                 cout<< intervalDP(s) <<endl;
    
52.                
    
53. 
    
54.                 // solution 2 lcs
    
55.                 memset(dp,0,sizeof(dp));
    
56.                 string t = s;
    
57.                 reverse(s.begin(),s.end());
    
58.                 int len = lcs(s,t);
    
59.                 cout<<n-len<<endl;
    
60.                
    
61. 
    
62.                 // solution 3 memory search
    
63.                 memset(dp,-1,sizeof(dp));
    
64.                 cout<<dfs(0,n-1,s)<<endl;
    
65. 
    
66.         }
    
67.         return 0;
    
68. }

复制代码

第四题三种方法：
1. 区间dp
2. 与翻转串求lcs, 答案：n-lcs
3. 记忆化搜索（比较好理解）

第四题，可以把string拆成left和right两半，然后题目就转化为了shortestEditDistance(left,right)

renwoxing 发表于 2016-12-18 07:37
多谢回答。
原题在这个https://www.careercup.com/question?id=18880663，里面有个很好的答案。
光看这 ...

我感觉其实就按照那个题的思路，single list的话要判断之前的点（pre），就再见一个hashset存这个点有没有之前的点加了进来就好了，用C++写了一下

int numComponents(vector<Node*> nodes) {
        unordered_set<Node*> exist;
        unordered_set<Node*> preExist;
        int count = 0;
        for (auto node : nodes) {
                if (exist.find(node) == exist.end()) {
                        count++;
                        if (node->next && exist.find(node->next) != exist.end()) {
                                count--;
                        }
                        if (preExist.find(node) != preExist.end()) {
                                count--;
                        }
                        exist.insert(node);
                        if (node->next) {
                                preExist.insert(node->next);
                        }
                }
        }
        return count;
}

第四轮是把原字符串reverse之后跟原字符串找common longest sequence 吗？

补充内容 (2016-11-25 13:40):

第三轮是不是只能dfs呀...没其他想法

补充内容 (2016-11-25 13:44):

想了一下 应该是跟edit distance比较像才对 用二维dp

楼主的面筋在最近狗家面筋里面相对算温和一点的了，没把握好机会很可惜

楼主请问二面的是double linked list还是single list呀？

catinclay 发表于 2016-11-25 13:38
第四轮是把原字符串reverse之后跟原字符串找common longest sequence 吗？

补充内容 (2016-11-25 13:40) ...

二维dp不够，需要三维，[当前结点，当前skip数，当前路径的最后一个结点]

SiyaoZhu 发表于 2016-11-25 13:58
楼主请问二面的是double linked list还是single list呀？

single list

第三轮这题只要找到最长的两条distance 就行了吧

duziyuanyang 发表于 2016-11-26 01:54
第三轮这题只要找到最长的两条distance 就行了吧

不是很懂你的意思，为什么是最长的两条？

第三题
skip[i, j] is the min distance end at i(i is skipped) with j skips
noSkip[i, j] is the min distance end at i(i isn't skipped) with j skips
sLast[i, j] is the last index for skip[i, j]

skip[i, j] = Math.Min(skip[i - 1, j], noSkip[i - 1, j]);
noSkip[i, j] = Math.Min(skip[i - 1, j - 1] + dst[sLast[i - 1, j - 1], i], noSkip[i - 1, j - 1] + dst[i - 1, i]);
sLast[i, j] = skip[i - 1, j] < noSkip[i - 1, j] ? sLast[i - 1, j] : i - 1;

printf_ll 发表于 2016-11-26 01:24
二维dp不够，需要三维，[当前结点，当前skip数，当前路径的最后一个结点]

哈哈 我說的二維dp是palindrome那題
另一題確實是要三維dp