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


一亩三分地论坛

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

G Onsite

[复制链接] |试试Instant~ |关注本帖
netfriend7109 发表于 2015-9-3 19:48:03 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 猎头 - Onsite |Other在职跳槽

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

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

x
刚刚做的onsite。 新人求些大米

. From 1point 3acres bbs
1. design and implement a data structure and API to complete a following task..1point3acres缃
   a. allow the clients to register the event with fire time, and one call back function ( event time,9/8/2015 3:00 PM)
   b. when the event approached, the server should fire corresponding call back function at the exactly event time.
   c. how to scale it.. From 1point 3acres bbs
2. a tube with different diameter, vertical erected, throw coins (different size) into it, the coin could drop to the bottom, stop in the middle because of the diameters(bigger than tube's diameter) or land on another coins (previous thrown coins but stuck in the middle), make the computation for every coins position in the tube.
3. design a pub/sub system.
4. Shuffle a deck of the cards,
    a. odd one on hand, even one on the table.  
    b. when it is completed, take the card on the table, repeat step a.
    c. until there is no card on the table, which called one round from step a to c.
    d. repeat a ~ c, until the cards restore to the original state. How many round it needed. what is complexity.
5. Valid the UTF 8 encoding for a given stream.  all the possible valid decoding if you start to evaluate from the last byte.

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. more info on 1point3acres.com

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| netfriend7109 发表于 2015-9-10 00:20:54 | 显示全部楼层
hbsophia 发表于 2015-9-9 13:30. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
LZ好人!祝早日拿到offer, 第四个题好像咋写啊,怎么才能回到原来的顺序?求指导求指导!

谢谢了, OFFER 好几个,可是想去的一个还没有.鐣欏璁哄潧-涓浜-涓夊垎鍦

这几道题都不是很容易,尤其是第四题, 当时给的是暴力, 两个queue, 然后计数。
这样是N!复杂度,回来想了一下,找到了一个比较简单的方法, 话说面试考这种问题比较变态,没见过肯定想不出来啊。
最近有点忙,在外面出差, 你先想想,也可以讨论一下, 如果感兴趣, 我下星期给个思路,贴上来
回复 支持 1 反对 0

使用道具 举报

sunnyroom 发表于 2015-9-4 05:53:43 | 显示全部楼层
看来 experience的面试,还是很难啊。。。。.1point3acres缃
楼主感觉怎么样。。

补充内容 (2015-9-4 05:54):
都没有算法题。。。
是不是experience就不用刷题了。。。。

补充内容 (2015-9-4 05:54):
都没算法题。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
是不是experience就不用刷题了
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2015-9-4 05:54:51 | 显示全部楼层
都没算法题。
是不是experience 职位就不用刷题了。
回复 支持 反对

使用道具 举报

 楼主| netfriend7109 发表于 2015-9-4 06:02:00 | 显示全部楼层
sunnyroom 发表于 2015-9-4 05:54
都没算法题。
是不是experience 职位就不用刷题了。

2,4,5 都是算法题啊,

2. 4 expected O(N)解法。
5. 是道backtracking 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一题是比较tricky, 基本属于多线程, producer/consumer 的一道经典题
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-4 06:02:57 | 显示全部楼层
楼主,对于第一个问题,急切求问how to scale?
回复 支持 反对

使用道具 举报

 楼主| netfriend7109 发表于 2015-9-4 06:09:28 | 显示全部楼层
jiebour 发表于 2015-9-4 06:02
楼主,对于第一个问题,急切求问how to scale?
. From 1point 3acres bbs
scale 比较容易, 既然是producer/consumer 的问题, 就是 多个producer/consumer/event storage in on single machine,  然后多个machine,彼此之间没有联系就好了。 这题的难点是怎么在exact time to fire the event. polling is not a solution.
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-8 10:30:18 | 显示全部楼层
netfriend7109 发表于 2015-9-4 06:09
scale 比较容易, 既然是producer/consumer 的问题, 就是 多个producer/consumer/event storage in o ...

感谢LZ 分享  有些想讨论一下
quesition 1:
这题需不需要考虑database, 假设有transaction 保护是不是就没有synchonization 的问题在同一台机器上? consumer 指的是什么? scale 的部分我是认为只要用session -sticky 的方式即使multiple machine 也因该问题不大不过要怎么fire event 能讲讲嘛? 要怎么存call back function?

Question 2:-google 1point3acres
我的理解是这样每个coin 可以veritcal or horizo​​ntal . random 决定任一种case 会决定在tube 的height 所以只要randomly 产生计算就好吗? 不知道有没有理解错
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Question 3:.鐣欏璁哄潧-涓浜-涓夊垎鍦
这题主要的考点是在? 有database 加transaction 的话跟第一题有什么不一样的地方吗

Question 4:
题目不太理解even 都在table repeat action a 还是都在table阿?

Question 5:
特别强调的stream 和from last byte 不知道跟一班的UTF-8 byte checking 有什么分别?

祝LZ有大offer
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-8 13:25:37 | 显示全部楼层
LZ的面经感觉好小众啊!!!神马情况!!!感谢lz分享,祝lz早日拿到大offer
回复 支持 反对

使用道具 举报

 楼主| netfriend7109 发表于 2015-9-9 12:59:48 | 显示全部楼层
hbsophia 发表于 2015-9-8 13:25
LZ的面经感觉好小众啊!!!神马情况!!!感谢lz分享,祝lz早日拿到大offer

呵呵, 谢谢了,
不是考3SUM 就是大众化的题.1point3acres缃
因为我的level比较senior所以可能有点儿不一样,其实也都是4道Algorithm, 一道design
回复 支持 反对

使用道具 举报

 楼主| netfriend7109 发表于 2015-9-9 13:24:40 | 显示全部楼层
say543 发表于 2015-9-8 10:30
感谢LZ 分享  有些想讨论一下
quesition 1:
这题需不需要考虑database, 假设有transaction 保护是不 ...

1. database won't work in this case because it won't alert you at the exactly event time.
you can think about this way. for example. alert system.. 鍥磋鎴戜滑@1point 3 acres
you schedule a meeting, which will happen on 3:00 PM next Tuesday, 15 minutes before the meeting , system need to send the alert to you and all the persons in the meeting list. so the event is ----- alert user on the 2:45 next Tuesday. basically you can think it as half blocking priority queue.. visit 1point3acres.com for more.
2. it is a tricky question, there is a tube array [4,5,2,3] (number means diameter of the tube.) second array is the coins diameter [1,3, 2], you throw the coin into the tube, what will happen, coin one will go to the bottom of the tube so result will be 3,  your second coin will stuck in index 2 because the tube diameter only 2, but coin 's diameter is 3, it can not go through,  then you throw the 3rd coin which diameter is 2,  it should go to the bottom of tube, but since the previous coin is stuck on index 2, so third one will stuck on top of second coin, finally result will be [3, 2, 2] which is the position of the coins in the tube.  The BF way is very easy O(N^2), but can you do it in linear way?

3. it is a publish/subscrible system,   Have you heard about Kalfka, AWS SQS? something similar.
4. 这是个洗牌的过程, 手里一副牌(52张). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一张牌放在桌子上, 第二张牌放在你手里牌的最后面, 不停的重复,直到手里的牌都到了桌子上, 这个叫一个回合,拿起来重复再发 写一个函数,返回需要多少个回合才能使得你手里的牌回到初始的顺序?close to linear.

5.UTF-8 byte checking 是从前向后, 这个问你从后向前。。。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

不知道我解释清楚了没有

回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-9 13:30:26 | 显示全部楼层
LZ好人!祝早日拿到offer, 第四个题好像咋写啊,怎么才能回到原来的顺序?求指导求指导!
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-10 00:26:25 | 显示全部楼层
netfriend7109 发表于 2015-9-10 00:20
谢谢了, OFFER 好几个,可是想去的一个还没有

这几道题都不是很容易,尤其是第四题, 当时 ...

求楼主思路
回复 支持 反对

使用道具 举报

newlxnewlx 发表于 2015-9-10 06:30:35 | 显示全部楼层
抛砖引玉吧, 1和3设计题还没看,
第2题, 先把所有tubes缩减成一个单调递减的stack, 比如tubes如果是3, 6, 5, 2, 这可以缩减成3,2. 这和原来的3,6,5,2效果等价。   然后从栈顶2开始,一个一个的检查coin。 如果当前的coin比当前的栈顶小,就pop stack(同时保存为last_top), 直到找到第一个比当前coin大的元素。这时coin的位置就确定为last_top了。实现时细节不少。总时间O(n)

第4题,没想到更好的方法。考虑cards 'A', 'B', 'C', 'D', 'E' , 每一个card的下一个位置只决定于总长度已经当前位置。那么可以写一个next_pos, 大概类似于这样
def next_pos(cur, length):
        if length == 1:
            return cur
        odds = length / 2
        evens = length - odds
        if cur % 2 != 0:. from: 1point3acres.com/bbs
            return cur / 2
        else:
            return odds + next_pos(cur / 2, evens)
然后对每一个元素, 分别求出这个元素返回到最初的位置所需要的rounds,这个我是暴力求解,每个最坏O(n)。
def restore(cur, length):
        original = cur
        rounds = 0
        while True:
            cur = next_pos(cur, length)
            rounds += 1
            if original == cur:
                break
        return rounds-google 1point3acres
对['A', 'B', 'C', 'D', 'E']求出来[4, 4, 1, 4, 4]。最后求这个[4, 4, 1, 4, 4]数组所有元素的最小公倍数,就是答案。多项式时间复杂度,肯定还有更好的算法。
. from: 1point3acres.com/bbs
第5题跟从前往后的utf8 check类似,换一下顺序。

晚点儿再看设计题。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

正在找工作中, 欢迎交流 : )
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-10 06:39:57 | 显示全部楼层
第一道题, 楼主具体说说吧?
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-13 07:45:34 | 显示全部楼层
newlxnewlx 发表于 2015-9-10 06:30
抛砖引玉吧, 1和3设计题还没看,
第2题, 先把所有tubes缩减成一个单调递减的stack, 比如tubes如果是3, 6 ...

先说第二题LZ的想法跟我很想维护单调递减的stack 但是我的stack 长相会不太依样
ex:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
tubes 4 5 2 3
stack = [4,2] 2 是stack top 也就是是top 会是一个diameter 最小但是index 最大的的element

同时为了计算方便, stack 会存tuble index 而不是tube diameter. From 1point 3acres bbs

每个coin的过程还要用boolean 来确定现在有没有coin stuck 在stack 的top 如果没有则coin可以到tube的bottom 如果有则coin卡在stack.top 的index.鏈枃鍘熷垱鑷1point3acres璁哄潧
.鏈枃鍘熷垱鑷1point3acres璁哄潧

LZ看看我的想法跟你的一样不?
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-13 07:47:49 | 显示全部楼层
netfriend7109 发表于 2015-9-9 13:24
1. database won't work in this case because it won't alert you at the exactly event time.
you can ...

谢谢LZ 另外LZ 第五题是stream 可是UTF 判断pattern 是在第一byte , 要怎么用呢?
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-13 09:28:53 | 显示全部楼层
newlxnewlx 发表于 2015-9-10 06:30
抛砖引玉吧, 1和3设计题还没看,. more info on 1point3acres.com
第2题, 先把所有tubes缩减成一个单调递减的stack, 比如tubes如果是3, 6 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
LZ好牛 好不容易搞懂第4题...
回复 支持 反对

使用道具 举报

newlxnewlx 发表于 2015-9-21 06:37:51 | 显示全部楼层
newlxnewlx 发表于 2015-9-10 06:30
抛砖引玉吧, 1和3设计题还没看,
第2题, 先把所有tubes缩减成一个单调递减的stack, 比如tubes如果是3, 6 ...

补充一下1,3.  第1题单机情况大概就是一个newScheduledThreadPool, 可以简单的用一个PriorityQueue和一个HashMap来模拟:
interface DelayedRunnable extends Runnable {
    long getFireTime();
}

class Scheduler {
    private Executor executor;
    private PriorityQueue<Long> triggers;
    private Map<Long, Queue<DelayedRunnable>> tasks;
    private Thread daemon;
    private volatile boolean isShutdown;
.1point3acres缃
    public Scheduler(Executor executor) {
        this.executor = executor;
        this.triggers = new PriorityQueue<>();. more info on 1point3acres.com
        this.tasks = new HashMap<>();. From 1point 3acres bbs
    }. 1point 3acres 璁哄潧

    public synchronized void start() {
        if (daemon == null) {
            daemon = new Thread(() -> {
                while (!isShutdown) {
                    try {. from: 1point3acres.com/bbs
                        long sleepTime = triggers.isEmpty() ? 10_000 : triggers.peek() - System.currentTimeMillis();
                        Thread.sleep(sleepTime);
                        executeTask();
                    } catch (InterruptedException e) {
                        // ignore to reschedule
                    } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                }
            });
            daemon.start();
        }
    }

    private synchronized void executeTask() {
        if (!triggers.isEmpty()) {
            long nextFireTime = triggers.poll();
            tasks.get(nextFireTime).forEach(task -> executor.execute(task));
            tasks.remove(nextFireTime);
. 1point 3acres 璁哄潧        }
    }

    public synchronized void schedule(DelayedRunnable task) {
        Queue<DelayedRunnable> taskQueue = tasks.getOrDefault(task.getFireTime(), new LinkedList<>());
        taskQueue.offer(task);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        tasks.put(task.getFireTime(), taskQueue);

        // update next earliest trigger
        long nextFireTime = triggers.isEmpty() ? Long.MAX_VALUE : triggers.peek();
        triggers.offer(task.getFireTime());.鏈枃鍘熷垱鑷1point3acres璁哄潧
        if (task.getFireTime() < nextFireTime)
            daemon.interrupt();
    }
.鐣欏璁哄潧-涓浜-涓夊垎鍦
    public void stop() {
        isShutdown = true;
        daemon.interrupt();
    }
}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

class SchedulerTester {
    public static void test() throws Exception {
        ExecutorService executor = Executors.newFixedThreadPool(4);.鐣欏璁哄潧-涓浜-涓夊垎鍦
        Scheduler scheduler = new Scheduler(executor);. visit 1point3acres.com for more.
        scheduler.start();
        scheduler.schedule(new DelayedEchor(2000, "hello"));
        scheduler.schedule(new DelayedEchor(3000, "world"));
        scheduler.schedule(new DelayedEchor(1000, "greeting : "));
        Thread.sleep(5000);
        scheduler.stop();
        executor.shutdown();
    }
}

class DelayedEchor implements DelayedRunnable {
    private long fireTime;
    private String message;. 鍥磋鎴戜滑@1point 3 acres

    DelayedEchor(long delay, String message) {
        fireTime = System.currentTimeMillis() + delay;
        this.message = message;
. From 1point 3acres bbs    }

    public long getFireTime() { return fireTime; }
    public void run() {
        System.out.println(message);
    }. Waral 鍗氬鏈夋洿澶氭枃绔,
}
这种情况所有schedule都是无状态的,可以简单的scale到多机。

第3题的实现参考各种开源message queue。
回复 支持 反对

使用道具 举报

newlxnewlx 发表于 2015-9-21 06:42:41 | 显示全部楼层
say543 发表于 2015-9-13 07:45
先说第二题LZ的想法跟我很想维护单调递减的stack 但是我的stack 长相会不太依样
ex:. visit 1point3acres.com for more.
tubes 4 5 2 3
. 鍥磋鎴戜滑@1point 3 acres
sorry我不是楼主。。。。
对 想法跟你一样。
我记得在某个oj好像见过这道题,实现起来比较繁琐
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-24 00:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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