Data Structures & Algorithms

1. 1.What is Big-O notation, and how do you work out the time complexity of a piece of code?easy

   Big-O describes how an algorithm's running time (or memory) grows as the input size n grows. It is an upper bound on the growth rate, so we drop constants and lower-order terms: 3n² + 5n + 2 is O(n²).

   To analyze code, I count how many times the dominant operation runs as a function of n:

   • Sequential blocks add: O(n) + O(n²) is O(n²)
   • Nested loops multiply: a loop over n inside a loop over n is O(n²)
   • Halving or doubling the problem each step gives O(log n)
   • Recursion: write a recurrence, or draw the recursion tree and sum the work per level
   • Separate inputs keep separate variables: O(a + b) or O(a · b), not O(n²)

   I also watch for hidden linear costs inside a single line, such as x in some_list, slicing, or copying a list.

   The common classes, fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).

   What interviewers listen for

   • Upper bound on growth as input size grows
   • Drop constants and lower-order terms
   • Sequential steps add; nested loops multiply
   • Halving the input each step gives O(log n)
   • Watch hidden costs like in on a list

   Likely follow-up: What is the complexity of a loop where j doubles each step, nested inside a loop over n? · How do you analyze the complexity of a recursive function?

   answer it out loud →
2. 2.Given an array of integers and a target, return the indices of two numbers that add up to the target (Two Sum). What is your approach?easy

   The brute force checks every pair: O(n²) time, O(1) space. That is my baseline, but the bottleneck is the inner search for the complement, so I replace it with a hash map.

   I walk the array once. For each x at index i, the number I need is target - x. If it is already in the map, I have my pair; otherwise I store x -> i and move on. Checking before inserting means an element is never paired with itself, and duplicates like [3, 3] with target 6 still work.

   That is O(n) time and O(n) extra space, relying on average-case O(1) hash lookups.

   If the array were already sorted, I would use two pointers from both ends instead: O(n) time and O(1) space. Sorting first costs O(n log n) and loses the original indices unless I sort (value, index) pairs.

   def two_sum(nums, target):
       seen = {}                     # value -> index
       for i, x in enumerate(nums):
           if target - x in seen:
               return [seen[target - x], i]
           seen[x] = i               # insert after checking
       return []

   What interviewers listen for

   • Brute force over all pairs is O(n²)
   • Hash map from value to index, single pass
   • Check for the complement before inserting
   • O(n) time, O(n) space on average
   • Sorted input: two pointers with O(1) space

   Likely follow-up: How would you solve 3Sum? · What changes if you must return all unique pairs?

   answer it out loud →
3. 3.What are the differences between an array and a linked list, and when would you choose each?easy

   An array stores elements in one contiguous block, so index access is O(1) by address arithmetic and iteration is very cache-friendly. The cost is that inserting or deleting in the middle shifts elements, O(n), and a fixed-size array must be reallocated to grow (dynamic arrays hide this behind amortized O(1) appends).

   A linked list stores nodes scattered in memory, each pointing to the next (and to the previous, if doubly linked). Accessing the i-th element or searching is O(n), but once you hold a reference to a node, inserting or removing next to it is O(1) with no shifting. Each node carries pointer overhead, and traversal has poor cache locality.

   In practice I default to a dynamic array (Python list, Java ArrayList) because locality usually wins. I pick a linked list when I need O(1) insert and remove at positions I already hold, like the doubly linked list inside an LRU cache, or when splicing lists together.

   What interviewers listen for

   • Array: contiguous, O(1) index access, cache-friendly
   • Array middle insert/delete is O(n) from shifting
   • Linked list: O(n) access, O(1) insert at a known node
   • Linked lists pay pointer overhead and poor locality
   • Default to dynamic arrays; lists for LRU-style splicing

   Likely follow-up: Why is linked-list insertion "O(1)" often misleading in practice? · How would you find the middle of a linked list in one pass?

   answer it out loud →
4. 4.How does a hash table work, and why are its lookups O(1) on average?easy

   A hash table stores key-value pairs in an array of buckets. To insert or find a key, it runs the key through a hash function to get an integer, then maps that to a bucket index, typically hash(key) % capacity. Jumping straight to the bucket instead of scanning is what makes it fast.

   Two keys can land in the same bucket, a collision, handled by chaining (each bucket holds a small list) or open addressing (probe for another free slot). The table tracks its load factor, entries divided by buckets, and past a threshold it allocates a bigger array and rehashes everything. That resize is O(n) but rare, so inserts stay amortized O(1).

   With a good hash function and a bounded load factor, buckets stay small on average, so get, put and delete are O(1) average. The worst case is O(n) when many keys collide.

   Keys must be hashable and stable: equal keys need equal hashes, and mutating a key after inserting it breaks lookups.

   What interviewers listen for

   • Hash function maps a key to a bucket index
   • Collisions: chaining or open addressing
   • Resize and rehash when the load factor passes a threshold
   • O(1) average, O(n) worst case
   • Equal keys must produce equal hashes

   Likely follow-up: What is the difference between chaining and open addressing? · Why shouldn't you use a mutable object as a dictionary key?

   answer it out loud →
5. 5.Walk me through how you approach a coding problem in an interview.easy

   I follow the same loop every time and talk through each step:

   • Clarify: restate the problem; ask about input size, value ranges, duplicates, negatives, empty input, and what to return when there is no answer.
   • Examples: work one normal case and a couple of edge cases by hand, which often reveals the pattern.
   • Brute force: state the obvious solution and its complexity, so there is a correct baseline.
   • Optimize: find the bottleneck and reach for a pattern: hash map, sorting, two pointers, sliding window, heap, BFS/DFS, binary search or DP. Constraints hint at the target: n around 10⁵ usually needs O(n log n) or better, while n ≤ 20 allows exponential search.
   • Code: write clean code with clear names, narrating the key decisions.
   • Test: dry-run my example, then edge cases, and fix bugs calmly.
   • Complexity: state the final time and space, plus trade-offs or what I would improve with more time.

   What interviewers listen for

   • Clarify inputs, constraints and edge cases first
   • Brute force with its complexity as a baseline
   • Optimize by finding the bottleneck and a pattern
   • Use constraints to infer the target complexity
   • Dry-run tests, then state time and space

   Likely follow-up: What do you do if you get stuck on the optimization step? · How do you choose which edge cases to test?

   answer it out loud →
6. 6.How do you reverse a singly linked list? Can you do it both iteratively and recursively?easy

   Iteratively, I walk the list with three references: prev (the already-reversed part, starting at None), curr, and a saved nxt. For each node I save curr.next, point curr.next back at prev, then advance both. When curr is None, prev is the new head. That is O(n) time and O(1) extra space. The classic bug is overwriting curr.next before saving it, which loses the rest of the list.

   Recursively, I first reverse everything after the head, which returns the new head (the old tail). Now head.next is the last node of the reversed part, so head.next.next = head appends the current node, and head.next = None cuts the old link. It is also O(n) time but uses O(n) call-stack space, so a long list can hit Python's recursion limit. I prefer the iterative version in real code.

   def reverse_list(head):
       prev, curr = None, head
       while curr:
           nxt = curr.next          # save the rest first
           curr.next = prev         # flip the pointer
           prev, curr = curr, nxt
       return prev                  # new head
   
   def reverse_rec(head):
       if head is None or head.next is None: return head
       new_head = reverse_rec(head.next)
       head.next.next = head        # hang head after its old successor
       head.next = None
       return new_head

   What interviewers listen for

   • Track prev and curr; save next before relinking
   • Iterative: O(n) time, O(1) space
   • Recursive: head.next.next = head, then head.next = None
   • Recursive version uses O(n) stack space
   • Handle empty and single-node lists

   Likely follow-up: How would you reverse only the nodes between positions m and n? · How would you reverse a list in groups of k?

   answer it out loud →
7. 7.Given a string of brackets like "([]{})", how do you check whether it is valid?easy

   Brackets must close in the reverse order they opened, which is exactly last-in, first-out, so I use a stack.

   I scan left to right and push every opening bracket. For a closing bracket, the stack must be non-empty and its top must be the matching opener; if so I pop it, otherwise the string is invalid right away. At the end the string is valid only if the stack is empty, because any leftover openers were never closed.

   A map from each closer to its opener keeps the code short. It is O(n) time and O(n) space in the worst case, such as a string of only opening brackets.

   Edge cases I test: the empty string (valid), a lone closer ")", interleaving like "([)]" (invalid) and "((" (invalid). With only one bracket type, a counter that never goes negative and ends at zero is enough, in O(1) space.

   def is_valid(s):
       pairs = {')': '(', ']': '[', '}': '{'}
       stack = []
       for ch in s:
           if ch in pairs:                       # closing bracket
               if not stack or stack.pop() != pairs[ch]:
                   return False
           else:
               stack.append(ch)                  # opening bracket
       return not stack                          # nothing left unclosed

   What interviewers listen for

   • Last-opened must close first, so use a stack
   • Push openers; a closer must match and pop the top
   • Valid only if the stack ends empty
   • O(n) time, O(n) space
   • One bracket type: a counter is enough

   Likely follow-up: How would you find the longest valid parentheses substring? · How would you generate all valid combinations of n pairs?

   answer it out loud →
8. 8.What is the difference between a stack, a queue and a deque, and how would you implement each in Python?easy

   A stack is last-in, first-out: you push and pop at the same end. It models function calls, undo, DFS and bracket matching. A Python list works well, since append and pop() at the end are amortized O(1).

   A queue is first-in, first-out: you add at the back and remove from the front. It models scheduling, buffering and BFS. I use collections.deque with append and popleft, both O(1). I avoid list.pop(0) because it shifts every remaining element, which is O(n).

   A deque (double-ended queue) supports O(1) insert and remove at both ends, so it can act as either. It is the tool behind sliding-window maximum and 0-1 BFS.

   For thread-safe producer-consumer queues Python has queue.Queue. A priority queue is a different structure again, usually a binary heap via heapq.

   What interviewers listen for

   • Stack is LIFO: list.append and list.pop()
   • Queue is FIFO: deque.append and deque.popleft()
   • list.pop(0) is O(n); avoid it for queues
   • Deque: O(1) operations at both ends
   • Stacks drive DFS; queues drive BFS

   Likely follow-up: How would you implement a queue using two stacks? · How would you design a stack that returns its minimum in O(1)?

   answer it out loud →
9. 9.What is the difference between BFS and DFS, and when would you use each?easy

   Both visit every reachable vertex and edge once, so both are O(V + E) time with an adjacency list. They differ in the order they explore.

   BFS (breadth-first search) uses a queue and explores level by level: every node at distance 1, then distance 2, and so on. That makes it the right choice for the shortest path in an unweighted graph, the minimum number of moves, and level-order tree traversal. Its memory grows with the widest frontier.

   DFS (depth-first search) uses a stack or recursion and goes as deep as possible before backtracking. It suits exhaustive exploration: connected components, cycle detection, topological sort, path finding and backtracking. Its memory grows with the depth, and deep recursion can overflow the call stack, so for very deep graphs I use an explicit stack.

   In both, I mark a node visited when I first discover it (for BFS, when I enqueue it) so it is never processed twice.

   What interviewers listen for

   • Both O(V + E) with an adjacency list
   • BFS: queue, level by level, unweighted shortest paths
   • DFS: stack or recursion, goes deep, then backtracks
   • DFS suits cycle detection, topo sort, components
   • Mark visited on discovery to avoid repeats

   Likely follow-up: Why does BFS give shortest paths only when edges are unweighted? · How would you run BFS on a grid with obstacles?

   answer it out loud →
10. 10.How do you detect whether a linked list has a cycle, ideally in O(1) extra space?easy

    The simple approach stores every visited node in a hash set and reports a cycle when it sees a node twice: O(n) time but also O(n) space.

    For O(1) space I use Floyd's tortoise and hare. Two pointers start at the head; slow moves one step and fast moves two. Without a cycle, fast reaches the end. With a cycle, both end up circling it, and each step the gap between them shrinks by one, so fast must land on slow within about one lap. It is O(n) time.

    The loop condition fast and fast.next protects both hops of the fast pointer. I compare nodes by identity (is), not by value, since values can repeat.

    To find where the cycle starts, after they meet I move one pointer back to the head and advance both one step at a time; they meet again at the cycle's entry node.

    def has_cycle(head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:          # compare nodes, not values
                return True
        return False

    What interviewers listen for

    • A hash set works but costs O(n) space
    • Slow moves one step, fast moves two
    • They meet if and only if there is a cycle
    • Guard the loop with fast and fast.next
    • Reset one pointer to head to find the entry

    Likely follow-up: Why does resetting one pointer to the head find the cycle start? · How would you compute the length of the cycle?

    answer it out loud →

No questions match that filter.