• Problems/
  • CTCI.md
  • DP PATTERNS.md
  • GRIND.md
  • NEETCODE.md
  • PARETO.md

📓 Data Structure & Algorithm Notes

---

🎭 Abstract Data Types (Interfaces)

Array (Abstract Interface)

• Abstract Data Types
  • Associative Array / Map
  • Set
• Concrete Data Types
  • Array
  • Hash Table
  • Linked List
  • Search Tree

Collection

List

• Concrete Data Structures
  • Array
  • Balanced Tree
  • Dynamic Array
  • Hashed Array Tree
  • Linked List
  • Random Access List

Queue

Stack

• Last in, first out (LIFO)
• Operations
  • push (aka. append)
  • pop
• Useful for tasks divided into sub-tasks
  • Tracking tokens while parsing
• Concrete Implementation
  • Dynamic Array
  • Linked List

---

🧑‍🏭 Algorithms

Backtracking

• Incrementally builds candidate solutions & backtracks/abandons candidate when it's no longer viable.
• Ideal for constraint satisfaction problems.
  • Crossword
  • Eight Queens
  • Graph/Map Coloring
  • Sudoku

Sorting

Comparison-based

• Determines if "key" is less, equal, or greater than another.
• Typical sorting algorithm in standard libraries.
• Most optimal time complexity for worst-case: O(n log n)

Heapsort

• In-place; unstable
• Slower than quicksort in practice.
• Time complexity
  • Best: O(n) equal keys; O(n log n) distinct keys
  • Average / Worst: O(n log n)
• Auxiliary space complexity
  • Worst: O(1)

Quicksort

• Divide-and-conquer / recursive algorithm; typically unstable.
• Ideal pivot point is middle value -- for guaranteed O(n lg n) for sorted data.
• Time complexity
  • Best / Average: O(n * log n)
  • Worst: O(n^2)
• Auxiliary space complexity
  • Naive: O(n)
  • In-place: O(log n)

Streaming

• Processes input as sequence; non-random access.
• May produce approximate results.
• May make multiple passes over input.
• Works with limited (logarithmic) memory sizes.

Boyer–Moore Majority Vote

• Finds majority element(s)

---

📦 Data Structures

Arrays

• An array is a contiguous sequence of the same type.
• A memory buffer is (pre)allocated for all elements.
• Random access of any element (via index).
• Lookup by index: O(1) time
• Lookup by value: O(n) time
• Dynamic Array
  • Occasionally resized (copies elements; typically faster than dynamic allocations required by linked list).
  • Typical "array" type for scripting languages (typically with static array(s) utilized internally).
  • Insertion / Deletion: Amortized O(1) | O(n) time
• Static Array
  • Cannot be resized at runtime; must re-allocate buffer & copy.
• String
  • Typically a read-only array of characters.
• Variable-Length Array
  • Length determined at runtime.
  • Not growable; generally preferable to use a dynamic array instead because it's growable.

Linked List

• Each element dynamically allocated (typically slower than occasional copies required by dynamic array).
• Complexities:
  • Lookup: O(n) time
  • Insertion / Deletion: O(1) time

---

🎨 Design

• Design code before writing:
  • To have a plan & avoid getting stuck.
  • To collaborate on approach for solution.
  • Because jumping straight into coding, on large projects, is a bad idea.

---

🗺️ Other Resources

• Example Sorting Implementations - Neetcode
• Algorithms - Kahn Academy (Cormen/Balkcom)
• VisuAlgo - visualising data structures and algorithms through animation
• ICPC Past Problems - international collegiate programming contest
• Writing Clear Code - introcs.cs.princeton.edu

📚 Books

IEEE/ACM Undergraduate CS Course Recommendations

• History of Curricular Guidelines
• Computer Science Curricula 2023

Competitive Programmer's Handbook

• github
• CSES Problem Set

Introduction to Algorithms

• Third Edition
  • CLRS Solutions - walkccc

Algorithms, 4th Ed

• Algorithms (Sedgewick, Wayne) - playlist, 45 videos
• Algorithms & Data Structures – Princeton COS 226 (Java) - playlist

The Algorithm Design Manual

• CSE 373 - Analysis of Algorithms - course homepage
  • CSE373 - Analysis of Algorithms - 1997 SBU - playlist
  • CSE373 - Analysis of Algorithms - 2007 SBU - playlist
  • CSE373 - Analysis of Algorithms - 2012 SBU - playlist
  • CSE373 - Analysis of Algorithms - 2016 SBU - playlist
  • CSE373 - Analysis of Algorithms - Fall 2020 - playlist
• CSE547 - Discrete Mathematics - 1999 SBU - playlist
• CSE 392 - Programming Challenges - course homepage
  • COMP300E - Programming Challenges - 2009 HKUST - playlist
  • Lecture Slides
  • Online Judge - problem sets

Programming Interviews Exposed

Cracking the Coding Interview

• Solutions - 6th edition
• Solutions - 5th edition
• Behavioral - prep sheet
• Coding - flow chart
• PM - interview questions

Beyond Cracking the Coding Interview

• Boosters
• Question Landscape
• Catalog of DSA Topics
• Interview Checklist
• Post Mortem Exmple Log
• Post-Mortem
• [Python] Interview Cheat Sheet
• Nine Free Chapters
• Set & Map Implementations
• Monotonic Stacks & Queues
• Union-Find
• All problems, solutions & test cases

Videos

• Algorithms 1 - Stanford
• Algorithms 2 - Stanford

• BINARY TREES
  • Binary tree traversal - breadth-first and depth-first strategies - mycodeschool
• HASH TABLES
  • Design Hashmap - Neetcode
  • Intro to Hash Tables and Dictionaries - CS Dojo
• HEAPS
  • Heaps in 3 minutes — Intro - Michael Sambol
• LOGARITHMS
  • Logarithms... How? - NancyPi
    • log2(n) => 2x = n
  • Log base2 using calculator
    • log2(n) = ln(n) / ln(2)
• QUICKSORT
  • Complete Quicksort Overview - CS Dojo
  • Quicksort algorithm - mycodeschool