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

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

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

谢谢LZ分享~请教，第二面的第一题里面Trie的空间复杂度是什么？我在网上搜索的结果是，Trie的空间复杂度最坏情况下并不会减少空间开销

zzgzzm 发表于 2016-10-31 13:02
是的，每个bit 是一个bit, 只能是0或1，相当于bool[]。但在具体实现的时候还是用int[]，只是每个int元素 ...

那是不是说bit[] 可以替代boolean[] 了呢

syjohnson 发表于 2016-11-1 00:08
那是不是说bit[] 可以替代boolean[] 了呢

实际不行的。在later Visual C++中，在内存bool是1byte (不是1 bit)，所以bool[] 比真正意义上的bitmap要占用8倍的空间。

zzgzzm 发表于 2016-11-1 04:44
实际不行的。在later Visual C++中，在内存bool是1byte (不是1 bit)，所以bool[] 比真正意义上的bitmap要 ...

那不是正说明bitmap比boolean要耗空间了嘛

第二题的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.

zzgzzm 发表于 2016-10-31 13:02
是的，每个bit 是一个bit, 只能是0或1，相当于bool[]。但在具体实现的时候还是用int[]，只是每个int元素 ...

bitmap 的具体实现如果是int[] 的话，不还是要2^32 size 的int[] 吗？那这样空间消耗还是大的呀

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

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

faithoverfear 发表于 2016-11-8 22:35
第二题的DFS代码。

call helper函数前应该加个判断
if(tmp != 0 || digits[i] != 0)

faithoverfear 发表于 2016-11-8 22:35
第二题的DFS代码。

如果digits[0]是0 ，runtime ？