PayPay interview questions & answers

10 real PayPay interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (10 PayPay questions in total).

CodingEasyPayPaySoftware Engineer

1. Two Sum (LeetCode)

Model answer

The task

Given a list of integers and a target, return the indices of two distinct elements whose values add up to the target. The usual version guarantees a valid pair.

Key idea

As we scan the list, store each value’s index in a hash table. For the current value, check whether its needed complement has already appeared; this finds a pair in one pass.

Approach

  1. Create a dictionary mapping previously seen values to their indices.
  2. For each element, compute the complement needed to reach the target.
  3. If that complement is in the dictionary, return its stored index and the current index.
  4. Otherwise, store the current value and index, then continue.
from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Map each value already visited to its index.
        seen = {}

        for index, value in enumerate(nums):
            complement = target - value

            # A match must come from an earlier, distinct element.
            if complement in seen:
                return [seen[complement], index]

            seen[value] = index

        # The standard problem guarantees a solution.
        raise ValueError("No two elements sum to the target")

Complexity:

  • Time: O(n), where n is the number of elements; each lookup and insertion is O(1) on average.
  • Space: O(n), for the dictionary of values seen so far.

Common follow-ups

  • What if there may be multiple valid pairs? Return the first pair found, or keep searching and collect pairs according to the required output rules.
  • What if the input is sorted? Use two pointers from opposite ends for O(1) extra space; preserve original indices if those are required.
  • What if values repeat? The dictionary stores indices, and checking before insertion ensures the current element is not paired with itself.
CodingEasyPayPaySoftware Engineer

2. 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.
CodingEasyPayPaySoftware Engineer

3. Largest 3-Same-Digit Number in String (LeetCode)

Model answer

The task

Find the largest three-character substring of a digit string whose characters are all identical. Return it as a string, or return an empty string if no such substring exists.

Key idea

Scan every window of length three. When all three digits match, keep the largest matching digit seen; comparing digits works because they are single characters from 0 to 9.

Approach

  1. Start with no matching digit recorded.
  2. Check each consecutive window of length three.
  3. If its digits match, update the best digit if it is larger.
  4. Return that digit repeated three times, or an empty string if none was found.
class Solution:
    def largestGoodInteger(self, num: str) -> str:
        best = ""

        for i in range(len(num) - 2):
            if num[i] == num[i + 1] == num[i + 2]:
                if not best or num[i] > best[0]:
                    best = num[i] * 3

        return best

Complexity:

  • Time: O(n), where n is the length of the string; each window takes constant time to check.
  • Space: O(1), excluding the returned string, which has at most three characters.

Common follow-ups

  • What if the required run length is k instead of three? Scan length-k windows, or track consecutive equal digits in one pass.
  • What if the input can contain non-digit characters? Define the ordering rule first, then compare matching characters using that rule.
  • Can you return the starting index as well? Store the window’s index whenever the best matching digit is updated.
CodingMediumPayPaySoftware Engineer

4. Min Cost to Connect All Points (LeetCode)

Model answer

The task

Given points in a plane, connect them so every point is reachable from every other point, minimizing the total Manhattan distance of the chosen connections.

Key idea

The points form a complete weighted graph, but explicitly building all edges is unnecessary. Prim’s algorithm can grow a minimum spanning tree by tracking each unconnected point’s cheapest connection to the current tree.

Approach

  1. Start the tree at point 0 with cost 0.
  2. Keep the cheapest known connection cost for each point and mark points as visited when added.
  3. Repeatedly add the unvisited point with the smallest connection cost.
  4. Add that cost to the answer, then update the remaining costs using Manhattan distance from the newly added point.
  5. Return the sum after all points have been added.
from typing import List

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 1:
            return 0

        # best[i] is the cheapest edge currently known from the tree to i.
        best = [float("inf")] * n
        best[0] = 0
        visited = [False] * n
        total_cost = 0

        for _ in range(n):
            # Select the unvisited point with the cheapest connection.
            current = -1
            for i in range(n):
                if not visited[i] and (
                    current == -1 or best[i] < best[current]
                ):
                    current = i

            visited[current] = True
            total_cost += best[current]

            x1, y1 = points[current]
            for i in range(n):
                if not visited[i]:
                    x2, y2 = points[i]
                    distance = abs(x1 - x2) + abs(y1 - y2)
                    best[i] = min(best[i], distance)

        return total_cost

Complexity:

  • Time: O(n²), from selecting the next point and updating distances for each point.
  • Space: O(n), for the connection costs and visited flags.

Common follow-ups

  • Can Kruskal’s algorithm solve it? Yes; generate all point pairs, sort by distance, and use Union-Find, taking O(n² log n) time and O(n²) space.
  • Can Prim’s algorithm use a heap? Yes, but this dense graph still has O(n²) possible edges; the array-based version is simpler and avoids storing them.
  • What if there is only one point? No connection is needed, so the cost is 0.
  • What if distances use another metric? Replace the Manhattan distance calculation, provided the edge weights remain well-defined.
CodingMediumPayPaySoftware Engineer

5. 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.
CodingMediumPayPaySoftware Engineer

6. Search in Rotated Sorted Array (LeetCode)

Model answer

The task

Given an ascending array that has been rotated at an unknown position, find the index of a target value, or return -1 if it is absent. The values are distinct.

Key idea

At each binary-search step, at least one half of the current range is still sorted. Check whether the target falls within that half; if so, keep it, otherwise search the other half.

Approach

  1. Initialize two pointers at the ends of the array.
  2. While the pointers have not crossed, inspect the middle value.
  3. If it matches the target, return its index.
  4. If the left half is sorted, check whether the target lies within its bounds and discard the other half if it does.
  5. Otherwise, use the sorted right half in the same way.
  6. Return -1 if the range becomes empty.
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid

            # The left half is sorted.
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Otherwise, the right half is sorted.
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

Complexity:

  • Time: O(log n), because each step discards about half the remaining range.
  • Space: O(1), since the search uses only a fixed number of variables.

Common follow-ups

  • What changes if duplicates are allowed? If the endpoints and midpoint are equal, discard one endpoint; worst-case time can become O(n).
  • How would you find the rotation pivot? Binary-search for the minimum element, then search the appropriate sorted portion.
  • How would you return all matching indices with duplicates? First locate a match, then scan outward across adjacent equal values.
CodingMediumPayPaySoftware Engineer

7. Zigzag Conversion (LeetCode)

Model answer

The task

Rearrange a string by writing its characters across rows in a down-and-diagonal zigzag pattern, then return the rows concatenated from top to bottom.

Key idea

Simulate the movement through the rows as characters are read. Reverse direction at the top and bottom rows; each character is appended to its current row exactly once.

Approach

  1. If there is only one row, or the string is shorter than the row count, return it unchanged.
  2. Create one character buffer per row.
  3. Track the current row and whether movement is downward or upward.
  4. Append each character to its row, changing direction at either end.
  5. Join the row buffers in order.
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # With one row, the zigzag has no turns.
        if numRows == 1 or numRows >= len(s):
            return s

        rows = [[] for _ in range(numRows)]
        current_row = 0
        direction = 1  # 1 means moving down; -1 means moving up.

        for char in s:
            rows[current_row].append(char)

            # Turn around when reaching either end of the rows.
            if current_row == 0:
                direction = 1
            elif current_row == numRows - 1:
                direction = -1

            current_row += direction

        return "".join("".join(row) for row in rows)

Complexity:

  • Time: O(n), where n is the length of the string; each character is processed once.
  • Space: O(n), for the row buffers and the returned string.

Common follow-ups

  • Can you compute the row of each character directly? Yes; use the repeating zigzag cycle of 2 * numRows - 2 positions.
  • What if the input is streamed? Keep the row buffers and movement state, and process each incoming character in order.
  • What edge cases matter? A single row, an empty string, and a row count at least as large as the string length.
CodingMediumPayPaySoftware Engineer

8. Successful Pairs of Spells and Potions (LeetCode)

Model answer

The task

For each spell, count how many potions make the spell–potion product reach at least the required success value. Return those counts in the original spell order.

Key idea

Sort the potions once. For a spell with value s, any successful potion must be at least ceil(success / s). Binary search for the first potion meeting that threshold; every potion from there to the end succeeds.

Approach

  1. Sort the potions.
  2. For each spell, compute the smallest potion value that can succeed.
  3. Use binary search to find its position in the sorted potions.
  4. The number of successful potions is the number of elements from that position to the end.
  5. Store each count in the order of the input spells.
from bisect import bisect_left
from typing import List

class Solution:
    def successfulPairs(
        self, spells: List[int], potions: List[int], success: int
    ) -> List[int]:
        sorted_potions = sorted(potions)
        pairs = []

        for spell in spells:
            # Integer ceiling of success / spell.
            minimum_potion = (success + spell - 1) // spell
            first_successful = bisect_left(sorted_potions, minimum_potion)
            pairs.append(len(sorted_potions) - first_successful)

        return pairs

Complexity:

  • Time: O(m log m + n log m), where m is the number of potions and n is the number of spells.
  • Space: O(m) for the sorted potion list, excluding the returned result.

Common follow-ups

  • Can the search be done without binary search? Yes; sort both arrays and sweep through them with two pointers.
  • What if many queries reuse the same potions? Keep the sorted potion list and binary-search it for each query.
  • What if the inputs include zero or negative values? The threshold shortcut relies on positive spells and potions; handle sign cases separately.
CodingMediumPayPaySoftware Engineer

9. Peak Index in a Mountain Array (LeetCode)

Model answer

The task

Given an array that strictly increases to one peak and then strictly decreases, return the peak’s index.

Key idea

The comparison between arr[mid] and arr[mid + 1] tells which side of the peak contains the answer. If the values rise, the peak is to the right; otherwise, it is at mid or to the left.

Approach

  1. Set search bounds to the first and last indices.
  2. While the bounds differ, inspect the midpoint and its next element.
  3. If the array is still rising at the midpoint, move the lower bound right.
  4. Otherwise, move the upper bound to the midpoint.
  5. The converged index is the peak.
from typing import List

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left, right = 0, len(arr) - 1

        while left < right:
            mid = (left + right) // 2

            # A rising slope means the peak lies to the right.
            if arr[mid] < arr[mid + 1]:
                left = mid + 1
            else:
                # The peak is at mid or to its left.
                right = mid

        return left

Complexity:

  • Time: O(log n), since the search interval is halved each iteration.
  • Space: O(1), using only a fixed number of variables.

Common follow-ups

  • What if the array is strictly increasing or decreasing? The same search returns the last or first index, respectively.
  • What if adjacent values can be equal? The comparison may not identify a direction; the algorithm may need modification and can take O(n) in the worst case.
  • Can the peak value be returned instead? Return arr[left] after the search.
CodingHardPayPaySoftware Engineer

10. Block Placement Queries (LeetCode)

Model answer

The task

Process queries that add obstacle points on a number line or ask whether a block of a given size can fit within the interval from 0 to a specified coordinate without covering an obstacle. Return a Boolean answer for each placement query.

Key idea

Keep the free gap ending at each obstacle, and track the maximum such gap with a segment tree. For a placement query, also check the final gap from the last obstacle at or before the limit to the limit itself.

Approach

  1. Coordinate-compress all coordinates mentioned in the queries.
  2. Use a Fenwick tree to track which compressed coordinates currently contain obstacles.
  3. On insertion, find the neighboring obstacles; update the gap ending at the new obstacle and the gap ending at its successor.
  4. For a placement query, take the maximum stored gap up to its coordinate and compare it with the trailing gap.
from typing import List

class Fenwick:
    def __init__(self, n: int) -> None:
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, index: int, delta: int) -> None:
        index += 1
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index

    def prefix_sum(self, end: int) -> int:
        """Count in indices [0, end)."""
        total = 0
        while end > 0:
            total += self.tree[end]
            end -= end & -end
        return total

    def kth(self, rank: int) -> int:
        """Index of the rank-th active item, using 1-based rank."""
        index = 0
        step = 1 << (self.n.bit_length() - 1)
        while step:
            candidate = index + step
            if candidate <= self.n and self.tree[candidate] < rank:
                index = candidate
                rank -= self.tree[candidate]
            step >>= 1
        return index

class MaxSegmentTree:
    def __init__(self, n: int) -> None:
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.tree = [0] * (2 * self.size)

    def set(self, index: int, value: int) -> None:
        index += self.size
        self.tree[index] = value
        index //= 2
        while index:
            self.tree[index] = max(self.tree[2 * index],
                                   self.tree[2 * index + 1])
            index //= 2

    def query(self, left: int, right: int) -> int:
        """Maximum over indices in [left, right)."""
        left += self.size
        right += self.size
        result = 0
        while left < right:
            if left & 1:
                result = max(result, self.tree[left])
                left += 1
            if right & 1:
                right -= 1
                result = max(result, self.tree[right])
            left //= 2
            right //= 2
        return result

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        coords = sorted({query[1] for query in queries})
        index_of = {x: i for i, x in enumerate(coords)}
        n = len(coords)

        active = Fenwick(n)
        gaps = MaxSegmentTree(n)
        answers = []

        for query in queries:
            if query[0] == 1:
                x = query[1]
                i = index_of[x]

                # Ignore a repeated insertion.
                if active.prefix_sum(i + 1) == active.prefix_sum(i):
                    before = active.prefix_sum(i)
                    total = active.prefix_sum(n)

                    pred_i = active.kth(before) if before else None
                    succ_i = active.kth(before + 1) if before < total else None

                    prev_x = coords[pred_i] if pred_i is not None else 0
                    gaps.set(i, x - prev_x)

                    if succ_i is not None:
                        gaps.set(succ_i, coords[succ_i] - x)

                    active.add(i, 1)

            else:
                x, size = query[1], query[2]
                i = index_of[x]

                # Last obstacle at or before x determines the trailing gap.
                count = active.prefix_sum(i + 1)
                prev_i = active.kth(count) if count else None
                prev_x = coords[prev_i] if prev_i is not None else 0
                trailing_gap = x - prev_x

                best_gap = max(gaps.query(0, i + 1), trailing_gap)
                answers.append(best_gap >= size)

        return answers

Complexity:

  • Time: O(q log q), for coordinate compression and logarithmic tree operations per query.
  • Space: O(q), for compressed coordinates and the trees.

Common follow-ups

  • How would you handle obstacle removal? Update the two affected neighboring gaps when removing an obstacle.
  • What if coordinates are too large to compress offline? Use a dynamic segment tree over the coordinate range.
  • What if blocks must fit in a specified subinterval? Query gaps intersecting that interval and account for its clipped boundaries.

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