谷歌店面

来源:有个猎头去年就在linkedin上联系我,发了好几个邮件和消息,当时我还没想跳槽,今年想跳的时候就没找人内推,还是直
接找了他,他帮我联系了公司的HR,然后和HR聊了聊约了电面,面的是general的sde
电面形式:45分钟电话面试,Google doc上写code,不需要编译

题目:
https://leetcode.com/problems/random-pick-with-weight/ 很类似的题,先写了一遍最直接的只pick一次,follow up是pick k次再写了一遍,用TreeMap或者binary search都
行,分析了时间空间复杂度,运气比较好考的题挺简单的

参考 https://www.cnblogs.com/grandyang/p/9784690.html

时间有多就又问了一题,只说了思路

Parallel Job Scheduling

There are N processes with some processes having dependencies on other processes (meaning if a process P1 is dependent on process P2, then P1 can only be started after P2 is complete). Assume that there won’t be a cyclic dependency in the inputs.

Each process has a time duration (in sec) given by Duration array.

Processes can be run in parallel. We need to find the minimum time such that all processes are completed.

TestCase:
There are 4 processes -
A (Duration: 2 sec), B (Duration: 3 sec), C (Duration: 4 sec) and D (Duration: 5 sec)

B is dependent on A
C is dependent on A
D is dependent on B & C

In this case, min time would be 11 sec.

感受:面试官是白人,虽然有就是来完成任务的感觉,一开始自我介绍也没说,但很容易交流也很友好,面试过程中很focus,后来他说自己是return intern,表示来狗家的最大原因是看重wlb
结果:过了两天通知可以去加州onsite了,但不知道这个时候还有没有HC,去面完了再看吧

店面, 2 题, 听声音 是一个比较和蔼的白人大叔。 还帮忙改了 typo error.1。给一个带环的 list, 从第2个node 开始删除, 每各一个删除一个。 for example : 1->2->3->1 结果: 1->3 ->1
同时关于 约瑟夫环 的问题

2。股票价格, 实现历史最小, 最大, 以及当前价格 和 更新价格4个functions‍‍‌‌‌‌‍‍‍‍‌‌‍‍‍‍‌‍‍. O(1)

题不难,希望水过。 bless.

报一下面经
一上來先自我介紹一下接著開始問問題
1: 實現Set(int index, int value), Get(int index), SetAll(int value)三個function,但時間複雜度必須滿足O(1)
网上搜了一下,感觉比较靠谱的回答是存时间。Map的value是包含time和val。在全局维护一个setAll的time和val。每次赋值,更新time和val,每次取值,拿自己的time和全局的time比较,在全局之前,说明已经被SetAll,在全局之后,则返回自己的val。每次call setAll,更新全局timestamp和val
2. 給一個一維數組,接著必須按照數組的大小順序重新給值,並從1開始給值
ex: [20, 10, 30, 40] -> [2, 1, 3, 4]
follow up 如果是二維?只考慮同行同列,不考慮斜線
ex: [[20,10],[40][30]] -> [[2, 1],[3, 2]]
行列都需要排序,参考 https://leetcode.com/problems/russian-doll-envelopes/
follow up 超時了沒答好
祝大家都有心儀的offer