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


一亩三分地论坛

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

Google onsite

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

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

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

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

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,只大概讲了一下思路,写了个开头就开始让问问题了。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
. from: 1point3acres.com/bbs

补充内容 (2015-12-16 10:24):
赏点大米
-google 1point3acres
补充内容 (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 怎么样. From 1point 3acres bbs
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
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的意思是扫雷主要考洗牌算法?

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

使用道具 举报

 楼主| ymqytw 发表于 2015-12-16 10:23:29 | 显示全部楼层
lzheng8 发表于 2015-12-15 08:14.鏈枃鍘熷垱鑷1point3acres璁哄潧
lz能讲讲system design题吗?谢谢!

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

使用道具 举报

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

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

使用道具 举报

xiaoniuona 发表于 2015-12-16 12:42:25 | 显示全部楼层
杰西Jesse 发表于 2015-12-16 09:10. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
可以直接用priorityqueue 统计次数,然后每次都放次数最多的,重新排序。

额,如果最多的那个放了一次之后还是最多的,第二个该放什么呢?譬如 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了
那个面试官进来先问我,前3轮有system design吗,我说没有,他说好吧那咱们就来system design吧
求大米
回复 支持 反对

使用道具 举报

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

import java.util.*;
class Letter{
        char c;
        int times;
        Letter(char x, int t){
                c = x;
                times = t;
        }
}. 1point 3acres 璁哄潧
public class OrderString{
        public String build(String str){
                StringBuilder sb = new StringBuilder();
                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);. visit 1point3acres.com for more.
                        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){
                                return l2.times - l1.times;
                        }
                });
                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();
. Waral 鍗氬鏈夋洿澶氭枃绔,                        sb.append(cur.c);
                        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 "";. 1point3acres.com/bbs
                        else sb.append(temp.c);-google 1point3acres
                }
                return sb.toString();
        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        public static void main(String args[]){
                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
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,然后往里填字母

明白了,先填充奇数个,再填充偶数个也成。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-27 04:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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