聊聊前端相关的公开课及学习资料(React为主)

一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

瞄准秋招
跟Shawn一起刷算法题

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code: 20%off 打八折

深入浅出AB Test
从入门到精通
coupon code: 20%off 打八折
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 3871|回复: 34
收起左侧

[经验总结] 一天一道系统设计/OOD

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
鹿鹿鹿鹿鹿鹿鹿 发表于 2019-3-11 02:08:18 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (13)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩

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

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

x
楼主感觉最近算法已经趋近通透,但是系统设计和OOD始终摸不到诀窍(上周跟面试官聊rate limiter聊到血崩)。决心攻坚。今后会每天坚持分享一道自己写的系统设计/OOD直到找到工作,并把答案放在这里面。求和大家分享讨论。
Design a call center


[Python] 纯文本查看 复制代码

"""
call_center
composition:
employee: opeartor, supervisor, directo
logic:
first: check operator : satisfy importance and available
\
V
second: check supervisor
\
V
third: check director
\
V 
going to waiting queue

employee:
logic:
	get_call, free
	get(): Success, fail
	free(): sucess, free


call:
logic: rank, state
	run()
	finished()

"""
class Rank(Enum):
	OPERATOR = 0
	SUPERVISOR = 1
	DIRECTOR = 2
class Employee(object):
	def __init__(self, employee_id, name, rank:Rank, call_center):
		self.employee_id = employee_id
		self.name = name
		self.rank = rank
		self.call_center = call_center

		self.call = None

	def take_call(self, call):
		self.call = call
		call.setCaller(self)
		call.run()

	def complete_call(self):
		# call.update_employee_finished(self)
		# self.
		self.call = None
		self.call_center.recheck()

	@abstractmethod
	def usable(self, rank):
		pass

class Opeartor(Employee):
	def __init__(self, employee_id, name, call_center):
		super(Operator, self).__init__(...,...,Rank.OPERATOR, call_center)

	def usable(self, rank):
		return True if self.call == None
		

class ...
calss ...

class CallState(Enum):
	READY = 0
	IN_PROGRESS = 1
	FINISHED = 1

class Call(object):
	def __init__(self, rank):
		self.rank = rank
		self.state = CallState.READY
		self.employee = None

	def set_caller(self, employee):
		sefl.employee = employee

	def run(self):
		self.state = CallState.IN_PROGRESS
		pass

	def finished(self):
		self.state = FINISHED
		self.employee.complete_call() 

class CallCenter(object):
	def __init__(self, opeartors, supervisors, directors):
		self....
		self....
		self....
		self.waitingqueue = []
		self.lock = Threading.lock()
	def add_call(self, call):
		with self.lock:
			employee = None
			if call.rank == RANK.OPERATOR:
				employee = self._dispatch(call, self.operators)
			if call.rank == RANK.... and not employee:

			if ...


			if not employee:
				self.waitingqueue.append(call)

	def _dispatch(self, call, employees):
			for employee in employees:
				if employee.call is None:
					employee.take_call(call)

	def recheck(self, employee):
		with self.lock:
			for waiting_call in waitingqueue:
				if employee.usable(waiting_call.rank):
					employee.take_call(waiting_call)
					break




评分

参与人数 10大米 +71 收起 理由
zhangrz2 + 1 给你点个赞!
Sheboke + 1 赞一个
xikunlun001 + 1 赞一个
Michelle321 + 1 赞一个
whusym + 3 很有用的信息!
yangjufo + 3 给你点个赞!
gerdo888 + 1 赞一个
hotoil + 5 给你点个赞!
jaychsu + 5 赞一个!
admin + 50 给你打气!希望能坚持!

查看全部评分

本帖被以下淘专辑推荐:

我的人缘0
 楼主| 鹿鹿鹿鹿鹿鹿鹿 发表于 2019-3-11 02:54:23 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩
nhqgoal 发表于 2019-3-11 02:39
楼主用的哪里的OOD的题目和练习?

https://github.com/donnemartin/s ... r/README-zh-Hans.md

+

cracking coding interviewe

不过现在还在做最经典的题的阶段。。chat center, 停车场, 呼叫中心啥的。。。
回复

使用道具 举报

我的人缘3
pxu 发表于 2019-3-11 03:25:41 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  71% (494)
 
 
28% (195)  踩
系统设计跟算法对ratelimiter的要求不一样吧。算法是你找到一种数据结构及相应的算法去解决问题。系统设计是分析可能的feature,服务及数据库存储,然后在已经实现的基础上如何scale。
具体实现上可以考虑用cache server(比如memcached 或redis),设置ttl,然后算出在ttl内的访问次数是否超过plannex。如果,超过了,则返回4xx

补充内容 (2019-3-11 03:33):
个人觉得,算法侧重于你自己完全实现基础的东西。而系统设计侧重于采用工业界以后的东西去实现你的需求,进而实现整个系统的 开发

评分

参与人数 3大米 +5 收起 理由
t__c___ + 3 给你点个赞!
Zia + 1 赞一个
qqaas + 1 赞一个

查看全部评分

回复

使用道具 举报

我的人缘0
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (140)
 
 
10% (16)  踩
rate limiter是不是用queue 里面存每次call的time stamp 每次请求进来时pop掉超过单位时间的旧timestamp然后看剩下的size是不是大于限制
回复

使用道具 举报

我的人缘0
nhqgoal 发表于 2019-3-11 02:39:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  89% (116)
 
 
10% (14)  踩
楼主用的哪里的OOD的题目和练习?
回复

使用道具 举报

我的人缘0
 楼主| 鹿鹿鹿鹿鹿鹿鹿 发表于 2019-3-11 03:01:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩
qqaas 发表于 2019-3-11 02:30
rate limiter是不是用queue 里面存每次call的time stamp 每次请求进来时pop掉超过单位时间的旧timestamp然 ...

对,我就是这么做的。
我和他聊崩主要原因是,我当时完全被算法硬思路困扰了。
我当时就是用的一个queue, 然后检查queue中最老的,pop出去。按照我的思路,这个复杂度完全应该是O(1)啊因为单位个体每个push一下,pop一下。但是他觉得就是O(n)。
后来我仔细仔细想了一下确实应该是O(n),因为实际上对单位次呼叫的worst case实际上就是queue中所有的个体。
我查了一些资料后来,这个题思路应该是:
queue -> 按时间分区间统计个数的queue(这样就能控制复杂度为O(1)了)-> token bucket。
更深的还要谈如果数据量上涨,就要用sticky session来控制服务器分配云云。不过那里太陌生我已经记不太清了。。。

评分

参与人数 1大米 +5 收起 理由
14417335 + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| 鹿鹿鹿鹿鹿鹿鹿 发表于 2019-3-11 03:08:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩
PS: 不是答案啊。。。就是我写的代码而已。。虚心蛤。。。
回复

使用道具 举报

我的人缘0
草鸡蛋 发表于 2019-3-11 04:50:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (26)
 
 
7% (2)  踩
紧跟LZ!
也需要SD尽快跟上!
回复

使用道具 举报

我的人缘0
14417335 发表于 2019-3-11 05:06:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  99% (372)
 
 
0% (3)  踩
鹿鹿鹿鹿鹿鹿鹿 发表于 2019-3-11 03:01
对,我就是这么做的。
我和他聊崩主要原因是,我当时完全被算法硬思路困扰了。
我当时就是用的一个queu ...
后来我仔细仔细想了一下确实应该是O(n),因为实际上对单位次呼叫的worst case实际上就是queue中所有的个体。
我同意worstcase是O(N)但那也是只有一次。所以平均下来仍然是O(1)。

即便你用bucket,如果ratelimit是按照月来计算的,那也只不过是系数的关系。仍然会碰到一次worst case。
回复

使用道具 举报

我的人缘0
ood和系统设计完全是俩种面试啊。ood faang什么lvl会面?我1-3 年经验与entry lvl的面试从没在大司面过ood
回复

使用道具 举报

游客
请先登录
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地

GMT+8, 2019-5-23 09:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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