Skip to content

refactor exercises for lower time complexity - #1

Open
Jenishai5 wants to merge 1 commit into
mainfrom
solutions
Open

refactor exercises for lower time complexity#1
Jenishai5 wants to merge 1 commit into
mainfrom
solutions

Conversation

@Jenishai5

Copy link
Copy Markdown
Owner

refactor exercises for lower time complexity

  • calculateSumAndProduct: merge two O(n) passes into one (still O(n),
    already optimal, just halves the constant factor)
  • findCommonItems: O(n*m) -> O(n+m) using a Set for lookups
  • hasPairWithSum: O(n^2) -> O(n) using a Set of seen values
  • removeDuplicates: O(n^2) -> O(n) using a Set for duplicate checks

Applied to both the JavaScript and Python versions of each exercise,
with brief Time/Space/Optimal complexity notes per the exercise brief.

implement data structures, caching, and precomputing

  • linked_list.py: doubly-linked list, O(1) push_head/pop_tail/remove
  • lru_cache.py: O(1) get/set via hashmap + doubly-linked list
  • skip_list.py: new file, O(log n) expected insert/contains
  • fibonacci.py / making_change.py: manual memoization (no @cache)
  • common_prefix.py: sort + adjacent-pair comparison instead of O(n^2)
  • count_letters.py: precomputed character set instead of O(n^2)

All test suites pass, including the large-scale ones (1M strings,
10M-char string, ways_to_make_change(9176)).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant