Algorithms for Coding Interviews

Learn the basics of complexity analysis for coding interviews, distinguishing time and space complexity, using Big-O notation to compare solutions and justify design choices based on performance and memory.

Examine constant time complexity, where the number of operations stays fixed as input size grows, exemplified by circle area calculation; the lecture previews linear time complexity in the next video.

Explore linear time complexity and how a linear search demonstrates O(n) performance by checking each element in an array, worst-case requiring n questions.

Analyze how polynomial time complexity grows, using quadratic and cubic time as examples like bubble sort and matrix multiplication.

Explain how binary search on a sorted array achieves logarithmic time by halving the data size each iteration, giving O(log n) and setting up exponential time discussion next video.

Explore exponential time complexity through recursive fibonacci, where each call doubles operations, yielding about 2^n time; understand backtracking as a brute force approach common in coding interviews.

Identify time and space complexity and choose the right data structure. Compare alternative solutions, including exponential backtracking, using OmegaUp problems to learn which is better.

Read the blame problem on OmegaUp, where each guest points to someone; for every starting guest, identify who buys the cake after two interrogations, and plan the approach before coding.

Demonstrate a naive blame-game simulation by interrogating people in sequence, using a set to track interrogated individuals, and showing the O(n^2) complexity when starting from each person.

Learn a naive approach to the blame problem in coding interviews by implementing getGuilty in C++, using a set and vector, with O(n^2) time and O(n) space.

Identify cycles in the blame graph and optimize with memoization to determine the guilty person in linear time, avoiding quadratic repetition.

Demonstrates an optimal linear, memoized method to determine the guilty person, using vectors for blame and results, a set to track interrogations, and cycle detection.

Identify the most common data structures used in interviews, including arrays, and learn when to apply them based on time complexity for insert, remove, retrieve, and search operations.

Learn how vectors (arrays) offer constant-time index access, while insertions and removals in arbitrary positions are linear; back insertions and last removals are constant time, with a C++ push_back example.

Explore the linked list data structure with head and tail pointers, where front or back insertions and removals are constant time, while middle insertions, removals, or searches require linear traversal.

Explore how a stack, implemented as a linked list, follows LIFO order to push and pop elements from the top, enabling constant-time top and empty checks.

Master queue fundamentals: insert at the back and remove from the front, delivering first-in, first-out order. Use this structure for unweighted graphs' shortest paths and as the base for BFS.

Explore heaps as binary trees with a root holding the largest element, supporting max-heap and min-heap variants. Learn insertion and removal in logarithmic time and constant-time root access via priority_queue.

Review interview tips and a concise data-structure overview, emphasizing operation time complexity for vectors, and when to use sets, maps, or heaps for k largest or smallest elements.

Compute the average of the best K scores after each new player score. Return the average of the current values when fewer than K players have appeared.

Use a min-heap to maintain the top k players, updating the sum for constant time average of the best scores while performing insertions in logarithmic time.

Master top-k selection by maintaining a min-heap (via negation in a max-heap). Sum scores and output the average in two decimals with n log k time.

Compute the integer part of the average of the last k numbers as each new number arrives; if fewer than k numbers exist, use the average of all seen numbers.

Avoid storing N numbers by maintaining a queue of the latest K numbers and a running sum to compute the integer part of the average in O(1), using O(K) space.

Use a queue to maintain the latest k numbers from n inputs, updating a running total and printing the average in O(n) time and O(k) space.

Explore sets and maps (hash maps) as essential data structures for coding interviews, using sets to check element existence without a linear search and maps to count occurrences.

Explore unordered set concepts and hashing, storing unique elements in buckets for constant-time operations. Learn how equals and hash functions enable this in C++ unordered_set and Java HashSet.

The ordered set, or tree set, stores unique elements in sorted order using a balanced tree, delivering logarithmic time for insert, remove, retrieve, and search, with C++ and Java examples.

Explore the unordered map, a key‑value data structure with bucket storage and constant-time operations. See a C++ example with string keys and integer values, where iteration may yield different orders.

Explore maps and TreeMaps, sorted versions of hash maps, to maintain key-value pairs with keys sorted, using a balanced tree for logarithmic operations.

Review the data structures table, compare operations by time complexities, and justify your approach for interview decisions. Practice identifying the data structure, with maps, sets, and ordered vs unordered variants.

Find a pair of numbers in a list that sums to k and print that pair. If no pair exists, print -1; input gives n numbers and k.

Learn a linear, hash map approach to find two numbers that sum to k, avoiding the naive O(n^2) nested-loop trap; handle duplicates by ensuring at least two occurrences.

implement a hash map based solution to find two numbers that sum to k by counting occurrences and checking complements, while avoiding duplicates in linear time.

Learn to count pairs of substrings that are anagrams using sets and maps, processing multiple lowercase strings up to length 100 across queries.

Explore solving the Lufillo and anagrams problem by generating all substrings, sorting them to detect anagrams, and counting pair occurrences with a hash map, acknowledging cubic worst‑case complexity.

Implement a solution for Lufillo and anagrams by generating all substrings of each query, sorting them with STL, and counting occurrences in an unordered map.

Explore using hash maps as counters to count anagrammatic substrings by sorting substrings, revealing a cubic approach and a possible optimization with an insertion sort to avoid log n costs.

Explore essential graph theory concepts tailored for coding interviews, review key theory, analyze time complexities of graph algorithms, and solve problems with implemented solutions.

Define a graph as nodes and edges, where nodes represent entities like users or countries and edges express relationships; illustrate with borders and preview graph types ahead of algorithms.

Explore directed graphs, where edges have a direction and arrows represent that direction. See how social follow relationships illustrate one-way connections, showing who follows whom in a graph.

Define disconnected graphs and explain that no path exists between nodes, illustrated by a flight from USA to Spain; preview graph traversal and definitions of path and cycle.

Explore how a path connects a source to a destination via edges, and how a cycle returns to the starting node, while an acyclic graph has no cycles.

Learn adjacency matrix representations for graphs, including DAGs and complete graphs, where rows and columns map to nodes and a 1 marks edges, with symmetry for undirected graphs.

An adjacency list represents a graph by listing each node's adjacent nodes, such as node 0 connected to 1, 2, and 3, while disconnected nodes may have empty lists.

Compare adjacency matrix and adjacency list, highlighting constant-time connectivity checks and simple implementation for matrices. Note the matrix's O(n^2) space and sparsity, and the list's O(n+m) efficiency for sparse graphs.

Explore depth-first search (dfs) as a stack-based graph traversal that dives deep, uses a visited set to avoid repeats, and runs in O(n + m) with adjacency lists.

Implement a basic dfs on a graph using a stack and a visited set, starting from node 0 and exploring adjacent nodes with an iterator.

Learn breadth-first search (BFS) for graph traversal using a queue, visiting nodes by distance from the start, contrasting with DFS's stack and analyzing adjacency lists with O(N+M) time.

Implement a basic BFS on a graph using an adjacency list, a queue, and a visited set to visit nodes by distance to find shortest routes in unweighted graphs.

Explore when to use dfs or bfs for graph traversal and how adjacency lists, rather than matrices, aid interview problems; learn to handle non-consecutive node ids with a map.

Model upland as a graph of cities connected by roads; treat connected components as countries and compute the number of countries and the maximum city count per country.

Identify connected components of the city graph using DFS or BFS, count cities in each component, and track the maximum component size to determine the largest country.

implement a dfs on an adjacency list to count connected components (countries) and track the maximum cities per component, by reading nodes and roads and building the graph in OmegaUp.

Apply a flood fill approach to a grid puzzle: starting from Dora, move vertically and horizontally through empty spaces, avoid walls, and mark all reachable cells in the map.

Use flood fill from Dora's location, with DFS or BFS to visit all reachable cells in a 5x5 grid, marking visited cells and analyzing O(nm) time and O(1) space.

implement a flood fill algorithm for Dora the Explorer A using dfs from Dora's location on a grid, marking reachable cells with #, and validating the results.

Solve a grid-based shortest path from S to E on an N by M map with walls, using four-direction moves, returning the minimum steps or -1 if unreachable.

Use a BFS-based approach on a grid with walls to guide Dora to Boots, tracking distance with a matrix to guarantee the shortest path in unweighted steps.

Discover how to implement a bfs solution to find the shortest route on a grid with equal weights, from Dora's location to Boots' location using a distance matrix.

Explore dynamic programming as a technique that uses previously calculated values to compute new ones. Represent problems recursively, visualize their relation to prior results, and manage memory with arrays.

Learn how to compute factorials with dynamic programming by storing previous results in an array, comparing recursive and for-loop iterative approaches.

Explore dynamic programming with the Fibonacci sequence, identify the inefficiency of naive recursion, and implement a dynamic programming solution that stores results in an array to compute Fibonacci numbers efficiently.

Derive a dynamic programming solution for tiling a 2×n board using 2×1 and 2×2 dominoes, establishing F(n)=F(n-1)+2F(n-2) with base cases and array storage.

Applies dynamic programming to count lufe numbers, numbers with no two consecutive even digits. Uses states: endings with even or odd digits, with base cases for n=1 and n=2.

Develop a habit of solving problems with dynamic programming by practicing cases like knapsack, LIS, LCS, and coin change. Get interview tips on explaining DP solutions and recognizing space constraints.

solve a dynamic programming problem about flags using green, white, and red tapestries under rules: no two adjacent tapestries share a color, and white lies between green and red.

Develop a recursive approach to the flags problem, using base cases n=1 and n=2 with red and green and white between colors, then apply f(n)=f(n-1)+f(n-2) with f(1)=2, f(2)=2.

Code the fibonacci-based approach up to n and then multiply the result by 2. Use a 64-bit long long and an array or two-number approach for linear-time computation.

Tackle the STARS problem with a dynamic programming approach: assign at least one star per student, ensure higher grades get more stars than neighbors, and minimize the total.

Develop a greedy two-pass strategy for the stars problem: compute left-to-right and right-to-left star counts, then take the maximum per student and sum to minimize total stars.

Apply a greedy left-to-right and right-to-left strategy to assign stars based on grades, using L and R arrays and the max to minimize total stars with linear space.

Master backtracking, a recursive brute-force technique that explores multiple paths to find solutions and marks and unmarks elements during recursion to adapt to constraints like Sudoku.

Learn the sudoku rules on a 9x9 grid: ensure digits 1-9 appear in every row, every column, and each 3x3 submatrix, and apply this approach to fill the board.

Explore a backtracking, brute-force approach to solving sudoku by filling empty cells with valid digits, using a recursive grid traversal and cell enumeration to guide the algorithm.

We implement a backtracking Sudoku solver using a cell ID to traverse the 9x9 grid, trying digits 1–9 for empty cells and backtracking when needed.

Learn to solve Sudoku with backtracking by implementing a 9x9 solver that uses isInRow, isInColumn, and isInSubmatrix checks, prints one solution, and stops after finding it.

Identify backtracking early, discuss simpler alternatives if needed, and design the recursive function with parameters, stopping criteria, and marking rules; note exponential time and OmegaUp's Super Sudoku.

Explore solving the knapsack problem from a supermarket scenario by using backtracking to maximize cart value within weight capacity, producing a 0/1 selection vector for N products.

Explore multiple approaches to the supermarket problem, including knapsack dynamic programming, backtracking, and a bitmask solution using 2^N iterations to select products.

Apply backtracking to the supermarket cart problem by reading product weights and values, storing them in a product class, and using take-or-leave decisions to maximize cart value within weight capacity.

Implement a bitmask solution to supermarket problem by evaluating all cart configurations using a vector of Product objects, updating the best cart by weight capacity and value, and printing bits.

Practice problems and mock interviews to strengthen coding interview skills and interviewing ability, while the course will be updated with more material to boost your career.