Algorithms Data Structures in Java #2 (+INTERVIEW QUESTIONS)

Explore prefix trees, or tries, for implementing associative arrays with string keys, enabling search, insert, and sorting by key length, and compare their memory tradeoffs with hash maps.

Discover how a trie enables fast autocomplete by listing all words that start with a given prefix through a traversal from that prefix node.

Explore prefix trees as associative arrays by storing string keys and values at leaf nodes, then perform lookups by traversing letters and spotting misses. Compare with hash tables for efficiency.

Learn to implement and validate trie search operations by traversing from the root, mapping characters to indices, and ensuring the final node is a leaf for valid keys.

Implement an associative array with a trie by storing key-value pairs at leaf nodes and traversing key letters during insert and search. Compare this to hash tables for string keys.

Explore implementing the longest common prefix with a trie for ip routing. Traverse single-child nodes to build the prefix, and use a 126‑child ascii trie to handle ip characters for routing decisions.

Explore ternary search trees, a memory-efficient alternative to tries, where each node stores a character and value and has left, middle, and right children. Balance via rotations when needed.

Implement a ternary search tree from scratch by building nodes with left, middle, and right children, storing characters and optional values, and inserting via a recursive, index-based method.

Implement a recursive get method for a ternary search tree to retrieve values by key, navigating left, middle, and right based on key characters and returning null on misses.

Explore recursion and stack memory as you visualize inserting the key car with value 20 into a ternary search tree, tracing stack frames, indices, and backtracking.

Explore how to solve boggle using tries and ternary search trees, implementing a depth-first backtracking search on a 2d grid with four neighbors to form valid words.

Implement a Boggle game using a ternary search tree to validate words on a three by three board, with put and isWord methods.

Implement the boggle game using a two-dimensional board and a visited matrix, traverse with depth-first search and backtracking, and store words in a ternary search tree.

Implement a brute force substring search in Java, returning the pattern’s starting index. Loop through the text, compare with the pattern, break on mismatch, and return index or -1.

Implement the Rabin-Karp substring search in Java using a 26-letter alphabet and a 31-prime modulo, with rolling hashes, precomputed pattern hash, and a sliding window verification.

Master the knuth-morris-pratt algorithm for substring search, achieving linear time by preprocessing the pattern into a pi table and using prefix and suffix insights to avoid extraneous comparisons.

Compare substring search algorithms including naive, Boyer-Moore, KMP, and Rabin-Karp, noting why the Z algorithm is not considered, with attention to running times and patterns.

Discover how strings are immutable in java, why concatenation creates new objects, and how the string constant pool and garbage collection affect memory, plus stringbuffer and stringbuilder efficiency.

Compare the string class and string builder for reversing text; implement reverse with a loop from length-1 to 0 using charAt and StringBuilder append for linear time and better memory.

Generate all prefixes of a given string using substring from the beginning, store them in an array list, and return the list with linear running time.

Understand stable versus unstable sorting, where stable algorithms preserve the relative order of equal values, crucial for multi-column sorts like sorting by name and company.

Learn how adaptive sorting algorithms exploit runtime information and local order to beat general n log n in nearly sorted data, with insertion sort and shell sort as key examples.

Implement shell sort in Java by using gap-based insertion steps, progressively reducing the gap until a final insertion sort, with code reuse from insertion sort.

Introduces Quicksort as a divide-and-conquer sorting algorithm with pivot-based partitioning. Explains in-place operation, recursive left and right subarrays, and its average n log n time with n^2 worst case.

Learn how quicksort sorts an array by partitioning around a pivot and recursively sorting left and right subarrays. See a concrete example with swaps around the pivot.

Implement quicksort from scratch by creating a partition-based sort with a pivot, swapping elements, and recursively sorting left and right subarrays.

Shows how Quicksort's worst-case degrades to quadratic time when the largest item is repeatedly chosen as pivot, and random pivots with hybrid algorithms mitigate it.

Visualizes how merge sort uses divide and conquer, recursive calls, and base cases to split data into left and right subarrays and merge them while illustrating stack memory for frames.

Hybrid sorting algorithms like Introsort and TimSort combine quicksort with heap sort or merge sort with insertion sort for improved performance and worst-case guarantees.

Learn counting sort, a non-comparison based integer sorting method that counts key occurrences, builds a cumulative count array, and produces a stable, linear-time output suitable when key variation is small.

Learn counting sort implementation for single-digit values using a count array, an output array, and a cumulative array to achieve not in place, stable, linear time sorting.

Explore radix sort as a non-comparison, stable sorting method that overcomes counting sort limits by using counting sort to sort digits from least to most significant.

Learn how Timsort combines merge sort and insertion sort to efficiently sort small subarrays, using a 32 (or 64) item threshold, merging left and right subarrays into a sorted result.

Explain data compression, its use of redundancy and the shift from two-dimensional image data to a one-dimensional form, and preview run-length encoding, Huffman encoding, lzw encoding, and lsb encoding.

Explore run-length encoding, a lossless data compression method that stores consecutive data values as a value and count. See its effectiveness on bitmap images and plain text on solid backgrounds.

Explore Huffman decoding by navigating a Huffman tree to decode a bitstring back to the original text, using root-to-leaf traversal with 0s and 1s.

Implement Huffman encoding in Java by building a Huffman tree with leaves storing characters and internal nodes summing frequencies. Use the comparable interface to merge subtrees by frequency.

Implement the Huffman encoding by building a Huffman tree from leaf nodes using character frequencies and a priority queue, merging until one tree remains.

Learn how LZW decompression reconstructs the original text from compressed data using a hash map or trie, starting with single characters and building substrings from prior outputs.