Agoda interview questions & answers

20 real Agoda interview questions with full model answers — Product & growth, Coding. Drawn from the same verified bank ChannelPulse drills from (42 Agoda questions in total).

CodingEasyAgodaSoftware Engineer

1. Valid Word Abbreviation (LeetCode)

Model answer

The task

Check whether an abbreviation describes a given word. Letters must match in order, and each number skips that many characters in the word; a number cannot start with zero.

Key idea

Walk through the word and abbreviation with two pointers. When the abbreviation has a digit, parse the whole number and advance the word pointer by that amount; otherwise, the characters must match.

Approach

  1. Start both pointers at the beginning of their strings.
  2. If the next abbreviation character is a letter, require it to match the current word character, then advance both pointers.
  3. If it is a digit, reject a leading zero, parse all consecutive digits as one skip count, and advance the word pointer.
  4. Reject if a skip goes beyond the word.
  5. Return true only if both pointers reach the ends together.
class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        word_index = 0
        abbr_index = 0

        while abbr_index < len(abbr):
            if abbr[abbr_index].isdigit():
                # Leading zeroes are not valid in a skip count.
                if abbr[abbr_index] == "0":
                    return False

                skip = 0
                while abbr_index < len(abbr) and abbr[abbr_index].isdigit():
                    skip = skip * 10 + int(abbr[abbr_index])
                    abbr_index += 1

                word_index += skip
                if word_index > len(word):
                    return False
            else:
                if word_index >= len(word) or word[word_index] != abbr[abbr_index]:
                    return False

                word_index += 1
                abbr_index += 1

        return word_index == len(word)

Complexity:

  • Time: O(n + m), where n and m are the lengths of the word and abbreviation.
  • Space: O(1), using only a few pointer and counter variables.

Common follow-ups

  • How would you handle Unicode letters? Use the same pointer logic, with the desired definition of “digit” and “letter.”
  • Can the abbreviation be validated without parsing large integers? Yes; cap the skip count once it exceeds the remaining word length.
  • What edge cases matter? Empty strings, a skip past the end, unmatched trailing characters, and numbers with leading zeroes.
CodingEasyAgodaSoftware Engineer

2. Backspace String Compare (LeetCode)

Model answer

The task

Compare two strings after applying backspaces: each # removes the most recent character when one exists. Return whether the resulting strings are equal.

Key idea

Scan both strings from right to left. Count how many characters each backspace should skip, so the strings can be compared without building their edited versions.

Approach

  1. Start a pointer at the end of each string.
  2. For each string, move left while tracking pending backspaces.
  3. Skip a character if a backspace is pending; otherwise it is the next visible character.
  4. Compare the next visible characters. If they differ, return False.
  5. Continue until both strings have no visible characters left, then return True.
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def next_visible(text: str, index: int) -> tuple[str | None, int]:
            """Return the next character not erased by a backspace, and its index."""
            skips = 0

            while index >= 0:
                if text[index] == "#":
                    skips += 1
                elif skips > 0:
                    skips -= 1
                else:
                    return text[index], index - 1

                index -= 1

            return None, -1

        i, j = len(s) - 1, len(t) - 1

        while i >= 0 or j >= 0:
            char_s, i = next_visible(s, i)
            char_t, j = next_visible(t, j)

            if char_s != char_t:
                return False

        return True

Complexity:

  • Time: O(m + n), where m and n are the string lengths; each character is visited at most once.
  • Space: O(1), excluding the helper’s constant-size state.

Common follow-ups

  • What if backspace is represented by a different character? Pass it into the helper or replace the "#" check.
  • How would you implement this with a stack? Build each edited string by appending ordinary characters and popping on backspace, then compare.
  • What happens when a backspace appears with nothing to erase? It is ignored, as handled by the skip count.
CodingEasyAgodaSoftware Engineer

3. Next Greater Element I (LeetCode)

Model answer

The task

For each value in one array, find the first larger value appearing to its right in a second array that contains it. Return -1 when no such value exists.

Key idea

Scan the second array from left to right with a decreasing stack. When a new value is larger than values on the stack, it is the next greater value for each of them; store those answers in a hash map.

Approach

  1. Initialize an empty stack and a map of answers.
  2. For each value in the second array, pop smaller values from the stack and map each popped value to the current value.
  3. Push the current value onto the stack.
  4. Values still on the stack have no greater value to their right.
  5. Build the result by looking up each value from the first array, using -1 when it has no mapped answer.
from typing import List

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        next_greater = {}
        decreasing_stack = []

        for value in nums2:
            # The current value is the first greater value for each
            # smaller value waiting on the stack.
            while decreasing_stack and decreasing_stack[-1] < value:
                next_greater[decreasing_stack.pop()] = value
            decreasing_stack.append(value)

        # Any value without a recorded answer has no greater value to its right.
        return [next_greater.get(value, -1) for value in nums1]

Complexity:

  • Time: O(n + m), where n and m are the lengths of the two arrays; each value is pushed and popped at most once.
  • Space: O(m), for the stack and answer map.

Common follow-ups

  • What if the second array is circular? Scan it twice, using indices modulo its length, and push only during the first pass.
  • What if values can repeat? Track indices on the stack and define how to match repeated values from the first array.
  • Can the answers be found online as values arrive? Yes; resolve stack entries when a larger value arrives, while retaining unresolved entries.
CodingEasyAgodaSoftware Engineer

4. Minimum Absolute Difference (LeetCode)

Model answer

The task

Given an integer array, return every pair of values whose absolute difference is as small as possible. Each pair should list its smaller value first.

Key idea

Sort the values. The smallest difference must occur between two neighbors in sorted order: any non-neighboring pair has at least one intervening value and cannot have a smaller gap. A single scan can find the minimum gap and collect all pairs that achieve it.

Approach

  1. Sort the array in ascending order.
  2. Scan adjacent values to find the smallest difference.
  3. Scan adjacent values again, adding each pair whose difference equals that minimum.
  4. Return the collected pairs; the sorted scan produces them in ascending order.
from typing import List

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        values = sorted(arr)

        # Find the smallest gap between neighboring values.
        min_gap = min(
            values[i] - values[i - 1]
            for i in range(1, len(values))
        )

        # Collect every neighboring pair with that gap.
        pairs = []
        for i in range(1, len(values)):
            if values[i] - values[i - 1] == min_gap:
                pairs.append([values[i - 1], values[i]])

        return pairs

Complexity:

  • Time: O(n log n), dominated by sorting; the scans take O(n).
  • Space: O(n), for the sorted copy and the returned pairs.

Common follow-ups

  • Can this be done without sorting? Not generally in linear time for arbitrary integers; sorting gives the required order efficiently.
  • What if the input may be modified? Sort arr in place to avoid creating a separate sorted copy.
  • What if values can repeat? Adjacent equal values have gap zero; collect every adjacent pair attaining the minimum.
  • Why are non-neighboring pairs unnecessary? In sorted order, a value between two elements makes their difference at least as large as one of the neighboring gaps.
CodingEasyAgodaSoftware Engineer

5. Degree of an Array (LeetCode)

Model answer

The task

Given an integer array, find the length of its shortest contiguous subarray whose elements have the same degree as the full array. The degree is the highest frequency of any value in the array.

Key idea

For each value, record its frequency and the indices of its first and last occurrences. A value’s shortest covering subarray spans those two indices; among values with maximum frequency, return the smallest such span.

Approach

  1. Scan the array once, recording each value’s count, first index, and last index.
  2. Track the largest count seen, which is the array’s degree.
  3. For every value with that count, calculate last - first + 1.
  4. Return the minimum calculated length.
from typing import List

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        counts = {}
        first = {}
        last = {}

        for i, value in enumerate(nums):
            if value not in counts:
                counts[value] = 0
                first[value] = i

            counts[value] += 1
            last[value] = i

        degree = max(counts.values())
        shortest = len(nums)

        for value, count in counts.items():
            if count == degree:
                span = last[value] - first[value] + 1
                shortest = min(shortest, span)

        return shortest

Complexity:

  • Time: O(n), for scanning the array and checking the distinct values.
  • Space: O(k), where k is the number of distinct values stored in the dictionaries.

Common follow-ups

  • How would you return the actual subarray as well as its length? Keep the start and end indices of the best span.
  • What if the array is empty? Define the expected behavior, such as returning 0, and handle it before calling max.
  • Can the result be found in one pass? Yes; update each value’s span and count while tracking the best span for the current degree.
CodingEasyAgodaSoftware Engineer

6. Happy Number (LeetCode)

Model answer

The task

Determine whether repeatedly replacing a positive integer with the sum of the squares of its digits eventually reaches 1. If the sequence loops without reaching 1, the number is not happy.

Key idea

The digit transformation is deterministic, so the sequence either reaches 1 or eventually repeats a value. Floyd’s cycle-finding algorithm detects a repeat using two pointers and constant extra space.

Approach

  1. Define a helper that computes the sum of the squared digits of a number.
  2. Start a slow pointer at the input and a fast pointer one transformation ahead.
  3. Advance the slow pointer once and the fast pointer twice per iteration.
  4. Stop if the fast pointer reaches 1 or the pointers meet.
  5. Return whether the fast pointer reached 1.
class Solution:
    def isHappy(self, n: int) -> bool:
        def next_value(value: int) -> int:
            total = 0
            while value > 0:
                digit = value % 10
                total += digit * digit
                value //= 10
            return total

        slow = n
        fast = next_value(n)

        while fast != 1 and slow != fast:
            slow = next_value(slow)
            fast = next_value(next_value(fast))

        return fast == 1

Complexity:

  • Time: O(log n), since digit transformations rapidly reduce the value and each transformation processes its digits.
  • Space: O(1), because only two pointers and a few temporary values are used.

Common follow-ups

  • How can a set solve this? Store values as they appear; a repeated value proves a cycle, using O(k) extra space for k visited values.
  • What if the transformation changes? The cycle-detection method still works for any deterministic transformation.
  • How would you test edge cases? Check 1, a known happy value, and values whose sequences enter a non-1 cycle.
CodingEasyAgodaSoftware Engineer

7. Valid Parentheses (LeetCode)

Model answer

The task

Determine whether a string of opening and closing round, square, and curly brackets is correctly nested and matched. Return a boolean.

Key idea

A closing bracket must match the most recent unmatched opening bracket. A stack captures that order: push openings, and check each closing bracket against the stack’s top.

Approach

  1. Return False if the string has odd length.
  2. Map each closing bracket to its matching opening bracket.
  3. Scan the string from left to right.
  4. Push opening brackets onto the stack.
  5. For a closing bracket, return False if the stack is empty or its top does not match; otherwise pop.
  6. Return True only if the stack is empty after the scan.
class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {")": "(", "]": "[", "}": "{"}
        openings = set(pairs.values())
        stack = []

        for char in s:
            if char in openings:
                stack.append(char)
            else:
                # A closing bracket must match the latest unmatched opening.
                if not stack or stack[-1] != pairs.get(char):
                    return False
                stack.pop()

        # Unmatched opening brackets make the sequence invalid.
        return not stack

Complexity:

  • Time: O(n), where n is the string length; each character is processed once.
  • Space: O(n) in the worst case, when all characters are opening brackets.

Common follow-ups

  • How would you support additional bracket types? Add their matching pairs to the map.
  • Can you stop early? Yes; return False as soon as a closing bracket mismatches or has no opening bracket.
  • What if the input includes non-bracket characters? Define how to handle them, then either ignore them or reject them during the scan.
CodingEasyAgodaSoftware Engineer

8. Rank Transform of an Array (LeetCode)

Model answer

The task

Replace each array value with its rank among the distinct values, where the smallest value has rank 1. Equal values receive the same rank, and ranks increase consecutively.

Key idea

Sort the distinct values to determine their order, then map each value to its position in that order. A hash map lets us transform the original array in linear time after sorting.

Approach

  1. Collect the distinct values and sort them.
  2. Assign each sorted value a rank starting at 1.
  3. Build a value-to-rank hash map.
  4. Use the map to transform each element of the input array.
class Solution:
    def arrayRankTransform(self, arr: list[int]) -> list[int]:
        # Sorting distinct values makes their positions their ranks.
        sorted_values = sorted(set(arr))
        rank_by_value = {
            value: rank
            for rank, value in enumerate(sorted_values, start=1)
        }

        # Preserve the original order while replacing values with ranks.
        return [rank_by_value[value] for value in arr]

Complexity:

  • Time: O(n log n), from sorting up to n distinct values.
  • Space: O(n), for the distinct values and rank map.

Common follow-ups

  • What if the input is empty? The implementation returns an empty list.
  • Can equal values have different ranks? No; the map assigns one rank per distinct value.
  • Can the input be transformed in place? Yes, if modifying the original array is allowed; replace each element using the rank map.
  • What if values arrive as a stream? Exact ranks may require seeing all distinct values first, unless the value range is bounded or approximate ranks are acceptable.
CodingEasyAgodaSoftware Engineer

9. Find Pivot Index (LeetCode)

Model answer

The task

Given an integer array, return the leftmost index where the sum of the elements before it equals the sum of the elements after it. Return -1 if no such index exists.

Key idea

Compute the total sum once, then scan from left to right while maintaining the sum to the left. At each index, the right sum is the total minus the left sum and the current element.

Approach

  1. Sum all elements to get the total.
  2. Initialize the running left sum to zero.
  3. For each index, compare the left sum with total - left_sum - nums[index].
  4. Return the index when the sums match; otherwise, add the current value to the left sum.
  5. Return -1 if the scan finishes without a match.
from typing import List

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        left_sum = 0

        for i, value in enumerate(nums):
            right_sum = total - left_sum - value

            if left_sum == right_sum:
                return i

            left_sum += value

        return -1

Complexity:

  • Time: O(n), for one pass through the array after summing it.
  • Space: O(1), using only a fixed number of extra variables.

Common follow-ups

  • What if there are multiple pivot indices? The left-to-right scan returns the first; collect each matching index instead if all are required.
  • Can this handle negative values? Yes. The equality check relies on sums, not on values being positive.
  • What if the array is updated repeatedly? A single update changes the sums for many indices; a Fenwick tree or segment tree can support range-sum queries and updates more efficiently.
CodingEasyAgodaSoftware Engineer

10. Best Time to Buy and Sell Stock (LeetCode)

Model answer

The task

Given daily stock prices, find the greatest profit possible from one buy followed by one later sale. If no sale would make money, return zero.

Key idea

As we scan the prices, keep the lowest price seen so far. Treat each current price as a possible sale and update the best profit using the difference from that minimum.

Approach

  1. Initialize the minimum price to a value larger than any price and the best profit to zero.
  2. Visit each price in order.
  3. Update the minimum price with the current price.
  4. Check the profit from selling today and update the best profit.
  5. Return the best profit.
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float("inf")
        best_profit = 0

        for price in prices:
            # The current price can be a new best day to buy.
            min_price = min(min_price, price)

            # Or it can be the day to sell after the cheapest earlier buy.
            best_profit = max(best_profit, price - min_price)

        return best_profit

Complexity:

  • Time: O(n), where n is the number of prices; each is processed once.
  • Space: O(1), since only a few variables are stored.

Common follow-ups

  • What if multiple buy-and-sell transactions are allowed? Sum the gains from every adjacent price increase.
  • What if a transaction fee is charged? Track the best holding and non-holding profits, incorporating the fee when selling.
  • What if at most k transactions are allowed? Use dynamic programming over the number of completed transactions and whether a share is currently held.
CodingEasyAgodaSoftware Engineer

11. Find the Child Who Has the Ball After K Seconds (LeetCode)

Model answer

The task

Children are arranged in order, and a ball moves one child each second, reversing direction at either end. Return the child holding it after k seconds, starting from child 0.

Key idea

The motion repeats after 2 * (n - 1) seconds: the ball travels to the far end and back. Reduce k modulo this period, then reflect positions in the return half of the journey.

Approach

  1. If there is only one child, the ball always stays with child 0.
  2. Compute the period, 2 * (n - 1), and reduce k modulo it.
  3. If the reduced time is at most n - 1, the ball is moving forward, so its position is that time.
  4. Otherwise, it is moving back, so its position is period - time.
class Solution:
    def numberOfChild(self, n: int, k: int) -> int:
        # With one child, no movement can change the holder.
        if n == 1:
            return 0

        period = 2 * (n - 1)
        time = k % period

        # The first half moves toward the last child;
        # the second half retraces the path.
        if time <= n - 1:
            return time
        return period - time

Complexity:

  • Time: O(1), using a fixed number of arithmetic operations.
  • Space: O(1), using only a few variables.

Common follow-ups

  • How would you simulate the passing directly? Track position and direction for each second; this takes O(k) time.
  • What if the ball starts at a different child? Add the initial position to the unfolded movement, then map it through the endpoints.
  • What if the children form a circle? The position is (start + k) % n, with no direction reversal.
CodingEasyAgodaSoftware Engineer

12. Climbing Stairs (LeetCode)

Model answer

The task

Count how many distinct ways there are to reach the top of a staircase with n steps when each move advances either one or two steps.

Key idea

To reach step i, the last move must come from step i - 1 or i - 2. Thus the number of ways to reach i is the sum of the ways to reach those two earlier steps. Only the previous two counts are needed, so there is no need to store a full table.

Approach

  1. Set the number of ways to reach step 0 to 1, representing the single empty sequence of moves.
  2. Set the number of ways to reach step 1 to 1.
  3. For each step from 2 through n, add the counts for the preceding two steps.
  4. Return the count for step n.
class Solution:
    def climbStairs(self, n: int) -> int:
        # Ways to reach steps 0 and 1.
        two_back = 1
        one_back = 1

        # Build the count using the two preceding results.
        for _ in range(2, n + 1):
            current = two_back + one_back
            two_back = one_back
            one_back = current

        return one_back

Complexity:

  • Time: O(n), since each step is processed once.
  • Space: O(1), since only two prior counts are retained.

Common follow-ups

  • What if each move can advance 1, 2, or 3 steps? Sum the counts for the previous three steps.
  • What if the result must be returned modulo a number? Apply the modulus after each addition.
  • What if some steps are forbidden? Set their ways count to zero and use dynamic programming for the allowed steps.
CodingMediumAgodaSoftware Engineer

13. 3Sum (LeetCode)

Model answer

The task

Given an integer array, return every distinct triplet of values whose sum is zero. Triplets are considered the same if they contain the same values, regardless of order.

Key idea

Sort the array, then fix each value in turn and use two pointers to find pairs that complete its sum to zero. Skipping repeated values prevents duplicate triplets.

Approach

  1. Sort the input array.
  2. For each index, treat its value as the first element of a triplet.
  3. Skip the index if its value is the same as the previous value.
  4. Set two pointers immediately after the fixed index and at the end of the array.
  5. Move a pointer according to whether the current sum is too small or too large.
  6. When a triplet is found, record it and advance past duplicate pointer values.
from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        triplets = []
        n = len(nums)

        for i in range(n - 2):
            # Only use the first occurrence of each fixed value.
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    triplets.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    # Avoid repeating the same pair for this fixed value.
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

        return triplets

Complexity:

  • Time: O(n²), from fixing each value and scanning with two pointers.
  • Space: O(n) for Python's in-place sort; excludes the returned triplets.

Common follow-ups

  • How would you return unique index triplets instead of value triplets? Track original indices while sorting, then return the corresponding index triples.
  • What if the target sum is a variable? Replace the zero-sum check with a comparison against the target.
  • Can the approach be extended to four values? Fix two values and use two pointers for the remaining pair, giving O(n³) time.
CodingMediumAgodaSoftware Engineer

14. Reorganize String (LeetCode)

Model answer

The task

Rearrange the characters of a string so that no two identical characters are adjacent. Return an empty string if no valid rearrangement exists.

Key idea

Always place the most frequent available character first, but keep the character used in the previous step out of the heap for one turn. This prevents adjacent duplicates while preserving the greedy choice among the remaining characters.

Approach

  1. Count each character and build a max-heap by storing negative counts.
  2. Pop the most frequent available character and append it to the result.
  3. Reinsert the previously used character, if it still has copies remaining.
  4. Decrease the selected character’s remaining count and hold it aside.
  5. If copies remain when the heap is empty, no valid arrangement exists.
from collections import Counter
import heapq

class Solution:
    def reorganizeString(self, s: str) -> str:
        # Negative counts turn Python's min-heap into a max-heap.
        heap = [(-count, char) for char, count in Counter(s).items()]
        heapq.heapify(heap)

        result = []
        previous = None  # (negative remaining count, character)

        while heap:
            negative_count, char = heapq.heappop(heap)
            result.append(char)

            # The previous character is now eligible again.
            if previous is not None and previous[0] < 0:
                heapq.heappush(heap, previous)

            # One copy of the selected character has been used.
            previous = (negative_count + 1, char)

        # A negative count means some copies could not be placed.
        if previous is not None and previous[0] < 0:
            return ""

        return "".join(result)

Complexity:

  • Time: O(n log k), where n is the string length and k is the number of distinct characters.
  • Space: O(k) auxiliary space for the heap and character counts, excluding the result.

Common follow-ups

  • How can impossibility be checked up front? A rearrangement is possible only if the most frequent character occurs at most ⌈n / 2⌉ times.
  • What if equal-frequency choices need a particular order? Add a tie-breaker to heap entries, such as the character itself for lexicographic ordering.
  • What if identical characters must be at least d positions apart? Use a cooldown queue to delay returning each used character to the heap.
CodingMediumAgodaSoftware Engineer

15. Find Diameter Endpoints of a Tree (LeetCode)

Model answer

The task

Find two vertices that form the endpoints of a longest path in a tree. The exact required input and return format are not specified, so the solution below uses vertices numbered 0 through n - 1 and an edge list.

Key idea

In a tree, start a traversal from any vertex and find a farthest vertex; that vertex is an endpoint of a diameter. Traverse again from it, and a farthest vertex reached is the other endpoint.

Approach

  1. Build an adjacency list from the edges.
  2. Run breadth-first search from an arbitrary vertex to find a farthest vertex.
  3. Run BFS from that vertex to find the opposite endpoint.
  4. Return the two endpoints. If multiple farthest vertices tie, any tied choice is valid.
from collections import deque

def find_diameter_endpoints(n: int, edges: list[list[int]]) -> tuple[int, int]:
    """Return endpoints of a diameter in a tree labeled 0 through n - 1."""
    if n <= 0:
        raise ValueError("The tree must contain at least one vertex.")

    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    def farthest_from(start: int) -> int:
        distances = [-1] * n
        distances[start] = 0
        queue = deque([start])
        farthest = start

        while queue:
            node = queue.popleft()
            if distances[node] > distances[farthest]:
                farthest = node

            for neighbor in graph[node]:
                if distances[neighbor] == -1:
                    distances[neighbor] = distances[node] + 1
                    queue.append(neighbor)

        return farthest

    first_endpoint = farthest_from(0)
    second_endpoint = farthest_from(first_endpoint)
    return first_endpoint, second_endpoint

Complexity:

  • Time: O(n), since each vertex and edge is visited a constant number of times.
  • Space: O(n), for the adjacency list, queue, and distance array.

Common follow-ups

  • Return the diameter length too? Track distances in the second BFS and return the distance to the farthest vertex.
  • Return the path, not just its endpoints? Store parent pointers during the second BFS and reconstruct the path from the farthest vertex.
  • What if the tree is weighted? Use a tree traversal that accumulates edge weights; for nonnegative weights, the same two-traversal idea applies.
CodingMediumAgodaSoftware Engineer

16. Decode String (LeetCode)

Model answer

The task

Decode a string where a number before brackets indicates how many times to repeat the bracketed section. Sections may be nested.

Key idea

Parse the input into a compact tree of literal fragments and repeat nodes instead of expanding nested sections immediately. Then traverse that tree to produce the decoded string, avoiding repeated copying of large intermediate strings.

Approach

  1. Scan the input, accumulating each repetition count.
  2. On an opening bracket, save the current fragment list and count, then start a new list.
  3. On a closing bracket, wrap the current list in a repeat node and add it to its parent.
  4. Traverse the resulting structure with an explicit stack, yielding literal fragments as they are needed.
  5. Join the yielded fragments into the result.
class Solution:
    def decodeString(self, s: str) -> str:
        # Each repeat node is a (count, fragments) tuple.
        current = []
        stack = []
        count = 0

        for char in s:
            if "0" <= char <= "9":
                count = count * 10 + int(char)
            elif char == "[":
                stack.append((current, count))
                current = []
                count = 0
            elif char == "]":
                parent, repeat = stack.pop()
                # Omit zero repetitions so traversal skips empty sections.
                if repeat:
                    parent.append((repeat, current))
                current = parent
            else:
                current.append(char)

        def fragments():
            # Frames contain a fragment list, its next index, and
            # how many times to traverse that list.
            frames = [[current, 0, 1]]

            while frames:
                parts, index, remaining = frames[-1]

                if index == len(parts):
                    remaining -= 1
                    if remaining == 0:
                        frames.pop()
                    else:
                        frames[-1][1] = 0
                        frames[-1][2] = remaining
                    continue

                node = parts[index]
                frames[-1][1] += 1

                if isinstance(node, str):
                    yield node
                else:
                    repeat, nested = node
                    frames.append([nested, 0, repeat])

        return "".join(fragments())

Complexity:

  • Time: O(n + m), where n is the encoded length and m is the decoded length.
  • Space: O(n + m) for the parsed structure and returned string.

Common follow-ups

  • How would you handle malformed input? Validate bracket balance and ensure each opening bracket has a preceding count.
  • How could this support streaming output? Yield decoded fragments to a consumer instead of joining them into one string.
  • What if the grammar adds escaping or other operators? Extend the parser with explicit rules and represent each operation as a distinct node.
Product & growthMediumAgodaProduct Manager

17. What is the biggest challenge you face with your KPI?

Model answer

The challenge

The biggest challenge is improving booking conversion without optimizing for bookings that are low quality or short-lived. In travel, the decision happens before the stay, while the most important signals—cancellation, whether the property is as expected, and overall satisfaction—can arrive days or weeks later. That makes fast product decisions harder and creates a risk of overvaluing an immediate conversion lift.

How I break it down

I first check where the conversion change occurs: search results, property details, room selection, or checkout. Then I segment by market, device, traffic source, and customer type. A headline improvement can hide a harmful effect—for example, a change may help returning customers but confuse first-time travelers, or work in one market while failing in another.

I also separate leading indicators from mature outcomes. Payment success and confirmation reliability arrive quickly; cancellations, support contacts, and post-stay feedback take longer. I avoid treating those measures as interchangeable.

How I investigate and respond

  • I validate the event definitions, exposure logging, and experiment assignment before interpreting a result.
  • I use a controlled experiment and agree on success criteria and guardrail thresholds before launch.
  • I inspect cancellation and customer-experience results by booking cohort, giving delayed metrics time to mature.
  • If results conflict, I diagnose the affected funnel step and segment rather than averaging away the problem.
  • I use a gradual rollout when early signals are healthy, with a clear rollback condition.

Decision

I would ship only when the conversion gain is credible and the quality and economic guardrails remain acceptable. If the experiment increases bookings but also increases cancellations or complaints, I would treat that as evidence to improve the underlying experience, not as a win. The key lesson is that KPI ownership includes making sure the metric continues to represent real customer and company value.

Product & growthMediumAgodaProduct Manager

18. Are there any guardrail metrics that help you ensure everything is moving in the right direction?

Model answer

Clarify the goal

My primary KPI is accommodation booking conversion, but I would not ship a change based on conversion alone. The guardrails help answer whether the additional bookings are good for travelers, partners, and Agoda—not just whether more people clicked “book.”

Guardrails I monitor

  • Cancellation and refund rate: A rise can signal that customers misunderstood policies, prices, or the property they selected. I track it by booking cohort and allow for the cancellation window.
  • Customer experience: I monitor post-stay ratings, complaints, and support contacts per booking. I interpret these with enough volume and time to avoid reacting to noisy results.
  • Commercial quality: I check contribution per booking and discount or incentive cost. A conversion lift that depends on unsustainable economics is not a durable win.
  • Booking reliability: Payment success, confirmation failures, and latency protect customers from friction or uncertainty at a critical moment.
  • Marketplace health: Where relevant, I examine partner cancellation rates and availability accuracy, since a booking that cannot be honored hurts both sides.

How I use them

I define thresholds before an experiment, distinguish hard stop metrics from indicators that need investigation, and review results by market, device, and customer segment. A statistically credible deterioration in a critical guardrail can block a rollout even when the aggregate conversion result is positive. For less severe movements, I check whether the change is concentrated in a segment or reflects seasonality, mix shift, or instrumentation.

I also account for outcome timing. Payment failure can be seen quickly, while cancellation and post-stay experience mature later. I may ramp a change gradually using early reliability signals, but I would not call the test a full success until the delayed quality metrics have been reviewed.

Product & growthMediumAgodaProduct Manager

19. How does your KPI contribute to overall company goals?

Model answer

Clarify the company goal

I see the company goal as creating sustainable growth: helping more travelers find and book suitable accommodation while building a healthy, trusted marketplace for partners. My KPI—accommodation booking conversion—contributes by measuring whether people who arrive with lodging intent can successfully complete a booking.

Connect the metric to outcomes

When conversion improves because search results are more relevant, property information is clearer, or checkout is easier, more qualified demand can become bookings. That supports traveler value, partner demand, and Agoda’s commercial goals. But conversion is a leading product metric, not the company goal itself. Revenue, contribution, cancellations, repeat behavior, and partner health determine whether the growth is valuable and sustainable.

I therefore think about the metric as part of a chain:

Qualified demand → useful options → confident booking → fulfilled stay → repeat trust

A conversion gain early in that chain is only positive if it does not damage the later stages. For example, hiding important fees might increase immediate bookings but create cancellations, complaints, and lower trust. Similarly, driving bookings through uneconomic discounts could improve volume while harming contribution.

How I align my work

For each initiative, I make the connection explicit: what customer problem it solves, which part of the funnel it should improve, and which company outcome should follow. I then evaluate the experiment on conversion alongside guardrails such as cancellation rate, contribution per booking, and post-stay feedback. Where possible, I also look at longer-term outcomes such as repeat booking behavior.

That approach lets my team move quickly on an actionable KPI without confusing a local metric improvement with overall company success.

Product & growthMediumAgodaProduct Manager

20. What is your current KPI?

Model answer

KPI and scope

My primary KPI is accommodation booking conversion: the share of eligible accommodation-shopping sessions that result in a confirmed booking. I define the denominator carefully—for example, excluding employee traffic, bots, and sessions that never reach a usable search result—and deduplicate bookings so the metric reflects customer decisions rather than event volume.

I look at conversion by market, device, traffic source, and new versus returning customer. I also follow bookings through cancellation and stay outcomes, because a booking that is quickly cancelled is not the same customer or business value as a booking that is fulfilled.

Why this KPI

It is close enough to the product experience that a team can influence it through search relevance, property content, pricing clarity, availability, and checkout improvements. It is also connected to Agoda’s marketplace outcomes: more travelers finding suitable stays can create more completed bookings for accommodation partners and sustainable revenue for the business.

How I use it

I do not treat a short-term conversion increase as an automatic win. I pair the headline KPI with cancellation, customer experience, and commercial guardrails, and I read experiment results across important segments. For instance, a checkout change that lifts conversion overall but creates a large decline in a key market or increases payment failures needs investigation before rollout.

My goal is to improve conversion by removing genuine friction and helping customers make a confident choice—not by making it harder to understand a price or booking condition. That gives the team a clear outcome to optimize while keeping the broader customer and marketplace impact visible.

Practice these out loud, don't memorise them

Reading an answer is not the same as being able to give one under pressure. ChannelPulse plays the interviewer, asks the follow-ups, and scores each answer with feedback and a model answer so you can hear the gap between what you said and what lands.

Get ChannelPulse Browse all questions