Beginner algorithms (optional)
The Amazon intern: search, sorting, complexity, greedy, line sweep
In this chapter, you will learn to
- Estimate how costly a program is (complexity)
- Pick the right approach: sorting, search, sweeping, greedy choices
Tools: Python
7 exercises
Each exercise is graded automatically, in your browser. The full statements are available once you have an account.
What this is for in real life
Two programs can give the same answer, yet one replies in the blink of an eye while the other never finishes. - Huge catalogues. An online shop or a search engine finds one item among billions in a fraction of a…
The infinite catalog
Welcome to MegaStock, the largest warehouse in Europe. First day of your internship. Your manager hands you a tablet: "A customer wants product
#738291045. The catalog contains 1 billion products sorted by…The waiting line
Second day of the internship. The logistics manager explains: "We have two processing zones. In Zone A, orders are processed in order of arrival: the oldest first. In Zone B, parcels are stacked on top of one…
The conveyor sort
Day three. The main conveyor is down: parcels arrive in random order, but the delivery truck requires a load sorted by weight (lightest to heaviest). Your only capability: compare two parcels and swap their…
The time counter
Your manager gives you, for an internal routine
routine(n)whose code nobody knows, its measured running times at different input sizes: a listmeasurementsof pairs[n, temps_en_secondes]. "Just tell me how…The delivery intervals
End of the week. The warehouse has a single truck this Saturday. Each customer has a delivery window
[start, end]. The truck serves only one customer at a time: once a delivery has started, it is busy until the end of…The scanner sweep
Final project of the internship. The warehouse is equipped with a laser scanner that sweeps the shelves from left to right. Each product on a shelf occupies a rectangle defined by
[x_start, x_end, hauteur]. Rectangles…