狗狗加面面经【2016-10-13】

刚面完来发面经
--------------------
十月初一面
面得挺不好的，第一题只记得是个BFS/DFS给地图找路径的题，后来加了什么条件也没听懂，直接跳到第二题，当时还没出的LC399，在他的提示下只来得及说一下数据结构
两周后接到电话加面一轮
--------------------
刚刚二面

第一题不要求写code，要求说数据结构：
假设每天都给一个employee list，里面有id，

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

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

复数字了。。。orz
最后又问了复杂度，一开始答O(n^2)，后来觉得不对，改成了O(n!)。【每题必问复杂度。。。
最后问了几个问题基本准时结束。
求人品！


补充内容 (2016-10-18 06:04):
刚刚接到电话，通知onsite了，求人品！

第二题的DFS代码。

1. void helper(vector<int>& digits, int tmp, int maxNumber, vector<int> &res) {
   
2.     if (tmp > maxNumber) {
   
3.         return;
   
4.     }
   
5.     if (tmp != 0) {
   
6.         res.push_back(tmp);
   
7.     }
   
8.     for (int i = 0; i < digits.size(); i++) {
   
9.         helper(digits, tmp * 10 + digits[i], maxNumber, res);
   
10.     }
    
11. }
    
12. 
    
13. vector<int> getNumbers(vector<int>& digits, int maxNumber) {
    
14.     vector<int> res;
    
15.     sort(digits.begin(), digits.end());
    
16.     helper(digits,0, maxNumber, res);
    
17.     if (digits[0] == 0) {
    
18.         res.push_back(0);
    
19.     }
    
20.     return res;
    
21. }
    
22. 
    
23. 
    
24. int main() {
    
25.     vector<int> nums{3, 7, 8};
    
26.     vector<int> res = getNumbers(nums, 1000);
    
27.     for (auto a : res) {
    
28.         cout << a <<endl;
    
29.     }
    
30.     getchar();
    
31. }

复制代码

补充内容 (2016-11-8 22:38):
Assume no duplicates in digits array.

第二题：

1. public List<Integer> getNumbers(int[] digits, int maxNumber) {
   
2.                 List<Integer> result = new ArrayList<Integer>();
   
3.                 if(digits.length == 0) return result;
   
4.                
   
5.                 Arrays.sort(digits);
   
6.                 Queue<Integer> queue = new LinkedList<Integer>();
   
7.                 queue.add(0);
   
8.                
   
9.                 while(!queue.isEmpty()){
   
10.                         int size = queue.size();
    
11.                         for(int i = 0; i < size; i++){
    
12.                                 int previous = queue.poll();
    
13.                                 for(int j = 0; j < digits.length; j++){
    
14.                                         int current = previous * 10 + digits[j];
    
15.                                         if(current <= maxNumber && current != 0){
    
16.                                                 queue.add(current);
    
17.                                                 result.add(current);
    
18.                                         }
    
19.                                 }
    
20.                         }
    
21.                 }
    
22.                
    
23.                 if(digits[0] == 0) result.add(0, 0); // corner case when there is 0 in digits array
    
24.                 return result;
    
25.         }

复制代码

应该是类似于combination sum的backtracking

谢谢楼主分享
第一题很有意思啊。我是这么想的，前一天的用一个hashset来存，第二天加两个新的hashset，一个存新人，一个存和前一天重复的（从前一天的里面删掉），算完以后没删掉的是离职的，再把两个新的hashset合并用于下一天计算。
如果list很长的话可以分成多个hashset， 比方讲分10个，那就是hashvalue %10来决定存在第几个hashset里面

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

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

最后又问了复杂度，一开始答O(n^2)，后来觉得不对，改成了O(n!)。【每题必问复杂度

这个时间复杂度是怎么来的呢？我知道这个类似于combination sum，
但是假设平均k个数字组成1000，那么就是n^k啊

printf_ll 发表于 2016-10-14 06:02
对，这个方法我在很多关于scalability题目里都有看到，不过我当时没有想到它

我上的dbms课要求implement hash join，当时是这么做的，所以一下子就想到了~

wopani007 发表于 2016-10-14 06:34
最后又问了复杂度，一开始答O(n^2)，后来觉得不对，改成了O(n!)。【每题必问复杂度

这个时间复杂度是怎 ...

其实我也不太清楚，之前也没有考虑过这个，然后就说了一个n!，不一定是对的

巨巨加油！！祝你好运！！！！

黄豆沙君 发表于 2016-10-14 09:28
巨巨加油！！祝你好运！！！！

你怎么会认出我的！

第二题只能backtracking，不能用dp或者memorization?