查看:5405|回复:25
qiqi_hua
头像
中尉
  • 中尉
  • 2428
  • 3
  • 6
  • 2
  • @2015-04-06
发表于:2020-07-29 09:10|只看楼主
字体大小:T|T

职场历史故事:Leetcode

占个位置。


根据我目前的进度,应该每3天一个小note,每星期一个topic summary。

和文史有关,绝对有关。职场历史也是历史,不能歧视!版主四马是拦不住我的!


3
Advertisement
kengdie
头像
大校
  • 大校
  • 9516
  • 11
  • 15610
  • 0
  • @2013-01-31
发表于:2020-07-29 09:48|只看TA
字体大小:T|T

给楼主点赞

0
Advertisement
qiqi_hua
头像
中尉
  • 中尉
  • 2428
  • 3
  • 6
  • 2
  • @2015-04-06
发表于:2020-07-29 11:04|只看楼主
字体大小:T|T

https://forums.huaren.us/showtopic.html?topicid=2573159&fid=398&page=30


从这里开始。Leetcode读书笔记。


本来是发chats;不过,有点不合适。放这里吧。

0
tidewater
头像
大校
  • 大校
  • 27382
  • 35
  • 30756
  • 0
  • @2005-08-13
发表于:2020-07-31 00:06|只看TA
字体大小:T|T

友情支持

0
Advertisement
qiqi_hua
头像
中尉
  • 中尉
  • 2428
  • 3
  • 6
  • 2
  • @2015-04-06
发表于:2020-07-31 13:53|只看楼主
字体大小:T|T

友情支持


tidewater 发表于 2020-07-31 00:06

谢潮水。军功章有你的一半


你在原帖的评论我会汇总加过来。现在正在和concurrency的leetcode奋斗,tree的搞定,这个周末写notes。

0
qiqi_hua
头像
中尉
  • 中尉
  • 2428
  • 3
  • 6
  • 2
  • @2015-04-06
发表于:2020-07-31 22:35|只看楼主
字体大小:T|T

我的第二份工作,是在Linux kernel mode device driver。大系统里面,16 computing blades,每个blades上面4个CPU complex,每个CPU若干个core,还有hyper thread。每个thread齐头并进,有时候需要lock。一个CPU里面的lock,用semephore/mutex可以解决;不同blades之间的lock,必须靠硬件支持的atomic transaction。这个特殊硬件需要的device driver,就是我们小组负责。


今天的leetcode,随便看了concurrency的topic,做了几个题目;refresh memory也学新东西。潮水说的,c++17。那就从这几个lock开始吧。(有的是c++11)。说错了由潮水老师补充(


  1. lock_handle
  2. unique_lock
  3. scope_lock


lock_handle(mutex): 一直blocking,直到mutex available。不需要unlock。从当前程序/section{} 退出的时候,自动release。工作中,我一般用这个。

unique_lock():支持unlock。比lock_handle 灵活。用condition_variable的时候,必须用它。condition_variable(unique_handle, condition)相当于”only when condition is true, do we try to lock"。这样可以直接把checking写入lock。当程序从这里退出,condition is true,plus the lock is obtained. 当然必须记住:需要unlock later。

scope_lock: 属于c++17。对于多个mutex一起lock。如果用以前的stand_lock,需要考虑multi-lock的顺序,极其容易deadlock。这个scope_lock很方便。


常见的用法,当然是multi-thread 情况了。

https://en.cppreference.com/w/cpp/thread/scoped_lock


几个points:

  1. lock_guard wrapped in {}, only effective inside this code section.
  2. scoped_lock works with multiple locks, grabbing them atomically.
  3. threads use emplace_back rather than push_back. This is a performance improvement, reduced from construction & copy into in-place construction.



0
qiqi_hua
头像
中尉
  • 中尉
  • 2428
  • 3
  • 6
  • 2
  • @2015-04-06
发表于:2020-08-25 14:18|只看楼主
字体大小:T|T

Graph Theory


常见的Tree,属于Graph的一个特殊分类。Tree在leetcode里面有tag,可以专门挑tree类的题目做。

Grid,尤其是2D grid,也是Graph的一个表达方式。扫地机器人的navigation,一般用Grid形式表达map。


Navigation算法里面,A*(和它的变种,Dixxxx)是weighted navigation的普遍算法。无人驾驶的navigation,或者circuit自动连线的算法,都是A*。A* 是 Dijkastra 的加速版,加上 heuristic cost。

Robotics 里很多是用 hybrid A*,因为 quasi continuously differentiable 的要求,law of physics。

Mapping算法里面,RRT是Robotics领域经常用的。RPM(PRM?)用的也多。


我工作的方向是这个,所以我以为我对graph theory和里面的题目应该没有问题;结果,,,我错了!


加上一个Youtube link,里面的解释不错。


https://www.youtube.com/watch?v=DgXR2OWQnLc&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P

1
qiqi_hua
头像
中尉
  • 中尉
  • 2428
  • 3
  • 6
  • 2
  • @2015-04-06
发表于:2020-08-25 14:19|只看楼主
字体大小:T|T


如果要去control 组,A*只怕是必考;去network组,minmax flow估计是必考;去path planning,那就是TSP,traveling of a salesman.

潮水如果以后想走Robotics,告诉你,Jacobian Matrix那就是必考必考题!还有,空间旋转的4个表达方式。


leetcode pace, 差不多20个easy 一天,10个medium勉强。

0
Advertisement
qiqi_hua
头像
中尉
  • 中尉
  • 2428
  • 3
  • 6
  • 2
  • @2015-04-06
发表于:2020-08-25 14:20|只看楼主
字体大小:T|T

Summary 算法的用途 scenarios:

  1. DFS 的用处,是finding connection。例如,find center (the nodes with the most levels); find weakest link (same as finding isolated islands).
  2. BFS: is about to find path.


潮水哥说: BFS / DFS / Best-First-Search 其实可以用同一种写法,差别只是 DFS 用 LIFO ,BFS 用 FIFO,Best-First-Search 用 cost-based-heap (priority queue) 。。。 其它部分写法一样一招鲜吃遍天。

不过工业界里,大尺寸或者 High performance low latency 的 DFS,一般也避免写成递归函数,因为避免递归的 overhead 以及系统栈的尺寸限制。



Common data structures for Graph representation:

  1. unordered_map<int, vector<int>>: the benefit is the key part can be used directly as index to the map
  2. vector<vector<int>>: representing individual edge, typically requiring to translate this into unordered_map
  3. vector<vector<int>> as a matrix[n.m]: huge waste of memory, but typically used for grid situation.
  4. TreeNode/left/right: most commonly used in leetcode


潮水哥又说: std::push_heap() 是 O(log(N))

std::sort() 是 O(N*log(N))

除非 problem size 很小,或者 implementation 有问题,否则 heap (priority queue 的底层实现) 应该更快。

你如果做工业界的 high-performance / low-latency programming, 看具体应用,有些应用要避免用 std::priority_queue,考虑直接用 std::push_heap() / std::pop_heap() 在 std::vector 上,因为这样可以事前 std::vector::reserve() 以及避免 vector realloc ... 还有就是可以保持 std::vector allocated space persistent 来避免 loading time.

另外 std:: priority_queue 的底层也可以是 std::deque。。。但 std::deque 对于大尺度问题,RandomAccessIterator 会有附加 overhead 。

对于 pre-sorted but algorithm do not know it is pre-sorted,std::sort() 会快一些,但咋都比不过 std::push_heap() 否则香浓的 paper 药丸 。。。

当然 heap 的最大价值在于 std::push_heap() 和 std::pop_heap() 对称美 。。。 如果你的应用都是 batch push 一次给我来一百打然后我一个一个 pop 的这种比较极端情况,另说。

最后编辑qiqi_hua 最后编辑于 2020/08/25 14:25:17
0
qiqi_hua
头像
中尉
  • 中尉
  • 2428
  • 3
  • 6
  • 2
  • @2015-04-06
发表于:2020-08-25 14:33|只看楼主
字体大小:T|T

Links


1.     https://leetcode.com/explore/interview/card/top-interview-questions-medium/

2.     https://leetcode.com/discuss/career/456930/must-do-arrays-questions-for-tech-interviews

3.     Search key words for topics

a.     Dynamic programming 209

b.     Graph 44

c.     Tree 140

d.     Network flow

e.     Hash table 129

0
查看:5405|回复:25
Advertisement

回复贴子