D*****r
发帖数: 133 | 1 有硬件背景， 和一些系统底层开发的经历， 可能和一般的纯软件面试有点不太一样。
Recruiter说要找背景相近的人面试。没有碰到印度人面试官
1。 面试官对我以前读书时的一个课题比较感兴趣，聊了一会儿。确认我要面试软件职
位后，出了一道题。有一个3维矩阵，从原点开始遍历所有的点。随便怎么走都可以。
2。 算数据流最近N个数的平均值。 接着分别讨论整型溢出的情况和浮点数精度丢失的
问题。
3。 实现一个内核的延时任务处理功能。就是可以注册将来要处理的一些任务，时间中
断发生时，执行那些到时的任务。实现任务注册函数和时间中断处理函数。
4。 A） 写函数实现32位数的位异或操作 （算奇偶校验位）
B） 模拟普通电梯的运行，实现一个电梯控制器
5。 有一个分布式系统，提供一个返回64位数的服务。有两个要求： 1。所返回的数是
唯一的。 2。所返回的是一个近似递增序列。如何实现使得要求1必须满足，要求2不严
格要求，但越接近越好。同时对用户的响应延迟要越短越好。 |
c******n
发帖数: 4965 | 2 最后那个 uid 生成器的题常见， 楼主怎么答的？
【在 D*****r 的大作中提到】
: 有硬件背景， 和一些系统底层开发的经历， 可能和一般的纯软件面试有点不太一样。
: Recruiter说要找背景相近的人面试。没有碰到印度人面试官
: 1。 面试官对我以前读书时的一个课题比较感兴趣，聊了一会儿。确认我要面试软件职
: 位后，出了一道题。有一个3维矩阵，从原点开始遍历所有的点。随便怎么走都可以。
: 2。 算数据流最近N个数的平均值。 接着分别讨论整型溢出的情况和浮点数精度丢失的
: 问题。
: 3。 实现一个内核的延时任务处理功能。就是可以注册将来要处理的一些任务，时间中
: 断发生时，执行那些到时的任务。实现任务注册函数和时间中断处理函数。
: 4。 A） 写函数实现32位数的位异或操作 （算奇偶校验位）
: B） 模拟普通电梯的运行，实现一个电梯控制器
|
h*********n
发帖数: 11319 | 3 twtr snowflake:
timestamp block + unique machine id + local seq id
【在 c******n 的大作中提到】
: 最后那个 uid 生成器的题常见， 楼主怎么答的？
|
c******n
发帖数: 4965 | 4 wow, thanks!
【在 h*********n 的大作中提到】
: twtr snowflake:
: timestamp block + unique machine id + local seq id
|
c******n
发帖数: 4965 | 5 看了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*********n
发帖数: 11319 | 6 这样的话，只能每个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******n
发帖数: 12088 | 7 这题用一个数据库不就行了？
【在 h*********n 的大作中提到】
: 这样的话，只能每个thread分别申请unique thread id了。
|
c******n
发帖数: 4965 | 8 那立马就要被毙掉。要 scalable
【在 n******n 的大作中提到】
: 这题用一个数据库不就行了？
|
k**l
发帖数: 2966 | 9 同一个机器上thread沟通应该不难吧，
或者每个worker 最开始时向同总服务器要一个 worker 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
|
k**l
发帖数: 2966 | 10 电梯问题想想挺好玩的，
还可以分 single car 和 multi-car system
【在 D*****r 的大作中提到】
: 有硬件背景， 和一些系统底层开发的经历， 可能和一般的纯软件面试有点不太一样。
: Recruiter说要找背景相近的人面试。没有碰到印度人面试官
: 1。 面试官对我以前读书时的一个课题比较感兴趣，聊了一会儿。确认我要面试软件职
: 位后，出了一道题。有一个3维矩阵，从原点开始遍历所有的点。随便怎么走都可以。
: 2。 算数据流最近N个数的平均值。 接着分别讨论整型溢出的情况和浮点数精度丢失的
: 问题。
: 3。 实现一个内核的延时任务处理功能。就是可以注册将来要处理的一些任务，时间中
: 断发生时，执行那些到时的任务。实现任务注册函数和时间中断处理函数。
: 4。 A） 写函数实现32位数的位异或操作 （算奇偶校验位）
: B） 模拟普通电梯的运行，实现一个电梯控制器
|
|
|
m*****n
发帖数: 204 | 11 Huh? Try design a scalable solution based on 数据库.
【在 c******n 的大作中提到】
: 那立马就要被毙掉。要 scalable
|
m*****n
发帖数: 204 | 12 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******n
发帖数: 12088 | 13 只提供id服务的数据库还不够？多少qps？
【在 c******n 的大作中提到】
: 那立马就要被毙掉。要 scalable
|
z*******o
发帖数: 4773 | 14 不用数据库persistent怎么解决？突然down机呢？
【在 c******n 的大作中提到】
: 那立马就要被毙掉。要 scalable
|
c******n
发帖数: 4965 | 15 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**l
发帖数: 2966 | 16 第一部分是timestamp, down 机怕啥？
不过可以在dispatcher上跑一个DB, 只负责在worker startup时给分配一个unique
worker id以后就不管
这样的问题和timestamp 差不多, worker也不能constantly crash and start, worker
id 就溢出了
【在 z*******o 的大作中提到】
: 不用数据库persistent怎么解决？突然down机呢？
|
z*******o
发帖数: 4773 | 17 嗯， 而且题目没要求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******n
发帖数: 12088 | 18 不是64位？
worker
【在 k**l 的大作中提到】
: 第一部分是timestamp, down 机怕啥？
: 不过可以在dispatcher上跑一个DB, 只负责在worker startup时给分配一个unique
: worker id以后就不管
: 这样的问题和timestamp 差不多, worker也不能constantly crash and start, worker
: id 就溢出了
|
k**l
发帖数: 2966 | 19 总共64位， worker id / machine id 用一点，worker thread 里面的 incrementor/
counter 用一些，如果有timestamp还要用去一大半
【在 n******n 的大作中提到】
: 不是64位？
:
: worker
|
c******n
发帖数: 4965 | 20 你这样不如时间 prefix 的办法， 如果 worker 不死， private section 很快就溢出
， 你还得回来再要一个 prefix
worker
【在 k**l 的大作中提到】
: 第一部分是timestamp, down 机怕啥？
: 不过可以在dispatcher上跑一个DB, 只负责在worker startup时给分配一个unique
: worker id以后就不管
: 这样的问题和timestamp 差不多, worker也不能constantly crash and start, worker
: id 就溢出了
|
k**l
发帖数: 2966 | 21 可是我要是省了 timestamp 可以省出至少32位，比如 private section 48位，
timestamp 有 waste bits
这个方法理论上可以没有
【在 c******n 的大作中提到】
: 你这样不如时间 prefix 的办法， 如果 worker 不死， private section 很快就溢出
: ， 你还得回来再要一个 prefix
:
: worker
|
c******n
发帖数: 4965 | 22 你这个办法从 id sequence increase 角度跟时间区别不大， 但是为了 handle
reboot, 你必须每个 sequence bump 或者隔100个 persist to disk. 如果靠时钟的自
然属性， 起来后先停一会儿 就可以了
【在 k**l 的大作中提到】
: 可是我要是省了 timestamp 可以省出至少32位，比如 private section 48位，
: timestamp 有 waste bits
: 这个方法理论上可以没有
|
