Databricks电面SnapshotSet和HM面

我用C++写的，题目如下，要求实现SnapshotSet Interface，能够用iterator()取某一时刻这个set的所有元素，在调用iterator()和使用Iterator<T>之间，可以对SnapshotSet进行修改，不考虑多线程，所有操作都是顺序执行:

// java
// interface SnapshotSet

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

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

2
// --------- contains(2) = false
// --------- [x for x in it] = [2, 8] (No ordering guarantees)，把2和8读出来。

这个heyho是来偷面经的烙印，楼主别理。这b每个数据砖面经都有他，已经几个月了还没面。。

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

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

技术面是上面那道题；隔了一天HM面，又被烙印manager黑了。三哥真是老中的克星。

请问楼主第一题是怎么做的呢？set里每个val都单独记录timestamp和operation，然后做binary search，还是直接每次创建iterator的时候把整个set copy？

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

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

1. import java.util.*;
   
2. import java.lang.*;
   
3. 
   
4. class MyIterator implements Iterator<Integer> {
   
5.     Map<Integer, Integer> snapshot;
   
6.     Map<Integer, Integer> curset;
   
7.     Iterator<Integer> it;
   
8.     MyIterator(Map<Integer, Integer> s, Map<Integer, Integer> c) {
   
9.         this.snapshot = s;
   
10.         this.curset = c;
    
11.         it = s.keySet().iterator();
    
12.     }
    
13.     @Override
    
14.     public boolean hasNext() {
    
15.         boolean res = it.hasNext();
    
16.         if(res == false) snapshot.clear();
    
17.         return res;
    
18.     }
    
19.     @Override
    
20.     public Integer next() {
    
21.         Integer res = it.next();
    
22.         if(snapshot.get(res) == 0) curset.put(res, 0);
    
23.         return res;
    
24.     }
    
25. }
    
26. 
    
27. public class SnapshotSet {
    
28.     Map<Integer, Integer> snapshot = new HashMap<Integer, Integer>();
    
29.     Map<Integer, Integer> curset = new HashMap<Integer, Integer>();
    
30.     void add(Integer e) {
    
31.         if(snapshot.containsKey(e)) snapshot.put(e, 0); // not deleted
    
32.         else curset.put(e, 0);
    
33.     }
    
34.     void remove(Integer e) {
    
35.         if(snapshot.containsKey(e)) snapshot.put(e, 1); // deleted
    
36.         else curset.remove(e);
    
37.     }
    
38.     boolean contains(Integer e) {
    
39.         return snapshot.containsKey(e) && snapshot.get(e) == 0 || curset.containsKey(e);
    
40.     }
    
41.     Iterator<Integer> iterator() {
    
42.         snapshot = curset;
    
43.         curset = new HashMap<Integer, Integer>();
    
44.         return new MyIterator(snapshot, curset);
    
45.     }
    
46.    
    
47.     public static void main(String[] args) {
    
48.         SnapshotSet ss = new SnapshotSet();
    
49.         ss.add(8);
    
50.         ss.add(2);
    
51.         ss.add(5);
    
52.         ss.remove(5);
    
53.         Iterator<Integer> it = ss.iterator();
    
54.         System.out.println(ss.contains(2));
    
55.         ss.add(1);
    
56.         ss.remove(2);
    
57.         System.out.println(ss.contains(2));
    
58.         while(it.hasNext()) {
    
59.             System.out.print(it.next() + ",");
    
60.         }
    
61.         System.out.println();
    
62.         
    
63.         ss.add(5);
    
64.         it = ss.iterator();
    
65.         while(it.hasNext()) {
    
66.             System.out.print(it.next() + ",");
    
67.         }
    
68.         System.out.println(ss.contains(2));
    
69.         
    
70.     }
    
71. }

复制代码

Can you explain why we need line 22? ( if(snapshot.get(res) == 0) curset.put(res, 0);)

匿名者 发表于 2022-3-25 21:54
技术面是上面那道题；隔了一天HM面，又被烙印manager黑了。三哥真是老中的克星。

HM挂我感觉其实不算黑吧，毕竟manger有一票否决这个人要不要我组里面，如果真招你进去了背锅那更惨

This code fails the test below. It needs to print 1,5,8 but prints 1,5.

1.         SnapshotSet ss = new SnapshotSet();
   
2.         ss.add(8);
   
3.         ss.add(2);
   
4.         ss.add(5);
   
5.         ss.remove(5);
   
6.         Iterator<Integer> it = ss.iterator();
   
7.         ss.add(1);
   
8.         ss.remove(2);
   
9. 
   
10.         ss.add(5);
    
11.         Iterator<Integer> it2 = ss.iterator();
    
12.         while(it2.hasNext()) {
    
13.             System.out.print(it2.next() + ",");
    
14.         }

复制代码

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