一亩三分地论坛

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

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

Google onsite

[复制链接] |试试Instant~ |关注本帖
ymqytw 发表于 2015-12-15 08:04:19 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
12/11在MTV
第一轮白人姐姐,1)meeting room II 变形,给了一些task <startTime, endTime, memoryUsed>求peak memory usage.
2) rearrage string,使得相邻的字母不相同。时间不够了,没有完全写完. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二轮还是做wifi的白人姐姐,BFS变形,以及一些followup,都是跟拓扑相关的。.鐣欏璁哄潧-涓浜-涓夊垎鍦
午餐一个在Google工作了9年白人老头,人很nice。
第三轮白人小哥,MineSweeper,我估计是想考这个shuffle算法 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
第四轮白人小哥shadow,system design: 设计一个系统能生成 unique ID,user的请求速率非常高,必须用multiple machine. Follow up: 如何让ID可以粗略的按照时间排序。最后还有15分钟,出了一道number of island II,只大概讲了一下思路,写了个开头就开始让问问题了。



补充内容 (2015-12-16 10:24):
赏点大米

补充内容 (2016-1-14 03:15):
这周拿到offer了,好高兴

评分

7

查看全部评分

本帖被以下淘专辑推荐:

lzheng8 发表于 2015-12-15 08:14:12 | 显示全部楼层
lz能讲讲system design题吗?谢谢!
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-12-15 08:48:34 | 显示全部楼层
感觉LZ 应该答得不错。
题目都还好,不知道system design 怎么样. more info on 1point3acres.com

belss LZ 了
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-12-15 14:13:45 | 显示全部楼层
lz的意思是扫雷主要考洗牌算法?
回复 支持 反对

使用道具 举报

lin126 发表于 2015-12-15 21:07:56 | 显示全部楼层
楼主,不是说5年工作经验以上才考system design吗
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-16 02:58:13 | 显示全部楼层
额,扫雷为什么要考shuffle算法呢?是要先把雷随机分布到矩阵里,再每个空格计算周围有多少雷嚒?
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-12-16 08:37:12 | 显示全部楼层
xiaoniuona 发表于 2015-12-16 02:58
额,扫雷为什么要考shuffle算法呢?是要先把雷随机分布到矩阵里,再每个空格计算周围有多少雷嚒?

可能随机布雷这一块需要shuffle,等lz详解
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-16 08:43:18 | 显示全部楼层
同问,用这个shuffle怎么随机布雷呢?
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2015-12-16 08:52:29 | 显示全部楼层
Rearrange String求解法,和wiggle sort应该不一样吧?
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-12-16 09:10:38 | 显示全部楼层
yucheyang2 发表于 2015-12-16 08:52
Rearrange String求解法,和wiggle sort应该不一样吧?

可以直接用priorityqueue 统计次数,然后每次都放次数最多的,重新排序。
回复 支持 反对

使用道具 举报

 楼主| ymqytw 发表于 2015-12-16 10:13:16 | 显示全部楼层
yjfox 发表于 2015-12-15 14:13
lz的意思是扫雷主要考洗牌算法?

. 1point3acres.com/bbs面试官让实现一个初始化函数,给定grid长宽,和雷的个数,让随机的把雷放进去
回复 支持 反对

使用道具 举报

 楼主| ymqytw 发表于 2015-12-16 10:23:29 | 显示全部楼层
lzheng8 发表于 2015-12-15 08:14
lz能讲讲system design题吗?谢谢!

楼主最开始是先设计了一个master-slave的结构
followup,楼主在这个系统纠结了一会儿,后来面试官提示可以不要局限于这个系统,楼主就把master去掉了,同时把timestamp加进ID里了。
最后又问了一点fault tolerance followup
回复 支持 反对

使用道具 举报

lzheng8 发表于 2015-12-16 10:34:47 | 显示全部楼层
ymqytw 发表于 2015-12-16 10:23
楼主最开始是先设计了一个master-slave的结构
followup,楼主在这个系统纠结了一会儿,后来面试官提示可 ...

. from: 1point3acres.com/bbs 哦,楼主是在简历上有系统设计的经历吗?还是new grad就有可能碰到系统设计?谢谢。
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-16 12:42:25 | 显示全部楼层
杰西Jesse 发表于 2015-12-16 09:10
可以直接用priorityqueue 统计次数,然后每次都放次数最多的,重新排序。
. visit 1point3acres.com for more.
额,如果最多的那个放了一次之后还是最多的,第二个该放什么呢?譬如 aaaaabbbccd, 5个a,3. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
个b,2个c和1个d,先放了个a,变成4个a还是最多的呀
回复 支持 反对

使用道具 举报

 楼主| ymqytw 发表于 2015-12-16 12:44:30 | 显示全部楼层
lzheng8 发表于 2015-12-16 10:34
哦,楼主是在简历上有系统设计的经历吗?还是new grad就有可能碰到系统设计?谢谢。

我觉得new grad本身就有可能碰到system design吧
我简历主要都是学校的project,一个相关一点的可能就是一个分布式系统的课的project了. from: 1point3acres.com/bbs
那个面试官进来先问我,前3轮有system design吗,我说没有,他说好吧那咱们就来system design吧. 1point 3acres 璁哄潧
求大米
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-12-16 12:48:50 | 显示全部楼层
xiaoniuona 发表于 2015-12-16 12:42
额,如果最多的那个放了一次之后还是最多的,第二个该放什么呢?譬如 aaaaabbbccd, 5个a,3
个b,2个c ...

import java.util.*;
class Letter{
        char c;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        int times;
        Letter(char x, int t){. Waral 鍗氬鏈夋洿澶氭枃绔,
                c = x;
                times = t;
        }
}
public class OrderString{
        public String build(String str){
                StringBuilder sb = new StringBuilder();. 1point 3acres 璁哄潧
                HashMap<Character, Integer> map = new HashMap();
                for(int i= 0;i<str.length();i++){
                        char c = str.charAt(i);
                        if(!map.containsKey(c))
                                map.put(c,1);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        else map.put(c,map.get(c)+1);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                }
                Queue<Letter> que = new PriorityQueue<Letter>(10,new Comparator<Letter>(){
                        public int compare(Letter l1, Letter l2){. 1point3acres.com/bbs
                                return l2.times - l1.times;
                        }. from: 1point3acres.com/bbs
                });
                for(char c: map.keySet()){
                        Letter letter = new Letter(c,map.get(c));
                        que.offer(letter);
                }
                Letter temp = null;
                while(!que.isEmpty()){
                        Letter cur = que.poll();
                        sb.append(cur.c);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        cur.times = cur.times - 1;
                        if(temp!=null && temp.times>0)
                                que.offer(temp);
                        temp = cur;
                }
                if(temp!=null && temp.times> 0){
                        if(temp.times>1) return "";
                        else sb.append(temp.c);
                }
                return sb.toString();
        }
        public static void main(String args[]){. 1point3acres.com/bbs
                OrderString os = new OrderString();
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴                System.out.println(os.build("aaaaabbbccd"));//abacabacbad
        }
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| ymqytw 发表于 2015-12-16 13:06:54 | 显示全部楼层
yucheyang2 发表于 2015-12-16 08:52
Rearrange String求解法,和wiggle sort应该不一样吧?

我的做法是先统计次数,从次数多的来。
把string分成若干个大小为2的bucket,然后往里填字母
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2015-12-16 13:07:22 | 显示全部楼层
杰西Jesse 发表于 2015-12-16 12:48. from: 1point3acres.com/bbs
import java.util.*;
class Letter{
        char c;

哦哦!!!好思路,如果某个字符超过len / 2的话,一定不可能,有没有扫一遍的方法啊?
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2015-12-16 13:08:01 | 显示全部楼层
ymqytw 发表于 2015-12-16 13:06
我的做法是先统计次数,从次数多的来。
把string分成若干个大小为2的bucket,然后往里填字母
.1point3acres缃
明白了,先填充奇数个,再填充偶数个也成。
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-12-16 13:11:08 | 显示全部楼层
yucheyang2 发表于 2015-12-16 13:07
哦哦!!!好思路,如果某个字符超过len / 2的话,一定不可能,有没有扫一遍的方法啊?

一开始统计次数的时候就可以判定了吧。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 10:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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