AndroidHire

Android Coding Interview Patterns Interview Questions

Two pointers, sliding window, graphs, and DP.

50 questions in this topic · 8 sample questions below

Practice Coding Interview Patterns in the quiz engine

Sample questions

  1. You must find whether any two elements in a SORTED array sum to a target. Which approach is optimal in both time and space?

    • Two pointers from both ends, O(n) time and O(1) space — correct
    • Hash set of seen values, O(n) time and O(n) space
    • Nested loops, O(n^2) time and O(1) space
    • Binary search for each complement, O(n log n) time and O(1) space

    Why: Because the array is already sorted, two pointers converge in one pass with no extra memory. The hash-set answer also runs in O(n) time but wastes O(n) space that the sortedness makes unnecessary.

  2. Finding the longest substring without repeating characters is best solved with which pattern?

    • Fixed-size sliding window
    • Variable-size sliding window with a hash set/map — correct
    • Merge intervals
    • Two pointers on a sorted copy

    Why: The window grows and shrinks based on a constraint (no repeats), which is the variable-size sliding window. A fixed window is wrong because the answer length is unknown in advance.

  3. To detect whether a singly linked list has a cycle using O(1) extra space, you should use:

    • A hash set of visited nodes
    • Reversing the list twice
    • Floyd's fast and slow pointers — correct
    • Recursion with a visited flag

    Why: Floyd's tortoise-and-hare uses two pointers at different speeds and O(1) space; they meet if a cycle exists. The hash-set approach also detects a cycle but needs O(n) extra space.

  4. What is the average and worst-case time of a lookup in a hash table?

    • O(1) average, O(1) worst case
    • O(log n) average, O(n) worst case
    • O(1) average, O(log n) worst case
    • O(1) average, O(n) worst case — correct

    Why: With collisions all keys can land in one bucket, degrading a lookup to O(n) in the worst case; only the average is O(1). Claiming O(1) worst case ignores adversarial collisions.

  5. Merging a list of intervals like [[1,3],[2,6],[8,10]] most efficiently requires first:

    • Sorting the intervals by start time — correct
    • Building a union-find over interval indices
    • Sorting the intervals by end time only
    • Using a min-heap keyed by interval length

    Why: Sorting by start lets a single linear sweep merge any overlapping neighbors. Sorting by length or using union-find does not expose adjacency of overlaps in a way that helps the O(n log n) merge.

  6. Binary search can be applied to which of the following?

    • Only sorted arrays of numbers
    • Any monotonic predicate over a search space, including answer spaces — correct
    • Any array, sorted or not
    • Only data structures that support random access by pointer

    Why: Binary search works whenever a predicate is monotonic (false...false,true...true), which includes answer-space searches, not just numeric arrays. Restricting it to numeric sorted arrays misses common uses like binary search on capacity.

  7. To search a rotated sorted array (distinct values) in O(log n), the key insight is:

    • You must first find the pivot in O(n)
    • Binary search cannot work; you need O(n) linear scan
    • At each step at least one half is normally sorted, so you can decide which half to keep — correct
    • Rotate the array back to sorted first, then binary search

    Why: Even after rotation, one side of mid is always sorted, letting you test whether the target lies in that ordered half. Physically rotating the array back would itself cost O(n), defeating the purpose.

  8. For finding the shortest path in an UNWEIGHTED graph, the right choice is:

    • Depth-first search
    • Dijkstra's algorithm with a heap
    • Bellman-Ford
    • Breadth-first search — correct

    Why: BFS explores in layers, so the first time it reaches a node it has used the fewest edges, giving the shortest unweighted path. DFS may reach the target via a longer path first and does not guarantee minimality.

Practice all 50 Coding Interview Patterns questions

These 8 are a sample. The full Coding Interview Patterns bank is scored, tracks your progress, and explains every answer.

Open the quiz

More Android interview topics