一亩三分地论坛

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

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

Google 电面

[复制链接] |试试Instant~ |关注本帖
simon1990zcs 发表于 2016-4-5 12:29:55 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
两周前约的电话面试,今天中午面的,希望不要跪,发发面经攒人品。一如既往的google作风,非常准时在给我打了电话,感觉是一个白人小哥,人还是比较nice的。一开始介绍了一下他所在的小组情况,是Google Play的内部数据统计等等,然后让我介绍一下我最喜欢的project等等,然后遇到的challenge等等,这些差不多用了10分钟左右吧。然后就是coding了,在Google Doc里面进行
1) 一个binary tree,如果对其进行inorder traverse,但要求是iteratively。听到题目,心中暗喜,太便宜我了吧,然后balabala的把代码写出来,虽然中间也停顿几回,不是太确定细节了,然后在脑子里推敲了几下,觉得答案就是这个。(所以说熟记代码,包括细节,还是很有好处的)
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴参考答案:
Stack<TreeNode>stack = new Stack<>();.1point3acres缃
TreeNode curt = root;
While( curt != null || !stack.isEmpty()){
            While(curt != null){
                        stack.push(curt);
                        curt = curt.left;
            }
            curt = stack.pop();
            System.out.print(curt.val);
            curt = curt.right;
写完之后,也讨论一下时间和空间的复杂度。时间O(N), 空间O(depth)
2)  第二题,我没见过,表面看着也非常简单,但因为太简单,反而让我有些慌乱。
Given:
int[] F of size k, with numbers in [0, k)
int a_init, within [0, k)
int N
A_0 = a_init
A_1 = F[A_0]
A_2 = F[A_1]
...
A_i = F[A_i-1]

Find A_N.
其实题目本身,特别简单,一个N次的循环,就能找到最后的答案。当时我压根就没把这三行代码当成solution,就一个劲的想优化算法。
当时我犯了两个错误:1,怎么样我都要把暴力解法给出来,但是我居然傻乎乎的避开了,他还以为我这个最简单的solution都没想出来。 2. 我当时想要的优化结果太aggressive了,想着优化到O(1)时间,导致自己陷入自己的思维陷阱出不来。
后来他看我半天没琢磨出什么来,就说先不要想优化算法,把最简单的写出来。我当时有些慌乱,简单的代码,我自己的声明的变量忘了写类型,还提醒了我两次,我居然都没看出来(丢死人了)。
然后他就说有什么优化算法,又重新回到之前自己的陷阱中(无语),然后他就提示说,中间是不是会出现重复,然后我就立马想到了要记录之前index,然后一旦发现有重复,就进行用数学求余的方式得到答案。(太笨了,自责一下,其实也不难想到,当时就不清楚为啥想不出来)由于中间耗费了一些时间,然后我匆匆忙忙就把自己的思路写完代码,思维未必缜密,估计有bug,然后他看时间差不多,就说这个代码未必通过得了test case,不过思路应该是对了的。(希望他这句不是美国的礼貌用语而已,只要有对我一些肯定,我就感激了)参考答案我就不发了,未必对,大家可以琢磨一下,有没更好的solution!

求过!!求人品!!!求Onsite!!!!

评分

1

查看全部评分

 楼主| simon1990zcs 发表于 2016-4-7 07:35:57 | 显示全部楼层
yueliu2366 发表于 2016-4-7 05:40
第二题是不是可以这么做, 就是用个hashset来记录重复,一旦重复了,就break,同时记录循环周期cycle。然后 ...

你这个solution有个很大的失误点,cycle并确定等于i-1,比如1-3-6-2-8-6, 这里8之后跳到了6,所以这个cycle就是6-2-8,只有三的长度。所以还得用一个list去确定具体cycle到底是在哪里开始出现的,然后才能求出cycle的长度。
回复 支持 1 反对 0

使用道具 举报

yueliu2366 发表于 2016-4-7 05:40:10 | 显示全部楼层
第二题是不是可以这么做, 就是用个hashset来记录重复,一旦重复了,就break,同时记录循环周期cycle。然后就是取余运算了。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
       HashSet<Integer> set = new HashSet<Integer>();
        int A[] = new int[N + 1];-google 1point3acres
        A[0] = a_init;
        int cycle = -1;
        for(int i = 1; i <= N; i++) {
            A = F[A[i - 1]];
            if (set.contain(A)) {
                cycle = i - 1;
                break;
            } else {
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴                set.put(A);
            }
        }
        return (cycle == -1) ? A[N] : A[N % cycle];

补充内容 (2016-4-7 05:50):
最差时间依然是O(N),平均时间是O(N / cycle)。空间是O(N), 为A数组的大小
回复 支持 1 反对 0

使用道具 举报

Alice0701 发表于 2016-4-6 03:47:28 | 显示全部楼层
谢谢楼主分享 希望能够onsite啊
回复 支持 1 反对 0

使用道具 举报

kiviljc 发表于 2016-4-7 04:40:42 | 显示全部楼层
第二题是好题,,
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-7 05:42:05 | 显示全部楼层
yueliu2366 发表于 2016-4-7 05:40
第二题是不是可以这么做, 就是用个hashset来记录重复,一旦重复了,就break,同时记录循环周期cycle。然后 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
另: 希望楼主好运拿到onsite
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-7 08:31:28 | 显示全部楼层
simon1990zcs 发表于 2016-4-7 07:35
你这个solution有个很大的失误点,cycle并确定等于i-1,比如1-3-6-2-8-6, 这里8之后跳到了6,所以这个c ...

多谢指正,改成这样应该可以了吧。用hashmap<A, i> map记录 <数值,数值对应下标>。 然后break的时候,cycle=当前重复的坐标i - 第一次出现这个值的坐标,同时记录第一次出现这个值的坐标。
HashMap<Integer, Integer> map = new HashSet<Integer, Integer>();. more info on 1point3acres.com
        int A[] = new int[N + 1];-google 1point3acres
        A[0] = a_init;
        int cycle = -1;
        int cycle_start_index = 0;
        for(int i = 1; i <= N; i++) {
            A = F[A[i - 1]];
            if (map.containsKey(A)) {
                cycle = i - map.get(A);//周期=当前重复的坐标i - 第一次出现这个值的坐标. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                cycle_start_index = map.get(A); //记录第一次出现这个值的坐标
                break;
            } else {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                map.put(A, i);
            }. visit 1point3acres.com for more.
        }
        
        return (cycle == -1) ? A[N] : A[(N + 1) % cycle + cycle_start_index];



补充内容 (2016-4-7 08:31):
你的做法没有用到hashmap吗?求教
回复 支持 反对

使用道具 举报

 楼主| simon1990zcs 发表于 2016-4-7 09:03:57 | 显示全部楼层
yueliu2366 发表于 2016-4-7 08:31
多谢指正,改成这样应该可以了吧。用hashmap map记录 。 然后break的时候,cycle=当前重复的坐标i - 第一 ...

现在你的solution应该就可以了。
其实你的HashMap<Integer, Integer>,第二个Integer就是那个值所在的index,从你的代码里面也能看出第二个Integer,一直是从1加到N,我就是用了List<Integer>(这个Int就是你的第一个int,然后你的第二个,我直接用list.indexOf(int)就能得到了)
思路跟你的一样,只是方法不一样,效果应该是一样的,
回复 支持 反对

使用道具 举报

say543 发表于 2016-4-7 14:45:55 | 显示全部楼层
觉得这是个好题 不会过难也能体现coding 祝福LZ~~~
回复 支持 反对

使用道具 举报

csh130 发表于 2016-4-18 15:14:45 | 显示全部楼层
第二题的解法跟楼上的方法差不多, 不过求模的地方不太一样, 不知道是不是我想错了
  1. public int Solution(int[] F, int a_init, int k, int N) {
  2.                 Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  3.                 int[] A = new int[N + 1];
  4.                 A[0] = a_init;
  5.                 for (int i = 1; i <= N; i++) {
  6.                         A[i] = F[A[i - 1]];
  7.                         // If it contains a cycle
  8.                         if (map.containsKey(A[i])) {
  9.                                 int cycleLenth = i - map.get(A[i]) + 1;. 鍥磋鎴戜滑@1point 3 acres
  10.                                 return A[(N- i) % cycleLenth + map.get(A[i])];. from: 1point3acres.com/bbs

  11.                         } else {
  12.                                 map.put(A[i], i);
  13.                         }
  14.                 }
  15.                 return A[N];
  16.         }
复制代码
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-18 19:23:28 | 显示全部楼层
csh130 发表于 2016-4-18 15:14
第二题的解法跟楼上的方法差不多, 不过求模的地方不太一样, 不知道是不是我想错了

大胸弟,我看你也经常活跃在解答狗家面经的帖子里 你啥时候面试狗家?交流交流
回复 支持 反对

使用道具 举报

csh130 发表于 2016-4-19 00:33:03 | 显示全部楼层
yueliu2366 发表于 2016-4-18 19:23
大胸弟,我看你也经常活跃在解答狗家面经的帖子里 你啥时候面试狗家?交流交流

我下午就电面了.. 紧张ing啊.  你不会认识我吧?
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-19 01:56:46 | 显示全部楼层
csh130 发表于 2016-4-19 00:33
我下午就电面了.. 紧张ing啊.  你不会认识我吧?
. 1point3acres.com/bbs
不认识啊。 看你经常答题。加油!祝好运。
回复 支持 反对

使用道具 举报

csh130 发表于 2016-4-19 06:20:38 | 显示全部楼层
yueliu2366 发表于 2016-4-19 01:56
不认识啊。 看你经常答题。加油!祝好运。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
面完了... 感觉交流蛮不错的, 题都不难, 也都做出来了. 第一个题效率太低了.. 居然什么都不问我follow up... 我怎么感觉会有第二面....  跪求RP 让我过....
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-19 07:43:47 | 显示全部楼层
csh130 发表于 2016-4-19 06:20
面完了... 感觉交流蛮不错的, 题都不难, 也都做出来了. 第一个题效率太低了.. 居然什么都不问我follow up ...

恭喜呀。都打出来应该没问题了。总共问了几个题呢。能不能写下面经
回复 支持 反对

使用道具 举报

csh130 发表于 2016-4-19 08:13:44 | 显示全部楼层
yueliu2366 发表于 2016-4-19 07:43
恭喜呀。都打出来应该没问题了。总共问了几个题呢。能不能写下面经

不知道呀... 面完更紧张 过两天写吧 ..坐等消息
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-19 08:41:21 | 显示全部楼层
第一题是inorder倒说的过去...
如果是postorder......“看上去很简单但是很恶心人的那些题”之一
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-11 14:34:22 | 显示全部楼层
yueliu2366 发表于 2016-4-7 08:31
多谢指正,改成这样应该可以了吧。用hashmap map记录 。 然后break的时候,cycle=当前重复的坐标i - 第一 ...

直接hashSet就行吧,不是记value,要记index
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 19:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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