Problems Base course RU

Solves

scheduling

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 Graph colouring Different colours for neighbours: the greedy way, the smallest-last order, DSatur and exact search on maps and timetables. O(V + E) for greedy in a given order and smallest last; O((V + E) log V) for DSatur with a heap 2 problems GRA Algorithm Bipartite matching The largest number of pairs in a bipartite graph: Kuhn, Hopcroft–Karp, the theorems of König and Hall. O(E √V) 2 problems DP Technique Convex hull trick A minimum of lines instead of a search: 1776 catalogue tests split into sandbox runs, and a quadratic DP becomes linear. O(n) 2 problems PAR Technique Greedy algorithms The best step now with no looking back: when it is optimal, when almost, and how to prove it. usually O(n log n): a sort or a heap 2 problems SYS Technique Retry with jitter The pause before a retry doubles and is chosen at random: clients spread out in time and do not hit the server in waves. O(1) per pause decision 2 problems

Problems

A storm of retries How many rooms are needed Orders by deadline Seismic watch Calls and repairers Batches of tests Exam days

Often together

classic 4 interviews 4 contests 3 heap 2 in production 2 graph 2 greedy 2 optimization 2 array 1 tree 1 simulation 1 science and physics 1