一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2014|回复: 12
收起左侧

Snapchat video面经

[复制链接] |试试Instant~ |关注本帖
ladyM1896 发表于 2016-8-20 07:32:50 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Snapchat - 网上海投 - 技术电面 |Fail在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本人EE MS,工作了小几年,网上海投,直接给的面试。S最近刚融到资,在扩张,小伙伴们可以去试试。七月份最后一个星期面的。摄像头Google hangout,面试官是个中年国男。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
介绍一下自己的project,然后直接一道题:.鐣欏璁哄潧-涓浜-涓夊垎鍦
以BST实现Hash table,只需要支持int型hash到int型。.鐣欏璁哄潧-涓浜-涓夊垎鍦
几个接口函数:
int getValue(int)
void insert(int)
bool erase(int)

题目本身倒也不难,代码量稍微大一点,本来是可以拿下的。只是代码是在hackerrank上写。其实我亚马逊面过,对hackerrank还是比较熟悉的,但是这里提供的hackerrank我一上来相当懵逼,代码写完了但最后实在是编译不过。后来面试结束以后自己也尝试着运行最基本的hello world都调了比较久。只能说自己一开始没好好把这个在线编译平台熟悉好吧。

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

评分

1

查看全部评分

熊亮亮111 发表于 2016-8-22 05:16:53 | 显示全部楼层
嗯 你说的在java里面叫treemap 因为并不用hash 所以感觉叫hashmap有点misleading
回复 支持 1 反对 0

使用道具 举报

熊亮亮111 发表于 2016-8-20 22:21:05 | 显示全部楼层
bst实现hashmap? do u mean treemap?
回复 支持 反对

使用道具 举报

 楼主| ladyM1896 发表于 2016-8-21 03:20:46 | 显示全部楼层
熊亮亮111 发表于 2016-8-20 22:21. 1point 3acres 璁哄潧
bst实现hashmap? do u mean treemap?

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

使用道具 举报

何打发123 发表于 2016-8-23 09:47:53 | 显示全部楼层
请问楼主~ 这里需要自己设计hash function 考虑collision吗?~  还是其实这题可以理解为在BST中插入删除寻找node?~
回复 支持 反对

使用道具 举报

熊亮亮111 发表于 2016-8-23 11:15:49 | 显示全部楼层
何打发123 发表于 2016-8-23 09:47
请问楼主~ 这里需要自己设计hash function 考虑collision吗?~  还是其实这题可以理解为在BST中插入删除寻 ...

这里和hash function并没有关系 hash map 和tree map是不一样的
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
BST中插入删除寻找node  可以这么理解
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-23 12:47:48 | 显示全部楼层
熊亮亮111 发表于 2016-8-23 11:15
这里和hash function并没有关系 hash map 和tree map是不一样的

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

看我的ID你不觉得认识我嘛
回复 支持 反对

使用道具 举报

熊亮亮111 发表于 2016-8-23 12:55:45 | 显示全部楼层
何打发123 发表于 2016-8-23 12:47. 1point3acres.com/bbs
看我的ID你不觉得认识我嘛

哈哈 我知道你是谁
回复 支持 反对

使用道具 举报

sniffsky 发表于 2016-8-30 09:54:44 | 显示全部楼层
请问是要implement一个BST吗?red-black or AVL?
回复 支持 反对

使用道具 举报

 楼主| ladyM1896 发表于 2016-8-30 11:57:15 | 显示全部楼层
sniffsky 发表于 2016-8-30 09:54
请问是要implement一个BST吗?red-black or AVL?

普通的BST就可以了
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-5 09:37:50 | 显示全部楼层
不需要考虑balanced tree么? 以及这道题目跟实现一个int类型BST的区别是什么。。
回复 支持 反对

使用道具 举报

importcoder 发表于 2016-9-10 18:15:28 | 显示全部楼层
所以这道题是要实现一个BST,但是BST的node里存的是int类型的key-value pair?
  1. public class MyHashtable {. 鍥磋鎴戜滑@1point 3 acres
  2.        
  3.         private Pair root;-google 1point3acres
  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.         }. more info on 1point3acres.com
  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) {. more info on 1point3acres.com
  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.                 }. visit 1point3acres.com for more.
  44.         }
  45.        
  46.         private void insert(Pair node, Pair newNode) {. From 1point 3acres bbs
  47.                 if (node.key < newNode.key) {
  48.                         if (node.right == null) {
  49.                                 node.right = newNode;
  50.                         } else {
  51.                                 insert(node.right, newNode);
    . more info on 1point3acres.com
  52.                         }
  53.                 } else {
  54.                         if (node.left == null) {
  55.                                 node.left = newNode;
  56.                         } else {
    . From 1point 3acres bbs
  57.                                 insert(node.left, newNode);
  58.                         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  59.                 }
  60.         }
  61.         .1point3acres缃
  62.         public boolean remove(int k) {
  63.                 if (!containsKey(k)) {
  64.                         return false;
  65.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.                 }
    . 1point3acres.com/bbs
  90.                 return node;
  91.         }
  92.         . from: 1point3acres.com/bbs
  93.         private Pair min(Pair node) {
  94.                 if (node.left == null) {. more info on 1point3acres.com
  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);-google 1point3acres
  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.                 }. 鍥磋鎴戜滑@1point 3 acres
  119.                 if (node.key < k) {
  120.                         return containsKey(node.right, k);
  121.                 } else {
  122.                         return containsKey(node.left, k);
  123.                 }. 鍥磋鎴戜滑@1point 3 acres
  124.         }
  125.         鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  126.         public int size() {. From 1point 3acres bbs
  127.                 return size;
  128.         }
  129.        
  130.         class Pair {
  131.                 int key;
  132.                 int val;. 1point 3acres 璁哄潧
  133.                 Pair left;. from: 1point3acres.com/bbs
  134.                 Pair right;
  135.                 public Pair(int k, int v) {
  136.                         key = k;
  137.                         val = v;
  138.                         left = null;
  139.                         right = null;.1point3acres缃
  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);. 鍥磋鎴戜滑@1point 3 acres
  148.                 table.put(3, 8);
  149.                
  150.                 System.out.println(table.get(1));
  151.                 System.out.println(table.get(2));. 1point3acres.com/bbs
  152.                 System.out.println(table.get(3));. 鍥磋鎴戜滑@1point 3 acres
  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. }. 1point3acres.com/bbs
复制代码
回复 支持 反对

使用道具 举报

dc_726 发表于 2016-9-10 20:29:46 | 显示全部楼层
个人理解应该是BST实现Dictionary接口的意思吧,除了Key其他作为卫星数据?
普通BST还行,RB和AVL是真写不出来,左旋右旋……
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 07:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表