TikTok 2027 Intern OA (10/2): Robot Position, KMP Pattern Matching, Bouncing Diagonals, Max Profit After a Strategy Change

Four questions on the TikTok 2027 Intern OA — nothing too challenging; if you're fluent at coding you'll pass on the first try.

1. The robot's final position

Treat the robot's position as an integer starting at 0. Scan commands: L subtracts 1, R adds 1.

At the end: a position < 0 returns "L", > 0 returns "R", and 0 means it's back at the start — return an empty string. Time O(n), space O(1).

def final_direction(commands):
    pos = commands.count("R") - commands.count("L")
    return "R" if pos > 0 else "L" if pos < 0 else ""

2. Counting a pattern in a comparison array

First turn the relationship between neighbors into a comparison array: 1 if the next element is larger, 0 if equal, −1 if smaller. The problem becomes counting occurrences of pattern in that array.

You can match position by position, or use KMP to count every match in linear time: build the pattern's prefix function, then scan the comparison array. Time O(n + m), space O(m).

def count_pattern_matches(nums, pattern):
    cmp = [(b > a) - (b < a) for a, b in zip(nums, nums[1:])]
    m = len(pattern)
    if m == 0:
        return 0
    fail = [0] * m                       # KMP prefix function
    j = 0
    for i in range(1, m):
        while j and pattern[i] != pattern[j]:
            j = fail[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        fail[i] = j
    count = j = 0
    for x in cmp:
        while j and x != pattern[j]:
            j = fail[j - 1]
        if x == pattern[j]:
            j += 1
        if j == m:
            count += 1
            j = fail[j - 1]
    return count

3. Sort the first column by bouncing-diagonal weight

For each element of the first column, compute the weight of its bouncing diagonal: start at (r, 0), move one column right at a time while moving up, and bounce off the edges. In an n×n matrix, column c corresponds to row abs(r − c).

Sum the values along each path to get the weight. Store each element as (weight, first-column value), sort by weight ascending (ties by value ascending), and read off the sorted first column. Time O(n²), sorting O(n log n).

def sort_first_column_by_bounce(matrix):
    n, m = len(matrix), len(matrix[0])
    items = []
    for r in range(n):
        row, step, weight = r, -1, 0     # start by moving up
        for c in range(m):
            weight += matrix[row][c]
            if n > 1:
                if not 0 <= row + step < n:
                    step = -step         # bounce off the edge
                row += step
        items.append((weight, matrix[r][0]))
    return [v for _, v in sorted(items)]

The simulation above also works for non-square matrices; for an n×n matrix you can use matrix[abs(r - c)][c] directly.

4. Maximum profit after modifying the strategy

First compute the profit of the original strategy: strategy −1 means buy (contributes −price), 1 means sell (contributes +price), 0 contributes nothing.

Then try every window of length k: after modification, the first half becomes 0 and the second half becomes 1. To evaluate each window quickly, build prefix sums of the original profit and of the prices:

• The window's original profit comes from the profit prefix sums.
• After modification only the second half's prices count as profit, from the price prefix sums.

Take the maximum gain over all windows. Not modifying is allowed, so the maximum gain starts at 0.

def max_profit_with_one_change(prices, strategy, k):
    n, half = len(prices), k // 2
    pp, ps = [0], [0]                    # prefix sums of original profit and of prices
    for p, s in zip(prices, strategy):
        pp.append(pp[-1] + p * s)
        ps.append(ps[-1] + p)
    best_gain = 0                        # not changing anything is allowed
    for i in range(n - k + 1):
        before = pp[i + k] - pp[i]
        after = ps[i + k] - ps[i + half]
        best_gain = max(best_gain, after - before)
    return pp[n] + best_gain

Time O(n), space O(n).