数据砖头电面

经典的面试题 string的操作

• insert(char s, int index)
• remove(int index)
• get(int index)
  

这个问题我看其实好多人都已经在这里报过了，但是没有什么人给出一个特别好的solution，这边我给一下我的想法

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

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

所以建议就是如果大家想要面试几个公司然后db是其中一个的话，其实可以考虑这个稍微晚一点点reach out，因为他家进行得很快。

看在这么detail的份上，求大米，感恩！！

斗胆发一个自己写过的
两周前店面pass

1. class BlockList {
   
2.     struct Block {
   
3.       vector<char> data;  
   
4.      };
   
5. 
   
6.     typedef list<Block>::iterator blockIter;
   
7.     typedef vector<int>::iterator dataIter;
   
8.     list<Block> blockList;
   
9.     int totalSize = 0;
   
10.     int blockSize = 0;
    
11.     public :
    
12.     void insert(char c, int pos){
    
13.         totalSize ++;
    
14.         blockSize = sqrt(totalSize);
    
15.         if (blockList.empty()) {
    
16.             auto iter = blockList.insert(blockList.begin(), Block());
    
17.             iter->data.emplace_back(c);
    
18.          } else {
    
19.             auto iter = find(pos);
    
20.             if (iter == blockList.end()) {
    
21.                 blockList.back().data.emplace_back(c);
    
22.             } else {
    
23.                 iter->data.insert(iter->data.begin()+pos, c);
    
24.             }
    
25.         }
    
26.         maintain();
    
27.     }
    
28.    
    
29.     void maintain(){
    
30.         // split bigger
    
31.         // merge smaller
    
32.         for(auto iter = blockList.begin(); iter != blockList.end(); iter ++) {
    
33.             if (iter->data.size() > 2 * blockSize) {
    
34.                 Block b;
    
35.                 b.data.assign(iter->data.begin(), iter->data.begin() + blockSize);
    
36.                 blockList.insert(iter, b);
    
37.                 iter->data.erase(iter->data.begin(), iter->data.begin() + blockSize );
    
38.             }
    
39.         }
    
40.         for(auto iter = blockList.begin(); iter != blockList.end(); iter ++) {
    
41.             auto nextIter = next(iter);
    
42.             if (nextIter != blockList.end() && iter->data.size() + nextIter->data.size() <blockSize) {
    
43.                 iter->data.insert(iter->data.end(), nextIter->data.begin(), nextIter->data.end());
    
44.                 iter = blockList.erase(nextIter);
    
45.             }
    
46.         }
    
47.     }
    
48.    
    
49.     blockIter find(int& pos) {
    
50.         int sum = 0;
    
51.         for(auto iter = blockList.begin(); iter != blockList.end(); iter ++) {
    
52.             sum += iter->data.size();
    
53.             if (sum>pos) {
    
54.                 pos -= sum - iter->data.size();
    
55.                 return iter;
    
56.             }
    
57.         }
    
58.         return blockList.end();
    
59.     }
    
60.    
    
61.     void erase(int pos){
    
62.         auto iter = find(pos);
    
63.         if (iter != blockList.end()) {
    
64.              totalSize --;
    
65.              blockSize = sqrt(totalSize);
    
66.             iter->data.erase(iter->data.begin() + pos);
    
67.         }
    
68.         maintain();t
    
69.     }
    
70.     char get(int pos) {
    
71.         auto iter = find(pos);
    
72.         if (iter == blockList.end()) return '.';
    
73.         else return iter->data[pos];
    
74.     }
    
75.    
    
76.     void print() {
    
77.         for(Block b : blockList) {
    
78.             cout << "| " ;
    
79.             for (char c : b.data) {
    
80.                 cout << c << " ";
    
81.             }
    
82.         }
    
83.      cout <<endl;
    
84.     }
    
85.    
    
86. 
    
87.    
    
88. 
    
89. };
    
90. 
    
91. 
    
92. 
    
93. int main() {
    
94.     BlockList bl;
    
95.     bl.insert('a', 10);
    
96.     bl.insert('b', 10);
    
97. 
    
98.     bl.insert('c', 10);
    
99. 
    
100.     bl.insert('d', 10);
     
101. 
     
102.     bl.insert('e', 1);
     
103.         bl.insert('e', 1);
     
104. 
     
105.         bl.insert('e', 1);
     
106. 
     
107.         bl.insert('e', 1);
     
108. 
     
109.     bl.insert('e', 1);
     
110.     bl.print();
     
111.     cout << bl.get(7) << endl;
     
112.     bl.erase(7);
     
113.     bl.print();
     
114.     bl.erase(7);
     
115.     bl.erase(4);
     
116.     bl.erase(4);
     
117.     bl.print();
     
118.     bl.erase(3);
     
119. 
     
120.     bl.print();
     
121. }

复制代码

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

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

请问楼主怎么拿到Data Brick的面试的？

wjw779 发表于 2021-4-6 06:00
请问楼主怎么拿到Data Brick的面试的？

linkedin有recruiter找我

lz可以发一下你的解答吗，这个证明过程还是很难的

这个块是个linked list还是array ? 所有的块都通过一个array管理起来? 类似于hash table的bucket + 链式冲突解决 ? 感觉如果这些块的大小要经常被调整的话, 是不是用linked list作为存储, 开销会较低.

metacpp1982 发表于 2021-4-12 10:43
这个块是个linked list还是array ? 所有的块都通过一个array管理起来? 类似于hash table的bucket + 链式冲 ...

我用了array，但是你这么一说我突然觉得可能用linked list更好一点

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

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

匿名者 发表于 2021-4-12 11:35
我用了array，但是你这么一说我突然觉得可能用linked list更好一点

sqrt(n)的时间复杂度可以使均摊的复杂度吗?

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

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

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

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