Tag:

Anagram

ArrayLists

Arrays

INFO

A linear data structure used to store multiple values in a single variable. Arrays are foundational in programming and support indexed access, making them ideal for iteration, sorting, and manipulation.

Array Lists

Properties

• Indexed: each element has a position starting from 0
• Fixed or dynamic size depending on language
• Mutable in most languages—elements can be updated or removed
• Can store homogeneous or heterogeneous types depending on language
• Often used as the basis for more complex structures like matrices, heaps, and hash tables

Common Operations

• Access: Retrieve an element by index (arr[2] → third item)
• Update: Modify an element (arr[1] = 42)
• Append: Add to the end (arr.append(5) or arr.push(5))
• Insert: Add at a specific index (arr.insert(2, "x"))
• Delete: Remove by index or value (del arr[0], arr.remove("x"))
• Slice: Extract a sub-array (arr[1:4])
• Length: Count elements (len(arr) or arr.length)
• Sort: Rearrange elements (arr.sort())

Binary

BinarySearchTree

INFO

a specialized form of binary tree that maintains a sorted hierarchical structure

Each node satisfies the following properties:

• Value Property:
  Each node contains a unique value (or key).
• Left Subtree Rule:
  All values in the left subtree of a node are less than the node’s value.
• Right Subtree Rule:
  All values in the right subtree of a node are greater than the node’s value.
• Recursive Structure:
  Both the left and right subtrees must also be binary search trees.
• No Duplicate Values (in standard BSTs):
  Typically, duplicate values are not allowed, though some implementations handle them with custom rules.

Binary Search Tree

Properties

• The left subtree contains only nodes with keys less than the node’s key
• The right subtree contains only nodes with keys greater than the node’s key
• Both left and right subtrees are also binary search trees

Common Operations

• Search: O(log n) average, O(n) worst case
• Insert: O(log n) average, O(n) worst case
• Delete: O(log n) average, O(n) worst case

BinaryTree

INFO

A hierarchical data structure in which each node has at most two children, referred to as the left and right child. Unlike BinarySearchTree, Binary Trees do not enforce any ordering constraints between node values.

Binary Tree

Properties

• Each node can have zero, one, or two children
• No requirement for left < root < right relationships
• Can be used to represent structured data like expressions, hierarchies, or traversal paths

Common Variants

• Full Binary Tree: Every node has 0 or 2 children
• Complete Binary Tree: All levels are fully filled except possibly the last, which is filled left to right
• Perfect Binary Tree: All internal nodes have two children and all leaves are at the same level
• Balanced Binary Tree: Height difference between left and right subtrees is minimized

Common Operations

• Traversal:
  • Inorder: Left → Root → Right
  • Preorder: Root → Left → Right
  • Postorder: Left → Right → Root
  • Level-order: Breadth-first traversal
• Insert/Delete: Depends on specific variant (e.g., heap, expression tree)
• Search: No guarantees on performance unless structured (e.g., BST or heap)

Use Cases

• Expression parsing (e.g., arithmetic trees)
• Hierarchical data modeling (e.g., file systems)
• Priority queues (via binary heaps)
• Tree-based traversal algorithms

Binomial

BreadthFirstSearch

INFO

A traversal algorithm that explores all neighbors at the current depth before moving to the next level. Breadth First Search (BFS) is widely used in graph traversal, shortest path algorithms, and level-order tree traversal.

More Details here: Breadth First Search (BFS)

Properties

• Explores nodes level-by-level from the starting point
• Uses a queue to maintain traversal order (FIFO)
• Guarantees the shortest path in unweighted graphs
• Requires a visited set to avoid revisiting nodes
• Time complexity: O(V + E) for graphs with V vertices and E edges

Common Operations

• Traversal: Visit all nodes in a graph or tree
• Shortest Path: Find minimum steps between two nodes
• Level Order Traversal: Traverse trees by depth
• Connected Components: Identify clusters in undirected graphs
• Cycle Detection: Check for loops in undirected graphs

CircularArrays

Combinations

Combinatorics

Complement

Counting

DeMorgan

DepthFirstSearch

INFO

A traversal algorithm that explores as deep as possible along each branch before backtracking. Depth-First Search (DFS) is widely used in graph traversal, tree algorithms, cycle detection, and topological sorting.

Depth First Search (DFS)

Properties

• Explores nodes by diving deep before moving laterally
• Can be implemented recursively or iteratively (using a stack)
• Requires a visited set to avoid revisiting nodes
• Not guaranteed to find the shortest path
• Space complexity depends on depth of recursion or stack size

Common Variants

• Pre-order DFS: Visit node → left → right
• Post-order DFS: Left → right → visit node
• In-order DFS (binary trees): Left → node → right
• Reverse DFS: Used in Kosaraju’s algorithm for strongly connected components

Common Operations

• Traversal: Visit all nodes in a graph or tree
• Pathfinding: Explore paths from source to destination
• Cycle Detection: Identify loops in directed or undirected graphs
• Topological Sort: Order nodes based on dependencies
• Connected Components: Group nodes reachable from each other

Deques

Design

INFO

These problems require you to design and implement classes that model real-world systems, behaviors, or constraints. They often involve encapsulation, state management, and method orchestration, and are common in low-level design (LLD) interviews.

Classes

Properties

• Focuses on modeling behavior and state through class interfaces
• Requires thoughtful use of constructors, access modifiers, and encapsulation
• Often involves designing multiple interacting classes
• May include constraints like immutability, thread safety, or extensibility
• Encourages use of design patterns (e.g., Singleton, Factory, State)

Common Patterns

• Singleton: Ensure only one instance of a class exists
• Factory: Abstract object creation logic
• Builder: Construct complex objects step-by-step
• State: Encapsulate varying behavior based on internal state
• Strategy: Swap algorithms dynamically via composition

Common Operations

• Define class attributes and methods
• Implement constructors and initialization logic
• Handle edge cases and invalid inputs
• Maintain internal state across method calls
• Support extensibility and testability

Greedy

INFO

A Greedy Algorithm builds a solution step-by-step by choosing the locally optimal option at each stage, aiming for a global optimum. It’s efficient and often surprisingly effective, especially in problems with greedy-choice property and optimal substructure.

Greedy Algorithms

Properties

• Locally Optimal Decisions: Chooses the best option at each step without reconsidering previous choices
• No Backtracking: Once a choice is made, it’s never revisited
• Optimal Substructure: The optimal solution to the problem contains optimal solutions to subproblems
• Greedy-Choice Property: A global optimum can be arrived at by choosing local optima
• Fast and Simple: Often faster than dynamic programming or exhaustive search
• Not Always Correct: Only works when problem structure guarantees correctness

Common Applications

• Activity Selection: Choose the maximum number of non-overlapping intervals
• Huffman Coding: Build optimal prefix codes for data compression
• Minimum Spanning Tree: Kruskal’s and Prim’s algorithms
• Dijkstra’s Algorithm: Shortest path in weighted graphs (with non-negative weights)
• Fractional Knapsack: Maximize value with divisible items
• Job Scheduling: Maximize profit or minimize lateness

Common Operations

• Sort by Heuristic: Order elements by weight, value, deadline, etc.
• Iterate & Select: Traverse sorted list, pick if valid
• Accumulate: Build partial solution (e.g., total weight, cost, path)
• Terminate Early: Stop once constraints are violated or goal is reached

HashTable

Inclusion-Exclusion

LinkedList

Math

INFO

Programming math refers to the use of mathematical concepts and operations within code to solve problems, model systems, and perform computations. It is foundational to fields like data science, graphics, machine learning, and simulation.

Math for Computer Science

Properties

• Language-agnostic: Core math operations are consistent across most languages (e.g., Python, Java, C++)
• Supports primitive types like integers, floats, and complex numbers
• Often relies on libraries for advanced functionality (e.g., NumPy, Math, SymPy)
• Enables algorithmic thinking and numerical precision
  • Floating-point behavior governed by IEEE 754

Common Operations

• Arithmetic: Basic operations (+, -, *, /, %)
  • 3 + 5 → 8, 10 % 3 → 1
• Exponentiation: Raise to a power (2 ** 3 → 8)
• Rounding & Truncation: (round(3.1415, 2) → 3.14, int(3.9) → 3)
• Absolute Value: (abs(-7) → 7)
• Comparison: (x > y, x == y) for logical branching
• Math Functions: (math.sqrt(16) → 4, math.sin(π/2) → 1)
• Type Conversion: (float(5) → 5.0, int("42") → 42)

Multichoose

Multiset

Pair

Permutations

Power-Rule

PrefixSum

Queue

INFO

A linear data structure that follows the First-In, First-Out (FIFO) principle. Elements are added at the rear and removed from the front. Queues are widely used in scheduling, buffering, and breadth-first traversal algorithms.

Queues

Properties

• FIFO ordering: the first element added is the first to be removed
• Supports dynamic or fixed-size implementations
• Can be implemented using arrays, linked lists, or built-in language structures
• Often used in operating systems, simulations, and asynchronous processing

Common Operations

• Enqueue: Add an element to the rear (queue.append(x))
• Dequeue: Remove and return the front element (queue.pop(0))
• Peek: View the front element without removing it
• isEmpty: Check if the queue is empty
• Size: Return the number of elements in the queue

Variants

• Circular Queue: Wraps around to reuse space
• Priority Queue: Elements are dequeued based on priority, not order
• Double-Ended Queue (Deque): Supports insertion/removal from both ends
• Message Queue: Used in distributed systems for asynchronous communication

Quotient-rule

Repetition

Set

Stack

INFO

A linear data structure that follows the Last In, First Out (LIFO) principle. The most recently added element is the first to be removed. It’s conceptually similar to a stack of plates: you add to the top and remove from the top.

Stack

Properties

• Operates on LIFO: Last element added is the first to be removed
• Only the top element is accessible at any time
• Supports constant-time operations for push and pop
• Can be implemented using Array Lists or linked lists

Common Variants

• Bounded Stack: Has a fixed maximum size
• Dynamic Stack: Grows as needed (e.g., via dynamic arrays or linked lists)
• Call Stack: Used by programming languages to manage function calls and local variables
• Concurrent Stack: Thread-safe stack for multi-threaded environments

Common Operations

• Push: Add an element to the top of the stack
• Pop: Remove the top element
• Peek/Top: View the top element without removing it
• IsEmpty: Check if the stack is empty
• Size: Return the number of elements in the stack

Use Cases

• Function call management (e.g., recursion tracking via call stack)
• Undo/Redo functionality in applications
• Syntax parsing (e.g., matching parentheses or tags)
• Depth-first search (DFS) in graph traversal
• Backtracking algorithms (e.g., maze solving, puzzle solving)

Stars-And-Bars

String

INFO

A sequence of characters used to represent text. It is one of the most fundamental data types in programming and is typically enclosed in quotes.

String

Properties

• Immutable in many languages (e.g., Python, JavaScript), meaning once created, it cannot be changed
• Indexed: each character has a position starting from 0
• Can contain letters, digits, symbols, and whitespace
  • characters represented in ASCII

Common Operations

• Concatenation: Combine two or more strings ("Hello" + "World" → "HelloWorld")
• Substring: Extract part of a string ("Hello"[1:4] → "ell")
• Search: Find characters or patterns ("apple".find("p") → 1)
• Replace: Substitute characters or substrings ("cat".replace("c", "b") → "bat")
• Length: Count number of characters (len("hello") → 5)

Subset

Tree

INFO

A hierarchical data structure composed of nodes connected by edges, where each node may have child nodes but only one parent (except the root). Trees are used to model relationships, organize data, and support efficient traversal and search operations.

Tree

Properties

• Rooted: One node is designated as the root; all others descend from it
• Parent–Child Relationship: Each node links to its children via edges
• Leaf Node: A node with no children
• Height: The longest path from root to any leaf
• Depth: Distance from root to a given node
• Subtree: Any node and its descendants form a subtree

Common Types

• Binary Tree: Each node has at most two children
• Binary Search Tree (BST): Left child < parent < right child
• Balanced Tree: Height difference between subtrees is minimized
• AVL / Red-Black Trees: Self-balancing variants of BSTs
• N-ary Tree: Nodes can have more than two children
• Trie: Specialized tree for string prefix matching

Common Operations

• Traversal:
  • In-order: Left → Root → Right
  • Pre-order: Root → Left → Right
  • Post-order: Left → Right → Root
  • Level-order: Breadth-first traversal
• Insertion: Add a node while maintaining structure
• Deletion: Remove a node and restructure if needed
• Search: Locate a node by value or condition
• Height/Depth Calculation: Measure structural properties

TwoPointers

INFO

A technique that uses two indices to traverse a data structure—often in opposite directions or at different speeds—to solve problems more efficiently. It’s commonly used in arrays, strings, and linked lists to reduce time complexity from O(n²) to O(n).

Two Pointers

Properties

• Uses two pointers (e.g., left and right, or slow and fast)
• Often applied to sorted arrays, subarray problems, and linked list traversal
• Can be used for window-based problems, cycle detection, and partitioning
• Reduces nested loops into linear scans

Common Patterns

• Converging Pointers: Start at both ends and move toward the center
  • Used in palindrome checks, pair sums, and partitioning
• Sliding Window: Move both pointers forward to maintain a dynamic range
  • Used in substring problems, max/min subarrays
• Fast–Slow Pointers: One pointer moves faster than the other
  • Used in cycle detection, finding middle of linked list

Common Operations

• Pair Sum: Find two numbers that add up to a target (left + right)
• Reverse: Swap elements from both ends (arr[left], arr[right] = arr[right], arr[left])
• Window Expansion/Contraction: Adjust pointers based on constraints
• Cycle Detection: Use fast and slow pointers to detect loops in linked lists