Data Structures & Algorithms, Level-up for Coding Interviews

Explore arrays and vectors as dynamic, contiguous data structures in c++, with doubling growth, o(1) access, and passing by value versus by reference.

Learn to use the C++ vector STL with a hands on demo: create vectors, inspect size and capacity, push back elements, print them, and initialize with a fill constructor.

Explore 2d vectors as an alternative to 2d arrays, construct a vector of vectors with varying row lengths, and learn iteration, printing, and updating techniques using for and foreach loops.

Learn to submit coding exercises on Udemy, implement the given fizzbuzz function inside the template, and see how your solution is judged against tests.

Find two distinct numbers in an array that sum to a target S, using brute force, sorting with binary search, or a hash set for linear time.

implement the pair sum problem using an unordered set and a vector to return the matching pairs; check the complement before inserting the current element to avoid duplicates.

Solve the triplets problem by finding all distinct triplets that sum to a target sum, with internal and overall sorting in ascending order, using sorting and two-pointer techniques.

Sort the array, then use a two-pointer approach to find triplets that sum to the target, collecting and printing all valid triples.

Identify peaks in an array of distinct integers and calculate the longest mountain width by expanding left and right from each peak, achieving linear time.

Implement the highest mountain function by identifying peaks and counting contiguous elements to the left and right, updating the largest peak length while avoiding segmentation faults.

Uncover how to find the longest band in an array by forming the longest sequence of consecutive numbers after reordering, using sorting or an O(n) hash set approach.

Explore solving the longest band problem with an unordered set, starting chains from elements lacking a left neighbor and extending right to achieve O(N) time.

Compute trapped rain water on an elevation map using the min of left max and right max minus the bar height, with left and right max arrays in linear time.

Implement the rainwater trapping solution by computing left max and right max arrays from the heights, then accumulate water using the minimum of these bounds.

Identify smallest subarray to sort so the whole array becomes sorted; if already sorted, return -1 -1; use linear time to find the out-of-order min and max and their positions.

Implement the subarray sort solution by locating the smallest and largest out-of-order elements, then determine their left and right indices to sort the subarray.

Learn how to compute the minimum number of swaps to sort an array by building a value-to-position mapping, identifying disjoint cycles, and summing cycle lengths minus one.

Learn cycle-based solution to the minimum swaps problem: pair each element with its original index, sort by value, and count swaps as cycle length minus one using a visited array.

Compare character arrays and the string class in C++ and learn dynamic storage. Use getline for input, vector of strings for multiple inputs, and loop over each character.

Use the string class to search for a word inside a paragraph with the find function and obtain the first occurrence index, then locate subsequent occurrences.

Master space replacement by converting spaces to %20 using an in-place, right-to-left single-pass approach, counting spaces and shifting characters to accommodate extra space.

Execute an in-place space replacement by counting spaces, computing the final index, and performing a reverse pass to shift characters and insert %20, ensuring null termination.

Learn how tokenization splits a string by delimiters using a C++ stringstream and getline to extract tokens into a vector.

Strtok tokenizes a string by returning one token per call, starting at the input and using a static variable; call it first with the string, then null on subsequent calls.

Design a custom string tokeniser that scans left to right, uses a static state to track input, and builds tokens in a dynamic array until delimiters are reached.

We learn to sort strings by column keys formed from space-separated fields, using numeric or lexical comparisons, with an optional reverse and precomputed key pairs.

This lecture presents a string key sort implementation that reads lines, tokenizes input, builds a vector of string pairs, and sorts by numeric or lexicographic keys with optional reversal.

Learn to check whether the second string is a subsequence of the first using a two-pointer approach, achieving linear time O(m+n) instead of the exponential subset generation.

Implement the isSubset function using a two-pointer approach to determine whether the second string is a subset of the first by matching characters from the end.

Learn to generate all subsequences of a string using recursion, with a note on bit masking, then sort the results by length and, if tied, by lexicographic order.

Write a recursive solution to generate all subsequences of a string, using base and recursive cases, including or excluding each letter, building outputs, and sorting by length and lexicography.

Explore bit manipulation with bitwise operators like and, or, xor, and not, and learn how binary representations and two's complement enable fast operations such as 5, 7, and 8.

Explore binary left shift, which multiplies a number by 2^B, and right shift, which divides by 2^B, with concrete examples from five and ten.

Learn to check odd or even using a bitwise operator. Use the last bit (x and 1) to determine parity, with an example showing odd and even results.

Get the i-th bit of a number using bitwise operations. Create a mask by left shifting 1 i times and use it with the number to yield 1 or 0.

Set the i-th bit of a number using a left-shifted mask and bitwise OR. Update n by reference or return the new value, illustrated with five becoming seven.

Learn to clear the i-th bit by creating a mask with 1 << i, negating it, and using bitwise AND to zero only that bit in a number.

Learn to update the i-th bit by clearing it, then applying a mask from value left shifted by i to set or clear the bit.

Clear the last i bits of a number by left-shifting minus one to form a mask and applying a bitwise and with the original number.

Learn to replace bits between indices i and j in a 32-bit number with bits from m by clearing the range, creating a mask, left-shifting m, and or-ing with n.

Learn to determine if a number is a power of two using a bitwise and with n minus one, a fast order one check.

Count set bits in a number using bitwise operations, tracking the last bit with n & 1 and removing it by right shifting, with a loop running in O(log n).

Count set bits efficiently with the n and n minus one hack, removing one set bit each iteration. The loop runs once per set bit, as illustrated by examples.

Explore fast exponentiation using binary representation and bit masking. Learn to compute powers in O(log n) by iteratively squaring and multiplying when bits are set.

Convert a decimal number to binary using repeated division by two, capturing remainders and assembling the binary digits via powers of two.

Master sliding window techniques, reducing complexity from O(n^2) to O(n). Explore fixed windows of length k and variable windows with two pointers, using deques to maintain state.

Explore the housing problem by finding all continuous subarrays whose sum equals k using a sliding window two-pointer approach, achieving linear time and constant space.

Explore the window approach to find subarrays summing to k by expanding and contracting the window, tracking the current sum, and printing the i to j-1 window.

Explore the unique substring problem by applying a sliding window approach with two pointers and a hash map to track last occurrences, expanding or restarting windows to maximize length.

Implement the unique substring problem using a sliding window and hash map to track last occurrences, update start and max length, and return the corresponding substring.

Discover how to find the smallest window in a big string that contains all characters (including duplicates) of a small string, using a sliding window with frequency maps.

Learn a sliding window algorithm that uses frequency maps for the pattern and string, expands and contracts the window, and returns the smallest valid substring.

learn how merge sort uses divide and conquer to recursively sort an unsorted array's left and right subarrays. then merge them with two pointers into a single sorted array.

Learn to implement merge sort with a recursive approach that splits at the midpoint into left and right parts, merges with a temporary vector, and copies back.

Explore the inversion count problem on arrays, moving from brute force to a divide-and-conquer merge-sort approach that counts left, right, and cross inversions for an O(n log n) solution.

Learn a merge-based inversion count algorithm that tallies left inversions, right inversions, and cross inversions to produce the total, updating the count as elements are copied during merge.

Learn quicksort, a divide-and-conquer sorting algorithm that uses a pivot to partition an array into elements less than and greater than the pivot, then recursively sorts each part.

Implement the quicksort algorithm by writing the partition function and the recursive quicksort calls. Manage base cases and pivot placement for left and right partitions.

Learn to find the kth smallest element with quickselect using partition and pivot, building on quicksort with an array of distinct integers.

quick select code uses a partition from quicksort to find the k-th smallest element by pivot index, recursing left or right based on k, with zero-based indexing.

Learn to form the lexicographically smallest concatenation of strings by sorting with a custom comparator that compares x+y and y+x, guided by merge sort to build the final result.

Implement the smallest string traversing problem by sorting strings with a custom comparator that compares x+y and y+x, then concatenate the sorted array to produce the output like aabaab.

Explore the sparse search problem on a sorted array with empty strings, and learn a modified binary search that uses nearest non-empty strings to efficiently locate a key.

Implement sparse search by performing a modified binary search over an array with empty strings, adjusting mid to the nearest non-empty, and returning the index of the key or -1.

Discover how binary search, a divide and conquer technique, solves multiple problems with logarithmic time complexity. Apply its simple code patterns to efficiently locate a key and explore practical applications.

Learn to count frequency of a target in a sorted array using binary search by finding the first and last occurrences and computing frequency as last minus first plus one.

Find the lower bound of a key using a binary search, updating the answer whenever a match is found and searching the left part to locate the smallest index.

Learn to count frequency efficiently in C++ by using lower_bound and upper_bound from the standard template library; compute frequency as upper_bound minus lower_bound in one line of code.

Discover how to search a rotated sorted array with a modified binary search, using pivot-based halves and conditional decisions to locate an element's index efficiently.

Explore the rotated search implementation using a modified binary search, splitting the array around the pivot and narrowing the search by comparing against the left and right sorted parts.

Find the square root of a number to p decimal places using binary search on a monotonic search space, without library functions, refining digits with a linear search.

Implement the square root using binary search from 0 to n, then refine with a linear search for decimals to achieve the floating-point result.

Explains solving the aggressive cows problem by binary searching the maximum minimum distance between birds placed in nests along a line, using a monotonic feasibility check.

Sort nest positions, apply a binary search on the minimum separation, and use a canPlace feasibility check to maximize the distance between birds in nests.

Learn to find a pair with minimum absolute difference between two arrays using sorting and lower bound, yielding an efficient O(m log m + n log m) approach.

Sort one array, then for each element in the first array find the closest element in the second array using lower_bound, evaluating left and right neighbors to minimize the difference.

Explore the game of greed by partitioning an array into k subarrays to maximize the minimum sum each friend receives, using binary search on a monotonic feasibility predicate.

Learn to solve the game of greed by partitioning an array into k parts to maximize the minimum sum, using binary search to check if such partitioning is possible.

Recap recursion by showing how to break a problem into its smallest case. Define base and recursive cases, and follow a depth-first, left-to-right call tree managed by a stack.

Explore the ladder problem with steps of 1, 2, or 3, derive f(n)=f(n-1)+f(n-2)+f(n-3), and examine base cases and overlapping subproblems leading to dynamic programming.

Learn to count ways with a recursive approach: base case n equals 0 returns 1, recursive calls n-1 and n-2, and negative n returns 0; dynamic programming handles overlapping subproblems.

Explore how to generate all subsequences of a given string using a recursive brute-force approach, by including or excluding each character and forming subsets.

Learn to solve subset sum problems for non-negative integers by counting how many subsets sum to a target X. Use a recursive include-or-exclude approach with clear base cases.

Count subsets that sum to x in an array using a recursive include/exclude approach, with base cases, and hint at dynamic programming for optimization.

Learn to generate all balanced parentheses strings for n pairs using recursive backtracking, enforcing opening before closing and pruning invalid branches to produce valid expressions.

Explore a recursive generate brackets solution that builds valid bracket strings by tracking open and close counts, uses backtracking and a base case to avoid mutating the output array.

Learn to generate all possible strings from a digit sequence using the keypad mapping, by reading input digit by digit and using recursion with backtracking.

Build a recursive print keypad output function that converts a numeric string into all possible letter combinations using keypad mappings, skipping 0 and 1, and printing results.

Learn to generate all permutations of a string using recursion and backtracking with character swaps. Restore the original array after each recursive call and print permutation at the base case.

Explore the n-queen problem and backtracking approach to place one queen per row on an n by n board so that no queens attack each other, printing a valid configuration.

Implement an n-queen solver with backtracking. Build a board, place one queen per row, use can_place to check column and diagonals, print on success, and backtrack otherwise.

Explore the n queen problem with a backtracking solution that builds a board, places queens row by row, checks the column and diagonals, backtracks when needed, and prints valid configurations.

Explore solving Sudoku on a 9x9 grid by backtracking and recursion, filling empty cells (zeros) with valid digits 1-9 while enforcing row, column, and subgrid constraints.

Learn to implement a sudoku solver using backtracking on a 9x9 grid, replacing zeros with valid numbers while enforcing row, column, and 3x3 subgrid constraints.

Explore the linked list concept, including non-contiguous memory, nodes with next pointers, head, and dynamic allocation, and outline basic operations like insertion, deletion, searching, and printing.

Learn how to implement a linked list with insertion at head and print operations, using a node class with data and next, managing the head pointer, and pass-by-reference concepts.

Practice inserting a node in the middle of a linked list by traversing to the prior position, creating a new node, and updating next pointers; handle head insertion.

Explore reversing a linked list with recursive and iterative approaches. Learn how to flip pointers, update head and tail, and handle base cases and null termination.

Implement a recursive reverse of a linked list by handling base cases for null or single-node lists, then recursively reverse the rest and reconnect the nodes.

Explore reversing a linked list using an iterative approach. Track current, previous, and temp nodes to safely update links and return the new head.

Iteratively reverse a linked list using previous, current, and a temp pointer to store next, update links, and set head to previous for order n time and order one space.

Reverse every k nodes in a linked list by reversing the first k nodes, recursively solving the remainder, and connecting the parts to build the final list.

Apply a recursive approach to the k-reverse problem by reversing the first k nodes of a linked list, using a base case, and reconnecting the reversed segment to the remainder.

merge two sorted linked lists by adjusting pointers without creating new nodes, compare a.data and b.data with a two-pointer approach and recursion, handling null end cases to return merged list.

Implement the merge function for two sorted linked lists using base cases and a recursive step with a temporary head pointer, merging by smaller value and returning the merged list.

Learn the runner technique in linked lists by using two pointers, fast and slow, to find the midpoint efficiently and apply this logic to other problems.

Learn to sort a linked list with merge sort by modifying pointers without creating a new list, dividing at midpoint, recursively sorting parts, and merging for O(n log n) time.

Implement merge sort on a linked list by handling zero or one node, splitting at the midpoint with slow and fast pointers, and merging the sorted halves.

Review stacks, queues, and deques, detailing their LIFO and FIFO behavior, push and pop operations, and how they enable BFS, level-order traversal, and iterative solutions for recursion.

Apply a stack-based approach to check balanced parentheses. Push opening brackets and pop on matching closings, ignoring operands and operators, and verify the stack is empty.

Implement a balanced parentheses check using a stack that pushes opening brackets and pops on matching closings. Return true if the stack is empty at the end.

Identify redundant parentheses in a balanced expression by using a stack to track operands and operators; if no operator exists inside brackets, mark them as redundant.

Use a stack-based approach to detect redundant parentheses in expressions. The method pops until the opening bracket and checks for an operator, returning true when no operator exists inside.

Learn to find the first non-repeating letter in a running stream using a frequency map and a queue. The method outputs the current non-repeating character or -1 if none.

Implement a streaming solution to find the first non-repeating character using a queue and a frequency map, reading input until a dot and outputting the result or -1.

Solve the sliding window maximum problem using a deque to maintain a monotonic queue, producing the maximum for every window in linear time.

Build a function to simplify a file path by normalizing absolute and relative paths, collapsing multiple slashes and dot-dot segments, and preserving root constraints to produce an equivalent path.

Tokenize the path by slashes, filter out dot and dot-dot tokens, and use a stack to resolve absolute and relative paths into a simplified result such as x, y, z.