Problems Base course RU

Built on

heap

Articles

DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems GRA Algorithm Dijkstra's algorithm Shortest paths from one vertex in a weighted graph without negative edges. O((V + E) log V) 3 problems GRA Algorithm A* Dijkstra with a hint of how far is left: the wave stretches towards the goal, and the path stays shortest. O((V + E) log V) 2 problems GRA Algorithm Bidirectional search Two Dijkstra waves towards each other: where to stop, how much is saved, and how to make it work with A*. O((V + E) log V) 2 problems GRA Algorithm Contraction hierarchies A navigator's precomputation: contract unimportant crossroads into shortcuts and find the path with two waves going up. O((V + E′) log V) 1 problem TEC Technique Choosing a data structure First the list of operations, then the structure: the cost of each operation in Python and Go on one map. depends on the choice 1 problem

Problems

A stop on the way Orders by deadline Seismic watch The courier's route Fire stations One free ride Queries over the tiers The median over a window The fifteen puzzle in the fewest moves

Often together

interviews 5 shortest path 4 weighted graph 4 graph 4 maps and navigation 4 classic 3 in production 3 heuristic 3 array 2 precomputation 2 tree 1 scheduling 1