查看: 5047|回复: 25

G Onsite

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

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


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

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

1. design and implement a data structure and API to complete a following task.
   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.. 鍥磋鎴戜滑@1point 3 acres
   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.. 1point 3acres 璁哄潧
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.





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

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

使用道具 举报

sunnyroom 发表于 2015-9-4 05:53:43 | 显示全部楼层
看来 experience的面试,还是很难啊。。。。

补充内容 (2015-9-4 05:54):
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-9-4 05:54):
都没算法题。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

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 都是算法题啊,
. 鍥磋鎴戜滑@1point 3 acres
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?

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 ...
. 1point 3acres 璁哄潧
感谢LZ 分享  有些想讨论一下
quesition 1:
这题需不需要考虑database, 假设有transaction 保护是不是就没有synchonization 的问题在同一台机器上? consumer 指的是什么? scale 的部分我是认为只要用session -sticky 的方式即使multiple machine 也因该问题不大不过要怎么fire event 能讲讲嘛? 要怎么存call back function?. Waral 鍗氬鏈夋洿澶氭枃绔,
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Question 2:
我的理解是这样每个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 有什么分别?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-8 13:25:37 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| netfriend7109 发表于 2015-9-9 12:59:48 | 显示全部楼层
hbsophia 发表于 2015-9-8 13:25

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

使用道具 举报

 楼主| netfriend7109 发表于 2015-9-9 13:24:40 | 显示全部楼层
say543 发表于 2015-9-8 10:30
感谢LZ 分享  有些想讨论一下
quesition 1:. Waral 鍗氬鏈夋洿澶氭枃绔,
这题需不需要考虑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.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
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.
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张). from: 1point3acres.com/bbs
第一张牌放在桌子上, 第二张牌放在你手里牌的最后面, 不停的重复,直到手里的牌都到了桌子上, 这个叫一个回合,拿起来重复再发 写一个函数,返回需要多少个回合才能使得你手里的牌回到初始的顺序?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-google 1point3acres
谢谢了, OFFER 好几个,可是想去的一个还没有

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

回复 支持 反对

使用道具 举报

newlxnewlx 发表于 2015-9-10 06:30:35 | 显示全部楼层
抛砖引玉吧, 1和3设计题还没看,.鏈枃鍘熷垱鑷1point3acres璁哄潧
第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). From 1point 3acres bbs

第4题,没想到更好的方法。考虑cards 'A', 'B', 'C', 'D', 'E' , 每一个card的下一个位置只决定于总长度已经当前位置。那么可以写一个next_pos, 大概类似于这样. Waral 鍗氬鏈夋洿澶氭枃绔,
def next_pos(cur, length):
        if length == 1:
            return cur
        odds = length / 2.鏈枃鍘熷垱鑷1point3acres璁哄潧
        evens = length - odds
        if cur % 2 != 0:
            return cur / 2
            return odds + next_pos(cur / 2, evens)
然后对每一个元素, 分别求出这个元素返回到最初的位置所需要的rounds,这个我是暴力求解,每个最坏O(n)。
def restore(cur, length):
        original = cur.1point3acres缃
        rounds = 0
        while True:. 1point3acres.com/bbs
            cur = next_pos(cur, length). 1point 3acres 璁哄潧
            rounds += 1
            if original == cur:
        return rounds
对['A', 'B', 'C', 'D', 'E']求出来[4, 4, 1, 4, 4]。最后求这个[4, 4, 1, 4, 4]数组所有元素的最小公倍数,就是答案。多项式时间复杂度,肯定还有更好的算法。

第5题跟从前往后的utf8 check类似,换一下顺序。


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

使用道具 举报

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

使用道具 举报

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

先说第二题LZ的想法跟我很想维护单调递减的stack 但是我的stack 长相会不太依样
tubes 4 5 2 3
stack = [4,2] 2 是stack top 也就是是top 会是一个diameter 最小但是index 最大的的element. visit 1point3acres.com for more.

同时为了计算方便, stack 会存tuble index 而不是tube diameter. visit 1point3acres.com for more.

每个coin的过程还要用boolean 来确定现在有没有coin stuck 在stack 的top 如果没有则coin可以到tube的bottom 如果有则coin卡在stack.top 的index
. from: 1point3acres.com/bbs

回复 支持 反对

使用道具 举报

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设计题还没看,
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷第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 {. 1point 3acres 璁哄潧
    long getFireTime();

class Scheduler {
    private Executor executor;
    private PriorityQueue<Long> triggers;
    private Map<Long, Queue<DelayedRunnable>> tasks;
    private Thread daemon;
    private volatile boolean isShutdown;

    public Scheduler(Executor executor) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        this.executor = executor;. Waral 鍗氬鏈夋洿澶氭枃绔,
        this.triggers = new PriorityQueue<>();
        this.tasks = new HashMap<>();

    public synchronized void start() {
        if (daemon == null) {
            daemon = new Thread(() -> {
                while (!isShutdown) {
                    try {
                        long sleepTime = triggers.isEmpty() ? 10_000 : triggers.peek() - System.currentTimeMillis();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        Thread.sleep(sleepTime);. From 1point 3acres bbs
                    } catch (InterruptedException e) {
                        // ignore to reschedule. 1point 3acres 璁哄潧
    }. From 1point 3acres bbs

    private synchronized void executeTask() {-google 1point3acres
        if (!triggers.isEmpty()) {
            long nextFireTime = triggers.poll();
            tasks.get(nextFireTime).forEach(task -> executor.execute(task));. from: 1point3acres.com/bbs
        }. more info on 1point3acres.com

    public synchronized void schedule(DelayedRunnable task) {. from: 1point3acres.com/bbs
        Queue<DelayedRunnable> taskQueue = tasks.getOrDefault(task.getFireTime(), new LinkedList<>());. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        tasks.put(task.getFireTime(), taskQueue);

        // update next earliest trigger
        long nextFireTime = triggers.isEmpty() ? Long.MAX_VALUE : triggers.peek();
        if (task.getFireTime() < nextFireTime)
            daemon.interrupt(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

    public void stop() {
        isShutdown = true;

class SchedulerTester {
-google 1point3acres    public static void test() throws Exception {
        ExecutorService executor = Executors.newFixedThreadPool(4);
        Scheduler scheduler = new Scheduler(executor);
        scheduler.schedule(new DelayedEchor(2000, "hello"));
        scheduler.schedule(new DelayedEchor(3000, "world"));. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        scheduler.schedule(new DelayedEchor(1000, "greeting : "));

class DelayedEchor implements DelayedRunnable {. Waral 鍗氬鏈夋洿澶氭枃绔,
    private long fireTime;
    private String message;. 鍥磋鎴戜滑@1point 3 acres

    DelayedEchor(long delay, String message) {
        fireTime = System.currentTimeMillis() + delay;
        this.message = message;.鐣欏璁哄潧-涓浜-涓夊垎鍦

    public long getFireTime() { return fireTime; }
    public void run() {

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

使用道具 举报

newlxnewlx 发表于 2015-9-21 06:42:41 | 显示全部楼层
say543 发表于 2015-9-13 07:45. Waral 鍗氬鏈夋洿澶氭枃绔,
先说第二题LZ的想法跟我很想维护单调递减的stack 但是我的stack 长相会不太依样
tubes 4 5 2 3

对 想法跟你一样。
回复 支持 反对

使用道具 举报



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


custom counter

GMT+8, 2017-7-28 03:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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