《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2778|回复: 29
收起左侧

2015年10月22日 google MTV onsite

[复制链接] |试试Instant~ |关注本帖
domofeng 发表于 2015-10-23 11:12:14 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Other在职跳槽

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

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

x
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2015年10月22日 google MTV onsite
共计5轮, 没有老印, 没有老中, 4个老美, 2个像是南美人, 最后一轮是2个人
没有design, 没有tech communication, 顺便说下, 感觉google的45分钟,好紧张呀, 可能还是我弱的厉害

1. 实现一个动态数组, 可以自动扩容那种, 用了loadfactor.

2. 画了一个图, 两端是A和B, A,B之间有若干个stop points, 一个人要从A走到B, 中间可以任意停在stop点上,
a. 这些点的间隔不一样, 例如(想象个一维坐标, e.g. A: 0, B, 1000), 我们有 stop 点 50,60,85, 100.。。。。
b. 50 penalty, 假如从一点到另外一点的距离是50, penalty为0, 否则penalty=Math.abs(50-distance);
找出来从A走到B最小的penalty.
e.g. input{0, 50, 60, 85, 100} where 0 is A, 100 is B,
so penalties are:
-google 1point3acres(0-50:0), (50-100:0) total=0
(0-50:), (50-60:10), (60-100:10) total=20
....
(0-85:35), (85-100:15) total=50.

So (0-50-100) is what we want, 只用返回最小值, 不用求序列, 可以用dp O(n^2) 解决。

3. 给你一个整数数组{2,3,5}, 一个target 33, 求出所有能用数组中数组成的<=target的数
例如:
2,3,5
22,23,25-google 1point3acres
32,33

subset的变种, 在23,32的时候纠结了一会。

4. 给你一个无向图edge list, 求里面的三角形, 南美人不友好, 不给hint, 就自己在那边干活, 而且最后我就做出来个暴力解, 他没留意, 还讲了半天才明白, 我了个去。
a.
0-1. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1-2
3-2
4-3
1-0
自己想如何设计数据结构来表示input.
b. 求里面的三角形
我会求cycle, 但是三角形, 没想到太好的解法, 说完题目都过了20分钟了, 因为之前还扯了别的, 最后给了个最暴力的解法
i. 对于每个node, 找出他们的邻居
ii. 看邻居之间有没有相连, 有则找到, 没有继续

5. 给你一个循环链表, 4-7-3-5-2-4, 一个大圈的那种链表, 代表一个roadmap,
a. 每个节点的整数是在该节点能够加的油。
b. 然后告诉你从一个节点到另一个节点的边上是有cost的, 既要花费的油,当当前攒的油+当前节点加的油-到下一个节点cost<0就代表不能走了
问, 给你任意一个环上的node, 让你返回一个set<node> 包含哪些可以走一圈的节点,
有点象是gas station+linkedlist的应用。
.1point3acres缃
弱呀, 每轮都只做了一个题。。。去年面google的时候还是9个算法+1个设计。。。。。。。, 老了

积极发面经, 攒人品, 希望下面onsite能拿到offer, 现在都成了onsite就死了, 真。。。。。。

本帖被以下淘专辑推荐:

hj867955629 发表于 2015-10-27 16:11:29 | 显示全部楼层
returning 发表于 2015-10-27 08:12
50 penalty 这个题有意思,一时想不出。求三角形那个应该是lintcode原题吧。. visit 1point3acres.com for more.

补充内容 (2015-10-27 08:34) ...

public int minPenalty(int[] nums) {. from: 1point3acres.com/bbs
                int[] dp = new int[nums.length];
                for (int i = 1; i < nums.length; i++) {
                        int tmp = Integer.MAX_VALUE;
                        for (int j = i-1; j >= 0; j--) {
                                tmp = Math.min(tmp, (int)(dp[j]+Math.abs(50-(nums-nums[j]))));
                        }
                        dp = tmp;
                }
                return dp[nums.length-1];
        }
回复 支持 1 反对 0

使用道具 举报

头像被屏蔽
feierqi 发表于 2015-10-27 23:12:34 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 1 反对 0

使用道具 举报

3Gdesigner 发表于 2015-10-26 14:30:59 | 显示全部楼层
我觉得3可以用ugly numberII的方法吧,用dp
用三个指针指向2,3,5,然后每次从 首位加2,3,5的新数中选一个最小的 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这样O(n)就可以了
回复 支持 1 反对 0

使用道具 举报

孤笑客 发表于 2015-10-23 12:22:16 | 显示全部楼层
我去…大哥你去年9个算法+1个设计居然都还没拿到…哎…
回复 支持 反对

使用道具 举报

头像被屏蔽
feierqi 发表于 2015-10-23 12:35:28 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-10-23 15:05:56 | 显示全部楼层
G家的题有意思,2是rob cutting的变形,4是matrix multiplication
回复 支持 反对

使用道具 举报

soysenioritasue 发表于 2015-10-23 15:43:37 | 显示全部楼层
孤笑客 发表于 2015-10-23 12:22-google 1point3acres
我去…大哥你去年9个算法+1个设计居然都还没拿到…哎…

为什么啊,G家的bar也太高了吧,都是什么人进去的呀
回复 支持 反对

使用道具 举报

 楼主| domofeng 发表于 2015-10-25 08:43:48 | 显示全部楼层
feierqi 发表于 2015-10-23 12:35
祝楼主offer啊。顺便问一下,第三题数组中只有个位数么,还是可能有十位数以上的数

都是个位数, 应该没有重复的
回复 支持 反对

使用道具 举报

3Gdesigner 发表于 2015-10-26 14:41:34 | 显示全部楼层
4的话可以这么做 O(e v)
for each edge (u, v):
  for each vertex w:
     if (v, w) is an edge and (w, u) is an edge:
          return true
return false
回复 支持 反对

使用道具 举报

头像被屏蔽
feierqi 发表于 2015-10-27 03:50:27 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

returning 发表于 2015-10-27 08:12:36 | 显示全部楼层
50 penalty 这个题有意思,一时想不出。求三角形那个应该是lintcode原题吧。

补充内容 (2015-10-27 08:34):
直觉是不需要N^2。原因是,假设从A开始更新到C的cost,中间隔着B,当C很大时,肯定不如先到B再到C,原因是A直接到C的cost是减去一个50,而经过B的话很大可能会减去2个50。但是其中corner case较多。
回复 支持 反对

使用道具 举报

douya 发表于 2015-10-27 08:59:31 | 显示全部楼层
marthew777 发表于 2015-10-23 15:05
G家的题有意思,2是rob cutting的变形,4是matrix multiplication

高人。。rob cutting 是啥? 我觉得像Palindrome Partitioning II
回复 支持 反对

使用道具 举报

douya 发表于 2015-10-27 10:50:46 | 显示全部楼层
returning 发表于 2015-10-27 08:12
50 penalty 这个题有意思,一时想不出。求三角形那个应该是lintcode原题吧。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2015-10-27 08:34) ...

lintcode原题?没看到啊,题目叫什么名字? 50 penalty我觉得可以类似Palindrome Partitioning II
回复 支持 反对

使用道具 举报

returning 发表于 2015-10-27 10:57:26 | 显示全部楼层
douya 发表于 2015-10-27 10:50
lintcode原题?没看到啊,题目叫什么名字? 50 penalty我觉得可以类似Palindrome Partitioning II

lintcode有道题是给定一堆数组,求其中多少个triple可以构成三角形。

补充内容 (2015-10-27 10:58):. more info on 1point3acres.com
我去,仔细一看,你的题不是,我错了。
回复 支持 反对

使用道具 举报

douya 发表于 2015-10-27 11:50:16 | 显示全部楼层
5 有什么好想法?
回复 支持 反对

使用道具 举报

douya 发表于 2015-10-27 12:11:33 | 显示全部楼层
returning 发表于 2015-10-27 10:57. Waral 鍗氬鏈夋洿澶氭枃绔,
lintcode有道题是给定一堆数组,求其中多少个triple可以构成三角形。

补充内容 (2015-10-27 10:58):

所以这个题是要暴力解了? matrix 乘法可以求个数,但是不好求出是哪几个点吧?
回复 支持 反对

使用道具 举报

returning 发表于 2015-10-27 13:07:28 | 显示全部楼层
douya 发表于 2015-10-27 12:11
所以这个题是要暴力解了? matrix 乘法可以求个数,但是不好求出是哪几个点吧?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
给一个graph求三角形,我不知道怎么弄,我估计就是做depth为3的dfs,暴力弄。
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-10-27 15:02:37 | 显示全部楼层
douya 发表于 2015-10-27 08:59
高人。。rob cutting 是啥? 我觉得像Palindrome Partitioning II

打错字了,不过估计你能猜出来。。教科书上的经典DP-rod cutting,这题就是变形加了一个penalty而已,很简单,方程改改就行, A=0, B=m, S={i~j}; T(0, m) = min(P(m-j, 50)+T(0,j), P(m-(j-1), 50)+T(0,j-1), ....);
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-27 16:10:13 | 显示全部楼层
3Gdesigner 发表于 2015-10-26 14:30
我觉得3可以用ugly numberII的方法吧,用dp
用三个指针指向2,3,5,然后每次从 首位加2,3,5的新数 ...

不行的,如果target是1000, 235任意排列都可以了,加上允许重复,这结果都是指数级的了,还能O(N)?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-27 16:23:13 | 显示全部楼层
写了下第三题,不过没看到单个字符的条件,数组里字符可以重复或者超长。有问题请指正,感谢!这题复杂度应该是指数级的吧。。应该还能再做点优化。。
        第四题找三角形就记录一下前两个dfs节点,然后第三个dfs的时候,如果next和上上个一样,并且不等于上一个节点,就是一个三角形了吧

                private String deleteHeadZero(String s) {
                        int i = 0;
                        while (i < s.length() && s.charAt(i) == '0') {
                                i++;. 鍥磋鎴戜滑@1point 3 acres
                        }
                        if (i == s.length()) {
                                return "0";
                        }
                        return s.substring(i);
                }
               
                private void combination(List<String> allCombination, StringBuilder cur, int target, int[] nums, int pos) {
                        if (deleteHeadZero(cur.toString()).length() > (""+target).length()) {. 1point 3acres 璁哄潧
                                return;
                        }
                        if (cur.length() != 0) {
. more info on 1point3acres.com                                allCombination.add(cur.toString());
                        }
                        if (pos == nums.length) {
                                return;
                        }
                        int curLen = cur.length();
                        for (int i = pos; i < nums.length; i++) {
                                cur.append(""+nums[i]);
                                combination(allCombination, cur, target, nums, i);
                                cur.delete(curLen, cur.length());
                        }
                }
                .鐣欏璁哄潧-涓浜-涓夊垎鍦
                private void getPermutation(List<String> res, HashSet<String> vis, int target, char[] s, boolean[] visited, StringBuilder cur, int cnt) {
                        if (cnt == s.length) {
                                String tmp = deleteHeadZero(cur.toString());
                                if (tmp.length() <= (""+target).length()) {
                                        if (Integer.parseInt(tmp) <= target && !vis.contains(tmp)) {
                                                vis.add(tmp);
                                                res.add(tmp);
                                        }
                                }
                                return;
                        }
                        for (int i = 0; i < visited.length; i++) {
                                if (visited[i]) {
                                        continue;
                                }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                visited[i] = true;
                                cur.append(s[i]);. From 1point 3acres bbs
                                getPermutation(res, vis, target, s, visited, cur, cnt+1);. 1point 3acres 璁哄潧
                                visited[i] = false;
                                cur.deleteCharAt(cur.length()-1);
                        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
               
                public List<String> getNumSmallerOrEqualTarget(int[] nums, int target) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        List<String> res = new ArrayList<>(), allCombination = new ArrayList<>();. 鍥磋鎴戜滑@1point 3 acres
                        HashSet<String> vis = new HashSet<>();
                        combination(allCombination, new StringBuilder(), target, nums, 0);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        for (String combination: allCombination) {
                                boolean[] visited = new boolean[combination.length()];
                                getPermutation(res, vis, target, combination.toCharArray(), visited, new StringBuilder(), 0);
                        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        Collections.sort(res, new Comparator<String>(){
                                public int compare(String a, String b) {
                                        return Integer.parseInt(a) - Integer.parseInt(b);
                                }
                        });
                        return res;
                }
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-22 17:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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