# Solve common data-structure and puzzle problems Solve the following independent problems (language of your choice; assume typical 32/64-bit constraints): 1) **Reverse a singly linked list** - Given the head of a singly linked list, reverse it and return the new head. (Iterative and/or recursive.) 2) **Numbering on an outward spiral grid** - Integers are written on an infinite 2D grid starting with `1` at `(0,0)`, then `2` at `(1,0)`, and continuing counterclockwise in an outward square spiral (right, up, left, down, ...). - Given integer coordinates `(x, y)`, compute the value written at that cell in **O(1)** time (no simulating the spiral). 3) **100 bulbs toggling** - There are 100 bulbs labeled `1..100`, all initially OFF. - Person 1 toggles every bulb; person 2 toggles bulbs `2,4,6,...`; person 3 toggles `3,6,9,...`; ...; person 100 toggles bulb `100`. - Which bulbs are ON at the end? 4) **Delete a node with only that node** - You are given a pointer/reference to a node `p` inside a singly linked list (you do **not** have the head pointer). - Delete `p` from the list in O(1) time. State any required assumptions. 5) **Bridge-and-torch scheduling** - Four people must cross a bridge with one torch. At most two people cross at a time, and they must carry the torch. - Their individual crossing times are `1, 2, 5, 6` minutes; when two cross together, the pair takes the slower person’s time. - Find a schedule that gets everyone across in **≤ 13 minutes**, or prove it’s impossible. 6) **Validate a BST** - Given the root of a binary tree, determine whether it satisfies the binary search tree property. 7) **Merge intervals** - Given a list of intervals `[start, end]` (inclusive), merge all overlapping intervals and return the merged list. 8) **Maximum adjacent gap after sorting** - Given an unsorted array of integers, if the array were sorted, what is the maximum difference between two adjacent elements in the sorted order? - Design an algorithm better than O(n log n) if possible, and state assumptions. ### Constraints & Assumptions - Preserve the scope, facts, inputs, and requested outputs from the prompt above. - If the prompt leaves a detail unspecified, state a reasonable assumption before relying on it. - Keep the answer interview-ready: concise enough to present, but concrete enough to implement or evaluate. ### Clarifying Questions to Ask - Clarify input sizes, value ranges, mutability, return format, and tie-breaking. - State the target time and space complexity before coding. - Call out edge cases such as empty inputs, duplicates, invalid values, overflow, and boundary sizes. ### What a Strong Answer Covers - A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it. - A correctness argument that explains why the algorithm covers all required cases. - Time and space complexity, plus at least one alternative approach when relevant. - Focused tests for normal cases, edge cases, and failure modes. ### Follow-up Questions - How would the approach change if the input were streaming or too large for memory? - What invariants would you assert in production code? - Which tests would catch off-by-one, duplicate, or tie-breaking bugs?