《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4633|回复: 31
收起左侧

Airbnb电面Skype面

[复制链接] |试试Instant~ |关注本帖
xiubiubong 发表于 2016-10-15 00:43:45 | 显示全部楼层 |阅读模式

() @ - -  |

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

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

x
简介: 9月网申,隔天HR 就来找了,然后电面, 然后Skype面,不知道为什么现在onsite之前还要skype。
.1point3acres缃
电面一轮: floor and ceiling那道题,有轻微变化。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Skype 两轮: 1. Boggle Game, 就是给一个char board(n*m), 给一个dictionary, 求出在不重复使用board里头的character的情况下最多可以在board里头找到多少dictionary里头的词。当时准备面经的时候就没好好准备这题,虽然国人小哥基本一点没为难,上来就把思路跟我说了,但是因为之前没写过,再加上学艺不精,所以最后也没写完。
. visit 1point3acres.com for more.
2. 新题新题,面经中没见过的!给一堆飞机票, 要求给出在从城市a到b,花钱最少,并且connection次数超过k次的行程及价钱(connection可以理解为历经的城市)。 理解题目跟讨论解法上花了很长时间,lz说了bfs的解法,小哥暗示了一下用dp,但lz是个渣渣,实在想不出来,最后写了个bfs的,显然不是面试小哥想要的。
. Waral 鍗氬鏈夋洿澶氭枃绔,
比如要求 a 到 b, connection: 4

[a, d, 2], [a, b, 12], [d, c, 5]

结果应该是: a ->d, d->c, 7

面试感受: 三面全是国人小哥,都是毕业不久的年轻小哥,其实人都还不错,最后一面这个小哥感觉面试别人经验比较少,不怎么会引导,语言上也比前两面的稍微差一点点,沟通起来感觉比较难。他家回信还挺快,我都是周五面的,然后下周周二的样子就给回信了。

最后,lz是今年8月才毕业的文科转CS的master,背景不太好,之前也网投了内推了一些公司,但是都被拒了,在地里求内推的帖子里回复只有一个salesforce的姑娘给我推了,当时还没毕业,被拒了。 A家是第一个给我面试的,也没想着能拿到offer的,能够过了电面已经很开心了!(来自**发自内心的喜悦,啊哈哈哈,然后当时也没想到还有Skype面,地里小伙伴有知道为什么要加面skype的吗?因为电面不够满意?)现在已经毕业两月了,有些紧张了,不过紧张也没啥卵用,反正刷刷刷,投投投,与大家共勉!!!!!!!!!
gy21 发表于 2016-11-4 05:32:51 | 显示全部楼层
机票题目DP思想解,欢迎指正~~~.1point3acres缃
  1. public int minCost(String[] input, char source, char dest, int k){
  2.                 HashSet<Character> set = new HashSet<>();
  3.                 //get how many cities in the input
  4.                 for(String s : input){
  5.                         String[] arr = s.split(",");. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6.                         set.add(arr[0].charAt(0));
  7.                         set.add(arr[0].charAt(3));
  8.                 }
  9.                 int[][] dp = new int[set.size()][set.size()];. 鍥磋鎴戜滑@1point 3 acres
  10.                 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  11.                 for(int[] arr : dp){
  12.                         Arrays.fill(arr, 999999);
  13.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.                 //build a graph
  16.                 for(String s : input){
  17.                         String[] arr = s.split(",");
  18.                         Character from = arr[0].charAt(0);. 1point 3acres 璁哄潧
  19.                         Character to = arr[0].charAt(3);
  20.                         //cycle exists
  21.                         if(from == to){
  22.                                 dp[from-'A'][to-'A'] = 0;
  23.                         }
  24.                         dp[from-'A'][to-'A'] = Integer.parseInt(arr[1]);
  25.                 }
  26.                 List<Character> path = new ArrayList<>();. 鍥磋鎴戜滑@1point 3 acres
  27.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  28.                 for(int k1=0; k1<dp.length; k1++){
  29.                         for(int i=0; i<dp.length; i++){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  30.                                 for(int j=0; j<dp.length; j++){
  31.                                         if(k1 <= k){
  32.                                                 if(dp[i][j] > dp[i][k1] + dp[k1][j]){
  33.                                                         dp[i][j] = dp[i][k1] + dp[k1][j];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  34.                                                 }
  35.                                         }
  36.                                 }
  37.                         }
  38.                 }
  39.                
  40.                
  41.                 for(int i=0; i<dp.length; i++){
  42.                         for(int j=0; j<dp.length; j++){
  43.                                 System.out.print(dp[i][j] + " ");
  44.                         }
  45.                         System.out.println();
  46.                 }
  47.                 return dp[source-'A'][dest-'A'];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  48.         }. from: 1point3acres.com/bbs
  49.        
  50.         public static void main(String[] args) {. 1point 3acres 璁哄潧
  51.                  String [] input = {
  52.                                         "A->B,8", . visit 1point3acres.com for more.
  53.                                         "B->C,4",
  54.                                         "A->D,1",
  55.                                         "D->E,2",
  56.                                         "E->B,3"
  57.                          };. 鍥磋鎴戜滑@1point 3 acres
  58.                  Floyd f = new Floyd();
  59.                  
  60.                  System.out.println(f.minCost(input, 'A', 'E', 2));
  61.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

seekingJob320 发表于 2016-10-15 01:05:34 | 显示全部楼层
请问楼主第二题结果是a 到d, d到c, 可是要求是a到b, 能进一步解释一下吗
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-10-15 01:09:56 | 显示全部楼层
dp[start][end][connection]
想了一个三维dp的,不知道能不能work。。

补充内容 (2016-10-15 01:19):
想错了。。忽略我
回复 支持 反对

使用道具 举报

 楼主| xiubiubong 发表于 2016-10-15 01:30:43 | 显示全部楼层
seekingJob320 发表于 2016-10-15 01:05. more info on 1point3acres.com
请问楼主第二题结果是a 到d, d到c, 可是要求是a到b, 能进一步解释一下吗

是打错了真是不好意思哈,第三个输入应该是[d,b,5], 结果也应该是a ->d, d->b, 7
回复 支持 反对

使用道具 举报

seekingJob320 发表于 2016-10-15 01:51:51 | 显示全部楼层
xiubiubong 发表于 2016-10-15 01:30
是打错了真是不好意思哈,第三个输入应该是[d,b,5], 结果也应该是a ->d, d->b, 7

楼主您好 还有一个问题, 请问每张飞机票的价格,是不是还需要给出?谢谢
回复 支持 反对

使用道具 举报

 楼主| xiubiubong 发表于 2016-10-15 02:14:45 | 显示全部楼层
seekingJob320 发表于 2016-10-15 01:51. from: 1point3acres.com/bbs
楼主您好 还有一个问题, 请问每张飞机票的价格,是不是还需要给出?谢谢

你是说结果里面吗,结果里要求给出的最后总的机票价格
回复 支持 反对

使用道具 举报

cocaptainco 发表于 2016-10-15 06:41:15 | 显示全部楼层
楼主能分享一下第一轮的思路吗
回复 支持 反对

使用道具 举报

cocaptainco 发表于 2016-10-15 06:41:47 | 显示全部楼层
不好意思,我指的是skype第一轮找最多词的思路
回复 支持 反对

使用道具 举报

 楼主| xiubiubong 发表于 2016-10-15 07:37:58 | 显示全部楼层
cocaptainco 发表于 2016-10-15 06:41
不好意思,我指的是skype第一轮找最多词的思路

先找到每一个单词的所有位置信息, 然后判断各单词间是否有位置重叠,lz也没想到什么比较好的办法做这一步.鏈枃鍘熷垱鑷1point3acres璁哄潧
比如: a b c
a: [[[0,0]]]
b:  [[[0,1]]]
c:  [[[0,2]]]. 1point 3acres 璁哄潧

. 1point 3acres 璁哄潧然后这个情况下三个单词都没有重合,结果就是3
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2016-10-21 05:48:25 | 显示全部楼层
楼主想问下第二题,a,d,2 的2 是connection的意思吗,那每张票是不是还要给出价格呀?还是说2 是价格,那a - d - b 只有三个城市没有到4 啊
回复 支持 反对

使用道具 举报

yvenica 发表于 2016-10-22 02:13:04 | 显示全部楼层
楼主问一下floor and ceiling那个是哪题呀?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-2 06:16:41 | 显示全部楼层
飞机票那题感觉DP不能做啊,因为可能有环啊。。。
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-2 06:29:46 | 显示全部楼层
connection次数应该是小于等于k次吧。
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-2 07:56:28 | 显示全部楼层
个人感觉DP做不了那个飞机票的题目。面试官是不是期待dp做记录中间结果呢?不知道。。。掐表写了个graph DFS的,找到所有路径-》计算cost-》找到最小 写完了已经43分钟了。。。

  1. import java.util.*;
  2. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  3. public class flightMinCost {
  4.        
  5.         public int minCost(String[] input, char source, char dest, int k){
  6.                 HashMap<Character, HashMap<Character, Integer>> graph = new HashMap<>();
  7.                
  8.                 //build a graph.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.                 for(String s : input){. From 1point 3acres bbs
  10.                         String [] arr = s.split(",");
  11.                         char start = arr[0].charAt(0);
  12.                         char end = arr[0].charAt(3);
  13.                         int cost = Integer.parseInt(arr[1]);
  14.                        
  15.                         if(!graph.containsKey(start)){
  16.                                 HashMap<Character, Integer> map = new HashMap<Character, Integer>();
  17.                                 map.put(end, cost);
  18.                                 graph.put(start, map);
  19.                         }
  20.                         else{
  21.                                 . more info on 1point3acres.com
  22.                                 HashMap<Character, Integer> m = graph.get(start);
  23.                                 m.put(end, cost);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  24.                         }. 1point3acres.com/bbs
  25.                 }
  26.                 List<Character> path = new ArrayList<>();
  27.                 List<List<Character>> allPath = new ArrayList<>();
  28.                 HashSet<Character> visited = new HashSet<>();
  29.                
  30.                 helper(source, dest, path, allPath, graph, visited);
  31.                
    . from: 1point3acres.com/bbs
  32.                 for(char c : graph.keySet()){
  33.                         HashMap<Character, Integer> m = graph.get(c);
  34.                         for(Character nei : m.keySet()){
  35.                                 System.out.println("source is: " + c +" dest is:" + nei + " cost is: " + m.get(nei));
  36.                         }.1point3acres缃
  37.                 }
  38.                
  39.                 int minCost = Integer.MAX_VALUE;
  40.                
  41.                 for(List<Character> p : allPath){
  42.                         if(p.size() < k){
  43.                                 int cost = getCost(graph, p);
  44.                                 minCost = Math.min(cost, minCost);
  45.                         }
  46.                 }
  47.                
  48.                 return minCost;
  49.         }
  50.         .鐣欏璁哄潧-涓浜-涓夊垎鍦
  51.         int getCost(HashMap<Character, HashMap<Character, Integer>> graph, List<Character> p){
  52.                 int sum = 0;
  53.                
  54.                 for(int i=0; i<p.size()-1; i++){
  55.                         char start = p.get(i);. 1point 3acres 璁哄潧
  56.                         char dest = p.get(i+1);
  57.                         sum += graph.get(start).get(dest);
  58.                 }
  59.                 return sum;
  60.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  61.        
  62.         void helper(Character source, Character dest,List<Character> path,List<List<Character>> allPath,
  63.                         HashMap<Character, HashMap<Character, Integer>> graph, HashSet<Character> visited ){
  64.                 . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  65.                 visited.add(source);
  66.                 path.add(source);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  67.                
  68.                 if(source == dest){
  69.                         allPath.add(new ArrayList<>(path));
  70.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  71.                 else{. more info on 1point3acres.com
  72.                         Set<Character> neis = graph.get(source).keySet();. Waral 鍗氬鏈夋洿澶氭枃绔,
  73.                          
  74.                         for(char n : neis){
  75.                                 if(!visited.contains(n)){
  76.                                         helper(n, dest, path, allPath, graph, visited);
  77.                                 }
  78.                         }
  79.                 }
  80.                
  81.                 path.remove(path.size()-1);
  82.                 visited.remove(source);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  83.         }
  84.        
  85.        
  86.        
  87. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  88.         public static void main(String[] args) {
  89.                  flightMinCost fmc = new flightMinCost();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  90.                  String [] input = {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  91.                                 "A->B,8", . visit 1point3acres.com for more.
  92.                                 "B->C,4",
  93.                                 "A->D,1",
  94.                                 "D->E,2",.1point3acres缃
  95.                                 "E->B,3"
  96.                  };.鐣欏璁哄潧-涓浜-涓夊垎鍦
  97.                  
  98.                  System.out.println(fmc.minCost(input, 'A', 'C', 12));
  99.                  

  100.         }

  101. }
复制代码
回复 支持 反对

使用道具 举报

vesalius 发表于 2016-11-3 06:16:44 | 显示全部楼层
gy21 发表于 2016-11-2 07:56
个人感觉DP做不了那个飞机票的题目。面试官是不是期待dp做记录中间结果呢?不知道。。。掐表写了个graph DF ...

DP bellman ford算法 别的面经帖子里大牛给的解法
回复 支持 反对

使用道具 举报

梦醒的我 发表于 2016-11-3 09:52:22 | 显示全部楼层
如果是小于k次connection的话,可不可以直接dijkstra,多记上从source到每个node中间经过了多少node,超过的话就不update呢
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-4 01:00:04 | 显示全部楼层
vesalius 发表于 2016-11-2 14:16
DP bellman ford算法 别的面经帖子里大牛给的解法
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
求链接。想看看这题。谢谢!
回复 支持 反对

使用道具 举报

vesalius 发表于 2016-11-4 01:05:39 | 显示全部楼层
gy21 发表于 2016-11-4 01:00
求链接。想看看这题。谢谢!

就这个帖子里的第二个题 没代码 你搜一下bellman-ford正好符合题目要求,这个是dp的
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-4 01:17:35 | 显示全部楼层
http://www.cnblogs.com/gaochundong/p/bellman_ford_algorithm.html
机票那题根据ls的反馈,找到了这个算法。空气床啊,空气床,考这些你有想过工作中实际需要么!?!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-20 08:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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