找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2124|回复: 10
收起左侧

[Google] 狗狗新鲜实习面经

[复制链接]

1120

主题

177

精华

3493

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3493
发表于 2-6-2017 09:49 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 2-6-2017 09:51 PM 编辑 7 b2 H5 s, n  N; F/ I$ E0 c, H

3 W$ k; P% ^& {& s. q' EConsidering a server that should ignore requests older than 1 second, create a structure to handle this behavior and give its complexity.
" Z$ p5 o8 \  Y0 A* {, [4 y+ ]Use any language you want.

1163

主题

182

精华

3625

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3625
发表于 2-6-2017 09:49 PM | 显示全部楼层

What does he mean? From the context of google, I would assume they mean requests from a client to a back-end server that have not gotten a response for a second or more. This would be RPC requests sent from a "client" (e.g. a front end server) to a "server" (e.g. a back end server). This can be 10 thousands of requests but it's probably save to assume it's less than 100'000 or let's say 500'000 requests in any 1 second timeframe: < 500K RQS 2 P `" I" Y W# b, W3 Z
. ~1 v9 w# i7 u$ h9 p3 W# M' }
I'd pretend requests are executed strictly sequential so I place them in a queue together with the timestamp. New requests are placed at the head (front), requests at tail that are >= 1 second can be canceled and removed. I would use a ring buffer with 500K entries fix allocated with a start and end index. So, the index I'd get for a call is as well an identifier that I need back on the request's response so I can mark the request as completed. If a request is completed that is = to the tail, I can advance the tail as far as there are entries marked completed. . ^$ m; R/ k' ^0 _& V* N m! U( M
. C9 T% f! S& p7 ~/ d1 ^
Complexity: O(1) to insert, O(1) to find > 1s and O(1) amortized to complete a call. + C% M. Y+ Y% I
The problem with the apporach is, that a call that really takes 1s compared with other calls being returned in fractions of milliseconds will keep the queue from being emptied, so the queue can get full because of only one call. If it can be restricted in terms there are never more than 500'000 requests a second, this can still be a good solution, but if the number of calls lasting long increases and if the accepted timeout is changed to maybe 10 seconds, the solution starts to break.

回复 支持 1 反对 0

使用道具 举报

1112

主题

164

精华

3400

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3400
发表于 2-6-2017 09:49 PM | 显示全部楼层

I think the following might work:

Start with a doubly link list with 2 nodes and 3 pointers ( head, next, tail ) .

head is head
next is head.next
and tail is last node .

every second the head breaks connection to the next node,

head.right=null;
next.left=null;
head=next;

and add a node to the tail
tail.next=newNode
tail = newNode.

The server keeps reading data from the head of the doubly link list.

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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