传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 3995|回复: 19
收起左侧

Google(Youtube) 电面 五月中

[复制链接] |试试Instant~ |关注本帖
jhhuang 发表于 2015-5-15 21:42:14 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
昨天刚面热腾腾的面经!

第一题相当简单,给int n,求n所有factors,然后问问算法的running time。. 1point3acres.com/bbs

下一题问我知不知道http和https的差异,加密的方式如何?我表示没学过security,简单讲讲大概观念呼咙过去。

接下来就是第一题的follow up,给distinct primes list,回传所有由这些primes组成的数字。再follow up,那给的primes有重复呢?

题目不难,自己觉得没答得很顺,东改改西改改,尝试了不同作法才弄好,但是当天晚上拿到onsite了...

攒人品求onsite顺利啊! !
. 1point 3acres 璁哄潧

评分

5

查看全部评分

 楼主| jhhuang 发表于 2015-5-18 06:11:45 | 显示全部楼层
tianshuapple 发表于 2015-5-18 05:37
还有请问lz能解释下follow up的题目吗?
什么是“回传所有由这些primes组成的数字”?

其实也不太算是follow up,不过数学概念上是反过来的。

原本题是n=20,回传{1, 2, 4, 5, 10, 20};后面两道题是给你{2, 5},回传{1, 2, 5, 10},或是primes有重复,例如给你{2, 2, 5},回传{1, 2, 4, 5, 10, 20}。
. 1point 3acres 璁哄潧
没讲清楚,不好意思!
回复 支持 1 反对 0

使用道具 举报

tianshuapple 发表于 2015-5-17 11:59:47 | 显示全部楼层
赞lz~刚约youtube的店面
有个问题大家有人知道吗 我还申了mountain view的new graduate的
会分开联系吗?
回复 支持 反对

使用道具 举报

tianshuapple 发表于 2015-5-18 05:37:44 | 显示全部楼层
还有请问lz能解释下follow up的题目吗?
什么是“回传所有由这些primes组成的数字”?
回复 支持 反对

使用道具 举报

tianshuapple 发表于 2015-5-18 06:29:44 | 显示全部楼层
jhhuang 发表于 2015-5-18 06:11. 1point 3acres 璁哄潧
其实也不太算是follow up,不过数学概念上是反过来的。
. From 1point 3acres bbs
原本题是n=20,回传{1, 2, 4, 5, 10, 20};后 ...

谢谢lz解答!祝onsite顺利~
回复 支持 反对

使用道具 举报

tianshuapple 发表于 2015-5-18 12:33:08 | 显示全部楼层
请问lz 最后一问 在把数放入结果之前 只要多加一个check 看结果中是不是已经有这个数就可以了吧?
回复 支持 反对

使用道具 举报

 楼主| jhhuang 发表于 2015-5-18 21:07:03 | 显示全部楼层
tianshuapple 发表于 2015-5-18 12:33
请问lz 最后一问 在把数放入结果之前 只要多加一个check 看结果中是不是已经有这个数就可以了吧?

當然也是可以這麼做,用同樣例子來說,2跟10你各會多做一次,然後在檢查結果,才發現做過,這其實是多餘的運算,相信interviewer並不是期望這種簡單的modified。

我自己是用兩個array,一個存distinct primes,一個存每個primes可以出現幾次,然後跑interation。拿同一個例子來說,我的input會是{2, 5}和{2, 1},代碼你要參考的話我再發給你!
回复 支持 反对

使用道具 举报

tianshuapple 发表于 2015-5-19 01:14:55 | 显示全部楼层
jhhuang 发表于 2015-5-18 21:07
當然也是可以這麼做,用同樣例子來說,2跟10你各會多做一次,然後在檢查結果,才發現做過,這其實是多餘 ...

感觉这道题和LC的Permutations II有点类似,那个解法是多加了一个bollean array存是不是visited过,如果直接在放到最终结果之前check,大数据会不过。 我先做下,如果有问题再向lz来要代码参考~多谢咯
回复 支持 反对

使用道具 举报

mlz024 发表于 2015-5-25 07:18:37 | 显示全部楼层
求问lz申的直接就是youtube? 还是申的是google职位被分到youtube的? 我目前正在面google的new grad (过了1电面 正在等2电面) 不知还能不能投youtube了?.1point3acres缃
回复 支持 反对

使用道具 举报

 楼主| jhhuang 发表于 2015-5-26 07:59:15 | 显示全部楼层
mlz024 发表于 2015-5-25 07:18
求问lz申的直接就是youtube? 还是申的是google职位被分到youtube的? 我目前正在面google的new grad (过了1 ...
.1point3acres缃
我是请在google的朋友内推的,然后拿到面试就是youtube
回复 支持 反对

使用道具 举报

xanadulord 发表于 2015-5-30 02:35:48 | 显示全部楼层
jhhuang 发表于 2015-5-18 06:11. from: 1point3acres.com/bbs
其实也不太算是follow up,不过数学概念上是反过来的。

原本题是n=20,回传{1, 2, 4, 5, 10, 20};后 ...

请问lz,第二题 给{2,5}, 回传{1,2,5,10}

回传里面为什么有1呢?
回复 支持 反对

使用道具 举报

 楼主| jhhuang 发表于 2015-5-30 04:09:21 | 显示全部楼层
xanadulord 发表于 2015-5-30 02:35
请问lz,第二题 给{2,5}, 回传{1,2,5,10}. From 1point 3acres bbs

回传里面为什么有1呢?

其实就2和5都不使用。

要有1或没有1都可以,端看你和interviewer怎么定义最后要求,我在做的时候是有把1放进去。
回复 支持 反对

使用道具 举报

xanadulord 发表于 2015-5-30 08:22:32 | 显示全部楼层
jhhuang 发表于 2015-5-30 04:09
其实就2和5都不使用。
. visit 1point3acres.com for more.
要有1或没有1都可以,端看你和interviewer怎么定义最后要求,我在做的时候是有 ...

好的,明白了,多谢回复
回复 支持 反对

使用道具 举报

夏末微凉 发表于 2015-6-27 03:28:17 | 显示全部楼层
jhhuang 发表于 2015-5-18 21:07
當然也是可以這麼做,用同樣例子來說,2跟10你各會多做一次,然後在檢查結果,才發現做過,這其實是多餘 ...

楼主我想再问下,这个由prime组成的数字,是找这个array里所有能成的数的乘积是吗,比如[2,3,5] 得到[2,3,5,6,10,15,30],能不能麻烦你再解释下,有duplicate的话是怎么做的,没有看大懂你的解法
回复 支持 反对

使用道具 举报

 楼主| jhhuang 发表于 2015-6-27 18:09:18 | 显示全部楼层
夏末微凉 发表于 2015-6-27 03:28
楼主我想再问下,这个由prime组成的数字,是找这个array里所有能成的数的乘积是吗,比如[2,3,5] 得到[2,3 ...
. from: 1point3acres.com/bbs
是的。

假设input是{2, 2, 5},那我会先前处理成{2, 5}, {2, 1};如果是{2, 2, 2, 5}那就会是{2, 5}, {3, 1}这样。计算还有几个prime可以用
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-7-6 05:02:15 | 显示全部楼层
想请问以下楼主第一个找出数字n所有的factor,这个time complexity是O(logn)还是O(n^1/2) ?谢谢楼主!
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-7-6 05:50:04 | 显示全部楼层
麻烦楼主能不能把duplicate的prime input方法说一说,做了一下,发现没有实现。。。。谢谢!
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-5 13:36:08 | 显示全部楼层
跟subset差不多
class Solution2 {
        private void dfs(List<Integer> res, int pos, int cur, int[] arr) {
                res.add(cur);
                if (pos == arr.length) {
                        return;
                }
                for (int i = pos; i < arr.length; i++) {
                        if (i != pos && arr[i] == arr[i-1]) {
                                continue;
                        }
                        dfs(res, i+1, cur*arr[i], arr);
                }
        }
        public List<Integer> get(int[] arr) {.1point3acres缃
                Arrays.sort(arr);
                List<Integer> res = new ArrayList<>();
                dfs(res, 0, 1, arr);
                Collections.sort(res);. From 1point 3acres bbs
                return res;
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
}
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-10-28 09:20:01 | 显示全部楼层
UmassJin 发表于 2015-7-6 05:02
想请问以下楼主第一个找出数字n所有的factor,这个time complexity是O(logn)还是O(n^1/2) ?谢谢楼主!

感觉应该是O(n^0.5)吧。。难道还有logn的方法么?
回复 支持 反对

使用道具 举报

maplain 发表于 2015-11-7 21:03:54 | 显示全部楼层
杰西Jesse 发表于 2015-10-28 09:20
感觉应该是O(n^0.5)吧。。难道还有logn的方法么?

应该是O(sqrt(n)). 因为你要用sort(n)时间找出所有质因数,然后在输出所有因数。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-23 03:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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