Snapchat video面经

本人EE MS，工作了小几年，网上海投，直接给的面试。S最近刚融到资，在扩张，小伙伴们可以去试试。七月份最后一个星期面的。摄像头Google hangout，面试官是个中年国男。

介绍一下自己的project，然后直接一道题：
以B

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

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

lo world都调了比较久。只能说自己一开始没好好把这个在线编译平台熟悉好吧。

然后不出意外就跪了。就这样。。。。

嗯 你说的在java里面叫treemap 因为并不用hash 所以感觉叫hashmap有点misleading

所以这道题是要实现一个BST，但是BST的node里存的是int类型的key-value pair？

1. public class MyHashtable {
   
2.        
   
3.         private Pair root;
   
4.         private int size;
   
5.        
   
6.         public MyHashtable() {
   
7.                 root = null;
   
8.                 size = 0;
   
9.         }
   
10.        
    
11.         public int get(int k) {
    
12.                 Pair node = search(root, k);
    
13.                 if (node == null) {
    
14.                         throw new NoSuchElementException();
    
15.                 }
    
16.                 return node.val;
    
17.         }
    
18.        
    
19.         private Pair search(Pair node, int k) {
    
20.                 if (node == null) {
    
21.                         return null;
    
22.                 }
    
23.                 if (node.key == k) {
    
24.                         return node;
    
25.                 }
    
26.                 if (node.key < k) {
    
27.                         return search(node.right, k);
    
28.                 }
    
29.                 return search(node.left, k);
    
30.         }
    
31.        
    
32.         public void put(int k, int v) {
    
33.                 if (root == null) {
    
34.                         root = new Pair(k, v);
    
35.                         return;
    
36.                 }
    
37.                 Pair node = search(root, k);
    
38.                 if (node != null) {
    
39.                         node.val = v;
    
40.                 } else {
    
41.                         node = new Pair(k, v);
    
42.                         insert(root, node);
    
43.                 }
    
44.         }
    
45.        
    
46.         private void insert(Pair node, Pair newNode) {
    
47.                 if (node.key < newNode.key) {
    
48.                         if (node.right == null) {
    
49.                                 node.right = newNode;
    
50.                         } else {
    
51.                                 insert(node.right, newNode);
    
52.                         }
    
53.                 } else {
    
54.                         if (node.left == null) {
    
55.                                 node.left = newNode;
    
56.                         } else {
    
57.                                 insert(node.left, newNode);
    
58.                         }
    
59.                 }
    
60.         }
    
61.        
    
62.         public boolean remove(int k) {
    
63.                 if (!containsKey(k)) {
    
64.                         return false;
    
65.                 }
    
66.                 root = remove(root, k);
    
67.                 return true;
    
68.         }
    
69.        
    
70.         private Pair remove(Pair node, int k) {
    
71.                 if (node == null) {
    
72.                         return null;
    
73.                 }
    
74.                 if (node.key < k) {
    
75.                         node.right = remove(node.right, k);
    
76.                 } else if (node.key > k) {
    
77.                         node.left = remove(node.left, k);
    
78.                 } else {
    
79.                         if (node.left == null) {
    
80.                                 return node.right;
    
81.                         }
    
82.                         if (node.right == null) {
    
83.                                 return node.right;
    
84.                         }
    
85.                         Pair temp = node;
    
86.                         node = min(temp.right);
    
87.                         node.right = deleteMin(temp.right);
    
88.                         node.left = temp.left;
    
89.                 }
    
90.                 return node;
    
91.         }
    
92.        
    
93.         private Pair min(Pair node) {
    
94.                 if (node.left == null) {
    
95.                         return node;
    
96.                 }
    
97.                 return min(node.left);
    
98.         }
    
99.        
    
100.         private Pair deleteMin(Pair node) {
     
101.                 if (node.left == null) {
     
102.                         return node.right;
     
103.                 }
     
104.                 node.left = deleteMin(node.left);
     
105.                 return node;
     
106.         }
     
107.        
     
108.         private boolean containsKey(int k) {
     
109.                 return containsKey(root, k);
     
110.         }
     
111.        
     
112.         private boolean containsKey(Pair node, int k) {
     
113.                 if (node == null) {
     
114.                         return false;
     
115.                 }
     
116.                 if (node.key == k) {
     
117.                         return true;
     
118.                 }
     
119.                 if (node.key < k) {
     
120.                         return containsKey(node.right, k);
     
121.                 } else {
     
122.                         return containsKey(node.left, k);
     
123.                 }
     
124.         }
     
125.        
     
126.         public int size() {
     
127.                 return size;
     
128.         }
     
129.        
     
130.         class Pair {
     
131.                 int key;
     
132.                 int val;
     
133.                 Pair left;
     
134.                 Pair right;
     
135.                 public Pair(int k, int v) {
     
136.                         key = k;
     
137.                         val = v;
     
138.                         left = null;
     
139.                         right = null;
     
140.                 }
     
141.         }
     
142.        
     
143.        
     
144.         public static void main(String[] args) {
     
145.                 MyHashtable table = new MyHashtable();
     
146.                 table.put(1, 6);
     
147.                 table.put(2, 7);
     
148.                 table.put(3, 8);
     
149.                
     
150.                 System.out.println(table.get(1));
     
151.                 System.out.println(table.get(2));
     
152.                 System.out.println(table.get(3));
     
153.                 table.put(4, 10);
     
154.                 System.out.println(table.get(4));
     
155.                 table.remove(4);
     
156. //                System.out.println(table.get(4));
     
157.                 System.out.println(table.get(1));
     
158.                 table.remove(1);
     
159. //                System.out.println(table.get(1));
     
160.         }
     
161. 
     
162. }
     

复制代码

何打发123 发表于 2016-8-23 09:47
请问楼主~ 这里需要自己设计hash function 考虑collision吗？~  还是其实这题可以理解为在BST中插入删除寻 ...

这里和hash function并没有关系 hash map 和tree map是不一样的

BST中插入删除寻找node  可以这么理解

bst实现hashmap？ do u mean treemap？

熊亮亮111 发表于 2016-8-20 22:21
bst实现hashmap？ do u mean treemap？

Java我其实不太了解，基本上没怎么用过。就是和C++ STL里的map一样，并没有一个hash function，而是根据key作为BST的排序依据把key value pair存在BST里。

请问楼主~ 这里需要自己设计hash function 考虑collision吗？~  还是其实这题可以理解为在BST中插入删除寻找node？~

熊亮亮111 发表于 2016-8-23 11:15
这里和hash function并没有关系 hash map 和tree map是不一样的

BST中插入删除寻找node  可以这么理 ...

看我的ID你不觉得认识我嘛

何打发123 发表于 2016-8-23 12:47
看我的ID你不觉得认识我嘛

哈哈 我知道你是谁

请问是要implement一个BST吗？red-black or AVL？

sniffsky 发表于 2016-8-30 09:54
请问是要implement一个BST吗？red-black or AVL？

普通的BST就可以了