Android Coding Interview Questions

A short, practical list covers almost everything an Android interview actually tests, and it lines up closely with structures you already use in real Android code, not abstract theory.

• Arrays and ArrayList. The default for ordered data, and the base most other structures are explained in terms of.
• HashMap and HashSet. By far the most common tool in these interview questions, anything that says "find duplicates," "count occurrences," or "check membership fast" wants one of these, O(1) average lookup is the reason.
• Linked lists. Less common in app code directly, but a frequent interview topic on its own, cycle detection and palindrome checks both lean on the same two pointer technique.
• Stacks and queues. Stacks show up in anything with undo behavior or matching pairs like parentheses, queues show up in MessageQueue itself, which is worth connecting back to if it comes up.
• Trees, specifically binary trees and BSTs. Traversal order, depth, and balance are the recurring questions, and a RecyclerView's view hierarchy or a JSON payload are both trees in practice, which is a natural bridge if an interviewer asks why this matters for app work.
• Heaps or priority queues. Less frequent, but the right answer whenever a question is really "give me the smallest or largest n things," like the minimum meeting rooms problem.

The honest framing for an interview is that HashMap and HashSet alone answer a large share of the DSA questions you'll actually be asked, so if time is short, that's the one to be fluent in cold, everything else is worth recognizing and being able to reason through, even if it's not muscle memory.

You get one buy and one later sell over an array of daily prices, and you have to return the largest profit possible. Go through the prices once carrying the cheapest day seen so far, and at every day ask what selling today against that cheapest day would make.

The problem

You are given an array where each slot is the price of the stock on that day. You return one number, the largest profit a single buy and a single later sell can make. You must buy before you sell, and if no trade makes money the answer is 0, not the smallest loss.

Input prices = [7, 1, 5, 3, 6, 4].

Output 5.

• Day 0 costs 7. It is the cheapest so far, and selling into itself makes nothing.
• Day 1 costs 1, which is cheaper, so the cheapest day so far drops to 1.
• Day 2 costs 5. Selling here against 1 makes 4, so the best answer so far is 4.
• Day 4 costs 6. Selling here against 1 makes 5, which no later day beats.

fun maxProfit(prices: IntArray): Int {
    var min = Int.MAX_VALUE
    var best = 0
    for (p in prices) {
        min = minOf(min, p)
        best = maxOf(best, p - min)
    }
    return best
}

static int maxProfit(int[] prices) {
    int min = Integer.MAX_VALUE;
    int best = 0;
    for (int p : prices) {
        min = Math.min(min, p);
        best = Math.max(best, p - min);
    }
    return best;
}

The rule is that you must buy before you sell, and this loop respects that for free. When you are standing on day p, min only ever holds prices from days at or before it, so p - min is always a legal trade. Updating min before you compute the profit is safe, because buying and selling on the same day just yields zero.

best starts at zero, and that is the deliberate part. If prices only ever fall, no trade is worth making, so the correct answer is to do nothing and take zero rather than the least bad loss.

The naive answer is the nested loop over every buy day and every later sell day, which is O(n squared). This is O(n) time and O(1) space. The follow up is unlimited transactions. That one collapses to something even smaller, add up every upward step, meaning sum prices[i] - prices[i - 1] whenever it is positive, because any profitable run can be sliced into single day gains.

You are given an array and a target, and you have to return the positions of the two numbers that add up to that target. Walk the array once, and at each number ask a hash map whether the number that completes the pair has already gone by.

The problem

You are given an array of integers and one target integer. You return the positions of the two numbers that add up to the target, not the numbers themselves. The array is not sorted, exactly one pair works, and a number cannot pair with itself.

Input nums = [2, 6, 5, 8, 11] and target = 14.

Output [1, 3].

• Index 0 holds 2, so you need 12. The map is empty, so store 2 at index 0.
• Index 1 holds 6, so you need 8. Not there, so store 6 at index 1.
• Index 2 holds 5, so you need 9. Not there, so store 5 at index 2.
• Index 3 holds 8, so you need 6. The map has 6 at index 1, so the answer is [1, 3].

fun twoSum(nums: IntArray, target: Int): IntArray {
    val seen = HashMap<Int, Int>()
    for (i in nums.indices) {
        val need = target - nums[i]
        val j = seen[need]
        if (j != null) return intArrayOf(j, i)
        seen[nums[i]] = i
    }
    return intArrayOf(-1, -1)
}

static int[] twoSum(int[] nums, int target) {
    var seen = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) return new int[] { seen.get(need), i };
        seen.put(nums[i], i);
    }
    return new int[] { -1, -1 };
}

The map turns "is this value somewhere in the array" from a scan into a single lookup. It maps a value to the index it was found at, so when the lookup hits you can hand back both positions. Checking before you insert is what stops a number from pairing with itself when the target is exactly double it.

The naive answer, and the one to say out loud first, is the nested loop over every pair, which is O(n squared). This is O(n) time and O(n) space for the map. That is the trade you name in the interview, you spend memory to buy back the inner loop.

If the interviewer says only the values matter and not the indices, there is a two pointer variant. Sort the array, put one pointer at each end, and move the left one in when the sum is too small and the right one in when it is too big. That is O(n log n) time and O(1) extra space, which wins when the input already arrived sorted.

Find the largest sum any contiguous stretch of the array can produce. Walk it once carrying a running sum, throw that sum away the moment it goes negative, and keep the best value you ever saw. That is Kadane's algorithm.

The problem

You are given an array of integers, and the values can be negative. A subarray is a contiguous stretch of it, so you may not skip elements. Return the largest sum any such stretch can reach, the sum alone and not the stretch itself. It must hold at least one element, so an array of only negative numbers answers with its largest single value.

Input nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output 6

• The running sum hits -2 at the first element, which is negative, so it resets to 0
• It climbs to 1, then -2 at the third element, so it resets again and the best so far stays 1
• From 4 it goes 4, 3, 5, 6, and each of those updates the best, which lands on 6
• The -5 pulls it to 1 and the final 4 only reaches 5, so 6 survives as the answer

fun maxSubarraySum(nums: IntArray): Int {
    var best = nums[0]
    var sum = 0
    for (n in nums) {
        sum += n
        best = maxOf(best, sum)
        if (sum < 0) sum = 0
    }
    return best
}

static int maxSubarraySum(int[] nums) {
    int best = nums[0];
    int sum = 0;
    for (int n : nums) {
        sum += n;
        best = Math.max(best, sum);
        if (sum < 0) sum = 0;
    }
    return best;
}

The reset is the whole trick. If the numbers behind you add up to something negative, dragging them along can only make whatever comes next smaller, so you drop them and start fresh. A prefix that sums to zero or more is still worth keeping, because it can only help.

The naive answer is to try every start and every end, which is O(n squared), or O(n cubed) if you re-add the slice each time. Kadane does it in O(n) time and O(1) space, since each element is looked at once and you hold two numbers.

The trap is starting best at zero, which returns zero for an all negative array when the right answer is the largest single element. Starting at nums[0] and updating before the reset handles it. The usual follow up is printing the subarray. Keep a start that moves to the next index on every reset, and record it alongside the current index whenever best improves.

Merge sort sorts an array by splitting it in half until every piece is one element, then merging sorted pieces back together. The merge is the only real work, walking two sorted halves with two pointers and always taking the smaller front value.

The problem

You get an unsorted array of integers and return it sorted into non decreasing order, using divide and conquer rather than a library call. Duplicates are allowed. The bound has to be O(n log n) on every input, not just on average, which is the reason this and not quicksort.

Input, [3, 1, 4, 2].

Output, [1, 2, 3, 4].

• Split into [3, 1] and [4, 2], then split each again into single elements.
• Merge 3 with 1 to get [1, 3], and merge 4 with 2 to get [2, 4].
• Merge [1, 3] with [2, 4], taking 1, then 2, then 3, then 4, and the array is sorted.

fun mergeSort(arr: IntArray, left: Int = 0, right: Int = arr.size - 1) {
    if (left >= right) return
    val mid = left + (right - left) / 2
    mergeSort(arr, left, mid)
    mergeSort(arr, mid + 1, right)
    merge(arr, left, mid, right)
}

private fun merge(arr: IntArray, left: Int, mid: Int, right: Int) {
    val temp = IntArray(right - left + 1)
    var i = left
    var j = mid + 1
    var k = 0
    while (i <= mid && j <= right) temp[k++] = if (arr[i] <= arr[j]) arr[i++] else arr[j++]
    while (i <= mid) temp[k++] = arr[i++]
    while (j <= right) temp[k++] = arr[j++]
    temp.copyInto(arr, left)
}

static void mergeSort(int[] arr) { mergeSort(arr, 0, arr.length - 1); }

static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    System.arraycopy(temp, 0, arr, left, temp.length);
}

A single element is trivially sorted, so the recursion bottoms out for free. The merge is linear in the size of the two halves combined and there are log n levels of splitting, so the total is O(n log n) on every input. There is no unlucky ordering that makes it worse.

It needs O(n) extra space for temp, since you cannot overwrite a half you are still reading from. Using <= rather than < in the comparison is what makes it stable, an element from the left half wins ties, so equal values never swap their original order.

Quicksort sorts in place with O(log n) space and is usually faster in practice thanks to cache locality, but its worst case is O(n squared) on a bad pivot. Merge sort trades memory for a guaranteed bound, which is why you reach for it when you need stability, or when sorting a linked list, or data too big to hold in memory.

A leader is an element with nothing bigger anywhere to its right. Scan from the right end carrying the largest value seen so far, and take every element that beats it.

The problem

You are given an array of integers. An element is a leader when every element to its right is smaller than it. Return the leaders as values, in the order they appear in the array. The last element is always a leader, since nothing sits to its right at all.

Input nums = [10, 22, 12, 3, 0, 6]

Output [22, 12, 6]

• Coming from the right, 6 beats an empty tail, so it is a leader and the running max becomes 6
• 0 and 3 both lose to 6, so neither is a leader
• 12 beats 6, so it is a leader and the max becomes 12
• 22 beats 12, so it is a leader and the max becomes 22, then 10 loses and is dropped
• Collected backwards that is [6, 12, 22], so reverse it to get [22, 12, 6]

fun leaders(nums: IntArray): List<Int> {
    val out = mutableListOf<Int>()
    var max = Int.MIN_VALUE
    for (i in nums.indices.reversed()) {
        if (nums[i] > max) {
            out.add(nums[i])
            max = nums[i]
        }
    }
    return out.reversed()
}

static List<Integer> leaders(int[] nums) {
    var out = new ArrayList<Integer>();
    int max = Integer.MIN_VALUE;
    for (int i = nums.length - 1; i >= 0; i--) {
        if (nums[i] > max) {
            out.add(nums[i]);
            max = nums[i];
        }
    }
    Collections.reverse(out);
    return out;
}

Going right to left is the whole idea. The question about each element is entirely about what sits after it, and arriving from the right means you already know that, it is the running max. A fresh scan of the tail at every position collapses into one comparison.

Because you collect them backwards you reverse at the end to put them back in array order. Starting the max at the smallest possible integer is what makes the last element a leader without a special case.

It is O(n) time and O(n) space for the output, or O(1) beyond it. The naive answer is a nested loop that checks every element against its whole tail, which is O(n squared). Pin one thing down before you write anything, ask whether an equal value to the right still counts. This code uses strictly greater, so in a run of equal values only the last one is a leader.

The array is sorted and you must collapse each run of equal values to one, without a second array. Use two pointers, one scanning for a value you have not kept yet, the other marking the end of the cleaned up front.

The problem

The array is sorted, so every copy of a value sits in one unbroken run. Rewrite the front of the array in place so it holds each distinct value once, in order, and return how many there are. You get no second array, and whatever sits past the returned length is ignored rather than cleared.

Input, [1, 1, 2, 2, 2, 3].

Output, 3, with the array now starting 1, 2, 3.

• The keep pointer sits on the first 1. The scan pointer sees another 1, a match, so it moves on.
• The scan reaches 2, which differs, so the keep pointer steps to index 1 and 2 is written there.
• The next two 2s match what was kept, so both are skipped.
• The scan reaches 3, so the keep pointer steps to index 2, 3 is written, and the length is 2 plus 1.

fun removeDuplicates(nums: IntArray): Int {
    if (nums.isEmpty()) return 0
    var i = 0
    for (j in 1 until nums.size) {
        if (nums[j] != nums[i]) {
            i++
            nums[i] = nums[j]
        }
    }
    return i + 1
}

static int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

Because the array is sorted, every copy of a value sits in one unbroken run. So the only comparison you need is against nums[i], the last value you kept. If nums[j] matches it you are still inside that run and you skip. If it differs the run has ended, so you make room at i + 1 and write the new value there.

Everything from index zero to i is the answer, and you return i + 1 as the new length. The tail beyond that is left as it was, which is why the caller gets a length rather than a shorter array. Java and Kotlin arrays cannot resize in place.

It is O(n) time and O(1) extra space, one pass and two integers. The naive version builds a new list or a set and copies back, which costs O(n) space and, with a set, loses the ordering you already had for free. The variant to be ready for is allowing each value twice. Compare against nums[i - 1] instead and start both pointers at index two.

You are given an array of integers and you have to return the largest product any contiguous stretch of it can make. Run a product from the left and a product from the right in the same loop, resetting either one to 1 when it hits zero, and the best value the two of them ever reach is the answer.

The problem

You are given an array of integers that can hold negatives and zeros. You return one number, the largest product any contiguous run of neighbouring elements can make. A run of one element counts, so the answer is never an empty product.

Input nums = [2, 3, -2, 4].

Output 6.

• The prefix product goes 2, then 6, then -12, then -48.
• The suffix product runs the other way, 4, then -8, then -24, then -48.
• The best value either scan ever showed is 6, which is the run [2, 3].
• On [-2, 0, -1] the zero resets both scans, so the answer is 0 rather than 2.

fun maxProductSubarray(nums: IntArray): Int {
    var best = Int.MIN_VALUE
    var prefix = 1
    var suffix = 1
    for (i in nums.indices) {
        if (prefix == 0) prefix = 1
        if (suffix == 0) suffix = 1
        prefix *= nums[i]
        suffix *= nums[nums.size - 1 - i]
        best = maxOf(best, maxOf(prefix, suffix))
    }
    return best
}

static int maxProductSubarray(int[] nums) {
    int best = Integer.MIN_VALUE;
    int prefix = 1;
    int suffix = 1;
    for (int i = 0; i < nums.length; i++) {
        if (prefix == 0) prefix = 1;
        if (suffix == 0) suffix = 1;
        prefix *= nums[i];
        suffix *= nums[nums.length - 1 - i];
        best = Math.max(best, Math.max(prefix, suffix));
    }
    return best;
}

Products do not behave like sums, and that is the whole difficulty. A long stretch of negatives can hold a huge positive product, so a running value that looks terrible right now can flip to the best answer on the very next multiplication. That is why you cannot just drop a bad prefix the way Kadane does.

Zeros are what let two simple scans cover it. A zero cuts the array into independent pieces, since no winning subarray ever crosses one. Inside a piece the number of negatives is either even, in which case the whole piece is the best product and the prefix scan finds it, or odd, in which case the answer skips everything up to the first negative or everything after the last one. One of those two is a prefix of the piece and the other is a suffix, so scanning from both ends catches both.

It is O(n) time and O(1) space, one pass and three numbers. The naive answer is every subarray at O(n squared). The trap is treating this like Kadane and resetting on a negative running product, that throws away exactly the case a later negative was going to rescue.

One value between 1 and n appears twice and another never appears at all, and you have to name both. Two unknowns need two equations, so compare the array's sum and its sum of squares against the sums a clean 1 to n would give.

The problem

You are given an unsorted array of n values, each between 1 and n. Exactly one value appears twice and exactly one value never appears at all. Return the repeating value first and the missing value second. The array is not sorted, so there is no run to look for a break in.

Input nums = [3, 1, 2, 5, 4, 6, 7, 5], so n is 8

Output [5, 8]

• The array sums to 33 while 1 through 8 sums to 36, so the repeating value minus the missing one is -3
• The squares sum to 165 while the squares of 1 through 8 sum to 204, so the difference of squares is -39
• Dividing -39 by -3 gives 13, which is the two values added together
• A difference of -3 and a sum of 13 can only be 5 and 8, so 5 repeats and 8 is gone

fun repeatingAndMissing(nums: IntArray): IntArray {
    val n = nums.size.toLong()
    var sum = 0L
    var squares = 0L
    for (v in nums) {
        sum += v
        squares += v.toLong() * v
    }
    val diff = sum - n * (n + 1) / 2
    val total = (squares - n * (n + 1) * (2 * n + 1) / 6) / diff
    val repeating = (diff + total) / 2
    return intArrayOf(repeating.toInt(), (repeating - diff).toInt())
}

static int[] repeatingAndMissing(int[] nums) {
    long n = nums.length;
    long sum = 0;
    long squares = 0;
    for (int v : nums) {
        sum += v;
        squares += (long) v * v;
    }
    long diff = sum - n * (n + 1) / 2;
    long total = (squares - n * (n + 1) * (2 * n + 1) / 6) / diff;
    long repeating = (diff + total) / 2;
    return new int[] { (int) repeating, (int) (repeating - diff) };
}

Call the repeated value x and the missing one y. Every other number appears exactly once, so those cancel and the sum is off by exactly x minus y. The squares are off by x squared minus y squared, which factors into x minus y times x plus y. Divide that by the first difference and you have x plus y. From a difference and a sum, both values fall out with an add and a halve.

It is O(n) time and O(1) space, one pass and a few counters. The naive answers are sorting and looking for the break in the run at O(n log n), or a count array at O(n) extra space. Name those first, then say why you can do better.

The trap is overflow, and it is why Long is not optional. The sum of squares up to n is roughly n cubed over three, so an n near two thousand already blows past a 32 bit Int even though every value is small. The alternative worth naming is XOR. Xor the array with 1 through n to get x xor y, then split everything into two buckets on any set bit of that result and xor each bucket down. No overflow, but a harder story to tell out loud.

With only three possible values you can sort the array in a single pass. Three pointers do it, low and high marking the boundaries of the 0s and 2s already placed, and mid scanning everything in between.

The problem

The array holds only the values 0, 1 and 2, in any order. Sort it ascending in place, in a single pass, so no library sort and no counting pass followed by an overwriting pass. Nothing is returned, the array itself is the answer.

Input, [2, 0, 2, 1, 1, 0].

Output, [0, 0, 1, 1, 2, 2].

• mid sees a 2, so it swaps with the back and high steps in, giving [0, 0, 2, 1, 1, 2].
• mid now sees a 0, swaps with low, which is the same slot, and both step forward. The next 0 does the same.
• mid sees a 2 at index 2, swaps with index 4, giving [0, 0, 1, 1, 2, 2], and high steps in again.
• mid sees 1 twice and just walks past them, mid passes high, and the array is sorted.

fun sortColors(nums: IntArray) {
    var low = 0
    var mid = 0
    var high = nums.size - 1
    while (mid <= high) {
        when (nums[mid]) {
            0 -> swap(nums, low++, mid++)
            1 -> mid++
            else -> swap(nums, mid, high--) // the value swapped in is still unchecked
        }
    }
}

private fun swap(nums: IntArray, i: Int, j: Int) {
    val t = nums[i]
    nums[i] = nums[j]
    nums[j] = t
}

static void sortColors(int[] nums) {
    int low = 0;
    int mid = 0;
    int high = nums.length - 1;
    while (mid <= high) {
        switch (nums[mid]) {
            case 0 -> swap(nums, low++, mid++);
            case 1 -> mid++;
            default -> swap(nums, mid, high--); // the value swapped in is still unchecked
        }
    }
}

static void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

Name it out loud, this is the Dutch national flag algorithm. The invariant is what each region already means at every step. Everything before low is a confirmed 0, everything from low up to mid is a confirmed 1, everything after high is a confirmed 2, and mid through high is still unexamined.

That invariant is also why swapping in a 2 does not advance mid. The value that came back from the high end has never been looked at, so it still needs checking on the next iteration. Swapping a 0 is different, the value coming back from low is always a 1 you have already cleared, so mid is safe to move.

The naive answer is worth mentioning first, counting the 0s, 1s and 2s in one pass and overwriting the array in a second. That is also O(n) time and O(1) space and perfectly correct. The three pointer version is really about doing it in a single pass, which is the specific thing this question tests.

You are given an array and you have to return every distinct triplet of values inside it that adds up to zero. Sort the array, then fix one number and solve two sum on the part to its right with two pointers closing in from both ends, skipping repeats so no triplet comes out twice.

The problem

You are given an array of integers that may hold duplicates, negatives and zeros. You return every distinct triplet of values that adds up to zero, so values and not indices. The same three values must never come back twice, however many ways the array can spell them.

Input [-1, 0, 1, 2, -1, -4].

Output [[-1, -1, 2], [-1, 0, 1]].

• Sorting first gives [-4, -1, -1, 0, 1, 2].
• Fix -4. The two pointers close in over the rest and nothing sums to 4, so no triplet.
• Fix the first -1. The pointers sit on -1 and 2, which sums to zero, so record [-1, -1, 2].
• Both pointers move in to 0 and 1, which also sums to zero, so record [-1, 0, 1].
• Fix the second -1 and skip it as a repeat. Everything left is positive, so the scan ends.

fun threeSum(nums: IntArray): List<List<Int>> {
    nums.sort()
    val out = mutableListOf<List<Int>>()
    for (i in nums.indices) {
        if (i > 0 && nums[i] == nums[i - 1]) continue
        var lo = i + 1
        var hi = nums.size - 1
        while (lo < hi) {
            val sum = nums[i] + nums[lo] + nums[hi]
            if (sum < 0) {
                lo++
            } else if (sum > 0) {
                hi--
            } else {
                out.add(listOf(nums[i], nums[lo], nums[hi]))
                lo++
                hi--
                while (lo < hi && nums[lo] == nums[lo - 1]) lo++
                while (lo < hi && nums[hi] == nums[hi + 1]) hi--
            }
        }
    }
    return out
}

static List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    var out = new ArrayList<List<Integer>>();
    for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int lo = i + 1;
        int hi = nums.length - 1;
        while (lo < hi) {
            int sum = nums[i] + nums[lo] + nums[hi];
            if (sum < 0) {
                lo++;
            } else if (sum > 0) {
                hi--;
            } else {
                out.add(List.of(nums[i], nums[lo], nums[hi]));
                lo++;
                hi--;
                while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
            }
        }
    }
    return out;
}

Sorting is what makes the two pointers legal. Once the values increase left to right, a sum that is too small can only grow by pulling lo right, and a sum that is too big can only shrink by pulling hi left. So every move rules out a whole block of pairs instead of one, and the inner search is linear rather than quadratic.

Sorting also makes duplicates cheap, because equal values sit next to each other. Skipping a repeated nums[i] stops the same first element being fixed twice, and the two while loops after a hit push both pointers past their own repeats, so you never need a set to deduplicate.

It is O(n squared) time, one outer pass times a linear inner scan, and O(1) extra space if you do not count the output list. The brute force is three nested loops at O(n cubed) plus a set to strip duplicate triplets. The trap is deduplicating with a set at the end and calling it optimal, that hides the real work and costs memory you did not need.

Find the longest run of characters that reads the same both ways. Treat every character and every gap between two characters as a possible centre, expand outward while the two sides match, and keep the widest match.

The problem

You are given a string. Return the longest substring of it that reads the same forwards and backwards, and any one of them when several tie for longest. A substring is contiguous, so you may not skip characters. One character on its own counts as a palindrome, so a non empty string always has an answer.

Input "babad"

Output "bab"

• Centred on the first b nothing extends, so the best so far is that one character
• Centred on the a at index 1, both neighbours are b, so it grows to "bab" with length 3
• Centred on the b at index 2 it grows to "aba", which ties at 3 and does not replace the winner

fun longestPalindrome(s: String): String {
    var start = 0
    var maxLen = 0
    for (i in s.indices) {
        val len = maxOf(expand(s, i, i), expand(s, i, i + 1))
        if (len > maxLen) {
            maxLen = len
            start = i - (len - 1) / 2
        }
    }
    return s.substring(start, start + maxLen)
}

private fun expand(s: String, left: Int, right: Int): Int {
    var l = left
    var r = right
    while (l >= 0 && r < s.length && s[l] == s[r]) {
        l--
        r++
    }
    return r - l - 1
}

static String longestPalindrome(String s) {
    int start = 0;
    int maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        int len = Math.max(expand(s, i, i), expand(s, i, i + 1));
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substring(start, start + maxLen);
}

static int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

You need two kinds of centre because a palindrome can have an odd length, with one middle character, or an even length, with a middle gap. Calling expand on (i, i) covers the odd case and (i, i + 1) covers the even one, so running both from every index can never miss a palindrome.

The expand helper returns the length rather than the bounds, which is why the caller recovers the start with i - (len - 1) / 2. That one formula works for both centre kinds, and it is the line to double check on paper before you claim you are done.

There are n centres and each expands at most n times, so it is O(n squared) time and O(1) space beyond the answer. The naive answer is checking every substring for being a palindrome at O(n cubed), worth naming first so the improvement is visible. There is an O(n) answer, Manacher's algorithm, but nobody expects it live, naming it is enough. The usual trap is skipping the even centres, which silently breaks on "abba".

Two strings are anagrams when one is a rearrangement of the other, so they hold the same characters in the same quantities. Count every letter of the first string up and every letter of the second down, then check that all the counts landed back on zero.

The problem

You are given two strings, and you may assume plain lowercase letters. Return true when one is a rearrangement of the other, meaning they hold the same letters in the same quantities. Order does not matter, quantity does, so "aab" and "abb" are not anagrams. Two strings of different lengths never are either.

Input a = "anagram" and b = "nagaram"

Output true

• Both strings have length 7, so the counting is worth starting
• Walking the first string leaves a at 3, and n, g, r and m at 1 each
• Walking the second string subtracts exactly those same letters
• Every one of the 26 slots is back to zero, so the answer is true

fun isAnagram(a: String, b: String): Boolean {
    if (a.length != b.length) return false
    val counts = IntArray(26)
    for (c in a) counts[c - 'a']++
    for (c in b) counts[c - 'a']--
    return counts.all { it == 0 }
}

static boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false;
    var counts = new int[26];
    for (var c : a.toCharArray()) counts[c - 'a']++;
    for (var c : b.toCharArray()) counts[c - 'a']--;
    return Arrays.stream(counts).allMatch(n -> n == 0);
}

One array does both jobs. Adding for the first string and subtracting for the second means a surplus shows up as a positive count and a shortfall as a negative one, so a single sweep at the end settles it. The length check is a cheap early exit worth saying out loud.

There are two honest answers and it helps to name both. Sorting both strings and comparing is the easiest to write under pressure, at O(n log n) time and O(n) space. The counting version is O(n) time and O(1) space, since 26 is a constant and does not grow with the input.

Ask the interviewer whether the input is guaranteed lowercase ASCII. If it is not, a fixed array stops working and you reach for a map from character to count, still O(n) time but O(k) space for the distinct characters actually seen.

You are given a list of strings and you have to return the longest starting stretch that every one of them shares. Scan the words vertically instead of one at a time, comparing character zero of every word, then character one, and stopping the moment a word disagrees or runs out.

The problem

You are given an array of strings. You return the longest run of characters that every one of them starts with, or an empty string when they share nothing. Comparison is exact, so casing matters, and the shortest word in the list caps how long the answer can be.

Input ["interview", "internet", "internal", "interval"].

Output "inter".

• The scan is vertical, one index across all four words, rather than one whole word at a time.
• At index 5 the first word has v and the second has n, so the scan stops there.
• The answer is the first five characters of the first word, inter.

fun longestCommonPrefix(words: Array<String>): String {
    if (words.isEmpty()) return ""
    val first = words[0]
    for (i in first.indices) {
        for (word in words) {
            if (i == word.length || word[i] != first[i]) return first.substring(0, i)
        }
    }
    return first
}

static String longestCommonPrefix(String[] words) {
    if (words.length == 0) return "";
    var first = words[0];
    for (int i = 0; i < first.length(); i++) {
        for (var word : words) {
            if (i == word.length() || word.charAt(i) != first.charAt(i)) {
                return first.substring(0, i);
            }
        }
    }
    return first;
}

The first word is the ceiling. The answer is a prefix of every word, so it can never be longer than the first one, and that is why the outer loop only walks its indices. At index i you check that character against index i of every other word. Two things end the scan, a word that has already run out of characters, and a word whose character differs. Either way the answer is the first i characters of the first word.

Worst case is O(n times m) for n words of length m, with O(1) extra space beyond the string you return. In practice it stops at the first mismatch, so on a real list it usually looks at very few characters.

The other answer worth having ready is to sort the words and compare only the first and the last. Sorting is alphabetical, so after the sort those two are the most different in the list. Anything they both start with is shared by everything sitting between them, so their common prefix is the answer for the whole list. It is a neat trick, though the sort makes it slower than the plain vertical scan.

You are handed the head of a singly linked list and asked whether it loops back on itself. Walk it with two pointers, one moving a node at a time and one moving two, and see whether the fast one ever lands on the slow one.

The problem

You are handed the head of a singly linked list, which may be empty. Return true if following next from the head ever revisits a node, false if it reaches null. You may not modify the list, and the answer the interviewer wants uses no extra memory.

Input, the list 3, 2, 0, -4 where the last node points back at the node holding 2.

Output, true.

• Both pointers start on 3. After one step slow is on 2 and fast is on 0.
• After two steps slow is on 0 and fast has wrapped around to 2.
• After three steps both are on -4, so they have met and the answer is true.
• On the same list without the back link, fast would run off the end and the loop would exit false.

class Node(val value: Int, var next: Node? = null)

fun hasCycle(head: Node?): Boolean {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next?.next
        if (slow === fast) return true
    }
    return false
}

class Node {
    int value;
    Node next;

    Node(int value) { this.value = value; }
}

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

Say the name out loud in the interview, this is Floyd's cycle detection, or the tortoise and hare. The reasoning worth stating is why the two must meet. Once both are inside the loop, the fast pointer gains one step on the slow one every iteration, so the gap shrinks by one each time until it hits zero. They cannot skip past each other on a singly linked list.

It runs in O(n) time and O(1) space, which is the whole reason this question exists. The naive answer is a HashSet of visited nodes, worth mentioning as the first thing you would reach for, but it costs O(n) space. The two pointer trick is what the interviewer is checking you know.

The natural follow up is finding where the loop starts. After the meeting point, move one pointer back to the head and advance both one step at a time. They meet again exactly at the first node of the cycle.

You are handed the head of a singly linked list and you have to return the middle node in one pass, without knowing the length. Walk two pointers from the head, one moving a node at a time and the other two at a time, and when the fast one runs off the end the slow one is standing on the middle.

The problem

You are handed the head of a singly linked list and you are not told its length. You return the middle node itself, not its value, in a single pass. On an even length list you return the second of the two middle nodes, and an empty list gives null back.

Input 1 -> 2 -> 3 -> 4 -> 5.

Output the node holding 3.

• Both pointers start on 1.
• One step later slow is on 2 and fast is on 3.
• One more step and slow is on 3 while fast is on 5.
• Node 5 has no next, so the loop stops with slow sitting on 3.

class Node(val value: Int, var next: Node? = null)

fun middleNode(head: Node?): Node? {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next?.next
    }
    return slow
}

class Node {
    int value;
    Node next;

    Node(int value) { this.value = value; }
}

static Node middleNode(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

The ratio does everything. Fast covers exactly twice the ground slow does, so by the time fast has crossed the whole list slow has crossed half of it. One pass, no length to store, nothing allocated.

For an even length this returns the second of the two middles. On a list of one through six it hands back four, not three. The loop condition is the reason. It keeps going while fast still has a next node, so on six nodes fast reaches node five, sees a next, takes one more double step and falls off, leaving slow one step past centre. If the interviewer wants the first middle instead, loop while fast.next and fast.next.next both exist, and on that same list you get three.

It is O(n) time and O(1) space. The naive answer is two passes, one to count the nodes and one to walk half that many, which is the same big O but not what they are asking for. The empty list falls out for free, both pointers start null, the loop never runs, and null comes back.

You are handed the head of a singly linked list and you have to return the head of the same list running backwards. Walk it once and flip each node's next pointer to point behind it instead of ahead, using three pointers, previous, current and next, so you never lose your place.

The problem

You are handed the head of a singly linked list. You return the head of the same list running backwards, rewiring the existing nodes rather than allocating new ones. The node that used to be last is the one you hand back, and the old head now points at null.

Input 1 -> 2 -> 3 -> 4 -> 5.

Output 5 -> 4 -> 3 -> 2 -> 1.

• Start with prev null and curr on 1. Save 2, point 1 back at null, and move both forward.
• Now prev is 1 and curr is 2. Save 3, point 2 back at 1, move forward.
• The same step runs for 3 and for 4, so the reversed part grows to 4 -> 3 -> 2 -> 1.
• On 5, save null, point 5 back at 4, and curr becomes null. prev is 5, the new head.

class Node(val value: Int, var next: Node? = null)

fun reverseList(head: Node?): Node? {
    var prev: Node? = null
    var curr = head
    while (curr != null) {
        val next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
}

class Node {
    int value;
    Node next;

    Node(int value) { this.value = value; }
}

static Node reverseList(Node head) {
    Node prev = null;
    Node curr = head;
    while (curr != null) {
        Node next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

The moment you rewrite curr.next you lose the only way to reach the rest of the list, which is why next gets saved before that line runs. prev is the piece of the list you have already reversed, curr is the node you are rewiring right now, and once curr runs out prev is sitting on the new head. It is one pass, so this is O(n) time and O(1) space, and that is the whole answer an interviewer wants.

A near certain follow up is to do it recursively. You reverse the rest of the list first, then point the next node's next back at the current one. The new head comes back up the call stack. It reads shorter, but it costs O(n) stack space, one frame per node, so say out loud that the iterative version is the one you would ship.

You are handed the head of a singly linked list and you have to say whether its values read the same forwards and backwards. Find the middle with a slow and fast pointer, reverse the second half in place, then walk the first half and the reversed second half together comparing values.

The problem

You are handed the head of a singly linked list. You return true when its values read the same forwards and backwards, false otherwise. Pointers only run one way, so there is no walking back from the tail, and an empty list or a single node both count as palindromes.

Input 1 -> 2 -> 3 -> 2 -> 1.

Output true.

• The two pointers leave slow on the middle node, the 3.
• Reversing from there turns the tail into 1 -> 2 -> 3.
• Walking both together compares 1 with 1, then 2 with 2, then 3 with 3.
• Nothing disagreed and the reversed half ran out, so the answer is true.

class Node(val value: Int, var next: Node? = null)

fun isPalindrome(head: Node?): Boolean {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next?.next
    }
    var second = reverse(slow)
    var first = head
    while (second != null) {
        if (first?.value != second.value) return false
        first = first.next
        second = second.next
    }
    return true
}

fun reverse(head: Node?): Node? {
    var prev: Node? = null
    var curr = head
    while (curr != null) {
        val next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
}

class Node {
    int value;
    Node next;

    Node(int value) { this.value = value; }
}

static boolean isPalindrome(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    Node second = reverse(slow);
    Node first = head;
    while (second != null) {
        if (first.value != second.value) return false;
        first = first.next;
        second = second.next;
    }
    return true;
}

static Node reverse(Node head) {
    Node prev = null;
    Node curr = head;
    while (curr != null) {
        Node next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Say the plan before the code, find the middle, reverse from there, compare from both ends inward. The first answer most candidates give is to copy the list into an array or a stack, and that is fine to offer, O(n) time and O(n) space. The reverse in place version is the one interviewers want, since it reaches O(n) time and O(1) extra space by reusing the list's own nodes.

Stopping when the reversed half runs out makes the odd length case free, because the middle node is shared by both walks and always matches itself. Worth saying out loud, this mutates the list. The second half stays reversed unless you reverse it back, which is a fair tradeoff to name, or to just fix.

For each position, report the first value to its right that is bigger than it. Scan from the right with a stack that holds only the values still worth comparing against, throwing away everything that the current value already blocks.

The problem

You are given an array of integers. For one position, the next greater element is the first value to its right that is strictly larger, and it is a value, not an index. Return an array of the same length holding that answer for every position, with -1 where nothing to the right is larger. Only the right side counts, so the last position is always -1.

Input nums = [4, 5, 2, 10]

Output [5, 10, 10, -1]

• Start at 10 with an empty stack, so its answer is -1, then push 10
• At 2 the top is 10, which is bigger, so the answer is 10, then push 2
• At 5 the 2 on top loses, so pop it, and the 10 underneath is the answer
• At 4 the 5 on top wins straight away, so the answer is 5

fun nextGreater(nums: IntArray): IntArray {
    val out = IntArray(nums.size)
    val stack = ArrayDeque<Int>()
    for (i in nums.indices.reversed()) {
        while (stack.isNotEmpty() && stack.last() <= nums[i]) stack.removeLast()
        out[i] = if (stack.isEmpty()) -1 else stack.last()
        stack.addLast(nums[i])
    }
    return out
}

static int[] nextGreater(int[] nums) {
    var out = new int[nums.length];
    var stack = new ArrayDeque<Integer>();
    for (int i = nums.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peekLast() <= nums[i]) stack.removeLast();
        out[i] = stack.isEmpty() ? -1 : stack.peekLast();
        stack.addLast(nums[i]);
    }
    return out;
}

The stack stays monotonic, meaning its values decrease from bottom to top, and that is the whole idea. Suppose a value to my right is smaller than or equal to me. It can never be the answer for anything further left, because those positions meet me first and I already block it. So it is safe to drop forever, and dropping it is what keeps the stack small.

Once the clearing is done, whatever sits on top is the nearest value to the right that actually beats the current one. An empty stack means nothing to the right is bigger, so the answer is -1. Then the current value goes on top, ready for the positions still to come on its left.

Each value is pushed once and popped at most once, so it is O(n) time and O(n) space, against the O(n squared) brute force of scanning right from every position. The follow up is the circular version where the array wraps. Run the same loop over twice the indices, read with i % n, and keep only the answers written during the second half of the walk.

Postfix writes each operator after its two operands, and infix writes it between them with brackets to hold the meaning. Keep a stack of half built strings, push every operand on its own, and let every operator pop the two most recent strings and push them back joined.

The problem

You are given a valid postfix expression, where each operator comes after its two operands and there are no brackets anywhere. Operands are single characters. Return the same expression in infix, the notation people write, with the operator between its two operands. Bracket every join, so the reading order can never be lost.

Input "AB*C+"

Output "((A*B)+C)"

• A and B are operands, so they go on the stack as one character strings
• * pops B then A and pushes back "(A*B)"
• C is an operand, so it goes on top of that
• + pops C then "(A*B)" and pushes "((A*B)+C)", which is the only thing left

fun postfixToInfix(expr: String): String {
    val stack = ArrayDeque<String>()
    for (ch in expr) {
        if (ch.isLetterOrDigit()) {
            stack.addLast(ch.toString())
        } else {
            val right = stack.removeLast()
            val left = stack.removeLast()
            stack.addLast("($left$ch$right)")
        }
    }
    return stack.last()
}

static String postfixToInfix(String expr) {
    var stack = new ArrayDeque<String>();
    for (char ch : expr.toCharArray()) {
        if (Character.isLetterOrDigit(ch)) {
            stack.addLast(String.valueOf(ch));
        } else {
            var right = stack.removeLast();
            var left = stack.removeLast();
            stack.addLast("(" + left + ch + right + ")");
        }
    }
    return stack.peekLast();
}

Postfix is already written in evaluation order, so this is the same loop that would evaluate the expression, only it builds a string where an evaluator would compute a number. Order matters when you pop. The first value off is the right operand and the second is the left, because the right one was pushed most recently. Swapping those two lines still runs and quietly reverses every subtraction and division.

The brackets are not decoration. Postfix carries no precedence at all, the whole meaning sits in the order, so AB*C+ has to come back as ((A*B)+C) and never as A*B+C read some other way. Wrapping every join preserves the meaning exactly, at the cost of brackets a human would not write, and that is the accepted answer.

One pass with one push or two pops per character, so O(n) time and O(n) space for the stack. Prefix is the mirror image. Walk the expression from right to left, and when you join, put the operator in front of the two operands instead of between them.

For every element you want the first value to its right that is smaller than it. Walk the array from right to left carrying a stack of candidates, popping everything on top that is greater than or equal to the current value.

The problem

You get an array of integers, duplicates allowed. Return a new array of the same length where each slot holds the first value to the right of that position that is strictly smaller than it. Where nothing smaller lies to the right, the slot holds -1. Strictly smaller matters, an equal value is not an answer.

Input, [4, 8, 5, 2, 25].

Output, [2, 5, 2, -1, -1].

• Start at 25 with an empty stack, so its answer is -1, and 25 goes on the stack.
• At 2, pop 25 because it is bigger, the stack empties, so the answer is -1, and 2 goes on.
• At 5, the top is 2 which is smaller, so the answer is 2, and 5 goes on above it.
• At 8, the top is 5, so the answer is 5. At 4, pop 8 and 5, and the surviving top 2 is the answer.

fun nextSmallerElements(nums: IntArray): IntArray {
    val result = IntArray(nums.size)
    val stack = ArrayDeque<Int>()
    for (i in nums.indices.reversed()) {
        while (stack.isNotEmpty() && stack.last() >= nums[i]) stack.removeLast()
        result[i] = if (stack.isEmpty()) -1 else stack.last()
        stack.addLast(nums[i])
    }
    return result
}

static int[] nextSmallerElements(int[] nums) {
    int[] result = new int[nums.length];
    var stack = new ArrayDeque<Integer>();
    for (int i = nums.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() >= nums[i]) stack.pop();
        result[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    return result;
}

The popping is the part worth saying out loud. If a value to the right is bigger than the current one, it can never be the answer for anything further left, because the current value sits closer and is already smaller. So it is safe to throw away forever. That leaves the stack increasing from the top down, and the top is always the nearest smaller value to the right.

The naive answer to mention first is a second loop scanning right from every index for the first smaller value, which is O(n squared). The stack version is O(n) time, because each element is pushed once and popped at most once, and O(n) space for the stack and the output.

This is the exact mirror of next greater element. Flip the pop condition from greater than or equal to less than or equal and you have that instead. The trap is the equality. Popping on greater than or equal gives the next strictly smaller value, which is what is usually asked, while popping only on greater would let an equal value stand as the answer.

Build first in first out behaviour out of two last in first out stacks. Push every new value onto one stack, and only when a dequeue finds the second stack empty, pour the whole first stack across, which flips the order.

The problem

Build first in first out behaviour where the only storage you may use is stacks, so push, pop and a test for empty and nothing else. Enqueue adds a value at the back, and dequeue removes and returns the oldest value still waiting. Each operation should cost O(1) on average, which is not the same as O(1) on every call.

Input, the calls enqueue 1, enqueue 2, dequeue, enqueue 3, dequeue, dequeue.

Output, 1, then 2, then 3.

The state after each call, with both stacks written bottom to top.

• The first dequeue finds the out stack empty, pours the in stack across so it holds 2 with 1 on top, and pops 1.
• The second dequeue pops 2 straight off the out stack, so the 3 sitting in the in stack is never touched.
• The last dequeue finds the out stack empty again, pours 3 across, and returns 3.

class QueueUsingStacks<T> {
    private val inStack = ArrayDeque<T>()
    private val outStack = ArrayDeque<T>()

    fun enqueue(x: T) {
        inStack.addLast(x)
    }

    fun dequeue(): T {
        if (outStack.isEmpty()) {
            while (inStack.isNotEmpty()) outStack.addLast(inStack.removeLast())
        }
        return outStack.removeLast()
    }
}

class QueueUsingStacks<T> {
    private final Deque<T> inStack = new ArrayDeque<>();
    private final Deque<T> outStack = new ArrayDeque<>();

    public void enqueue(T x) {
        inStack.addLast(x);
    }

    public T dequeue() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) outStack.addLast(inStack.removeLast());
        }
        return outStack.removeLast();
    }
}

The in stack collects values in arrival order, newest on top. Popping them all onto the out stack reverses that order, so the oldest value, the one a queue hands back first, ends up on top. The transfer only happens when the out stack runs dry, which is the lazy part. Anything already sitting there gets popped straight off without touching the in stack again.

Any single dequeue that triggers a transfer costs O(n), but each value is moved across exactly once in its whole lifetime. Spread that one move over the operations it takes to get a value in and back out and the average settles at O(1). Amortised is the word to say here, because it tells the interviewer you know one call can still cost O(n).

The common trap is transferring eagerly on every enqueue instead of lazily on dequeue. It still works, but it throws away the amortised saving and makes every operation pay the full O(n).

You have to give last in first out behaviour using only a structure that hands back the oldest item first. Keep everything in a single queue and rotate it after every push, so the newest value ends up at the front and the front of the queue is the top of the stack.

The problem

You build a stack, last in first out, out of a queue, which is first in first out. It supports four operations, push, pop, top and isEmpty. Inside the class you may only add at the back of the queue and remove from its front, so no array and no second kind of container.

Input the calls push 1, push 2, push 3, then top, then pop.

Output 3 from top, and 3 again from the pop after it.

• Pushing 1 leaves the queue as [1] with nothing to rotate.
• Pushing 2 makes it [1, 2], then one rotation moves the 1 behind, giving [2, 1].
• Pushing 3 makes it [2, 1, 3], then two rotations give [3, 2, 1].
• The newest value is at the front, so top reads it and pop removes it.

class StackUsingQueue<T> {
    private val queue = ArrayDeque<T>()

    fun push(x: T) {
        queue.addLast(x)
        repeat(queue.size - 1) { queue.addLast(queue.removeFirst()) }
    }

    fun pop(): T = queue.removeFirst()

    fun top(): T = queue.first()

    fun isEmpty(): Boolean = queue.isEmpty()
}

class StackUsingQueue<T> {
    private final Deque<T> queue = new ArrayDeque<>();

    public void push(T x) {
        queue.addLast(x);
        for (int i = queue.size() - 1; i > 0; i--) {
            queue.addLast(queue.removeFirst());
        }
    }

    public T pop() { return queue.removeFirst(); }

    public T top() { return queue.getFirst(); }

    public boolean isEmpty() { return queue.isEmpty(); }
}

The new value goes on the back like any queue insert, then rotating the older values from front to back, one at a time, walks them all around behind it. After that rotation the newest value is at the front, so pop and top just read the front of the queue as if it were the top of a stack.

The rotation is what costs you. push moves up to n elements, so it is O(n), while pop and top are O(1) because the queue is already in the right order by the time they are called. That trade is the whole point of the question. A queue naturally gives you the oldest item first, so you pay to flip that order back to newest first on every insert.

The two queue version is the same idea spread across two containers. You push into an empty queue, drain the other one into it, then swap which queue is active. It is the same O(n) push and O(1) pop. The natural follow up is to flip the cost, making push O(1) and paying the rotation on pop instead, which moves the work without reducing it.

Infix puts an operator between its two operands, postfix puts it after both, and the brackets disappear. Send operands straight to the output and park operators on a stack, popping anything already there that binds at least as tightly.

The problem

You are given a valid infix expression, the notation people write, where every operator sits between its two operands. Operands are single characters, and the operators are the four arithmetic ones, ^ for power, and round brackets. Return the same expression in postfix, where every operator comes after both of its operands. Postfix needs no brackets at all, because the order of the operators carries the meaning on its own.

Input "(p+q)*(m-n)"

Output "pq+mn-*"

• p goes out, + waits on the stack above the open bracket, q goes out
• The closing bracket drains down to that bracket, so + joins the output and both brackets vanish
• * finds an empty stack and waits, then the second bracket repeats the pattern and sends out mn-
• Only * is left waiting, so the final drain appends it and the output reads pq+mn-*

fun infixToPostfix(expr: String): String {
    val out = StringBuilder()
    val ops = ArrayDeque<Char>()
    for (ch in expr) {
        when {
            ch.isLetterOrDigit() -> out.append(ch)
            ch == '(' -> ops.addLast(ch)
            ch == ')' -> {
                while (ops.last() != '(') out.append(ops.removeLast())
                ops.removeLast()
            }
            // '^' is right associative, so nothing on the stack outranks it.
            else -> {
                while (ch != '^' && ops.isNotEmpty() && rank(ops.last()) >= rank(ch)) out.append(ops.removeLast())
                ops.addLast(ch)
            }
        }
    }
    while (ops.isNotEmpty()) out.append(ops.removeLast())
    return out.toString()
}

private fun rank(op: Char) = when (op) { '^' -> 3; '*', '/' -> 2; '+', '-' -> 1; else -> 0 }

static String infixToPostfix(String expr) {
    var out = new StringBuilder();
    var ops = new ArrayDeque<Character>();
    for (char ch : expr.toCharArray()) {
        if (Character.isLetterOrDigit(ch)) out.append(ch);
        else if (ch == '(') ops.addLast(ch);
        else if (ch == ')') {
            while (ops.peekLast() != '(') out.append(ops.removeLast());
            ops.removeLast();
        } else {
            // '^' is right associative, so nothing on the stack outranks it.
            while (ch != '^' && !ops.isEmpty() && rank(ops.peekLast()) >= rank(ch)) out.append(ops.removeLast());
            ops.addLast(ch);
        }
    }
    while (!ops.isEmpty()) out.append(ops.removeLast());
    return out.toString();
}

static int rank(char op) { return switch (op) { case '^' -> 3; case '*', '/' -> 2; case '+', '-' -> 1; default -> 0; }; }

Operands never wait, their order is the same in both notations. Operators do wait, because a postfix operator comes after both of its operands and you have only seen one when you read it. The stack holds those pending operators and rank decides when each is allowed to leave.

A + arriving on top of a * means the * already has both operands, so it pops first. A * arriving on top of a + means the + is still short one, so it stays. Equal ranks pop too, which gives left to right order for plus and minus. Giving ( a rank of zero makes it a wall no comparison pops past, and ) drains down to that wall and discards both brackets. Every character is pushed and popped at most once, so it is O(n) time and O(n) space. The usual slip is forgetting the drain at the end, since whatever is still on the stack belongs at the tail of the output.

Given bar heights, work out how much rain settles between them. Water above a bar is the smaller of the tallest bar to its left and the tallest to its right, minus its own height, so two pointers walk inward carrying those two maxima.

The problem

The array holds the heights of bars standing side by side, each one unit wide, and a height may be zero. Return the total units of water that settle between them after rain. Water sits above a bar only when a taller bar stands somewhere to its left and somewhere to its right, so the two outermost bars never hold any.

Input, [4, 2, 0, 3, 2, 5].

Output, 9.

• Both pointers start at the ends. The left bar 4 is shorter than the right bar 5, so the left side moves and leftMax becomes 4.
• Bar 2 is still on the short side, so it traps 4 minus 2, which is 2. Bar 0 traps 4 and bar 3 traps 1, running the total to 7.
• The last bar 2 traps another 2 for a total of 9, the pointers meet, and 9 is the answer.

fun trap(height: IntArray): Int {
    var left = 0
    var right = height.size - 1
    var leftMax = 0
    var rightMax = 0
    var water = 0
    while (left < right) {
        if (height[left] <= height[right]) {
            leftMax = maxOf(leftMax, height[left])
            water += leftMax - height[left++]
        } else {
            rightMax = maxOf(rightMax, height[right])
            water += rightMax - height[right--]
        }
    }
    return water
}

static int trap(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int leftMax = 0;
    int rightMax = 0;
    int water = 0;
    while (left < right) {
        if (height[left] <= height[right]) {
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left++];
        } else {
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right--];
        }
    }
    return water;
}

Start with the version you would write first, two passes filling a prefix max array and a suffix max array, then a third pass adding the smaller of the two minus the height. That is O(n) time but O(n) extra space, and it is the honest first answer.

The two pointer version removes those arrays. When the left bar is the shorter of the two ends, some bar at or beyond the right pointer is at least that tall, so the right side can only help. That means leftMax alone already decides the water over the left bar, and you can settle that column and step forward. The same argument runs the other way when the right end is shorter. It is O(n) time and O(1) space. There is also a monotonic stack version that fills water layer by layer as each bar pops a shorter one off the stack, worth naming but harder to get right under pressure. The trap in every version is the edges, and here the pointers converge before the first or last bar can wrongly collect water.

You are given the root of a binary tree and you have to return its values level by level, left to right, with each level as its own list. Push the root into a queue and read the queue's size at the start of every round, because that size is exactly how many nodes sit on the current level.

The problem

You are given the root of a binary tree, which may be null. You return a list of lists, one list per depth, each holding that depth's values from left to right. The tree is not sorted, and the levels come out top down.

Input the tree below, written level by level as [3, 9, 20, null, null, 15, 7].

Output [[3], [9, 20], [15, 7]].

• Round one, the queue holds 3. Take it, record [3], and push 9 and 20.
• Round two, the size is 2. Take 9 and 20, record [9, 20], and push 15 and 7.
• Round three, the size is 2. Take 15 and 7, record [15, 7], and nothing goes back in.

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun levelOrder(root: TreeNode?): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    if (root == null) return result
    val queue = ArrayDeque<TreeNode>()
    queue.add(root)
    while (queue.isNotEmpty()) {
        val level = mutableListOf<Int>()
        repeat(queue.size) {
            val node = queue.removeFirst()
            level.add(node.value)
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }
        result.add(level)
    }
    return result
}

class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int value) { this.value = value; }
}

static List<List<Integer>> levelOrder(TreeNode root) {
    var result = new ArrayList<List<Integer>>();
    if (root == null) return result;
    var queue = new ArrayDeque<TreeNode>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        var level = new ArrayList<Integer>();
        for (int i = 0; i < levelSize; i++) {
            var node = queue.removeFirst();
            level.add(node.value);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        result.add(level);
    }
    return result;
}

Reading queue.size once, before you start draining, is the one line that makes this work. Read it again inside the loop and it keeps growing as children arrive, so you lose the boundary between one level and the next. Kotlin's repeat takes that count up front and the Java loop copies it into levelSize for the same reason. Everything else is a plain breadth first search, dequeue a node, record it, enqueue its children.

It is O(n) time and O(n) space, since every node is visited once and a complete tree's last level holds about half of them. A common follow up is a zigzag traversal, where alternate levels come out reversed, and that is the same code with a boolean that flips each round.

The diameter is the longest path between any two nodes, and it does not have to pass through the root. One postorder walk does it, where every node returns its height upward and records the path bending through it on the way.

The problem

You get the root of a binary tree and return the length of its longest path, counted in edges. The path can run between any two nodes and does not have to pass through the root. Edges and not nodes, so a tree holding a single node has diameter zero.

Input, the tree [1, 2, 3, 4, 5] in level order.

Output, 3, the path 4 to 2 to 1 to 3.

• Leaves 4 and 5 see two empty children, record a bend of 0, and each return height 1.
• Node 2 gets 1 from each side, records a bend of 2, and returns height 2.
• Node 3 is a leaf, records 0, and returns height 1.
• Node 1 gets 2 on the left and 1 on the right, records a bend of 3, which beats 2 and is the answer.

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun diameter(root: TreeNode?): Int {
    var best = 0
    fun height(node: TreeNode?): Int {
        if (node == null) return 0
        val left = height(node.left)
        val right = height(node.right)
        best = maxOf(best, left + right)
        return 1 + maxOf(left, right)
    }
    height(root)
    return best
}

class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int value) { this.value = value; }
}

static int diameter(TreeNode root) {
    int[] best = { 0 };
    height(root, best);
    return best[0];
}

static int height(TreeNode node, int[] best) {
    if (node == null) return 0;
    int left = height(node.left, best);
    int right = height(node.right, best);
    best[0] = Math.max(best[0], left + right);
    return 1 + Math.max(left, right);
}

The key observation is that the longest path has a highest point, one node where it turns from going down the left side to going down the right side. So if you visit every node and ask how long the path bending here would be, one of those answers has to be the diameter. That length is just the left height plus the right height.

The two numbers a node deals in are different, and mixing them up is the classic mistake. What it reports upward is a height, one plus the taller child, because a parent can only continue down one side. What it records is a diameter, left plus right, because a path may bend here but nowhere above.

The naive version recomputes height from scratch at every node, which is O(n squared) on a skewed tree. One postorder pass makes it O(n) time and O(h) space for the recursion stack. Note this counts edges, so a single node has diameter zero. If the question asks for nodes on the path, add one.

The left view is what you see standing to the left of the tree, one node per level. Do a preorder walk that goes left before right and record a node the first time you reach a new level.

The problem

You get the root of a binary tree and return one value per level, from the top down. Each value is the leftmost node at that depth, meaning the first one you would meet reading that level left to right. That node is not always a left child, it is simply the one nothing else at that depth sits to the left of.

Input, the tree [1, 2, 3, 4, 5, null, 6] in level order.

Output, [1, 2, 4].

• Node 1 arrives at level 0 with an empty result, so 1 is recorded.
• Going left, node 2 arrives at level 1 with one value stored, so 2 is recorded, then node 4 at level 2 records 4.
• Node 5 is also at level 2, but the result already holds three values, so it is skipped.
• Back on the right, node 3 at level 1 and node 6 at level 2 are both skipped for the same reason.

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun leftView(root: TreeNode?): List<Int> {
    val result = mutableListOf<Int>()
    fun walk(node: TreeNode?, level: Int) {
        if (node == null) return
        if (level == result.size) result.add(node.value)
        walk(node.left, level + 1)
        walk(node.right, level + 1)
    }
    walk(root, 0)
    return result
}

class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int value) { this.value = value; }
}

static List<Integer> leftView(TreeNode root) {
    var result = new ArrayList<Integer>();
    walk(root, 0, result);
    return result;
}

static void walk(TreeNode node, int level, List<Integer> result) {
    if (node == null) return;
    if (level == result.size()) result.add(node.value);
    walk(node.left, level + 1, result);
    walk(node.right, level + 1, result);
}

The check level == result.size is doing the work of a highest level seen so far. The result holds one entry per level visited, so its size is exactly the next level waiting to be filled. Because left is recursed before right, the first call to reach a given level always comes from the leftmost node at that depth, so the check fires once per level.

The other common way is level order BFS with a queue. Take the first node dequeued at the start of each level and skip the rest. Same idea, iterative instead of recursive, and easier to reason about if recursion depth on a skewed tree worries you. Both are O(n) time, and space runs from O(h) to O(n) depending on whether you count the stack or the queue.

The right view is the mirror of this. Recurse right before left, or take the last node dequeued at each level instead of the first.

The top view is what you would see looking straight down at the tree, one node per vertical column. Give every node a horizontal distance from the root, then walk the tree breadth first and keep only the first node you meet at each distance.

The problem

You are given the root of a binary tree. Give every node a horizontal distance, 0 at the root, one less for a left child and one more for a right child, so nodes line up in vertical columns. The top view is the shallowest node in each column, what you would see looking straight down. Return one value per column, leftmost column first.

Input the tree [1, 2, 3, 4, 5, null, 6] in level order, null for a missing child

Output [4, 2, 1, 3, 6]

• The root claims distance 0 with the value 1
• The next level gives 2 at distance -1 and 3 at distance 1, both new columns, so both are kept
• The bottom level keeps 4 at distance -2 and 6 at distance 2, but hides the 5, since it lands at distance 0 and the root claimed that column first

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun topView(root: TreeNode?): List<Int> {
    if (root == null) return emptyList()
    val firstAtDistance = sortedMapOf<Int, Int>()
    val queue = ArrayDeque<Pair<TreeNode, Int>>()
    queue.add(root to 0)
    while (queue.isNotEmpty()) {
        val (node, hd) = queue.removeFirst()
        if (hd !in firstAtDistance) firstAtDistance[hd] = node.value
        node.left?.let { queue.add(it to hd - 1) }
        node.right?.let { queue.add(it to hd + 1) }
    }
    return firstAtDistance.values.toList()
}

class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int value) { this.value = value; }
}

record Visit(TreeNode node, int hd) {}

static List<Integer> topView(TreeNode root) {
    if (root == null) return List.of();
    var firstAtDistance = new TreeMap<Integer, Integer>();
    var queue = new ArrayDeque<Visit>();
    queue.add(new Visit(root, 0));
    while (!queue.isEmpty()) {
        var visit = queue.removeFirst();
        int hd = visit.hd();
        firstAtDistance.putIfAbsent(hd, visit.node().value);
        if (visit.node().left != null) queue.add(new Visit(visit.node().left, hd - 1));
        if (visit.node().right != null) queue.add(new Visit(visit.node().right, hd + 1));
    }
    return new ArrayList<>(firstAtDistance.values());
}