The Swift Arcade Data Structures and Algorithms Bootcamp

Big O notation compares algorithm performance in time and space, using worst-case measures such as O(1), O(n), O(log n), and O(n^2), plus time-space tradeoffs with hash maps.

Explore how arrays store elements, access data in constant time, and handle insertions, deletions, and resizing, revealing the internal mechanics behind their speed and versatility.

Inserting into an array involves copying up, shifting elements to the right, inserting the new item, and incrementing the size. The worst-case time is linear, O(n).

Delete mirrors insert by copying down, shifting elements above the target index and overwriting the removed position, running in linear time, O(n).

The lecture explains how fixed-size arrays resize by doubling capacity, copying elements, and performing appends in O(1) on average, with O(n) cost during reallocation.

Swift arrays encapsulate dynamic operations like insert, remove, and append, built right into the array object, without upfront sizing. That built-in behavior contrasts with Java or C array handling.

Swift arrays have fixed size and constant time random access. In inserts and deletes cost O(n) due to copying; Swift handles resizing, making arrays a go-to interview structure.

Practice interview questions to reinforce the data structures and algorithms covered. Read problems, note what you don't understand, and approach solutions with clarifying questions to deepen learning.

Learn how to rotate an array to the right by k positions using a brute-force approach, for loops, and edge-case handling in Swift, with playground testing and time complexity notes.

Reformat a phone number by removing spaces and dashes, then group digits into blocks of three separated by dashes, with the last block possibly two, using Swift string techniques.

Master a Swift array search to find contacts by phone substrings, returning no contact, a single match, or the first alphabetized contact. Use looping and sorting to pick the result.

Understand how a linked list uses nodes and next pointers to form a train-like chain with a head and tail. Compare its fast front insertions and dynamic sizing to arrays.

Learn to insert a new node at the front of a linked list by updating head and next pointers, achieving constant time O(1) inserts, unlike arrays with O(n).

Add back and get last: walk to the tail in a linked list, update the tail to a new node, and return last element as optional int with O(n) complexity.

Insert a new node into a linked list by walking to the target position and manipulating next pointers, handling front insertions and updates to reach the correct index.

Delete elements from a linked list by skipping nodes with delete first, delete last, and delete at position, using head, previous and next pointers, with O(1) and O(n) cases.

Linked lists power real-world, high-performance, real-time systems, from Doom's memory manager using a double linked list to Apple's UI kit's responder chain for event routing behind the scenes.

Compare linked lists and arrays by front operations, dynamic growth, and memory use. Recognize that arrays offer constant-time random access for indexing, unlike linked lists.

Master the essentials of linked lists for the technical interview: front operations are O(1) for add front, get first, and delete first; back operations are O(n) with no random access.

Learn to implement a function that counts a linked list length by walking from head to nil, using a current pointer and a length counter, useful for interview questions.

Find the merge point of two linked lists using a brute-force method that traverses each list with lengths and next pointers to locate the first common node.

Trade time for space by using a dictionary to store B’s elements and enable fast A lookups, reducing the embedded quadratic loops to O(n) + O(m) time.

Explore how to solve the linked list merge problem in a single pass using length calculations, difference D, and a pre-aligned walk to find the merge point in O(n) time.

Discover how to detect a cycle in a linked list using Floyd's tortoise and hare algorithm, with slow and fast pointers that collide to reveal a cycle.

Learn to reduce any complex algorithm to its big O notation by identifying runtime components, bottlenecks, and opportunities for improvement, making you a more efficient programmer.

Master practical rules to determine runtime complexity by reducing big O expressions. Drop non-dominant terms and constants, then combine dominant terms for cases like O(n+m) or O(n*m).

Apply big O reduction to merge algorithms on linked lists, determine runtimes such as O(m), O(n), O(m+n), and O(n*m), and compare dominant terms to optimize performance.

We reduce expressions by dropping non-dominant terms, identifying O(n), O(log n), and O(2^n) as dominant, and noting when O(n + m) cannot be reduced.

Review common runtimes, determine algorithm complexity, and apply reduction rules to simplify problems for interviews. Anticipate patterns like O(n), O(n+m), and O(n log n) as we approach stacks and queues.

Explain how a stack works by comparing it to a stack of books, showing push and pop operations in O(1) time. See why computer scientists use stacks in data structures.

Explore queues, a concept where the order of entry determines the order of exit, matching real-world lines like bank and bus queues.

Explore how stacks use LIFO and push-pop operations, and how queues use FIFO with enqueue and dequeue, then compare array vs linked list implementations and performance.

Learn to build stack and queue data structures in Swift using arrays, generics, and optional struct or class implementations, covering push, pop, enqueue, dequeue, peek, and performance notes.

learn to rotate an array to the right or left k times using stacks and queues in swift, exploring insert last at zero, append, and remove at operations.

Explore how to reverse a string with a stack by converting the string to an array, pushing characters onto a stack, and popping to build the reversed result.

Develop an algorithm to check balanced brackets in a string using a stack. Push opening brackets, pop on matching closings, and iterate with a for loop to validate balance.

Review key features of stacks and queues, including push and pop in O(1) and dequeue in O(n), and show how arrays or linked lists support these structures in Swift interviews.

Discover how hash tables enable fast key-value lookups using a hashing function, store and retrieve entries quickly, and why a strong algorithm supports interview-ready performance.

Explore how hash tables use hash functions to generate keys, map them to indices, and handle collisions, using Swift’s built-in hash and the hashable protocol for strings, integers, and floats.

Convert a hash into an index with the modulus operator to fit a small array, then address collisions in a hash table, noting Swift's runtime hash variability.

Handle collisions in hash tables by chaining, storing colliding objects in a linked list at the same index. Walk the list to locate items during lookup.

Explore hash table runtime characteristics, focusing on average O(1) search, insert, and delete with a good hashing function, and understand worst-case O(n) collisions.

Explore building a hash table from scratch in Swift, including hashing, index calculation, handling collisions with a linked list, and using a subscript to mimic a Swift dictionary.

Master hash tables by understanding quick O(1) lookups, worst-case O(n) collisions, linked-list collision handling, and modulus mapping; learn language-specific hash functions in Java, C#, .NET, and Swift.

Explore binary trees and binary search trees, with nodes, a root, and left and right branches. Understand how balanced height and breadth-first or depth-first traversals optimize searches.

Explore how binary search trees organize nodes by key to enable fast finds with the find method, halving the search space at each step and achieving O(log n) runtime.

Explore how a binary search tree operates by inspecting the node structure, root, and left and right children. Trace the recursive find method, handling nil roots and avoiding duplicates.

Inserting into a binary search tree preserves order by checking from the root, moving left or right, and placing the new node at the first null spot.

Traverse the left side of a binary search tree until you reach a null to locate the minimum, returning the leftmost node.

Learn to delete nodes in a binary search tree: handle no child, one child, and two-children cases; use the minimum on the right, copy up, remove duplicates, and Swift inout.

Explore depth-first traversals on binary trees with in-order, pre-order, and post-order patterns, learning left, root, right sequencing and their practical uses in code.

Master that a binary search tree provides O(log n) time for find, insert, and delete. See how recursive halving yields the log base 2 n behavior behind these operations.

Understand the binary search tree's ordered, recursive structure and traversals such as in order, preorder, and postorder. Recognize its O(log n) searches and how depth and balance affect performance.

Discover how binary space partitioning uses a binary tree to determine what parts of a game map are visible, enabling fast rendering in 3D shooters.

Implement an algorithm to determine if a binary tree is a binary search tree using min/max bounds and recursive checks of left and right subtrees, with no duplicates.

Master a common binary tree interview problem by computing height via a recursive function that measures the longest path, uses is leaf, and compares left and right subtrees.

Learn a recursive solution to the lowest common ancestor in a binary search tree by comparing n1, n2, and the root to decide left or right traversal.

Explore memoisation to boost algorithmic efficiency by transforming the fibonacci series into a fast, scalable computation.

Explore the Fibonacci series, its recurrence, and fib(0)/fib(1) bases. Learn how memoisation speeds up computation to beat naive recursion and its exponential time growth in nature and stock predictions.

Memoisation speeds up algorithms by caching previously calculated results, using them in future calculations. The Fibonacci series example shows how memoisation transforms exponential time into linear time, dramatically increasing efficiency.

See memoization in action by comparing a naive Fibonacci implementation with no storage to a memoized version that caches results in a dictionary, dramatically speeding up calculations.

Learn the Fibonacci series using the recurrence f(n-1) + f(n-2) and the memoization optimization to cache expensive calculations, essential for interviews.

Bubble sort finds the highest number by passes, swapping adjacent elements to bubble it to the end, then repeats with the remaining elements until sorted.

Master bubble sort in action through two nested loops performing progressive sweeps, comparing adjacent numbers, and swapping with a temporary variable.

Explore the runtime characteristics of bubble sort by examining two nested for loops in an interview-style exercise, using a cheat sheet to guide breakdown. The lesson shifts to merge sort.

Merge sort uses a divide-and-conquer approach: split the array into single elements, then merge them back via the merge step that repeatedly selects the smaller element and advances pointers.

Visualize how merge sort recursively halves the array and then merges the parts. Combine the halving with the merging steps to yield the runtime O(n log n).

Explore the quicksort algorithm by pivoting around a chosen element, partitioning the array with left and right pointers, swapping out-of-place elements, and recursively sorting the subarrays.

Master quicksort's runtime of O(n log n) and compare it to bubble sort and merge sort, noting quicksort is fastest among the three due to halving.

Identify the fastest and slowest sorting algorithms—quicksort, bubble sort, and merge sort—with run times O(n log n) and O(n^2). Visualize each with simple pictures to prep for interviews.