Pergunta de entrevista da empresa GitHub

(Second Email Screening Question) The git-daemon implementation that ships in Core Git has never been tuned for high concurrency situations (i.e. situations with thousands of clients performing git-daemon requests on the same machine). A particular source of concern is the way the daemon handles the children of the process. git-daemon stores the the list of live children in a linked list. New children are inserted into the list such that children with the same source address are clustered in the list, and the new child goes at the front of the cluster. As a result of this data structure, all operations regarding children management are extremely inefficient. • Can you spot and explain what are these operations, and what are their current asymptotic costs? This would be incredibly valuable information to have on the commit message for your changes. • How would you change the storage of the live children to make these operations significantly faster? • What are the new asymptotic costs of the implementation? Is it a strict improvement for all operations? Again, this would make great content for your commit messages. • Hint: Git already has a lot of generic data structures available -- you can reuse them instead of writing one from scratch. That should make the job much easier. • Bonus: Can you spot a corner case in the children handling code that would have terrible performance implications? What would be the easiest way to fix it?