一亩三分地论坛

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

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

2015年10月22日 google MTV onsite

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

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

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

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

x
.鐣欏璁哄潧-涓浜-涓夊垎鍦
2015年10月22日 google MTV onsite. 1point3acres.com/bbs
共计5轮, 没有老印, 没有老中, 4个老美, 2个像是南美人, 最后一轮是2个人
没有design, 没有tech communication, 顺便说下, 感觉google的45分钟,好紧张呀, 可能还是我弱的厉害
.1point3acres缃
1. 实现一个动态数组, 可以自动扩容那种, 用了loadfactor.

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴2. 画了一个图, 两端是A和B, A,B之间有若干个stop points, 一个人要从A走到B, 中间可以任意停在stop点上,
a. 这些点的间隔不一样, 例如(想象个一维坐标, e.g. A: 0, B, 1000), 我们有 stop 点 50,60,85, 100.。。。。. more info on 1point3acres.com
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, . From 1point 3acres bbs
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
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就代表不能走了 . from: 1point3acres.com/bbs
问, 给你任意一个环上的node, 让你返回一个set<node> 包含哪些可以走一圈的节点,
有点象是gas station+linkedlist的应用。

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

本帖被以下淘专辑推荐:

hj867955629 发表于 2015-10-27 16:11:29 | 显示全部楼层
returning 发表于 2015-10-27 08:12
50 penalty 这个题有意思,一时想不出。求三角形那个应该是lintcode原题吧。. from: 1point3acres.com/bbs
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-10-27 08:34) ...

public int minPenalty(int[] nums) {
                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 | 显示全部楼层
hj867955629 发表于 2015-10-27 16:23. From 1point 3acres bbs
写了下第三题,不过没看到单个字符的条件,数组里字符可以重复或者超长。有问题请指正,感谢!这题复杂度应 ...

我觉得你想的有些复杂了,一个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个设计居然都还没拿到…哎…
回复 支持 反对

使用道具 举报

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):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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. 1point 3acres 璁哄潧
用三个指针指向2,3,5,然后每次从 首位加2,3,5的新数 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
dp应该不太行吧,就算用dp也要先sort,sort就nlogn了,不太可能O(n)
回复 支持 反对

使用道具 举报

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

补充内容 (2015-10-27 08:34):.1point3acres缃
直觉是不需要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. 1point3acres.com/bbs
lintcode原题?没看到啊,题目叫什么名字? 50 penalty我觉得可以类似Palindrome Partitioning II

lintcode有道题是给定一堆数组,求其中多少个triple可以构成三角形。
. 1point3acres.com/bbs
补充内容 (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可以构成三角形。
. visit 1point3acres.com for more.
补充内容 (2015-10-27 10:58):

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

使用道具 举报

returning 发表于 2015-10-27 13:07:28 | 显示全部楼层
douya 发表于 2015-10-27 12:11-google 1point3acres
所以这个题是要暴力解了? 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 | 显示全部楼层
写了下第三题,不过没看到单个字符的条件,数组里字符可以重复或者超长。有问题请指正,感谢!这题复杂度应该是指数级的吧。。应该还能再做点优化。。
. from: 1point3acres.com/bbs         第四题找三角形就记录一下前两个dfs节点,然后第三个dfs的时候,如果next和上上个一样,并且不等于上一个节点,就是一个三角形了吧

                private String deleteHeadZero(String s) {. 1point3acres.com/bbs
                        int i = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        while (i < s.length() && s.charAt(i) == '0') {
                                i++;
                        }
                        if (i == s.length()) {
                                return "0";
                        }
                        return s.substring(i);
                }
               
                private void combination(List<String> allCombination, StringBuilder cur, int target, int[] nums, int pos) {. From 1point 3acres bbs
                        if (deleteHeadZero(cur.toString()).length() > (""+target).length()) {
                                return;. 1point 3acres 璁哄潧
                        }
                        if (cur.length() != 0) {
                                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) {. 1point 3acres 璁哄潧
                        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);. visit 1point3acres.com for more.
                                                res.add(tmp);
                                        }
                                }
.鐣欏璁哄潧-涓浜-涓夊垎鍦                                return;
                        }
                        for (int i = 0; i < visited.length; i++) {. from: 1point3acres.com/bbs
                                if (visited[i]) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                        continue;
                                }
                                visited[i] = true;
                                cur.append(s[i]);
                                getPermutation(res, vis, target, s, visited, cur, cnt+1);
                                visited[i] = false;
                                cur.deleteCharAt(cur.length()-1);
                        }
                }. more info on 1point3acres.com
               
                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);. From 1point 3acres bbs
                        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;
                }
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 13:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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