G家onsite面经9.1

刚面完G到家，回馈板上大家的帮助~~

第一轮：Longest Consecutive Sequence in a matrix，就是板上出现了好几次的滑雪问题，很高频啊，大家可以好好看下。
我先用dfs做的，后来优化加了dp。面试官是白人小哥，人挺不错。

第二轮：find the most popular number in an array of interger. The 'popula

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

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

且还和我说中文，结果我居然大脑短路了，我也不知道为啥写了半天吭哧吭哧的，虽然写出来了但是表现真的挺差的，感觉国人大哥已经笑得无语了

总结就是脑子不要短路，题目都不难，人也很nice，不要像卤煮一样大脑短路即可。。。另外，多看面经。。。

祝大家offer多多！！！

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

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

第二题是不是这样做的， 因为数组是排序的，所以如果有答案一定是在nums[1/4n], nums[2/4n], nums[3/4n]， 中的一个， 所以用Binary Search的方法找到这三个的开始和结尾，获得长度，取最大的那个？

请问一下，A,B,C,D shuffle 到D,C,B,A是怎么shuffle的？ 不是太明白意思，谢谢！

补充内容 (2015-9-2 06:56):
第一题貌似是 http://www.lintcode.com/en/problem/longest-increasing-continuous-subsequence-ii/

楼主厉害！ 第二题二分是怎么分的 能具体说说吗？

同问第二题怎么做呀？

purplesky85 发表于 2015-9-2 11:25
第二题是不是这样做的， 因为数组是排序的，所以如果有答案一定是在nums[1/4n], nums[2/4n], nums[3/4n]，  ...

我觉得你的思路没错！

我觉得楼主第三题的思路是对的啊~
可以把所有Index分组~求出每个组shuffle回原来index的步数，然后求最小公约数~

尝试一下~轻拍~

1. public class Solution {
   
2.         public static int countShuffle(int[] shuffle) {
   
3.                 if (shuffle == null || shuffle.length <= 1) {
   
4.                         return 0;
   
5.                 }
   
6.                 List<Integer> groupStep = new ArrayList<>();
   
7.                 HashSet<Integer> visited = new HashSet<>();
   
8.                 for (int i = 0; i < shuffle.length; i++) {
   
9.                         if (!visited.contains(i)) {
   
10.                                 visited.add(i);
    
11.                                 int count = 1;
    
12.                                 int curr = i;
    
13.                                 int next = shuffle[i];
    
14.                                 while (next != i) {
    
15.                                         count++;
    
16.                                         visited.add(next);
    
17.                                         curr = next;
    
18.                                         next = shuffle[curr];
    
19.                                 }
    
20.                                 groupStep.add(count);
    
21.                         }
    
22.                 }
    
23.                 return findSCM(groupStep);
    
24.         }
    
25.        
    
26.         public static int findSCM(List<Integer> groupStep) {
    
27.                 if (groupStep == null || groupStep.size() == 0) {
    
28.                         return 0;
    
29.                 }
    
30.                 while (groupStep.size() > 1) {
    
31.                         int first = groupStep.remove(0);
    
32.                         int second = groupStep.remove(0);
    
33.                         groupStep.add(lcm(first, second));
    
34.                 }
    
35.                 return groupStep.get(0);
    
36.         }
    
37.        
    
38.         public static int lcm(int a, int b) {
    
39.                 return (a * b) / gcd(a, b);
    
40.         }
    
41.        
    
42.         public static int gcd(int a, int b) {
    
43.                 if (a == b) {
    
44.                         return a;
    
45.                 }
    
46.                 if (a > b) {
    
47.                         return gcd(a - b, b);
    
48.                 }
    
49.                 return gcd(a, b - a);
    
50.         }
    
51.        
    
52.         public static void main(String[] args) {
    
53.                 System.out.println(countShuffle(new int[]{4, 3, 0, 1, 2}));
    
54.         }
    
55. }

复制代码

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

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

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

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