s*****e
发帖数: 115 | 1 This is a simplified version of a real problem we encountered.
Your solutions will preferably be implemented in Go. We'll also consider
solutions implemented in Python (or other languages on request), but since
Go can be learned in approximately a day, we really do prefer a solution
written in Go.
We're building a directed graph.
The graph consists of Nodes connected by Edges.
Each Node has an ID (int64).
Each Node keeps track of its outgoing Edges (list of ids).
There might be thousands of outgoing Edges.
Each outgoing Edge also has an edge weight (float64).
The Node needs to maintain a sorted list of its outgoing Edges.
Operations are triggered on Nodes that might change edge weights.
Some Operations might update one edge weight, others many.
For the purposes of this exercise, the operation is a function that (
randomly) changes a few edge weights.
The sorted list needs to efficiently stay sorted even as many weights are
changed.
For the purposes of this exercise it's initially enough to focus on one Node
and its outgoing Edges (to Node IDs that don't need an instantiated Node)
Multiple edges can have the same weight.
We recommend to build on top of https://github.com/google/btree/ but are
interested to hear if you have a different take.
目前发现有另外一个解法,比如做双向链表,好像跟btree一样可以做到log(n),不想误导
大家,过几天更新和大家探讨
这个问题应该是可以partition然后计算的,甚至可以request来了以后,直接随机发到任
意server上然后用chord做peer-to-peer通讯最后到达request应该被送到的server上,
跳过master-slave这个model的
Go其实最适合拿来怎么用呢?有什么具体例子么?哪里会容易找这样的工作? | w***g
发帖数: 5958 | 2 btree是磁盘数据结构，如果是内存操作，就是overengineer了，不如红黑树。数据结
构问题貌似和服务器架构没啥关系。
solution
【在 s*****e 的大作中提到】
: This is a simplified version of a real problem we encountered.
: Your solutions will preferably be implemented in Go. We'll also consider
: solutions implemented in Python (or other languages on request), but since
: Go can be learned in approximately a day, we really do prefer a solution
: written in Go.
: We're building a directed graph.
: The graph consists of Nodes connected by Edges.
: Each Node has an ID (int64).
: Each Node keeps track of its outgoing Edges (list of ids).
: There might be thousands of outgoing Edges.
| s*****e
发帖数: 115 | 3 可能这个题目的作者也没有想清楚,好像只要选一个BST就可以了?
doubly linked list能做到 initialize是nlogn(排序),剩下CRUD都是log n因为doubly
linked list可以binary search
关于架构,这个只是考虑到如果是maintain多个node(原题说只考虑一个node,one-to-
many),因为node之间的out-going edges是独立的,所以可以每个node都独立maintain一
个红黑树或者doubly linked list,只有删除node的时候需要互相通讯一下.
【在 w***g 的大作中提到】
: btree是磁盘数据结构，如果是内存操作，就是overengineer了，不如红黑树。数据结
: 构问题貌似和服务器架构没啥关系。
:
: solution
|
|
