This repository contains implementations of popular data structures and interview questions implemented in Python.

Each data structure has its own separate README with related explanations and links for further reading (including ones to YouTube videos).

This project is my attempt to document the materials I have studied on my journey to understand data structures and also prepare for interviews.

A data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

The explanations of the data structures below are from Oleksii Trekhleb's Project

B - Beginner, A - Advanced

• B Linked List
• B Circular Linked List
• B Doubly Linked List
• B Circular Doubly Linked List
• B Queue
• B Stack
• A Heap
• A Tree
  • A Binary Tree
  • A Binary Search Tree
  • A AVL Tree

This section categorizes coding interview problems into a set of 16 patterns. Under each pattern there will be a specific category of problems to solve. The goal is to develop an understanding of the underlying pattern, so that, we can apply that pattern to solve other problems.

• Sliding Window
• Two Pointers
• Fast & Slow Pointers
• Merge Intervals
• Cyclic Sort
• In-Place Reversal of Linkedlist
• Breath First Search
• Depth First Search
• Two Heaps
• Subsets
• Modified Binary Search
• Top K Elements
• K Way Merge
• Topological Sort
• Dynamic Programming Patterns

EPI is an invaluable book textbook presents a comprehensive introduction to modern competitive programming.
Below are solutions & questions found under various topics in the book.

• Recursion

  • Greatest Common Divisor
  • Towers Of Hanoi
  • Permutations
  • Power Set
  • Subset Of Size
  • Kth Node in Inorder Traversal
  • Generate Palindromic Decompositions
  • Generate Binary Trees
  • Compute Right Sibling Tree

• Binary Trees

  • Binary Tree Traversal
  • Is Binary Tree Height Balanced
  • Is Binary Tree Symmetric
  • Lowest Common Ancestor
  • Lowest Common Ancestor With Parent Pointers
  • Sum root to leaf
  • Root to leaf path with specified sum
    • Root to leaf path sum (All Paths)
  • Inorder Traversal Without Recursion
  • Preorder Traversal Without Recursion
  • Kth Node in Inorder Traversal
  • Compute Successor
  • Inorder Traversal in Constant Space
    • Preorder Traversal in Constant Space
    • Postorder Traversal in Constant Space
  • Reconstruct Binary Tree
  • Reconstruct Binary Tree
    • Reconstruct Binary Tree 2
  • Form a LinkedList From Leaves Of Binary Tree
    • Form a LinkedList From Leaves Of Binary Tree 2
  • Compute Exterior of Binary Tree
  • Compute Right Sibling Tree

• Binary Search Trees

  • Search Binary Tree
  • Check If Binary Search Tree Satisfies BST Property
    • Check If Binary Search Tree Satisfies BST Property - Solution 2
  • Find the First Key Greater Than A Given Value In A BST
  • Find The K Largest Elements In A BST
    • Find The K Largest Elements In A BST - Solution 2
    • Find The K Largest Elements In A BST - Solution 3
  • Compute The LCA In A BST
  • Reconstruct A BST From Preorder Traversal Data
  • Find The Closest Entries In Three Sorted Arrays
    • Reconstruct A BST From Postorder Traversal Data
  • Reconstruct A BST From Inorder Traversal Data
  • Enumerate Numbers Of The Form a + b sqrt2
    • Enumerate Numbers Of The Form a + b sqrt2 - Solution 2
  • Build A Minimum Height BST From A Sorted Array
    • Build A Minimum Height BST From A Sorted Array - Solution 2
  • Test If Three BST Nodes Are Totally Ordered
  • The Range Lookup Problem
  • Add Credits

• Heaps

  • Merge Sorted Arrays
  • Sort An Increasing Decreasing Array
  • Sort An Almost Sorted Array
  • Compute the K closest Stars
  • Compute Median From A Stream
  • K Largest Elements In A Max Heap
    • K Largest Elements In A Max Heap - Solution 2

• Linkedlist

  • Merge Two Sorted Lists
  • Merge Two Sorted Doubly LinkedList
  • Reverse A Sublist
    • Reverse A Sublist - Solution 2
    • Reverse A Singly LinkedList
  • Reverse Every K Sublist
  • Test For Cyclicity
  • Find The Start Of A Cycle In A LInkedList
    • Find The Start Of A Cycle In A LInkedList - Solution 2
  • Test For Overlapping List - Lists Are Cycle Free
  • Test For Overlapping List - Lists May Have Cycles
  • Delete Node From Singly Linkedlist
  • Remove Kth Last Element From List
  • Remove Duplicates From Sorted Lists
  • Implement Cyclic Right Shift For Singly LinkedList
  • Even Odd Merge
  • Test If Singly LinkedList Is Palindromic
  • Implement List Pivoting
  • Add Two LinkedLists

• Two Sum
• Best Time To Buy And Sell Stock
• Contains Duplicate
• Product of Array Except Self
• Maximum Subarray

E - Easy, M - Medium , H - Hard,

• Recursion
  • M Longest Univalue Path

• Binary Trees
  • E Binary Tree Inorder Traversal
  • E Same Tree
  • E Symmetric Tree
  • E Maximum Depth of Binary Tree
  • E Convert Sorted Array to Binary Search Tree
  • E Balanced Binary Tree
  • E Minimum Depth of Binary Tree
  • E Path Sum
  • E Binary Tree Preorder Traversal
  • E Binary Tree Postorder Traversal
  • E Invert Binary Tree
  • E Lowest Common Ancestor of a Binary Search Tree
  • E Binary Tree Paths
  • E Sum of Left Leaves
  • E Find Mode in Binary Search Tree
  • E Minimum Absolute Difference in BST
  • E Diameter of Binary Tree
  • E Binary Tree Tilt
  • E Subtree of Another Tree
  • E Construct String from Binary Tree
  • E Merge Two Binary Trees
  • E Average of Levels in Binary Tree
  • E Two Sum IV - Input is a BST
  • E Second Minimum Node In a Binary Tree
  • E Minimum Distance Between BST Nodes

A list of popular algorithms asked during Interviews

• Graph Algorithms
• Greedy Algorithms
• Sorting Algorithms
• General Algorithms

A simple crash course to get you up and started with recursion

• Recursion With Strings
• Recursion With Numbers
• Divide & Conquer

▶ Data Structures and Algorithms on YouTube

Big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows. On the chart below you may find most common orders of growth of algorithms specified in Big O notation.

Source: Big O Cheat Sheet.

Below is the list of some of the most used Big O notations and their performance comparisons against different sizes of the input data.