Capstone: a Mixed Problem Marathon

Count the occurrences of each character and then take the one with the highest count. The two steps are separate, which is the shape of most counting problems: build a summary with one pass, then answer the question from the summary.

from collections import Counter


def most_common_char(text):
    counts = Counter(text)
    return max(counts, key=counts.get)


print(most_common_char("interview"))
print(most_common_char("abc"))

The outputs are i and a. In interview the letter i appears twice, and so does the letter e, but the i appears first in the string and the counts dictionary preserves insertion order, so the i is returned. In abc every letter appears once and the a is the first.

The mechanism is that the dictionary maps each character to its count, and the maximum is taken over those counts. Using the count as the key of the max function is what makes it pick the character rather than the number, and it is the step people most often get wrong by returning the count instead.

The trade-off to name is the tie. When two characters share the highest count, the answer depends on the order, and saying which convention you are using is part of a good answer. There is also the empty string to handle, since the max of an empty sequence raises an error. For a longer text the same pattern is the first half of the top k frequent elements problem, where the second half is selecting the k largest counts, and a heap or a bucket sort does that part.

Put one pointer at each end of the sorted array and compare their sum with the target. If the sum is too small, the left pointer has to move right; if it is too large, the right pointer has to move left.

def two_sum_sorted(values, target):
    left, right = 0, len(values) - 1
    while left < right:
        total = values[left] + values[right]
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return None


print(two_sum_sorted([2, 7, 11, 15], 9))
print(two_sum_sorted([1, 2, 3, 4], 99))

The outputs are the pair zero and one, and None. The first call finds 2 and 7 in the first two positions, and the second fails because even the largest pair does not reach ninety nine.

The mechanism is the ordering argument. If the sum of the two end values is too small, then pairing the left value with any smaller right value would only make it smaller, so the left value cannot be part of any solution and can be discarded. The mirror argument handles the case where the sum is too large. Each pointer move therefore eliminates a candidate that provably cannot appear in any answer.

The trade-off to name is the precondition. The two pointers technique needs sorted data, so on unsorted input it will happily return wrong answers. Sorting first costs O of n log n time and O of n space if you copy, which is worse than the hash map version of two sum that runs in linear time, so the technique is a win when the data is already sorted or when you will query it many times. The other thing to remember is that this finds one pair, and returning all pairs means continuing the scan rather than stopping at the first hit.

The honest and effective answer is that you do not pretend. You say what you understand, what you have tried, and where you are stuck, and then you ask for a hint or for the smallest example that would move you forward. Interviewers are not running a test of whether you can solve every problem, they are assessing how you behave when you cannot, and most of them will give you a nudge.

What helps in the moment is narrowing the problem deliberately. Take a small input and work it through by hand. Try the simplest case, an empty or single element input, and see what your algorithm produces. Write down the invariant you believe your solution maintains and check it against that small case. Often the bug is not that the idea is wrong but that the base case or the boundary was handled wrongly, and the small case shows that immediately.

The mechanism is that partial progress is still signal. Explaining why the obvious approach fails, ruling out two approaches with clear reasoning, and narrowing the space of possible solutions all demonstrate the same engineering judgement that a complete solution would. A candidate who says nothing for ten minutes demonstrates very little.

The trade-off to name is that asking for help feels like failure, and candidates often burn ten minutes on a dead end rather than asking. The better trade is to spend two or three minutes attacking the problem yourself, because that produces the specific question that unblocks you, and then ask. Interviewers remember how you handled the hard part at least as much as the easy part, and they have a rubric for it.