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


一亩三分地论坛

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

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

G家onsite面经9.1

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

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

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

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

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。.鏈枃鍘熷垱鑷1point3acres璁哄潧
最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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第三题可以把array分成不同的loop,比如对{2,3,1,5,6,7,4}来说,可以分成{2,3,1}和{5,6,7,4}这两个loop
每个loop的步数是相同的。所以每个loop只要访问一次求出步数就可以了,loop当中其他的element都是相同的步数,设置为visited,下次不再访问。. Waral 鍗氬鏈夋洿澶氭枃绔,
for (int i = 0; i < input.length; i++) {
.1point3acres缃

补充内容 (2015-9-4 02:59):
int maxLoop = 0;
boolean[] visited = new boolean[input.length];. more info on 1point3acres.com
for (int i = 0; i < input.length; i++) {
  if (visited) continue;
  visited = true;
  int loopLength = 0;. From 1point 3acres bbs
  int next = input...
回复 支持 2 反对 1

使用道具 举报

zq13667243992 发表于 2015-9-2 06:55:06 | 显示全部楼层
关注一亩三分地微博:
Warald
请问一下,A,B,C,D shuffle 到D,C,B,A是怎么shuffle的? 不是太明白意思,谢谢!. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. more info on 1point3acres.com
补充内容 (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) {
  3.                 if (shuffle == null || shuffle.length <= 1) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4.                         return 0;
  5.                 }
  6.                 List<Integer> groupStep = new ArrayList<>();
  7.                 HashSet<Integer> visited = new HashSet<>();. From 1point 3acres bbs
  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;. From 1point 3acres bbs
  18.                                         next = shuffle[curr];
  19.                                 }
  20.                                 groupStep.add(count);
  21.                         }
  22.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.                 return findSCM(groupStep); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  24.         }
  25.        
  26.         public static int findSCM(List<Integer> groupStep) {
  27.                 if (groupStep == null || groupStep.size() == 0) {-google 1point3acres
  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.         }-google 1point3acres
  37.        
  38.         public static int lcm(int a, int b) {. visit 1point3acres.com for more.
  39.                 return (a * b) / gcd(a, b);
  40.         }
  41.        
  42.         public static int gcd(int a, int b) {
  43.                 if (a == b) {. From 1point 3acres bbs
  44.                         return a;
  45.                 }
  46.                 if (a > b) {
  47.                         return gcd(a - b, b);
  48.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  49.                 return gcd(a, b - a);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  50.         }
  51.        
  52.         public static void main(String[] args) {. From 1point 3acres bbs
  53.                 System.out.println(countShuffle(new int[]{4, 3, 0, 1, 2}));
  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.
. 1point3acres.com/bbsIf 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. From 1point 3acres bbs
  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]. visit 1point3acres.com for more.
  8.         else:
  9.         # if not, get the starting point of nums[end]s sequence
  10.             head = getHeadOfEnd(nums, head, end)
  11.             end = head + len(nums)/4
    -google 1point3acres
  12. def getHeadOfEnd(nums, head, end):
  13.     target = nums[end]. 鍥磋鎴戜滑@1point 3 acres
  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:
  19.             end = middle
  20.         else:. visit 1point3acres.com for more.
  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.
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;. Waral 鍗氬鏈夋洿澶氭枃绔,
  visited[i] = true;
  int loopLength = 0;.1point3acres缃
  int next = input[i];-google 1point3acres
  while (next != input[i]) {
    visited[next] = true;
    next = input[next];
    loopLength++; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  }
  maxLoop = Math.max(maxLoop, loopLength);
}
return maxLoop;
回复 支持 反对

使用道具 举报

zitfresh 发表于 2015-9-4 13:39:09 | 显示全部楼层
caizhuowei 发表于 2015-9-2 22:36. more info on 1point3acres.com
The shuffling machine problem can be solved by binary search. The following solution assume that the ...
. From 1point 3acres bbs
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.. Waral 鍗氬鏈夋洿澶氭枃绔,
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]

Another example is
([1 2 3 4] -> [2 3 4 1]) ^ 2 = [1 2 3 4] -> [3 4 1 2].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.鏈枃鍘熷垱鑷1point3acres璁哄潧
{-google 1point3acres
public:
        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])
                        {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                //如果没哟下面的判断,case 1,1,1,1,2,结果就会为1,1了,有两个1
                                if(res.empty() || arr[left] != res[res.size() - 1])
                                        res.push_back(arr[left]);
                                left = right + 1;
                                right = left + requreC;
                        }
                        else
                        {
                                left = getNewLeftIndex(arr, left, right);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                right = left + requreC;
                        }
                }
                return res;
        }
       
        //这个只是我自己用来验证的,可忽略这个函数. visit 1point3acres.com for more.
        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)
                                return mid+1;
                        else if(arr[mid] == target)-google 1point3acres
                                right = mid;
                        else
                                left = mid;. from: 1point3acres.com/bbs
                }
        }
        map<int, int> getCount(vector<int> &arr)
        {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                map<int, int> mp;
                for(int i = 0; i < arr.size(); i++). more info on 1point3acres.com
                {
                        if(mp.count(arr) == 0).1point3acres缃
                                mp[arr] = 1;
                        else
                                mp[arr] ++;
                }
                return mp;
        }
};. more info on 1point3acres.com
// 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
//int main()
//{. 1point3acres.com/bbs
//        int arr[] = {1,1,1,1,2,2,2,2,3,3,3};
//        int n = sizeof(arr)/sizeof(int);
//        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
我觉得楼主第三题的思路是对的啊~
可以把所有Index分组~求出每个组shuffle回原来index的步数,然后求最小 ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-28 02:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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