一亩三分地论坛

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

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

Airbnb 面经求问

[复制链接] |试试Instant~ |关注本帖
clxy2008 发表于 2016-10-30 14:40:09 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Airbnb - 内推 - 其他 |Otherfresh grad应届毕业生

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

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

x
有几道题想问下:

1. decode string  那道题,到底是什么意思呢?我总感觉这题有点简单的过分了吧?如果我把所有目标串里的大写改成小写,然后看这两个串一不一样不就可以了吗?. From 1point 3acres bbs

2.boggle game  到底题目是什么意思呢?如果是说一条路上的最多单词,那么就是找到了某个单词以后,有两种情况,一种回根继续重新找,一种继续下去,有可能目前这个单词是另一个字典里的单词的前缀,最后看这一条路上有多少单词,如果最多就记录下来然后输出?

可是貌似看到其他问法,而且难度极大,比如不再限定一条路,而是棋盘上随便找,看能否组合出最大种类。这一下就除了爆搜我想不出其他解法,求讲解。

求大神解答
sophie729 发表于 2016-10-30 15:03:02 | 显示全部楼层
可以贴一下原版题目么 这个 不知道在说什么啊?
回复 支持 1 反对 0

使用道具 举报

梦醒的我 发表于 2016-10-31 01:57:46 | 显示全部楼层
我记得题目好像是给你一个function,input是一个string,output一个id如果input string是decodeable不然就output null之类的。然后让你写一个decode string的function。所以不能改目标里面的东西吧。只能用backtracking一个个试
回复 支持 反对

使用道具 举报

susand33 发表于 2016-10-31 02:15:35 | 显示全部楼层
第一题原题应该是这个,简单点就点简单呗。。
URL Shortener. visit 1point3acres.com for more.
/*
Often, we want to encode raw IDs in our database by hiding them behind some 2-way decodeable hash. So, a URL which would have at one time been:
https://www.airbnb.com/rooms/848662
becomes
https://www.airbnb.com/rooms/kljJJ324hjkS_
We decode the ID kljJJ324hjkS to 848662 on our backend and serve the relevant content. At some point, we start getting 404 errors from clients requesting a certain URL of the form
https://www.airbnb.com/rooms/kljjj324hjks
This can happen if certain clients, email services, or url shorteners "sanitize" the url. Unfortunately, this change breaks decoding and the resource cannot be found.
To assess how big of a deal this is, we may want to recover the IDs of the targets that were 404ing.
Given a method decode(testEncStr) which will return the decoded int id if testEncStr is decodeable or will throw an exception (or return null) if not, implement a new method decodeFind(String badEncStr) which takes a string and returns the decoded int id.


第二题boggle game是给你一个board还有字典,然后要求找出board上出现最多的字典单词,并且你找出来的单词集合里的每个字母都不能重叠在同一个位置。所以你要是找到了一个单词是airbnb,airbnb所在的board位置就不在再用了。return单词集合。然后不一定是一个path可以很多个不重叠的path。楼主要是知道怎么做求教。。 我当年被问过这题,妥妥的跪了,至今还不知道怎么做 > <
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-1 12:11:39 | 显示全部楼层
第一题的自己刚才写了下,应该可以,供参考。第二题坐等大神!
  1. package bnb;
  2. import java.util.*;

  3. public class decodeURL {
  4.         public Integer decode(String testEncStr) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  5.             String truth = "kljJJ324hijkS_";
  6.              
  7.             if (testEncStr.equals(truth)) {
  8.               return 848662;
  9.             } else {
  10.               return null;
  11.             }
  12.          }
  13. . 1point3acres.com/bbs
  14.         public Integer decodeFind(String badEncStr){
  15.                 List<String> options = new ArrayList<String>();
  16.                 helper(badEncStr, options, 0);
  17.                
  18.                 for(String s : options){
  19.                         System.out.println(s+" ");
  20.                         if(decode(s) != null){. more info on 1point3acres.com
  21.                                 return decode(s);
  22.                         }
  23.                 }
  24.                 System.out.println("res length is" + options.size());
  25.                 return null;. visit 1point3acres.com for more.
  26.         }
  27.        
  28.         private void helper(String s, List<String> res, int start){
  29.                 if(start == s.length()){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  30.                         res.add(s);
  31.                         return ;
  32.                 }
  33.                 char[] arr = s.toCharArray();
  34.                
  35.                 if(Character.isLetter(arr[start])){
  36.                         char l = Character.toLowerCase(arr[start]);
  37.                         char u = Character.toUpperCase(arr[start]);
  38.                        
  39.                         String s1 = s.substring(0, start) + l + s.substring(start+1);
  40.                         helper(s1, res, start+1);
  41.                                        
  42.                         String s2 = s.substring(0,start) + u + s.substring(start+1);
  43.                         helper(s2, res, start+1);
  44.                 }
  45.                 else{-google 1point3acres
  46.                         helper(s, res, start+1);
  47.                 }.1point3acres缃
  48.         }
  49.         .鐣欏璁哄潧-涓浜-涓夊垎鍦
  50.         public static void main(String[] args) {
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  51.                 decodeURL du = new decodeURL();
    . 1point 3acres 璁哄潧
  52. //                System.out.println("result is: " + du.decodeFind("kljJJ324hjkS_"));
  53.                 System.out.println("result is: " + du.decodeFind("123abc"));. more info on 1point3acres.com

  54.         }
  55. . 鍥磋鎴戜滑@1point 3 acres
  56. }
复制代码
回复 支持 反对

使用道具 举报

Sayako 发表于 2016-11-1 12:55:39 | 显示全部楼层
boggle game是不是给个matri. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2016-11-1 12:56):
手机打的怎么断了,给个matrix给个字典,让找最长的字典中word连起来的path,就像LC word break II的2D版?
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-1 13:05:09 | 显示全部楼层
Sayako 发表于 2016-10-31 20:55
boggle game是不是给个matri. From 1point 3acres bbs

补充内容 (2016-11-1 12:56):

目前我看到的有两种版本,一种是你所说的;另外一种呢 - 地里的人的描述:boggle game是给你一个board还有字典,然后要求找出board上出现最多的字典单词,并且你找出来的单词集合里的每个字母都不能重叠在同一个位置。所以你要是找到了一个单词是airbnb,airbnb所在的board位置就不在再用了。return单词集合。然后不一定是一个path可以很多个不重叠的path。
回复 支持 反对

使用道具 举报

Sayako 发表于 2016-11-1 22:41:53 | 显示全部楼层
gy21 发表于 2016-11-1 13:05
目前我看到的有两种版本,一种是你所说的;另外一种呢 - 地里的人的描述:boggle game是给你一个board还 ...

你说的和我说那个是一个啊。

补充内容 (2016-11-1 22:42): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
要找最长的如果不是只有一个就是几个最长的长度相等,比较一下长度存起来就行了
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-2 00:00:15 | 显示全部楼层
Sayako 发表于 2016-11-1 06:41
你说的和我说那个是一个啊。

补充内容 (2016-11-1 22:42):

可是看你没有提到用过的字母不能再次使用以为说的是两道题目。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 05:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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