数据砖头电面

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

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

metacpp1982 发表于 2021-4-14 04:49
有道理. 这里的K, 也就是block的大小, 是在什么时间点去更新呢? 比如15个元素的情况, k是等于3. 那么再插 ...

是的 我是每次都算一下

您好！
本帖隐藏的内容需要积分高于 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

可以用类似力扣 LRU Cache的数据结构吗？map+list数据结构，可以让每个操作在O(1)或者(logn)复杂度。这个方法对比楼主提出的方法，在申请空间的时候单位是1而不是block，所以会差一些，但是代码写起来比较有底一些。好奇楼主的block和b+ tree的实现怎么做到的，因为我想想觉得很复杂啊。

斗胆发一个自己写过的
两周前店面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. }

复制代码

ShowMeTheOffer 发表于 2021-4-17 00:52
可以用类似力扣 LRU Cache的数据结构吗？map+list数据结构，可以让每个操作在O(1)或者(logn)复杂度。这个方 ...

我也觉得有点复杂，现在想想我觉得我的方法可能也不是特别的好，但是过了，可能我解释的比较好吧。。。

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

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

楼主你这个解法挺有意思，但是不是b+ tree 啊

也面到了这道题，写了简化版b+树解决的，但是似乎不是面试官期望的答案，因为说我这个solution比较hard code而且沟通过程中感觉他有些地方没get到，后来思考了一下，面试官想要的应该是块状链表的那种，写起来的确会比b+树轻松很多，并且也满足要求