Dynamic Programming Questions at PayPal: What to Expect

Dynamic Programming (DP) is a core algorithmic technique for optimizing decisions over time or sequences, making it directly relevant to financial technology. At PayPal, with its focus on payments, risk analysis, fraud detection, and transaction optimization, DP is used to model complex, state-dependent problems efficiently. For example, calculating optimal currency conversion paths, minimizing transaction settlement times, or evaluating sequences of user behaviors for risk scoring can all be framed as DP problems. Mastering DP demonstrates your ability to handle overlapping subproblems and optimal substructure—key to writing performant systems at scale. Out of 106 total coding questions in PayPal's interview repertoire, 19 are DP problems, indicating its significant weight in their technical evaluation.

What to Expect — Types of Problems

PayPal's DP questions typically fall into three categories, emphasizing practical applications over purely academic puzzles.

1. String/Sequence Analysis: These are among the most common. You might be asked to find the longest common subsequence (relevant for data matching or diff algorithms), edit distance (useful in fuzzy matching of transaction descriptions or user inputs), or count distinct subsequences. They test your ability to work with two-dimensional state representing indices in two strings or sequences.
2. Knapsack & Resource Allocation: Problems involving making optimal selections given constraints, like the classic 0/1 Knapsack or its variants. At PayPal, this could analogize to selecting a set of transactions to batch process under a time limit or allocating server resources to maximize throughput. These problems require thinking in terms of weight/value and capacity.
3. Pathfinding & State Transition: Problems like unique paths, minimum path sum, or climbing stairs. While seemingly simple, they test your grasp of state definition and transition. In a financial context, this pattern can model state machines for payment status flows or grid-based optimization in UI routing.

The problems are designed to be challenging but solvable within a 30-45 minute interview slot. Interviewers look for your ability to identify the DP pattern, correctly define the state and recurrence relation, and then implement it efficiently, often moving from a recursive memoization solution to an iterative tabulation one.

How to Prepare — Study Tips with One Code Example

Start by solidifying the fundamentals: understand what defines a DP problem (overlapping subproblems, optimal substructure). Memorization is not enough; you must learn to derive the solution. Follow this process for every problem:

1. Define the State: What does dp[i] or dp[i][j] represent? Be precise.
2. Define the Recurrence Relation: How does dp[i] relate to previous states (e.g., dp[i-1], dp[i-2])?
3. Base Cases: What are the smallest, simplest states you can define directly?
4. Order of Computation: In which order should states be computed to ensure needed subproblems are solved?
5. Final Answer: Which state holds the solution?

A critical pattern is the "Two-State Sequence DP" used in problems like "House Robber" (relevant to selecting non-adjacent transactions for review). The state often represents the maximum value achievable up to a certain point, with the recurrence choosing between including or excluding the current element.

def rob(nums):
    # dp[i] = max money robbing up to house i
    if not nums:
        return 0
    n = len(nums)
    if n == 1:
        return nums[0]

    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, n):
        # Recurrence: rob current house + dp[i-2] OR skip it (dp[i-1])
        dp[i] = max(dp[i-1], nums[i] + dp[i-2])

    return dp[n-1]

Recommended Practice Order

Do not jump into hard problems. Build competence progressively.

1. Foundation: Start with one-dimensional DP: Climbing Stairs, House Robber, Fibonacci. Focus on the state/recurrence definition.
2. Core Patterns: Move to fundamental 2D DP: Longest Common Subsequence, Edit Distance, and 0/1 Knapsack. These are the building blocks for most PayPal problems.
3. Variants & Optimization: Practice problems that are twists on the core patterns, like "Coin Change" (unbounded knapsack), "Longest Increasing Subsequence," or "Maximum Product Subarray."
4. PayPal-Specific: Finally, target the 19 PayPal-tagged DP problems. This sequence ensures you have the tools to deconstruct their specific questions.

Practice Dynamic Programming at PayPal