一亩三分地论坛

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

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

Airbnb电面Skype面

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

() @ - -  |

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

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

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

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

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

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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

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

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

使用道具 举报

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第一轮找最多词的思路
. 鍥磋鎴戜滑@1point 3 acres
先找到每一个单词的所有位置信息, 然后判断各单词间是否有位置重叠,lz也没想到什么比较好的办法做这一步
比如: a b c
a: [[[0,0]]]
b:  [[[0,1]]]. visit 1point3acres.com for more.
c:  [[[0,2]]]

然后这个情况下三个单词都没有重合,结果就是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. public class flightMinCost {
  3.        
  4.         public int minCost(String[] input, char source, char dest, int k){
  5.                 HashMap<Character, HashMap<Character, Integer>> graph = new HashMap<>();
  6.                
  7.                 //build a graph.1point3acres缃
  8.                 for(String s : input){
  9.                         String [] arr = s.split(",");.鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.                         char start = arr[0].charAt(0);
  11.                         char end = arr[0].charAt(3);
  12.                         int cost = Integer.parseInt(arr[1]);
  13.                        
  14.                         if(!graph.containsKey(start)){
  15.                                 HashMap<Character, Integer> map = new HashMap<Character, Integer>();
  16.                                 map.put(end, cost);
  17.                                 graph.put(start, map);
  18.                         }
  19.                         else{
  20.                                
  21.                                 HashMap<Character, Integer> m = graph.get(start);. 1point3acres.com/bbs
  22.                                 m.put(end, cost);
  23.                         }
  24.                 }
  25.                 List<Character> path = new ArrayList<>();
  26.                 List<List<Character>> allPath = new ArrayList<>();
  27.                 HashSet<Character> visited = new HashSet<>();-google 1point3acres
  28.                 .1point3acres缃
  29.                 helper(source, dest, path, allPath, graph, visited);. Waral 鍗氬鏈夋洿澶氭枃绔,
  30.                
  31.                 for(char c : graph.keySet()){
  32.                         HashMap<Character, Integer> m = graph.get(c);
  33.                         for(Character nei : m.keySet()){
  34.                                 System.out.println("source is: " + c +" dest is:" + nei + " cost is: " + m.get(nei));. 1point 3acres 璁哄潧
  35.                         }
  36.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  37.                
  38.                 int minCost = Integer.MAX_VALUE;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  39.                
  40.                 for(List<Character> p : allPath){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  41.                         if(p.size() < k){
  42.                                 int cost = getCost(graph, p);
  43.                                 minCost = Math.min(cost, minCost);
  44.                         }
  45.                 }
  46.                 -google 1point3acres
  47.                 return minCost;
  48.         }
  49.        
  50.         int getCost(HashMap<Character, HashMap<Character, Integer>> graph, List<Character> p){
  51.                 int sum = 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  52.                
  53.                 for(int i=0; i<p.size()-1; i++){
  54.                         char start = p.get(i);
  55.                         char dest = p.get(i+1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  56.                         sum += graph.get(start).get(dest);
  57.                 }
  58.                 return sum;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  59.         }
  60.         -google 1point3acres
  61.         void helper(Character source, Character dest,List<Character> path,List<List<Character>> allPath,
  62.                         HashMap<Character, HashMap<Character, Integer>> graph, HashSet<Character> visited ){
  63.                
  64.                 visited.add(source);
  65.                 path.add(source);
  66.                
  67.                 if(source == dest){
  68.                         allPath.add(new ArrayList<>(path));
  69.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  70.                 else{
  71.                         Set<Character> neis = graph.get(source).keySet();
  72.                          
  73.                         for(char n : neis){-google 1point3acres
  74.                                 if(!visited.contains(n)){
  75.                                         helper(n, dest, path, allPath, graph, visited);
  76.                                 }
  77.                         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  78.                 }
  79.                
  80.                 path.remove(path.size()-1);.1point3acres缃
  81.                 visited.remove(source);
  82.         }
  83.        
  84.        
  85.        
  86. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  87.         public static void main(String[] args) {
  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"
  95.                  };
  96.                  
  97.                  System.out.println(fmc.minCost(input, 'A', 'C', 12));
  98.                  
  99. . from: 1point3acres.com/bbs
  100.         }
  101. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  102. }
复制代码
回复 支持 反对

使用道具 举报

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的反馈,找到了这个算法。空气床啊,空气床,考这些你有想过工作中实际需要么!?!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 03:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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