Google 据信 ＋面经

上周g电话面试，这周就被拒了，直接说


Our hiring team has decided not to move forward with your candidac

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

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

quence; for example: input:
1234      
8765,  output should be 12345678
这个题我用dfs＋backtracking做的



补充内容 (2014-11-14 00:40):
1, 就是按照给定数组的顺序， A[]=5,6,10,11,15,1,2,3  output=3, 也就是 1，2，3；

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

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

第一题， 用个map记录之前访问过的以每个元素为最大值的长度，扫一遍就可以了。我这里用了个list of list，用来记录不止一个的最长的subsequence。

1. 
   
2. public static List<List<Integer>> longestConsecutiveSubsequence (int[] nums) {
   
3.                 Map<Integer, Integer> visited = new HashMap<Integer, Integer>();
   
4.                 int maxLength = 0;
   
5.                 Map<Integer, Integer> result = new HashMap<Integer, Integer>();
   
6.                 for (int i = 0; i < nums.length; i++) {
   
7.                         int currLength = 0;
   
8.                         if (!visited.containsKey(nums[i] - 1)) {
   
9.                                 currLength = 1;
   
10.                         }
    
11.                         else {
    
12.                                 currLength = visited.get(nums[i] - 1) + 1;                               
    
13.                         }
    
14.                         visited.put(nums[i], currLength);
    
15.                         if (currLength > maxLength) {
    
16.                                 maxLength = currLength;
    
17.                                 result.put(nums[i], currLength);
    
18.                         }
    
19.                 }
    
20.                
    
21.                 maxLength = 0;
    
22.                 for (int length : result.values()) {
    
23.                         maxLength = Math.max(maxLength, length);
    
24.                 }
    
25.                
    
26.                 List<List<Integer>> subsequences = new ArrayList<List<Integer>>();
    
27.                 for (int d : result.keySet()) {
    
28.                         if (result.get(d) == maxLength) {
    
29.                                 List<Integer> list = new ArrayList<Integer>();
    
30.                                 for (int i = d - maxLength + 1; i <= d; i++) {
    
31.                                         list.add(i);
    
32.                                 }
    
33.                                 subsequences.add(list);
    
34.                         }
    
35.                 }
    
36.                 return subsequences;
    
37.         }
    
38.        
    
39.         public static void main(String[] args) {
    
40.                 int[] nums = {1, 2, 5, 6, 8, 7, 3, 4};
    
41.                 List<List<Integer>> sub = longestConsecutiveSubsequence(nums);
    
42.                 for (List<Integer> list : sub) {
    
43.                         for (int d : list) {
    
44.                                 System.out.print(d + " ");
    
45.                         }
    
46.                         System.out.println();
    
47.                 }
    
48.         }

复制代码

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

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

真奇怪，楼主感觉为什么会被拒？

pat pat楼主，第二题思路可以再详细一些么？如果是每个点都dfs的话消耗有点大啊，求指导。

没事了，我太傻比。。。

应该是据了，不过半年以后还可以投。Lz move on吧，半年再去投一次。

还有， 请教lz, 第一题的"要求按顺序找"是啥意思啊？

lz这个是多长时间的面试啊。。。我收到了一个goole的说是15~20分钟的电面。。不知道他要问啥

第二题可以dp下

dp + dfs

楼主第一题的意思是consecutive sequence必须是increasing的顺序的？
{100,1,2,6,3,4,5} 那么最长是5？

qiaokan 发表于 2014-11-13 21:55
第二题可以dp下

要是两个方向还好，4个方向的dp？能写个递推公式吗？