一亩三分地论坛

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

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

Coursera, Houzz, Airbnb 面经

[复制链接] |试试Instant~ |关注本帖
cocaptainco 发表于 2016-11-1 10:22:17 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 全职@AirbnbCoursera, Houzz - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
发一下上周去面的全跪了的公司面经, 希望能帮到大家。

Coursera:.鏈枃鍘熷垱鑷1point3acres璁哄潧
1. Hangman, 可以搜github hangman看看相关的code, 最好自己写一下。这轮没准备,也没写好
2. Text justification
3. Sliding window minimum.

Houzz:
1. Remove any number containing 9 like 9, 19, 29, ... 91, 92, ... 99, 109... . 1point3acres.com/bbs
   Write a function that returns the nth number. E.g.  newNumber(1) = 1  newNumber(8) = 8, newNumber(9) = 10, 最后给了hint把数变成9-based.鐣欏璁哄潧-涓浜-涓夊垎鍦
2. kSum.... expect better runtime than backtracking... Consider 3sum's backtracking complexity is worse than n^2, which use's two sum's two pointer approach.
3. Design Excel. Implement
int get(string cell). from: 1point3acres.com/bbs
void put(string cell, string expr). expr can be "A1= B1+1".
这题的关键在于,要解决各个cell的dependence问题. 比如说call put(B1, "3")之后,同时也要update A1的值。会牵扯到topo sort的问题。总之这题是design题,就看你有没有意识到这种dependence。
4. Design Intagram
5. Android lock pattern from leetcode.

Airbnb:.鐣欏璁哄潧-涓浜-涓夊垎鍦
1. mincost of flight from start to end if allowed at most k connections. 比如:
A->B, 100, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
B->C, 100,
A->C, 500.
如果k是1的话,起点终点是A,C的话,那A->B->C最好, 我只想到BFS的解法。而且这题给的input给的是string和数字的混合形式,用C++parse好麻烦
2. Text justification. 鍥磋鎴戜滑@1point 3 acres
3. Design key-value store
4. project deep dive. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

1

查看全部评分

Monova 发表于 2016-11-1 11:28:54 | 显示全部楼层
请问 lz airbnb 面经的1-3是电面然后4是 onsite 么?onsite 没有 coding 题啦?
回复 支持 反对

使用道具 举报

ziyaoliu 发表于 2016-11-1 13:12:50 | 显示全部楼层
楼主 你为什么airbnb的onsite有design题目 不是说new grads没有的吗?? 是因为申请了特殊职位吗
回复 支持 反对

使用道具 举报

steveguang 发表于 2016-11-1 13:48:18 | 显示全部楼层
楼主houzz申请的什么职位?
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2016-11-1 21:30:58 | 显示全部楼层
Monova 发表于 2016-11-1 11:28. 1point 3acres 璁哄潧
请问 lz airbnb 面经的1-3是电面然后4是 onsite 么?onsite 没有 coding 题啦?

这些都是onsite的题
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2016-11-1 21:31:12 | 显示全部楼层
ziyaoliu 发表于 2016-11-1 13:12
楼主 你为什么airbnb的onsite有design题目 不是说new grads没有的吗?? 是因为申请了特殊职位吗

说我是博士给安排的吧
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2016-11-1 21:31:24 | 显示全部楼层
steveguang 发表于 2016-11-1 13:48
楼主houzz申请的什么职位?

就是back end SDE
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-11-2 01:19:55 | 显示全部楼层
k是1为什么A->B->C 难道不应该是A->C咩?
回复 支持 反对

使用道具 举报

Sayako 发表于 2016-11-2 01:29:48 | 显示全部楼层
clxy2008 发表于 2016-11-2 01:19-google 1point3acres
k是1为什么A->B->C 难道不应该是A->C咩?

cost最小 A-B 100 B-C 100加一起200 直接A-C 500
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-11-2 01:34:47 | 显示全部楼层
Sayako 发表于 2016-11-2 01:29
cost最小 A-B 100 B-C 100加一起200 直接A-C 500

这个k指的是最多可以中转城市的个数吗?。。
回复 支持 反对

使用道具 举报

南慕伦 发表于 2016-11-2 01:49:57 | 显示全部楼层
1. mincost of flight from start to end if allowed at most k connections 这题就用BFS最好了吧,到过的点记录mincost做剪枝。如果空间有限制就用迭代加深搜索
回复 支持 反对

使用道具 举报

Sayako 发表于 2016-11-2 01:52:33 | 显示全部楼层
clxy2008 发表于 2016-11-2 01:34. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这个k指的是最多可以中转城市的个数吗?。。
. visit 1point3acres.com for more.
根据以前地里的面经 是
回复 支持 反对

使用道具 举报

Sayako 发表于 2016-11-2 02:49:14 | 显示全部楼层
那个城市的题我的解法 不知道有没有bug,我默认输入的字符串没有错误,都是“A->B,100”这种格式的,具体面试的时候可能还要问面试官,然后我的解法里城市总数目是给出来的,这个具体给不给出来可能也得问,不给出来的话要用个set记录一下就是比较麻烦,我就没写,k我按照中转城市数目记,比如A->B,B->C中转城市数目就是1. 应该不是最优解,大家凑合看看……
  1. package airbnb;
  2. import java.util.*;. 1point3acres.com/bbs
  3. import java.io.*;
  4. public class FlightCost {

  5.         public static void main(String[] args) {
  6.                 String[] input = {"A->B,100","A->C,100","C->D,200","A->D,500","B->C,300"};
  7.                 FlightSolution sol = new FlightSolution(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.                 sol.search(input, 1, 'A', 'C', 4);
  9.         }
  10. . from: 1point3acres.com/bbs
  11. }
  12. class FlightSolution {
  13.         int min = Integer.MAX_VALUE;
  14.         String path = "";
  15.         public void search(String[] input, int k, char start, char end, int num) {
  16.                 Map<Character, List<Node>> map = new HashMap<>();
  17.                 for(String str:input) {
  18.                         char dep = str.charAt(0);
  19.                         char arr = str.charAt(3);
  20.                         String[] strs = str.split(",");
  21.                         int cost =Integer.parseInt(strs[1]);
  22.                         Node node = new Node(arr,cost);
  23.                         map.putIfAbsent(dep, new ArrayList<Node>());
  24.                         map.get(dep).add(node);
  25.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  26.                 boolean[] visited = new boolean[num];
  27.                 StringBuilder sb = new StringBuilder();
  28.                 sb.append(start);
  29.                 helper(map,k,start,end,sb,-1,0,visited);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  30.                 System.out.println("Minimum cost: "+min+" Path: "+path);
  31.         }
  32.         private void helper(Map<Character,List<Node>> map, int k, char start, char end,
  33.                         StringBuilder sb, int counter, int cost, boolean[] visited) {. visit 1point3acres.com for more.
  34.                 if(start==end && counter<=k) {
  35.                         if(cost<min) {
  36.                                 min = cost;
  37.                                 path = sb.toString();
  38.                         }
  39.                         sb.setLength(1);
  40.                         return;
  41.                 }
  42.                 if(cost>=min || counter>k) {
  43.                         sb.setLength(1);
  44.                         return;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  45.                 }
  46.                 List<Node> list = map.get(start);-google 1point3acres
  47.                 visited[start-'A'] = true;
  48.                 for(Node n:list) {
  49.                         sb.append(n.destination);
  50.                         helper(map,k,n.destination,end,sb,counter+1,cost+n.cost,visited);. from: 1point3acres.com/bbs
  51.                 }. visit 1point3acres.com for more.
  52.                 visited[start-'A'] = false;
  53.         }
  54. }
  55. class Node {
  56.         char destination;
  57.         int cost;
  58.         public Node(char des, int cost) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  59.                 destination = des;
  60.                 this.cost = cost;. more info on 1point3acres.com
  61.         }
  62. }
复制代码

补充内容 (2016-11-2 02:50):
起点终点我当成输入参数了,不一定要遍历所有城市

补充内容 (2016-11-2 11:19):
helper第二个return加上visited[]
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2016-11-2 11:15:06 | 显示全部楼层
楼主您好马上要去airbnb onsite啦,想问下是可以带自己电脑在自己的编译器上写的吗?
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2016-11-2 11:16:33 | 显示全部楼层
还有这个题目最佳用dp做吧
回复 支持 反对

使用道具 举报

Sayako 发表于 2016-11-2 11:20:33 | 显示全部楼层
yucheyang2 发表于 2016-11-2 11:16
还有这个题目最佳用dp做吧

dp怎么做?
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2016-11-2 11:45:19 | 显示全部楼层
yucheyang2 发表于 2016-11-2 11:15
楼主您好马上要去airbnb onsite啦,想问下是可以带自己电脑在自己的编译器上写的吗?

应该是可以的
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2016-11-2 11:54:36 | 显示全部楼层

就是connection一围cities一围,
回复 支持 反对

使用道具 举报

 楼主| cocaptainco 发表于 2016-11-2 11:55:05 | 显示全部楼层
  1. queue<string> q;. Waral 鍗氬鏈夋洿澶氭枃绔,
  2. q.push(start);

  3. .1point3acres缃
  4. int iter=0;
  5. while(iter <=k){
  6.     iter ++;
  7.     int size = q.size();. more info on 1point3acres.com
  8.     for(int i = 0; i < size; i++){
  9.         auto cur = q.front(); q.pop();
  10.         for(auto ng: neighbor[cur] && cost[ng] > cost[cur] + ticket[cur->ng]) {
  11.             cost[ng] = cost[cur]+ ticket[cur->ng];
  12.             q.push(ng);

  13.         }
  14.     }
  15. }
复制代码

.鐣欏璁哄潧-涓浜-涓夊垎鍦
当时写了个类似的代码,跑了一下结果好像没有被challenge说不对,烙印说我这个效率不行,会重复走边。。 我想了一下,感觉也没法删边吧。
回复 支持 反对

使用道具 举报

Sayako 发表于 2016-11-2 12:10:41 | 显示全部楼层
yucheyang2 发表于 2016-11-2 11:54
就是connection一围cities一围,

不太明白啊,求详细……
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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