Barcelona | Oct-2025 | Angela Onyekwelu | Module- Complexity |Sprint 2 - #2

Learners, PR Template

Self checklist

• I have titled my PR with Barcelona | Oct-2025 | Angela Onyekwelu | Module- Complexity |Sprint 2
• My changes meet the requirements of the task
• I have tested my changes
• My changes follow the style guide

Changelist

Briefly explain your PR.
Sprint 2: linked list, LRU cache, skip list, caching, and precomputing exercises

• Implement a doubly linked list (push_head, pop_tail, remove) with O(1) worst-case operations
• Implement an LRU cache (get/set/eviction) on top of a hash map + doubly linked list, all O(1)
• Implement a skip list (insert, contains, to_list) with O(log n) expected insert/contains
• Speed up fibonacci and ways_to_make_change with iterative bottom-up caching, avoiding both
  exponential blowup and Python recursion-depth limits on large inputs
• Speed up find_longest_common_prefix (trie-based, O(total characters) instead of pairwise
  O(n²) comparison) and count_letters (precomputed character set instead of rescanning the
  string per upper-case letter)

Test plan

• implement_linked_list: all tests pass (incl. 2 added: remove-head, pop_tail-on-empty)
• implement_lru_cache: all tests pass (incl. 2 added: update-existing-key, limit=1)
• implement_skip_list: all tests pass (incl. 2 added: empty list, out-of-order duplicates)
• improve_with_caches: fibonacci and making_change tests pass; making_change test_9176
  dropped from ~21s to milliseconds
• improve_with_precomputing: count_letters tests pass, verified O(n) on a 10M-char string
  (~0.15s)

Questions

Ask any questions you have for your reviewer. You must remove this section if you have no questions.