10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 4283|回复: 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里头的词。当时准备面经的时候就没好好准备这题,虽然国人小哥基本一点没为难,上来就把思路跟我说了,但是因为之前没写过,再加上学艺不精,所以最后也没写完。-google 1point3acres

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

比如要求 a 到 b, connection: 4

[a, d, 2], [a, b, 12], [d, c, 5]
. 1point3acres.com/bbs
结果应该是: a ->d, d->c, 7. more info on 1point3acres.com

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

最后,lz是今年8月才毕业的文科转CS的master,背景不太好,之前也网投了内推了一些公司,但是都被拒了,在地里求内推的帖子里回复只有一个salesforce的姑娘给我推了,当时还没毕业,被拒了。 A家是第一个给我面试的,也没想着能拿到offer的,能够过了电面已经很开心了!(来自**发自内心的喜悦,啊哈哈哈,然后当时也没想到还有Skype面,地里小伙伴有知道为什么要加面skype的吗?因为电面不够满意?)现在已经毕业两月了,有些紧张了,不过紧张也没啥卵用,反正刷刷刷,投投投,与大家共勉!!!!!!!!!
gy21 发表于 2016-11-4 05:32:51 | 显示全部楼层
机票题目DP思想解,欢迎指正~~~ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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(",");. 1point 3acres 璁哄潧
  6.                         set.add(arr[0].charAt(0));
  7.                         set.add(arr[0].charAt(3));.1point3acres缃
  8.                 }
  9.                 int[][] dp = new int[set.size()][set.size()]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10.                
  11.                 for(int[] arr : dp){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.                         Arrays.fill(arr, 999999);
  13.                 }
  14.                 . from: 1point3acres.com/bbs
  15.                 //build a graph
  16.                 for(String s : input){
  17.                         String[] arr = s.split(",");
  18.                         Character from = arr[0].charAt(0);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  19.                         Character to = arr[0].charAt(3);.1point3acres缃
  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.                 }. visit 1point3acres.com for more.
  26.                 List<Character> path = new ArrayList<>();
  27.                
  28.                 for(int k1=0; k1<dp.length; k1++){. From 1point 3acres bbs
  29.                         for(int i=0; i<dp.length; i++){
  30.                                 for(int j=0; j<dp.length; j++){-google 1point3acres
  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.                 . 鍥磋鎴戜滑@1point 3 acres
  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.                         }. visit 1point3acres.com for more.
  45.                         System.out.println();
  46.                 }
  47.                 return dp[source-'A'][dest-'A'];
  48.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  49.        
  50.         public static void main(String[] args) {
  51.                  String [] input = {
  52.                                         "A->B,8",
  53.                                         "B->C,4",
  54.                                         "A->D,1",
  55.                                         "D->E,2",. more info on 1point3acres.com
  56.                                         "E->B,3"
  57.                          };
  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
请问楼主第二题结果是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. 1point3acres.com/bbs
不好意思,我指的是skype第一轮找最多词的思路

先找到每一个单词的所有位置信息, 然后判断各单词间是否有位置重叠,lz也没想到什么比较好的办法做这一步
比如: a b c 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
a: [[[0,0]]]
b:  [[[0,1]]]
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
  8.                 for(String s : input){
  9.                         String [] arr = s.split(",");
  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);
  22.                                 m.put(end, cost);
  23.                         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  24.                 }
  25.                 List<Character> path = new ArrayList<>();
  26.                 List<List<Character>> allPath = new ArrayList<>();
  27.                 HashSet<Character> visited = new HashSet<>();
  28.                
  29.                 helper(source, dest, path, allPath, graph, visited);
  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));
  35.                         }
  36.                 }
  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.                
  47.                 return minCost;
  48.         }
  49.         .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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;. From 1point 3acres bbs
  59.         }
  60.         . visit 1point3acres.com for more.
  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.                 . visit 1point3acres.com for more.
  67.                 if(source == dest){
  68.                         allPath.add(new ArrayList<>(path));
  69.                 }
  70.                 else{
  71.                         Set<Character> neis = graph.get(source).keySet();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  72.                          
  73.                         for(char n : neis){
  74.                                 if(!visited.contains(n)){
  75.                                         helper(n, dest, path, allPath, graph, visited);
  76.                                 }
  77.                         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  78.                 }
  79.                 . more info on 1point3acres.com
  80.                 path.remove(path.size()-1);
  81.                 visited.remove(source);. from: 1point3acres.com/bbs
  82.         }
  83.        
  84.        
  85.        

  86.         public static void main(String[] args) {
  87.                  flightMinCost fmc = new flightMinCost();
  88.                  String [] input = {
  89.                                 "A->B,8",
  90.                                 "B->C,4",
  91.                                 "A->D,1",
  92.                                 "D->E,2",
  93.                                 "E->B,3"
  94.                  }; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  95.                  
  96.                  System.out.println(fmc.minCost(input, 'A', 'C', 12));. from: 1point3acres.com/bbs
  97.                  . visit 1point3acres.com for more.
  98. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  99.         }
  100. . more info on 1point3acres.com
  101. }
复制代码
回复 支持 反对

使用道具 举报

vesalius 发表于 2016-11-3 06:16:44 | 显示全部楼层
gy21 发表于 2016-11-2 07:56
个人感觉DP做不了那个飞机票的题目。面试官是不是期待dp做记录中间结果呢?不知道。。。掐表写了个graph DF ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
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-9-21 04:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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