一亩三分地论坛

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

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

2015年10月22日 google MTV onsite

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

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

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

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

x
. Waral 鍗氬鏈夋洿澶氭枃绔,
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:
(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
32,33

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

4. 给你一个无向图edge list, 求里面的三角形, 南美人不友好, 不给hint, 就自己在那边干活, 而且最后我就做出来个暴力解, 他没留意, 还讲了半天才明白, 我了个去。
a.
0-1
1-2. Waral 鍗氬鏈夋洿澶氭枃绔,
3-2
4-3
1-0.鏈枃鍘熷垱鑷1point3acres璁哄潧
自己想如何设计数据结构来表示input. . Waral 鍗氬鏈夋洿澶氭枃绔,
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的应用。

弱呀, 每轮都只做了一个题。。。去年面google的时候还是9个算法+1个设计。。。。。。。, 老了
. more info on 1point3acres.com
积极发面经, 攒人品, 希望下面onsite能拿到offer, 现在都成了onsite就死了, 真。。。。。。

本帖被以下淘专辑推荐:

hj867955629 发表于 2015-10-27 16:11:29 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
returning 发表于 2015-10-27 08:12. 1point3acres.com/bbs
50 penalty 这个题有意思,一时想不出。求三角形那个应该是lintcode原题吧。. 鍥磋鎴戜滑@1point 3 acres

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

public int minPenalty(int[] nums) {
                int[] dp = new int[nums.length];-google 1point3acres
                for (int i = 1; i < nums.length; i++) {. 1point 3acres 璁哄潧
                        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 | 显示全部楼层
关注一亩三分地微博:
Warald
hj867955629 发表于 2015-10-27 16:23
写了下第三题,不过没看到单个字符的条件,数组里字符可以重复或者超长。有问题请指正,感谢!这题复杂度应 ...

我觉得你想的有些复杂了,一个permutation的程序改一下ending condition就搞定了应该
回复 支持 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个设计居然都还没拿到…哎…
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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

使用道具 举报

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
我去…大哥你去年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 | 显示全部楼层
3Gdesigner 发表于 2015-10-26 14:30
我觉得3可以用ugly numberII的方法吧,用dp. From 1point 3acres bbs
用三个指针指向2,3,5,然后每次从 首位加2,3,5的新数 ...

dp应该不太行吧,就算用dp也要先sort,sort就nlogn了,不太可能O(n)
回复 支持 反对

使用道具 举报

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.1point3acres缃
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):
我去,仔细一看,你的题不是,我错了。
回复 支持 反对

使用道具 举报

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

使用道具 举报

douya 发表于 2015-10-27 12:11:33 | 显示全部楼层
returning 发表于 2015-10-27 10:57
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) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        int i = 0;. more info on 1point3acres.com
                        while (i < s.length() && s.charAt(i) == '0') {. 鍥磋鎴戜滑@1point 3 acres
                                i++;
                        }. visit 1point3acres.com for more.
                        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()) {
                                return;
                        }
                        if (cur.length() != 0) {.1point3acres缃
                                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]);. from: 1point3acres.com/bbs
                                combination(allCombination, cur, target, nums, i);
                                cur.delete(curLen, cur.length());
                        }
                }
                . visit 1point3acres.com for more.
                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);-google 1point3acres
                                        }
                                }
                                return;
                        }
                        for (int i = 0; i < visited.length; i++) {
                                if (visited[i]) {
                                        continue;
                                }
                                visited[i] = true;
                                cur.append(s[i]);. from: 1point3acres.com/bbs
                                getPermutation(res, vis, target, s, visited, cur, cnt+1);
-google 1point3acres                                visited[i] = false;
                                cur.deleteCharAt(cur.length()-1);
                        }
                }
                . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                public List<String> getNumSmallerOrEqualTarget(int[] nums, int target) {
                        List<String> res = new ArrayList<>(), allCombination = new ArrayList<>();
                        HashSet<String> vis = new HashSet<>();
                        combination(allCombination, new StringBuilder(), target, nums, 0);
                        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);. visit 1point3acres.com for more.
                                }
                        });
                        return res;
                }
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-28 19:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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