一亩三分地论坛

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

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

G Onsite

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

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

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

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

x
刚刚做的onsite。 新人求些大米. more info on 1point3acres.com


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.
   c. how to scale it.
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, . 鍥磋鎴戜滑@1point 3 acres
    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.




评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

谢谢了, OFFER 好几个,可是想去的一个还没有

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

使用道具 举报

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

补充内容 (2015-9-4 05:54):
都没有算法题。。。
是不是experience就不用刷题了。。。。
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (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?

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:
我的理解是这样每个coin 可以veritcal or horizo​​ntal . random 决定任一种case 会决定在tube 的height 所以只要randomly 产生计算就好吗? 不知道有没有理解错

Question 3:
这题主要的考点是在? 有database 加transaction 的话跟第一题有什么不一样的地方吗

Question 4:. 鍥磋鎴戜滑@1point 3 acres
题目不太理解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 就是大众化的题. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
因为我的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.
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 1point 3acres bbs
第一张牌放在桌子上, 第二张牌放在你手里牌的最后面, 不停的重复,直到手里的牌都到了桌子上, 这个叫一个回合,拿起来重复再发 写一个函数,返回需要多少个回合才能使得你手里的牌回到初始的顺序?close to linear.
. more info on 1point3acres.com
5.UTF-8 byte checking 是从前向后, 这个问你从后向前。。。。. 鍥磋鎴戜滑@1point 3 acres

不知道我解释清楚了没有.鐣欏璁哄潧-涓浜-涓夊垎鍦
-google 1point3acres
回复 支持 反对

使用道具 举报

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:
            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
对['A', 'B', 'C', 'D', 'E']求出来[4, 4, 1, 4, 4]。最后求这个[4, 4, 1, 4, 4]数组所有元素的最小公倍数,就是答案。多项式时间复杂度,肯定还有更好的算法。

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

晚点儿再看设计题。。。. more info on 1point3acres.com
. more info on 1point3acres.com
正在找工作中, 欢迎交流 : )
回复 支持 反对

使用道具 举报

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

使用道具 举报

say543 发表于 2015-9-13 07:45:34 | 显示全部楼层
newlxnewlx 发表于 2015-9-10 06:30
抛砖引玉吧, 1和3设计题还没看,. Waral 鍗氬鏈夋洿澶氭枃绔,
第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

每个coin的过程还要用boolean 来确定现在有没有coin stuck 在stack 的top 如果没有则coin可以到tube的bottom 如果有则coin卡在stack.top 的index. 鍥磋鎴戜滑@1point 3 acres


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

使用道具 举报

say543 发表于 2015-9-13 07:47:49 | 显示全部楼层
netfriend7109 发表于 2015-9-9 13:24. 鍥磋鎴戜滑@1point 3 acres
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. more info on 1point3acres.com
抛砖引玉吧, 1和3设计题还没看,
第2题, 先把所有tubes缩减成一个单调递减的stack, 比如tubes如果是3, 6 ...
. more info on 1point3acres.com
LZ好牛 好不容易搞懂第4题...
回复 支持 反对

使用道具 举报

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

补充一下1,3.  第1题单机情况大概就是一个newScheduledThreadPool, 可以简单的用一个PriorityQueue和一个HashMap来模拟:-google 1point3acres
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;

    public Scheduler(Executor executor) {
        this.executor = executor;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        this.triggers = new PriorityQueue<>();
        this.tasks = new HashMap<>();
    }

    public synchronized void start() {
        if (daemon == null) {
            daemon = new Thread(() -> {-google 1point3acres
                while (!isShutdown) {
                    try {
                        long sleepTime = triggers.isEmpty() ? 10_000 : triggers.peek() - System.currentTimeMillis();
                        Thread.sleep(sleepTime);
                        executeTask();
                    } catch (InterruptedException e) {. 1point 3acres 璁哄潧
                        // ignore to reschedule
                    }. Waral 鍗氬鏈夋洿澶氭枃绔,
                }
            });
            daemon.start();
        }
    }

    private synchronized void executeTask() {
        if (!triggers.isEmpty()) {
            long nextFireTime = triggers.poll();
            tasks.get(nextFireTime).forEach(task -> executor.execute(task));
            tasks.remove(nextFireTime);
        }-google 1point3acres
    }. Waral 鍗氬鏈夋洿澶氭枃绔,

    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());
        if (task.getFireTime() < nextFireTime)
            daemon.interrupt();
    }

    public void stop() {
        isShutdown = true;
        daemon.interrupt();
    }
}-google 1point3acres

class SchedulerTester {
    public static void test() throws Exception {
        ExecutorService executor = Executors.newFixedThreadPool(4);
        Scheduler scheduler = new Scheduler(executor);
        scheduler.start();
        scheduler.schedule(new DelayedEchor(2000, "hello"));-google 1point3acres
        scheduler.schedule(new DelayedEchor(3000, "world"));
        scheduler.schedule(new DelayedEchor(1000, "greeting : "));
        Thread.sleep(5000);
        scheduler.stop();
        executor.shutdown();
    }
}
. 1point3acres.com/bbs
class DelayedEchor implements DelayedRunnable {
    private long fireTime;
    private String message;.1point3acres缃

    DelayedEchor(long delay, String message) {
        fireTime = System.currentTimeMillis() + delay;
        this.message = message;
    }

    public long getFireTime() { return fireTime; }
    public void run() {-google 1point3acres
        System.out.println(message);
    }.鐣欏璁哄潧-涓浜-涓夊垎鍦
}
这种情况所有schedule都是无状态的,可以简单的scale到多机。

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

使用道具 举报

newlxnewlx 发表于 2015-9-21 06:42:41 | 显示全部楼层
say543 发表于 2015-9-13 07:45
先说第二题LZ的想法跟我很想维护单调递减的stack 但是我的stack 长相会不太依样-google 1point3acres
ex:
tubes 4 5 2 3

sorry我不是楼主。。。。
对 想法跟你一样。
我记得在某个oj好像见过这道题,实现起来比较繁琐
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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