前几天的G家面经 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

前几天的G家面经

前几天的G家面经# JobHunting - 待字闺中

s*y2015-07-30 07:07

1 楼

我来美国有两年了，这期间交了个女朋友，和女朋友感情还不错，昨天她跟我说她妈妈要来看她，我有点紧张，因为第一次和她见面，我也不知道该送点什么礼物，想了半天决定送她一对耳钉，是金的，中国人还是都很喜欢金子的。关于这几天都干啥，我女朋友也让我安排一下，这我实在没想太好，我们俩在亚特兰大住，我想带他们到附近转转，可有不知道行不行，现在实在是好紧张，甚至连说什么都不知道。但是又想想，早晚有那么一天就豁出去吧，还有就是这几天要带他们吃些什么呢，这也是个问题，她说她妈妈不太喜欢吃西餐，可是附近又没什么好的中餐馆，我住的地方倒是有厨房，但是我的厨艺估计她也不会觉得太好吃，本来就不怎么样，加上是给她做，我又紧张，估计最后肯定不怎么样，所以肯定是出去吃，不过到底这几天吃什么。要是每天都去饭店也不太好。而且她也不是就呆一天。最关键的还是她对我的印象怎么样，哎还是不瞎想了，爱怎么着就怎么着吧，总之还是以饱满的热情迎接这一切的到来吧。

D*r2015-07-30 07:07

2 楼

有硬件背景，和一些系统底层开发的经历，可能和一般的纯软件面试有点不太一样。
Recruiter说要找背景相近的人面试。没有碰到印度人面试官
1。面试官对我以前读书时的一个课题比较感兴趣，聊了一会儿。确认我要面试软件职
位后，出了一道题。有一个3维矩阵，从原点开始遍历所有的点。随便怎么走都可以。
2。算数据流最近N个数的平均值。接着分别讨论整型溢出的情况和浮点数精度丢失的
问题。
3。实现一个内核的延时任务处理功能。就是可以注册将来要处理的一些任务，时间中
断发生时，执行那些到时的任务。实现任务注册函数和时间中断处理函数。
4。 A）写函数实现32位数的位异或操作（算奇偶校验位）
B）模拟普通电梯的运行，实现一个电梯控制器
5。有一个分布式系统，提供一个返回64位数的服务。有两个要求： 1。所返回的数是
唯一的。 2。所返回的是一个近似递增序列。如何实现使得要求1必须满足，要求2不严
格要求，但越接近越好。同时对用户的响应延迟要越短越好。

c*n2015-07-30 07:07

3 楼

最后那个 uid 生成器的题常见，楼主怎么答的？

【在 D*****r 的大作中提到】

: 有硬件背景，和一些系统底层开发的经历，可能和一般的纯软件面试有点不太一样。
: Recruiter说要找背景相近的人面试。没有碰到印度人面试官
: 1。面试官对我以前读书时的一个课题比较感兴趣，聊了一会儿。确认我要面试软件职
: 位后，出了一道题。有一个3维矩阵，从原点开始遍历所有的点。随便怎么走都可以。
: 2。算数据流最近N个数的平均值。接着分别讨论整型溢出的情况和浮点数精度丢失的
: 问题。
: 3。实现一个内核的延时任务处理功能。就是可以注册将来要处理的一些任务，时间中
: 断发生时，执行那些到时的任务。实现任务注册函数和时间中断处理函数。
: 4。 A）写函数实现32位数的位异或操作（算奇偶校验位）
: B）模拟普通电梯的运行，实现一个电梯控制器

h*n2015-07-30 07:07

4 楼

twtr snowflake:
timestamp block + unique machine id + local seq id

【在 c******n 的大作中提到】

: 最后那个 uid 生成器的题常见，楼主怎么答的？

c*n2015-07-30 07:07

5 楼

wow, thanks!

【在 h*********n 的大作中提到】

: twtr snowflake:
: timestamp block + unique machine id + local seq id

c*n2015-07-30 07:07

6 楼

看了twitter 的impl, 我对scala 不是很熟，但看起来有问题，有可能duplicate.
它是一个thrift server, 下面的代码里可以个多个threads: serverOpts.
workerThreads
但worker 里面的sequence 都是独立的。
这样一个server上不同的thread 完全可能generate duplicate ID
val worker = new IdWorker(workerId, datacenterId, reporter)
val processor = new Snowflake.Processor(worker)
val transport = new TNonblockingServerSocket(serverPort)
val serverOpts = new THsHaServer.Options
serverOpts.workerThreads = thriftServerThreads
val server = new THsHaServer(processor, transport, serverOpts)
inside the worker:
sequence = (sequence + 1) & sequenceMask

【在 h*********n 的大作中提到】

: twtr snowflake:
: timestamp block + unique machine id + local seq id

h*n2015-07-30 07:07

7 楼

这样的话，只能每个thread分别申请unique thread id了。

【在 c******n 的大作中提到】

: 看了twitter 的impl, 我对scala 不是很熟，但看起来有问题，有可能duplicate.
: 它是一个thrift server, 下面的代码里可以个多个threads: serverOpts.
: workerThreads
: 但worker 里面的sequence 都是独立的。
: 这样一个server上不同的thread 完全可能generate duplicate ID
: val worker = new IdWorker(workerId, datacenterId, reporter)
: val processor = new Snowflake.Processor(worker)
: val transport = new TNonblockingServerSocket(serverPort)
: val serverOpts = new THsHaServer.Options
: serverOpts.workerThreads = thriftServerThreads

n*n2015-07-30 07:07

8 楼

这题用一个数据库不就行了？

【在 h*********n 的大作中提到】

: 这样的话，只能每个thread分别申请unique thread id了。

c*n2015-07-30 07:07

9 楼

那立马就要被毙掉。要 scalable

【在 n******n 的大作中提到】

: 这题用一个数据库不就行了？

k*l2015-07-30 07:07

10 楼

同一个机器上thread沟通应该不难吧，
或者每个worker 最开始时向同总服务器要一个 worker id

【在 c******n 的大作中提到】

k*l2015-07-30 07:07

11 楼

电梯问题想想挺好玩的，
还可以分 single car 和 multi-car system

【在 D*****r 的大作中提到】

m*n2015-07-30 07:07

12 楼

Huh? Try design a scalable solution based on 数据库.

【在 c******n 的大作中提到】

: 那立马就要被毙掉。要 scalable

m*n2015-07-30 07:07

13 楼

Depends on if there is requirement on value range.
Also depens on how "近似递增" the returns must be.

【在 h*********n 的大作中提到】

: twtr snowflake:
: timestamp block + unique machine id + local seq id

n*n2015-07-30 07:07

14 楼

只提供id服务的数据库还不够？多少qps？

【在 c******n 的大作中提到】

: 那立马就要被毙掉。要 scalable

z*o2015-07-30 07:07

15 楼

不用数据库persistent怎么解决？突然down机呢？

【在 c******n 的大作中提到】

: 那立马就要被毙掉。要 scalable

c*n2015-07-30 07:07

16 楼

good question, the snowflake solution is based on time, but if u crash and
come back immediately , potentially we could run into duplicate. so u might
have to wait a little bit after booting up

【在 z*******o 的大作中提到】

: 不用数据库persistent怎么解决？突然down机呢？

k*l2015-07-30 07:07

17 楼

第一部分是timestamp, down 机怕啥？
不过可以在dispatcher上跑一个DB, 只负责在worker startup时给分配一个unique
worker id以后就不管
这样的问题和timestamp 差不多, worker也不能constantly crash and start, worker
id 就溢出了

【在 z*******o 的大作中提到】

: 不用数据库persistent怎么解决？突然down机呢？

z*o2015-07-30 07:07

18 楼

嗯，而且题目没要求persistent

and
might

【在 c******n 的大作中提到】

: good question, the snowflake solution is based on time, but if u crash and
: come back immediately , potentially we could run into duplicate. so u might
: have to wait a little bit after booting up

n*n2015-07-30 07:07

19 楼

不是64位？

worker

【在 k**l 的大作中提到】

: 第一部分是timestamp, down 机怕啥？
: 不过可以在dispatcher上跑一个DB, 只负责在worker startup时给分配一个unique
: worker id以后就不管
: 这样的问题和timestamp 差不多, worker也不能constantly crash and start, worker
: id 就溢出了

k*l2015-07-30 07:07

20 楼

总共64位， worker id / machine id 用一点，worker thread 里面的 incrementor/
counter 用一些，如果有timestamp还要用去一大半

【在 n******n 的大作中提到】

: 不是64位？
:
: worker

c*n2015-07-30 07:07

21 楼

你这样不如时间 prefix 的办法，如果 worker 不死， private section 很快就溢出
，你还得回来再要一个 prefix

worker

【在 k**l 的大作中提到】

k*l2015-07-30 07:07

22 楼

可是我要是省了 timestamp 可以省出至少32位，比如 private section 48位，
timestamp 有 waste bits
这个方法理论上可以没有

【在 c******n 的大作中提到】

: 你这样不如时间 prefix 的办法，如果 worker 不死， private section 很快就溢出
: ，你还得回来再要一个 prefix
:
: worker

c*n2015-07-30 07:07

23 楼

你这个办法从 id sequence increase 角度跟时间区别不大，但是为了 handle
reboot, 你必须每个 sequence bump 或者隔100个 persist to disk. 如果靠时钟的自
然属性，起来后先停一会儿就可以了

【在 k**l 的大作中提到】

: 可是我要是省了 timestamp 可以省出至少32位，比如 private section 48位，
: timestamp 有 waste bits
: 这个方法理论上可以没有