ignitae Academy

Advanced Algorithms in PHP

Dynamic programming, Dijkstra with SplPriorityQueue, tries, topological sort and union-find: the interview classics, in PHP that reads well.

Syllabus

Dynamic programming

Dynamic programming: remember the subproblem, not the recursion
Coin change: fewest coins and number of ways (exercise)

Shortest paths

Dijkstra: a priority queue and a relaxation step
Dijkstra with SplPriorityQueue (exercise)

Tries

Tries: a tree of characters for prefix queries
Trie: prefix search, autocomplete and delete (exercise)

Topological order

Topological sort: build order from dependencies, and finding the cycle
Topological sort with cycle reporting (exercise)

Union-find

Union-find: who is connected to whom, in almost constant time
Union-find with path compression (exercise)