Airbnb 面经求问

有几道题想问下：

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

2.boggle game  

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

e/smiley/QQ/em34.gif" smilieid="112" border="0" alt="" />

第一题的自己刚才写了下，应该可以，供参考。第二题坐等大神！

1. package bnb;
   
2. import java.util.*;
   
3. 
   
4. public class decodeURL {
   
5.         public Integer decode(String testEncStr) {
   
6.             String truth = "kljJJ324hijkS_";
   
7.              
   
8.             if (testEncStr.equals(truth)) {
   
9.               return 848662;
   
10.             } else {
    
11.               return null;
    
12.             }
    
13.          }
    
14. 
    
15.         public Integer decodeFind(String badEncStr){
    
16.                 List<String> options = new ArrayList<String>();
    
17.                 helper(badEncStr, options, 0);
    
18.                
    
19.                 for(String s : options){
    
20.                         System.out.println(s+" ");
    
21.                         if(decode(s) != null){
    
22.                                 return decode(s);
    
23.                         }
    
24.                 }
    
25.                 System.out.println("res length is" + options.size());
    
26.                 return null;
    
27.         }
    
28.        
    
29.         private void helper(String s, List<String> res, int start){
    
30.                 if(start == s.length()){
    
31.                         res.add(s);
    
32.                         return ;
    
33.                 }
    
34.                 char[] arr = s.toCharArray();
    
35.                
    
36.                 if(Character.isLetter(arr[start])){
    
37.                         char l = Character.toLowerCase(arr[start]);
    
38.                         char u = Character.toUpperCase(arr[start]);
    
39.                        
    
40.                         String s1 = s.substring(0, start) + l + s.substring(start+1);
    
41.                         helper(s1, res, start+1);
    
42.                                        
    
43.                         String s2 = s.substring(0,start) + u + s.substring(start+1);
    
44.                         helper(s2, res, start+1);
    
45.                 }
    
46.                 else{
    
47.                         helper(s, res, start+1);
    
48.                 }
    
49.         }
    
50.        
    
51.         public static void main(String[] args) {
    
52.                 decodeURL du = new decodeURL();
    
53. //                System.out.println("result is: " + du.decodeFind("kljJJ324hjkS_"));
    
54.                 System.out.println("result is: " + du.decodeFind("123abc"));
    
55. 
    
56.         }
    
57. 
    
58. }
    

复制代码

可以贴一下原版题目么 这个 不知道在说什么啊？

第一题原题应该是这个，简单点就点简单呗。。
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.
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。楼主要是知道怎么做求教。。 我当年被问过这题，妥妥的跪了，至今还不知道怎么做 > <

boggle game是不是给个matri

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

Sayako 发表于 2016-10-31 20:55
boggle game是不是给个matri

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

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

gy21 发表于 2016-11-1 13:05
目前我看到的有两种版本，一种是你所说的；另外一种呢 － 地里的人的描述：boggle game是给你一个board还 ...

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

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

Sayako 发表于 2016-11-1 06:41
你说的和我说那个是一个啊。

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

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

gy21 发表于 2016-11-1 12:11
第一题的自己刚才写了下，应该可以，供参考。第二题坐等大神！

求问这个做法时间复杂度是多少？