Binary Search Questions at Tinkoff: What to Expect

Binary Search isn't just about finding an element in a sorted array. At Tinkoff, it's a critical tool for solving optimization and range-query problems efficiently. With 3 out of their 27 total coding problems dedicated to this algorithm, proficiency here is non-negotiable. Tinkoff's problems often involve large datasets or constraints where a linear scan would be too slow. Mastering binary search demonstrates you can think beyond brute force and apply algorithmic optimization—a key skill they assess for backend and data-intensive roles.

What to Expect — Types of Problems

You will not see textbook "find 5 in this array" questions. Tinkoff's binary search problems typically fall into two advanced categories:

1. Modified Search on Sorted Structures: The array is sorted, but it's rotated, has duplicates, or you need to find a boundary (like the first bad version, the first occurrence, or the insertion point). The challenge is adapting the classic loop condition and pointer updates.
2. Binary Search on Answer (or "Search Space"): This is the most common and tricky pattern. The problem presents a scenario where you must find a minimum or maximum value (like the smallest capacity, the largest minimum distance, or the earliest time) that satisfies a given condition. The key insight is that if a value X works, then all values greater (or lesser) than X might also work, creating a monotonic condition perfect for binary search. You implement a validation function check(mid) and search over a range of possible answers.

How to Prepare — Study Tips with One Code Example

Internalize the standard binary search pattern to avoid off-by-one errors. Then, practice the "Binary Search on Answer" framework:

1. Identify the search space (low, high).
2. Write a helper function canWeDo(x) that returns true if x is a feasible answer.
3. Perform a standard binary search. If canWeDo(mid) is true, look for a better (smaller/larger) answer; otherwise, adjust the search space.

Consider this classic "Koko Eating Bananas" style problem: Find the minimum rate to complete a task within a time limit.

def min_rate(work, h):
    def can_finish(rate):
        time = 0
        for w in work:
            time += (w + rate - 1) // rate  # ceil division
        return time <= h

    low, high = 1, max(work)
    while low < high:
        mid = (low + high) // 2
        if can_finish(mid):
            high = mid       # try for a smaller rate
        else:
            low = mid + 1    # need a faster rate
    return low

Recommended Practice Order

Build competence sequentially:

1. Fundamentals: Standard search, first/last position, search in rotated array.
2. Search on Answer: Start with straightforward conditions (like the eating bananas problem), then move to more complex validation logic.
3. Tinkoff-Specific: Finally, tackle problems from Tinkoff's tagged question bank to adapt to their style and constraints.

Practice Binary Search at Tinkoff