近期论坛无法登录的解决方案


一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2924|回复: 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,就是板上出现了好几次的滑雪问题,很高频啊,大家可以好好看下。. from: 1point3acres.com/bbs
我先用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
. 1point 3acres 璁哄潧
第四轮:八皇后
好不容易是个国人大哥,而且还和我说中文,结果我居然大脑短路了,我也不知道为啥写了半天吭哧吭哧的,虽然写出来了但是表现真的挺差的,感觉国人大哥已经笑得无语了

总结就是脑子不要短路,题目都不难,人也很nice,不要像卤煮一样大脑短路即可。。。另外,多看面经。。。. visit 1point3acres.com for more.

祝大家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,下次不再访问。
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 3 acres
  int loopLength = 0;.1point3acres缃
  int next = input...
回复 支持 2 反对 1

使用道具 举报

zq13667243992 发表于 2015-9-2 06:55:06 | 显示全部楼层
关注一亩三分地微博:
Warald
请问一下,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/
回复 支持 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 | 显示全部楼层
我觉得楼主第三题的思路是对的啊~. from: 1point3acres.com/bbs
可以把所有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.                 }. 鍥磋鎴戜滑@1point 3 acres
  6.                 List<Integer> groupStep = new ArrayList<>();. 鍥磋鎴戜滑@1point 3 acres
  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;. From 1point 3acres bbs
  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.         -google 1point3acres
  42.         public static int gcd(int a, int b) {
    . from: 1point3acres.com/bbs
  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.         .1point3acres缃
  52.         public static void main(String[] args) {. from: 1point3acres.com/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.
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:. 1point3acres.com/bbs
  9.         # if not, get the starting point of nums[end]s sequence
  10.             head = getHeadOfEnd(nums, head, end). 1point3acres.com/bbs
  11.             end = head + len(nums)/4
  12. def getHeadOfEnd(nums, head, end):
  13.     target = nums[end]
  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:
  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;
  visited[i] = true;
  int loopLength = 0;
  int next = input[i];
  while (next != input[i]) {
    visited[next] = true;
    next = input[next];. more info on 1point3acres.com
    loopLength++;
  }
  maxLoop = Math.max(maxLoop, loopLength);
}
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] .1point3acres缃

Another example is
([1 2 3 4] -> [2 3 4 1]) ^ 2 = [1 2 3 4] -> [3 4 1 2]
([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:
        vector<int> getPopularDigits(vector<int> arr)
        {
                vector<int> res;
                if(arr.size() < 4)
                        return arr;
                . 1point3acres.com/bbs
                int requreC = arr.size()/4;
                int left = 0;
                int right = requreC;
                while(right < arr.size())
                {
                        if(arr[left] == arr[right]). from: 1point3acres.com/bbs
                        {. more info on 1point3acres.com
                                //如果没哟下面的判断,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;. from: 1point3acres.com/bbs
                        }
                }
                return res;
        }
       
        //这个只是我自己用来验证的,可忽略这个函数
        int getNewLeftIndex(vector<int> &arr, int left, int right)
        {
                int target = arr[right];
                while(1)
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴                {
                        int mid = (left + right)/2;
                        if(arr[mid] != target && arr[mid+1] == target). From 1point 3acres bbs
                                return mid+1;
                        else if(arr[mid] == target)
                                right = mid;. From 1point 3acres bbs
                        else. 1point3acres.com/bbs
                                left = mid;
                }
        }
        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;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }
};
//
//int main(). 1point 3acres 璁哄潧
//{
//        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
我觉得楼主第三题的思路是对的啊~. 1point3acres.com/bbs
可以把所有Index分组~求出每个组shuffle回原来index的步数,然后求最小 ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-23 00:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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