一亩三分地论坛

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

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

G家onsite面经9.1

[复制链接] |试试Instant~ |关注本帖
flamen 发表于 2015-9-2 06:37:49 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

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

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

第二轮:find the most popular number in an array of interger. The 'popular number' is defined as the number occurs more than n/4, where n is the length of array. The array is already sorted.
我用binary search做的。三哥,表情比较严肃。

第三轮:shuffling machine. 对于某个shuffling machine,里面有个特殊的order。举例,shuffling order是4,3,2,1, 那么如果input是A,B,C,D, 那么output就是D,C,B,A. 求对于任意shuffling order, 求最少要多少步可以shuffle回原来的input。
最naive就是一直做shuffle,直到当前sequence是input,用hashset或者hashmap之类。然后他让我优化。我先考虑permutation,或者把shuffling order分成若干个subsequence,每个subsequence是一个正确位置的permutation,最后求最小公约数。后来又考虑每个index对应的value需要走的step,然后求最小公约数。总之这题比较莫名其妙,讨论到最后也没有给出特别好的solution。。。心塞
三哥主面,白哥shadow

第四轮:八皇后
好不容易是个国人大哥,而且还和我说中文,结果我居然大脑短路了,我也不知道为啥写了半天吭哧吭哧的,虽然写出来了但是表现真的挺差的,感觉国人大哥已经笑得无语了
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
总结就是脑子不要短路,题目都不难,人也很nice,不要像卤煮一样大脑短路即可。。。另外,多看面经。。。

祝大家offer多多!!!

本帖被以下淘专辑推荐:

huanghe0828 发表于 2015-9-4 02:55:11 | 显示全部楼层
第三题可以把array分成不同的loop,比如对{2,3,1,5,6,7,4}来说,可以分成{2,3,1}和{5,6,7,4}这两个loop
每个loop的步数是相同的。所以每个loop只要访问一次求出步数就可以了,loop当中其他的element都是相同的步数,设置为visited,下次不再访问。
for (int i = 0; i < input.length; i++) {


补充内容 (2015-9-4 02:59):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
int maxLoop = 0;
boolean[] visited = new boolean[input.length];
for (int i = 0; i < input.length; i++) {
  if (visited) continue;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  visited = true;. 1point 3acres 璁哄潧
  int loopLength = 0;. 鍥磋鎴戜滑@1point 3 acres
  int next = input...
回复 支持 2 反对 1

使用道具 举报

zq13667243992 发表于 2015-9-2 06:55:06 | 显示全部楼层
请问一下,A,B,C,D shuffle 到D,C,B,A是怎么shuffle的? 不是太明白意思,谢谢!. 1point 3acres 璁哄潧

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

使用道具 举报

purplesky85 发表于 2015-9-2 11:25:43 | 显示全部楼层
第二题是不是这样做的, 因为数组是排序的,所以如果有答案一定是在nums[1/4n], nums[2/4n], nums[3/4n], 中的一个, 所以用Binary Search的方法找到这三个的开始和结尾,获得长度,取最大的那个?
回复 支持 1 反对 0

使用道具 举报

hello2pig 发表于 2015-9-2 06:48:02 | 显示全部楼层
楼主厉害! 第二题二分是怎么分的 能具体说说吗?
回复 支持 反对

使用道具 举报

laurie洁 发表于 2015-9-2 11:07:54 | 显示全部楼层
同问第二题怎么做呀?
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-9-2 13:20:26 | 显示全部楼层
purplesky85 发表于 2015-9-2 11:25
第二题是不是这样做的, 因为数组是排序的,所以如果有答案一定是在nums[1/4n], nums[2/4n], nums[3/4n],  ...

我觉得你的思路没错!
回复 支持 反对

使用道具 举报

laurie洁 发表于 2015-9-2 13:29:59 | 显示全部楼层
我觉得楼主第三题的思路是对的啊~
可以把所有Index分组~求出每个组shuffle回原来index的步数,然后求最小公约数~
回复 支持 反对

使用道具 举报

laurie洁 发表于 2015-9-2 13:57:30 | 显示全部楼层
尝试一下~轻拍~
  1. public class Solution {
  2.         public static int countShuffle(int[] shuffle) {-google 1point3acres
  3.                 if (shuffle == null || shuffle.length <= 1) {
  4.                         return 0;
  5.                 }
  6.                 List<Integer> groupStep = new ArrayList<>();-google 1point3acres
  7.                 HashSet<Integer> visited = new HashSet<>();
  8.                 for (int i = 0; i < shuffle.length; i++) {
  9.                         if (!visited.contains(i)) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.                                 visited.add(i);
  11.                                 int count = 1;
  12.                                 int curr = i;-google 1point3acres
  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}));. visit 1point3acres.com for more.
  54.         }
  55. }
复制代码
回复 支持 反对

使用道具 举报

snklee 发表于 2015-9-2 18:21:49 | 显示全部楼层
Q2:
The logic is advance search interval end point by n/4 each time.
If head and end of the interval equals, then return.. more info on 1point3acres.com
If not, find the beginning of same number sequence, make that new head, and loop.
e.g when input is [0,1,2,2,2,2,3,4,6,6,7,7], head is pointing to 0, end is pointing to 3. 0 and 1 can be discarded, but the 2s between[2,3]inclusive needs to be considered. Thus we find the new head, which is 2, and start searching from there in the next loop.
  1. def mostPopularNum(nums):
  2.     head = 0
  3.     end = len(nums)/4
  4.     while end < len(nums):
  5.         # head to end, there are more than n/4 same nums
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.         if nums[head]==nums[end]:
  7.             return nums[head]
  8.         else:. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.         # if not, get the starting point of nums[end]s sequence
  10.             head = getHeadOfEnd(nums, head, end)
  11.             end = head + len(nums)/4
  12. def getHeadOfEnd(nums, head, end):
  13.     target = nums[end]. from: 1point3acres.com/bbs
  14.     while True:
  15.         middle = (head + end) / 2
  16.         if nums[middle]!=target and nums[middle+1]==target:
  17.             return middle+1
  18.         elif nums[middle]==target:. more info on 1point3acres.com
  19.             end = middle
  20.         else:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.             head = middle
复制代码
回复 支持 反对

使用道具 举报

caizhuowei 发表于 2015-9-2 22:36:56 | 显示全部楼层
The shuffling machine problem can be solved by binary search. The following solution assume that the number of steps *s* required in order to convert [4 3 2 1] back to [1 2 3 4] is less than INT_MAX.-google 1point3acres
Starting from *s* = (0 + INT_MAX) / 2, if *pow([1 2 3 4] -> [4 3 2 1], s)* is equal to [1 2 3 4], keep searching in the left half [0, *s*]. Otherwise, search in the right half.
The power of the permutation can be implemented in O(N * logs) time using divide and conquer (N is the length of the array), in pretty much the same way as implementing the power of a number.
So the overall time complexity is O(N * log(INT_MAX) * log(INT_MAX)).

PS: No Chinese input method on the lab's machines...
回复 支持 反对

使用道具 举报

mhbkb 发表于 2015-9-3 15:35:38 | 显示全部楼层
第二轮,我也面到了这一题。也是个特别严肃的三哥,不知道是不是同一个人。带个眼镜。
回复 支持 反对

使用道具 举报

 楼主| flamen 发表于 2015-9-4 00:53:18 | 显示全部楼层
mhbkb 发表于 2015-9-2 23:35
第二轮,我也面到了这一题。也是个特别严肃的三哥,不知道是不是同一个人。带个眼镜。

哈哈 很可能是的!也是戴个眼镜!
回复 支持 反对

使用道具 举报

huanghe0828 发表于 2015-9-4 02:59:46 | 显示全部楼层

第三题code:
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
int maxLoop = 0;
boolean[] visited = new boolean[input.length];
for (int i = 0; i < input.length; i++) {
  if (visited[i]) continue;
  visited[i] = true;
  int loopLength = 0;. 1point 3acres 璁哄潧
  int next = input[i];
  while (next != input[i]) {
    visited[next] = true;
    next = input[next];
    loopLength++;
  }. more info on 1point3acres.com
  maxLoop = Math.max(maxLoop, loopLength);. 1point3acres.com/bbs
}
return maxLoop;
回复 支持 反对

使用道具 举报

zitfresh 发表于 2015-9-4 13:39:09 | 显示全部楼层
caizhuowei 发表于 2015-9-2 22:36
The shuffling machine problem can be solved by binary search. The following solution assume that the ...

What is *pow([1 2 3 4] -> [4 3 2 1], s)* ??
回复 支持 反对

使用道具 举报

tiantiana 发表于 2015-9-4 14:15:42 | 显示全部楼层
bless lz。
所以,lz没有system design吗?是不是硕士应届都没有,博士就有呢。
回复 支持 反对

使用道具 举报

csushin1992 发表于 2015-9-4 14:23:29 | 显示全部楼层
shuffling 硬是看不懂题目。。
回复 支持 反对

使用道具 举报

caizhuowei 发表于 2015-9-4 23:16:23 | 显示全部楼层
zitfresh 发表于 2015-9-4 13:39
What is *pow([1 2 3 4] -> [4 3 2 1], s)* ??

That is the power of a permutation, which means to apply the permutation s times.
For example,
([1 2 3 4] -> [4 3 2 1]) ^ 1 = [1 2 3 4] -> [4 3 2 1]
([1 2 3 4] -> [4 3 2 1]) ^ 2 = [1 2 3 4] -> [1 2 3 4]
. Waral 鍗氬鏈夋洿澶氭枃绔,
Another example is
([1 2 3 4] -> [2 3 4 1]) ^ 2 = [1 2 3 4] -> [3 4 1 2]-google 1point3acres
([1 2 3 4] -> [2 3 4 1]) ^ 3 = [1 2 3 4] -> [4 1 2 3]
([1 2 3 4] -> [2 3 4 1]) ^ 4 = [1 2 3 4] -> [1 2 3 4]

Not explained very well. Sorry...
回复 支持 反对

使用道具 举报

zzwzhong698800 发表于 2015-9-8 20:31:34 | 显示全部楼层
第二题,我根据上面那个python的用C++写了一下,不过有一个小地方修改了,现在感觉很多case没有问题,大家可以看看,大家发现错误,可以回复我一下
class Solution
{
public:. Waral 鍗氬鏈夋洿澶氭枃绔,
        vector<int> getPopularDigits(vector<int> arr)
        {
                vector<int> res;
                if(arr.size() < 4)
                        return arr;
               
                int requreC = arr.size()/4;
                int left = 0;
                int right = requreC;
                while(right < arr.size())
                {
                        if(arr[left] == arr[right])
                        {. From 1point 3acres bbs
                                //如果没哟下面的判断,case 1,1,1,1,2,结果就会为1,1了,有两个1
                                if(res.empty() || arr[left] != res[res.size() - 1])
                                        res.push_back(arr[left]);
. 1point3acres.com/bbs                                left = right + 1;. from: 1point3acres.com/bbs
                                right = left + requreC;. 1point 3acres 璁哄潧
                        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        else
                        {
                                left = getNewLeftIndex(arr, left, right);
                                right = left + requreC;
                        }
                }
                return res;
        }
       
        //这个只是我自己用来验证的,可忽略这个函数
        int getNewLeftIndex(vector<int> &arr, int left, int right)
        {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                int target = arr[right];
                while(1). from: 1point3acres.com/bbs
                {
                        int mid = (left + right)/2;
                        if(arr[mid] != target && arr[mid+1] == target). from: 1point3acres.com/bbs
                                return mid+1;
                        else if(arr[mid] == target)
                                right = mid;
                        else
                                left = mid;
                }
        }. 鍥磋鎴戜滑@1point 3 acres
        map<int, int> getCount(vector<int> &arr)
        {
                map<int, int> mp;
                for(int i = 0; i < arr.size(); i++)
                {
                        if(mp.count(arr) == 0)
                                mp[arr] = 1;
                        else
                                mp[arr] ++;
                }
                return mp;
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
};
//. 1point3acres.com/bbs
//int main()
//{. 鍥磋鎴戜滑@1point 3 acres
//        int arr[] = {1,1,1,1,2,2,2,2,3,3,3};.1point3acres缃
//        int n = sizeof(arr)/sizeof(int);. visit 1point3acres.com for more.
//        vector<int> v(arr,arr+n);
//        Solution ss;
//        cout<<n/4<<endl;
//        vector<int> res = ss.getPopularDigits(v);
//        map<int, int> mp = ss.getCount(v);
//        int i =0;
//}

补充内容 (2015-9-8 20:32):
上面那个注释注错了地方……,下面那个count函数是没有用的,上面那个getNewLeftIndex是有用的
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-9 22:43:20 | 显示全部楼层
laurie洁 发表于 2015-9-2 13:29 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我觉得楼主第三题的思路是对的啊~. Waral 鍗氬鏈夋洿澶氭枃绔,
可以把所有Index分组~求出每个组shuffle回原来index的步数,然后求最小 ...

是求最小公倍数吧?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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