May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2871|回复: 3
收起左侧

whatsapp intern面经

[复制链接] |试试Instant~ |关注本帖
seckcoder 发表于 2015-3-23 14:43:25 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 实习@Facebookwhatsapp - 校园招聘会 - 技术电面 Onsite |Fail

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
电面一轮,onsite两轮。最后悲剧了。

电面:
1. 把一个sorted list转成balanced binary search tree
2. 把sorted list转成complete binary search tree


onsite第一轮:
主要讨论project。然后要实现Trie的插入。由于我说我会Haskell, 然后被要求用Haskell实现。由于之前没在白板上写过code,写得很乱。最后问hr,也说到我的code不够clean,感觉应该是因为这个悲剧了。

onsite第二轮:
也是主要讨论project。然后问了几个关于链表的题:

1. 给一个linked list, 求长度
2. 实现在linked list中append一个节点
3. 实现在linked list中prepend一个节点
4. 利用上面的函数,实现将一个数组变成linked list.
5. 要求提高4的性能。4已经是O(n), 所以要提高性能只能并发。我先是用fortress写了一个实现。利用Fortress的并发特性,可以达到O(lgn)。然后被要求不用Fortress。我又用openmp给了一个多线程实现。
. visit 1point3acres.com for more.

评分

2

查看全部评分

eric108 发表于 2015-3-23 22:13:59 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
周三面whatsapp的fulltime,楼主这问题也太难了点吧,看来whatsapp还挺高冷的 估计没戏了
回复 支持 反对

使用道具 举报

然姐Carol 发表于 2015-3-25 06:06:01 | 显示全部楼层
关注一亩三分地微博:
Warald
实习这么个面法也是蛮拼的
回复 支持 反对

使用道具 举报

joseph5wu 发表于 2016-2-7 16:07:55 | 显示全部楼层
那个sorted list to complete BST 参考了一下前面的balanced BST的递归做法,跑了一下inorder/level order/isBST检查了一下应该没什么问题:
  1. public class Solution {
  2.     private ListNode node;

  3.     private int getDividePos(int start, int end) {
  4.         int m = end - start + 1;
  5.         int height = (int)Math.ceil(Math.log(m + 1) / Math.log(2));-google 1point3acres
  6.         if(3 * Math.pow(2, height - 2) - 1 >= m) {
  7.             return end - (int) Math.pow(2, height - 2) + 1;
  8.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.         else { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10.             return start + (int) Math.pow(2, height - 1) - 1;
  11.         }
  12.     }

  13.     private int getLength(ListNode node) {. visit 1point3acres.com for more.
  14.         int length = 0;. visit 1point3acres.com for more.
  15.         while(node != null) {
  16.             length++;. visit 1point3acres.com for more.
  17.             node = node.next;. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.         }
  19.         return length;
  20.     }. visit 1point3acres.com for more.

  21.     public TreeNode convert(ListNode head) {
  22.         if(head == null) {
  23.             return null;
  24.         }.1point3acres缃

  25.         this.node = head;
  26.         int length = getLength(head);
  27.         return convert(0, length - 1);
  28.     } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  29.     private TreeNode convert(int start, int end) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.         if(start > end) {
  31.             return null;
  32.         }
  33. . 鍥磋鎴戜滑@1point 3 acres
  34.         int rootIndex = getDividePos(start, end);
  35.         TreeNode left = convert(start, rootIndex - 1);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  36.         TreeNode root = new TreeNode(node.value);
  37.         node = node.next;
  38.         TreeNode right = convert(rootIndex + 1, end);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  39.         root.left = left;. Waral 鍗氬鏈夋洿澶氭枃绔,
  40.         root.right = right;
  41.         return root;
  42.     }
  43. }
复制代码

回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-23 14:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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