Arrays, Linked Lists, Stacks and Queues

Arrays, Linked Lists, Stacks and Queues

Data structures are the core of technical interviews at product companies and an important part of service-company interviews too. This set covers the linear data structures and the classic problems built on them. Try each problem yourself before reading the code.

1. What is the difference between an array and a linked list?

An array stores elements in contiguous memory, so access by index is O(1), but inserting or deleting in the middle is O(n) because elements shift. A linked list stores nodes anywhere in memory, each pointing to the next; insertion and deletion at a known node are O(1), but finding the i-th element is O(n). Arrays are also more cache-friendly, which matters in practice.

2. What is Big-O notation?

Big-O describes how an algorithm’s time or memory grows as the input size grows, ignoring constants. Common orders: O(1) constant, O(log n) binary search, O(n) a single loop, O(n log n) efficient sorting, O(n²) nested loops. Interviewers expect you to state the complexity of every solution you write.

3. Reverse a singly linked list.

Walk through the list and reverse each next pointer, keeping track of the previous node. O(n) time, O(1) extra space.

Node reverse(Node head) {
    Node prev = null, curr = head;
    while (curr != null) {
        Node next = curr.next;  // remember the rest
        curr.next = prev;       // reverse the link
        prev = curr;
        curr = next;
    }
    return prev;                // new head
}

4. How do you detect a cycle in a linked list?

Use Floyd’s algorithm: move one pointer one step and another two steps at a time. If there is a cycle, they eventually meet; if the fast pointer reaches null, there is none. O(n) time, O(1) space.

boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

5. What are stacks and queues? Give real uses.

A stack is Last-In-First-Out: push and pop from the top. Uses: undo, browser back button, function calls, expression evaluation. A queue is First-In-First-Out: add at the rear, remove from the front. Uses: printer jobs, task scheduling, breadth-first search. In Java, ArrayDeque works well as both.

6. Check whether brackets in a string are balanced.

Push every opening bracket onto a stack. For each closing bracket, the top of the stack must be the matching opening bracket. At the end the stack must be empty. O(n) time.

boolean balanced(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (c == ')' || c == ']' || c == '}') {
            if (st.isEmpty()) return false;
            char o = st.pop();
            if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{')) return false;
        }
    }
    return st.isEmpty();
}

7. Implement a queue using two stacks.

Push new elements onto an “in” stack. To dequeue, if the “out” stack is empty, move everything from “in” to “out” (which reverses the order), then pop from “out”. Each element moves at most once, so operations are O(1) amortised.

class MyQueue {
    private Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
    void add(int x) { in.push(x); }
    int remove() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.pop();
    }
}

8. What is hashing? Solve “two sum” using a HashMap.

Hashing maps keys to array positions using a hash function, giving O(1) average lookups. For two sum (find two numbers that add up to a target), store each number’s index in a map and check whether target - x has already been seen. O(n) time instead of O(n²).

int[] twoSum(int[] a, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < a.length; i++) {
        Integer j = seen.get(target - a[i]);
        if (j != null) return new int[]{j, i};
        seen.put(a[i], i);
    }
    return new int[0];
}

9. Explain binary search and its condition.

Binary search works only on sorted data. Compare the target with the middle element and discard the half that cannot contain it. O(log n) time.

int binarySearch(int[] a, int key) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // avoids overflow
        if (a[mid] == key) return mid;
        if (a[mid] < key) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}