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


一亩三分地论坛

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

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

Airbnb电面Skype面

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

() @ - -  |

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

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

x
简介: 9月网申,隔天HR 就来找了,然后电面, 然后Skype面,不知道为什么现在onsite之前还要skype。

电面一轮: floor and ceiling那道题,有轻微变化。

Skype 两轮: 1. Boggle Game, 就是给一个char board(n*m), 给一个dictionary, 求出在不重复使用board里头的character的情况下最多可以在board里头找到多少dictionary里头的词。当时准备面经的时候就没好好准备这题,虽然国人小哥基本一点没为难,上来就把思路跟我说了,但是因为之前没写过,再加上学艺不精,所以最后也没写完。

2. 新题新题,面经中没见过的!给一堆飞机票, 要求给出在从城市a到b,花钱最少,并且connection次数超过k次的行程及价钱(connection可以理解为历经的城市)。 理解题目跟讨论解法上花了很长时间,lz说了bfs的解法,小哥暗示了一下用dp,但lz是个渣渣,实在想不出来,最后写了个bfs的,显然不是面试小哥想要的。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

比如要求 a 到 b, connection: 4. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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

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

最后,lz是今年8月才毕业的文科转CS的master,背景不太好,之前也网投了内推了一些公司,但是都被拒了,在地里求内推的帖子里回复只有一个salesforce的姑娘给我推了,当时还没毕业,被拒了。 A家是第一个给我面试的,也没想着能拿到offer的,能够过了电面已经很开心了!(来自**发自内心的喜悦,啊哈哈哈,然后当时也没想到还有Skype面,地里小伙伴有知道为什么要加面skype的吗?因为电面不够满意?)现在已经毕业两月了,有些紧张了,不过紧张也没啥卵用,反正刷刷刷,投投投,与大家共勉!!!!!!!!!
seekingJob320 发表于 2016-10-15 01:05:34 | 显示全部楼层
关注一亩三分地微博:
Warald
请问楼主第二题结果是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
请问楼主第二题结果是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

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

使用道具 举报

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

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

使用道具 举报

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]]]. 1point3acres.com/bbs

然后这个情况下三个单词都没有重合,结果就是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.*;. more info on 1point3acres.com
  2. . visit 1point3acres.com for more.
  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
  9.                 for(String s : input){. 鍥磋鎴戜滑@1point 3 acres
  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.                         .1point3acres缃
  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.                         }. 1point3acres.com/bbs
  20.                         else{
  21.                                 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.                                 HashMap<Character, Integer> m = graph.get(start);
  23.                                 m.put(end, cost);
  24.                         }
  25.                 }
    . 鍥磋鎴戜滑@1point 3 acres
  26.                 List<Character> path = new ArrayList<>();. 1point3acres.com/bbs
  27.                 List<List<Character>> allPath = new ArrayList<>();
  28.                 HashSet<Character> visited = new HashSet<>();
  29.                
  30.                 helper(source, dest, path, allPath, graph, visited);
  31.                
  32.                 for(char c : graph.keySet()){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  33.                         HashMap<Character, Integer> m = graph.get(c);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  34.                         for(Character nei : m.keySet()){
  35.                                 System.out.println("source is: " + c +" dest is:" + nei + " cost is: " + m.get(nei));
  36.                         }-google 1point3acres
  37.                 }
  38.                 . 1point 3acres 璁哄潧
  39.                 int minCost = Integer.MAX_VALUE;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  40.                
  41.                 for(List<Character> p : allPath){. From 1point 3acres bbs
  42.                         if(p.size() < k){
  43.                                 int cost = getCost(graph, p);
  44.                                 minCost = Math.min(cost, minCost);. more info on 1point3acres.com
  45.                         }
  46.                 }. 鍥磋鎴戜滑@1point 3 acres
  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);
  56.                         char dest = p.get(i+1);-google 1point3acres
  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{. 1point3acres.com/bbs
  72.                         Set<Character> neis = graph.get(source).keySet();
  73.                          
  74.                         for(char n : neis){
  75.                                 if(!visited.contains(n)){
  76.                                         helper(n, dest, path, allPath, graph, visited);. more info on 1point3acres.com
  77.                                 }
  78.                         }
  79.                 }. From 1point 3acres bbs
  80.                 . visit 1point3acres.com for more.
  81.                 path.remove(path.size()-1);
  82.                 visited.remove(source);
  83.         }
  84.         . visit 1point3acres.com for more.
  85.        
  86.        

  87.         public static void main(String[] args) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  88.                  flightMinCost fmc = new flightMinCost();
  89.                  String [] input = {
  90.                                 "A->B,8",
  91.                                 "B->C,4",
  92.                                 "A->D,1",
  93.                                 "D->E,2",
  94.                                 "E->B,3". From 1point 3acres bbs
  95.                  };
  96.                  
  97.                  System.out.println(fmc.minCost(input, 'A', 'C', 12));
  98.                  

  99.         }
  100. . from: 1point3acres.com/bbs
  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.1point3acres缃
机票那题根据ls的反馈,找到了这个算法。空气床啊,空气床,考这些你有想过工作中实际需要么!?!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-26 08:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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