推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

Airbnb 面经求问

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

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

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

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

x
有几道题想问下:
.鏈枃鍘熷垱鑷1point3acres璁哄潧
1. decode string  那道题,到底是什么意思呢?我总感觉这题有点简单的过分了吧?如果我把所有目标串里的大写改成小写,然后看这两个串一不一样不就可以了吗?

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

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

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

使用道具 举报

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

使用道具 举报

susand33 发表于 2016-10-31 02:15:35 | 显示全部楼层
第一题原题应该是这个,简单点就点简单呗。。
URL Shortener
/*
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.-google 1point3acres
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) {
  5.             String truth = "kljJJ324hijkS_";
  6.              . 鍥磋鎴戜滑@1point 3 acres
  7.             if (testEncStr.equals(truth)) {
  8.               return 848662;
  9.             } else {
  10.               return null;-google 1point3acres
  11.             }
  12.          }
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  13.         public Integer decodeFind(String badEncStr){
  14.                 List<String> options = new ArrayList<String>();
  15.                 helper(badEncStr, options, 0);
  16.                
  17.                 for(String s : options){. 1point3acres.com/bbs
  18.                         System.out.println(s+" ");
  19.                         if(decode(s) != null){
  20.                                 return decode(s);
  21.                         }
  22.                 }
  23.                 System.out.println("res length is" + options.size());
  24.                 return null;
  25.         }
  26.        
  27.         private void helper(String s, List<String> res, int start){
  28.                 if(start == s.length()){
  29.                         res.add(s);
  30.                         return ;
  31.                 }
  32.                 char[] arr = s.toCharArray();
  33.                
  34.                 if(Character.isLetter(arr[start])){. 1point3acres.com/bbs
  35.                         char l = Character.toLowerCase(arr[start]);
  36.                         char u = Character.toUpperCase(arr[start]);
  37.                         . 1point 3acres 璁哄潧
  38.                         String s1 = s.substring(0, start) + l + s.substring(start+1);. 1point 3acres 璁哄潧
  39.                         helper(s1, res, start+1);
  40.                                        
  41.                         String s2 = s.substring(0,start) + u + s.substring(start+1);. Waral 鍗氬鏈夋洿澶氭枃绔,
  42.                         helper(s2, res, start+1);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  43.                 }
  44.                 else{
  45.                         helper(s, res, start+1);
  46.                 }
  47.         }
  48.        
  49.         public static void main(String[] args) {
  50.                 decodeURL du = new decodeURL();
  51. //                System.out.println("result is: " + du.decodeFind("kljJJ324hjkS_"));
  52.                 System.out.println("result is: " + du.decodeFind("123abc"));
  53. . Waral 鍗氬鏈夋洿澶氭枃绔,
  54.         }

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

使用道具 举报

Sayako 发表于 2016-11-1 12:55:39 | 显示全部楼层
boggle game是不是给个matri

补充内容 (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. 1point3acres.com/bbs

补充内容 (2016-11-1 12:56):
. 鍥磋鎴戜滑@1point 3 acres
目前我看到的有两种版本,一种是你所说的;另外一种呢 - 地里的人的描述: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还 ...
. 1point 3acres 璁哄潧
你说的和我说那个是一个啊。

补充内容 (2016-11-1 22:42):
要找最长的如果不是只有一个就是几个最长的长度相等,比较一下长度存起来就行了
回复 支持 反对

使用道具 举报

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

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴补充内容 (2016-11-1 22:42):

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

使用道具 举报

fxjistc 发表于 2017-3-6 14:36:20 | 显示全部楼层
gy21 发表于 2016-11-1 12:11
第一题的自己刚才写了下,应该可以,供参考。第二题坐等大神!

求问这个做法时间复杂度是多少?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-27 06:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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