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


一亩三分地论坛

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

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

Coursera, Houzz, Airbnb 面经

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

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

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

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

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

coursera
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...
   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)
void put(string cell, string expr). expr can be "A1= B1+1".
这题的关键在于,要解决各个cell的dependence问题. 比如说call put(B1, "3")之后,同时也要update A1的值。会牵扯到topo sort的问题。总之这题是design题,就看你有没有意识到这种dependence。. 1point3acres.com/bbs
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
3. Design key-value store
4. project deep dive.

评分

1

查看全部评分

Sayako 发表于 2016-11-2 02:49:14 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
那个城市的题我的解法 不知道有没有bug,我默认输入的字符串没有错误,都是“A->B,100”这种格式的,具体面试的时候可能还要问面试官,然后我的解法里城市总数目是给出来的,这个具体给不给出来可能也得问,不给出来的话要用个set记录一下就是比较麻烦,我就没写,k我按照中转城市数目记,比如A->B,B->C中转城市数目就是1. 应该不是最优解,大家凑合看看……
  1. package airbnb;
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2. import java.util.*;
  3. import java.io.*;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4. public class FlightCost {
  5. . from: 1point3acres.com/bbs
  6.         public static void main(String[] args) {
  7.                 String[] input = {"A->B,100","A->C,100","C->D,200","A->D,500","B->C,300"};
    -google 1point3acres
  8.                 FlightSolution sol = new FlightSolution();
  9.                 sol.search(input, 1, 'A', 'C', 4);
  10.         }

  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(",");. From 1point 3acres bbs
  21.                         int cost =Integer.parseInt(strs[1]);. From 1point 3acres bbs
  22.                         Node node = new Node(arr,cost);. 1point3acres.com/bbs
  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) {. 1point3acres.com/bbs
  34.                 if(start==end && counter<=k) {-google 1point3acres
  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);. 1point 3acres 璁哄潧
  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);
  51.                 }
  52.                 visited[start-'A'] = false;
  53.         }. From 1point 3acres bbs
  54. }
  55. class Node {
  56.         char destination;
  57.         int cost;
  58.         public Node(char des, int cost) {.1point3acres缃
  59.                 destination = des;
  60.                 this.cost = cost;
  61.         }
  62. }
复制代码
. From 1point 3acres bbs
补充内容 (2016-11-2 02:50):
起点终点我当成输入参数了,不一定要遍历所有城市

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

使用道具 举报

Monova 发表于 2016-11-1 11:28:54 | 显示全部楼层
关注一亩三分地微博:
Warald
请问 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
请问 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
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
. 鍥磋鎴戜滑@1point 3 acres
这个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指的是最多可以中转城市的个数吗?。。

根据以前地里的面经 是
回复 支持 反对

使用道具 举报

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; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2. q.push(start);

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

  12.         }
  13.     }
  14. }
复制代码
. Waral 鍗氬鏈夋洿澶氭枃绔,

当时写了个类似的代码,跑了一下结果好像没有被challenge说不对,烙印说我这个效率不行,会重复走边。。 我想了一下,感觉也没法删边吧。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-25 11:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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