PayPal Previous Year Coding Questions
PayPal India (Bangalore and Chennai) hires software engineers across T21, T22, and T23 levels. The interview process is notably focused on Dynamic Programming, string manipulation, and array problems, with system design rounds becoming more rigorous at SDE2 and above. Interviewers expect an optimal solution from the start — they will stop you if the approach is wrong before you begin coding. The zigzag conversion question using "PAYPAL IS HIRING" as the example is famously a real PayPal interview question used repeatedly across multiple years.
Hiring Process
Step 1: Resume Screening Recruiter shortlists based on relevant experience, skills, and academic background. Roles are classified as T21 (SDE1), T22 (SDE1 senior), and T23 (SDE2).
Step 2: Online Assessment (HackerRank / HackerEarth) Duration: 60–90 minutes. Contains 10–15 MCQs covering CS fundamentals (OOPS, OS, DBMS, Networking, SQL, JavaScript) and 2–3 coding questions of Easy to Medium difficulty. Time management across the MCQ and coding sections is a common challenge.
Step 3: Technical Round 1 — DSA A 45–60 minute live coding interview with 2 LeetCode Medium problems. Interviewers expect you to state your approach and complexity before coding. They may redirect you if the approach is suboptimal.
Step 4: Technical Round 2 — DSA + Role Specialisation 45 minutes. A mix of one DSA problem and a deep dive into your previous project: architecture decisions, tech stack rationale, and scalability considerations. Java internals, Spring, HashMap implementation, and multithreading concepts appear here.
Step 5: System Design Round (HLD) For SDE2 and SDE3 candidates. 45–60 minutes covering functional and non-functional requirements, API design, database schema, and high-level architecture. Payment systems and large-scale booking systems are recurring themes given PayPal's domain.
Step 6: Bar Raiser / Hiring Manager Round 60 minutes of behavioural interview. No coding. Topics include cross-team conflicts, adapting to new environments, handling ambiguous requirements, and demonstrating ownership and leadership. A Senior or Principal engineer typically conducts this round.
Tips: PayPal puts a strong emphasis on Strings and DP. Prepare the zigzag pattern, palindrome problems, and all DP variants from the House Robber and Triangle families. For System Design, focus on payment processing and distributed consistency. Always state time and space complexity before the interviewer asks — they expect it proactively.
Preparation Resources
Part 1 — OA Questions
1. Zigzag Conversion Medium
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows. Given the string and the number of rows, return the string read line by line. This exact problem with "PAYPAL IS HIRING" has been used in real PayPal interviews.
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
P A H N
A P L S I I G
Y I R
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Approach: Create numRows string builders. Use a direction flag (going down or up). Assign each character to the current row's builder, then move down until the bottom row, reverse direction and move up until the top row. Concatenate all builders at the end.
Complexity: Time O(n) · Space O(n)
Follow-up: What is the mathematical index pattern for which characters land in each row without using extra row arrays?
2. Climbing Stairs Easy
You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach the top?
Input: n = 2
Output: 2
Explanation: 1+1 and 2.
Input: n = 3
Output: 3
Explanation: 1+1+1, 1+2, 2+1.
Approach: This is Fibonacci in disguise. dp[1]=1, dp[2]=2. For each step i, dp[i] = dp[i-1] + dp[i-2]. Optimise to O(1) space using two variables tracking the previous two values.
Complexity: Time O(n) · Space O(1)
Follow-up: Min Cost Climbing Stairs where each step has a cost (LeetCode #746).
3. Maximum Product Subarray Medium
Given an integer array nums, find a contiguous subarray with the largest product and return that product.
Input: nums = [2,3,-2,4]
Output: 6
Explanation: Subarray [2,3].
Input: nums = [-2,0,-1]
Output: 0
Approach: Track both max and min product ending at the current position (a negative times a negative becomes positive). At each step: curMax = max(nums[i], curMaxnums[i], curMinnums[i]) and similarly for curMin. Track the global max.
**Complexity: Time O(n) · Space O(1)
Follow-up: What if the array can contain zeros?
4. Check Whether Subarray with Zero Sum Exists Easy
Given an integer array nums, return true if there is a subarray of length at least 2 that sums to zero (or a multiple of k in the LC variant).
Input: nums = [1, 4, -5, 2, -3, 1]
Output: true
Explanation: Subarray [4, -5, 2, -3, 1] sums to -1... subarray [1,4,-5] = 0.
Input: nums = [1, 2, 3]
Output: false
Approach: Maintain a prefix sum. If the prefix sum is 0, or has been seen before in the hash set, a subarray with sum 0 exists. Insert each prefix sum into the set as you iterate.
Complexity: Time O(n) · Space O(n)
Follow-up: Count the total number of subarrays with sum equal to zero.
5. Decode String Medium
Given an encoded string where k[encoded_string] means the encoded_string should be repeated k times, return the decoded string.
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Input: s = "3[a2[c]]"
Output: "accaccacc"
Approach: Use two stacks — one for repeat counts and one for strings built so far. When you see a '[', push the current string and count onto the stacks. When you see ']', pop the count, repeat the current string that many times, and append it to the popped previous string.
Complexity: Time O(n * max_k) · Space O(n)
Follow-up: What is the maximum possible output length given n encoded characters?
6. Stars and Bars — Count Stars Between Boundaries Easy
Given a string containing '*' and '|' characters and an array of queries [left, right], count the number of stars between the left-th and right-th bars (1-indexed) for each query.
Input: s = "|**|*|*", queries = [[2,5],[5,6]]
Output: [2,1]
Explanation: Between the 2nd and 5th bars: "**" = 2 stars.
Approach: Build a prefix sum array where bars[i] stores the index of the i-th bar in the string. For each query [left, right], count the stars between bars[left] and bars[right] using a prefix count of stars. Precompute a stars prefix sum over the original string.
Complexity: Time O(n + q) · Space O(n)
Follow-up: What if the queries arrive in a stream and the string can be updated?
Part 2 — Phone Screen Questions
7. Min Stack Medium
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
MinStack()
push(-2), push(0), push(-3)
getMin() → -3
pop()
top() → 0
getMin() → -2
Approach: Use an auxiliary stack that tracks the current minimum. On every push, push to the main stack. Also push to the min stack if the new value is <= the current minimum. On pop, if the popped value equals the min stack top, pop from the min stack too.
Complexity: Time O(1) per operation · Space O(n)
Follow-up: Implement a Max Stack that supports O(log n) pop of the maximum element (LeetCode #716).
8. House Robber Medium
You are a robber planning to rob houses along a street. Adjacent houses have security systems and robbing two adjacent ones triggers an alert. Given an integer array nums representing the amount of money at each house, return the maximum amount you can rob.
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (1) and house 3 (3).
Input: nums = [2,7,9,3,1]
Output: 12
Approach: dp[i] = max money robbing up to house i. dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Optimise to two variables (prev1, prev2).
Complexity: Time O(n) · Space O(1)
Follow-up: Houses in a circle (House Robber II, LeetCode #213) and houses on a binary tree (LeetCode #337).
9. Triangle Minimum Path Sum Medium
Given a triangle array, return the minimum path sum from top to bottom. At each step, you may move to the adjacent number on the row below.
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: Path 2 → 3 → 5 → 1 = 11.
Approach: Bottom-up DP. Start from the second-to-last row. For each element, update it to itself plus the minimum of the two values directly below it. After processing all rows, triangle[0][0] holds the minimum path sum. This achieves O(1) extra space using the triangle itself.
Complexity: Time O(n²) · Space O(1)
Follow-up: What if you need to find the actual path, not just the sum?
10. Jump Game II Medium
Given an array where each element is the maximum jump length from that position, find the minimum number of jumps to reach the last index.
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: Jump from index 0 to 1 (value 3), then to end.
Input: nums = [2,3,0,1,4]
Output: 2
Approach: Greedy BFS-style. Maintain currentEnd (furthest reachable in current jump) and farthest (furthest reachable with one more jump). At each position up to currentEnd, update farthest. When you reach currentEnd, increment jumps and advance currentEnd to farthest.
Complexity: Time O(n) · Space O(1)
Follow-up: Can you reach the last index at all (Jump Game I, LeetCode #55)?
11. Remove All Adjacent Duplicates in String II Medium
Given a string s and an integer k, repeatedly remove k adjacent identical characters until no such group exists. Return the final string.
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: deeed→ (remove eee) →dbbcccbdaa→ (remove ccc)→dbbbd aa→ (remove bbb)→ddaa→(remove dd)→aa.
Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"
Approach: Use a stack of (character, count) pairs. For each character, if the stack top has the same character, increment its count; otherwise push a new pair. When a count reaches k, pop the pair. Rebuild the string from the stack at the end.
Complexity: Time O(n) · Space O(n)
Follow-up: k=2 variant (Remove All Adjacent Duplicates in String, LeetCode #1047).
12. Find the Smallest Divisor Given a Threshold Medium
Given an array nums and an integer threshold, choose a positive integer divisor such that the sum of ceil(nums[i] / divisor) for all i is at most threshold. Return the smallest such divisor.
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Input: nums = [44,22,33,11,1], threshold = 5
Output: 44
Approach: Binary search on the divisor in range [1, max(nums)]. For a given mid, compute the sum of ceil(nums[i] / mid). If the sum is <= threshold, mid is a valid divisor so try smaller. Otherwise try larger.
Complexity: Time O(n log max) · Space O(1)
Follow-up: Koko Eating Bananas (LeetCode #875) is structurally identical — identify the pattern.
13. Validate Binary Search Tree Medium
Given the root of a binary tree, determine if it is a valid BST where every node's value is strictly greater than all values in its left subtree and strictly less than all values in its right subtree.
Input: root = [2,1,3]
Output: true
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: Right child is 4 which is less than root 5.
Approach: Recursively validate with an allowed range (min, max). Root has range (-∞, +∞). Going left passes (min, node.val); going right passes (node.val, max). If a node's value is outside its range, return false.
Complexity: Time O(n) · Space O(h)
Follow-up: Recover a BST where exactly two nodes are swapped (LeetCode #99).
Part 3 — Onsite Questions
14. Trapping Rain Water Hard
Given n non-negative integers representing an elevation map, compute how much water can be trapped after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Input: height = [4,2,0,3,2,5]
Output: 9
Approach: Two pointers from both ends. Maintain leftMax and rightMax. At each step, process the side with the smaller max boundary. Water trapped at that position = boundary max − bar height. Advance the pointer inward.
Complexity: Time O(n) · Space O(1)
Follow-up: Trapping Rain Water II on a 2D grid (LeetCode #407) using a min-heap.
15. Merge K Sorted Lists Hard
Merge k sorted linked lists and return it as one sorted list.
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Approach: Use a min-heap of size k. Initialise with the head of each list. Pop the smallest node, add it to the result, and push its next node (if any) to the heap. Repeat until the heap is empty.
Complexity: Time O(n log k) · Space O(k)
Follow-up: Divide and conquer approach merging pairs of lists in O(n log k) with O(1) extra space.
16. Knight's Shortest Path Medium
In an infinite chessboard, a knight starts at position (0,0) and makes standard L-shaped moves. Given target (x, y), return the minimum number of moves to reach the target.
Input: x = 5, y = 5
Output: 4
Input: x = 2, y = 1
Output: 1
Approach: BFS from (0,0). Explore all 8 possible knight moves. Use a visited set. Due to symmetry, restrict the search space to the positive quadrant (abs(x), abs(y)). Return the level count when the target is reached.
Complexity: Time O(max(x,y)²) · Space O(max(x,y)²)
Follow-up: How does bidirectional BFS reduce the time complexity here?
17. Spiral Matrix Medium
Given an m x n matrix, return all elements in spiral order.
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Approach: Maintain four boundaries: top, bottom, left, right. Traverse right along top, down along right, left along bottom, up along left. Shrink the corresponding boundary after each direction. Stop when top > bottom or left > right.
Complexity: Time O(m*n) · Space O(1)
Follow-up: Generate a spiral matrix filled with 1 to n² (LeetCode #59).
18. Remove Nth Node From End of List Medium
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Input: head = [1], n = 1
Output: []
Approach: Two pointers with a gap of n. Advance the fast pointer n steps ahead. Then advance both pointers together until fast reaches the last node. The slow pointer is now just before the node to delete. Update its next pointer to skip the target node.
Complexity: Time O(L) · Space O(1)
Follow-up: Find the middle of a linked list in one pass (LeetCode #876).
19. Longest Palindromic Subsequence Medium
Given a string s, find the length of the longest palindromic subsequence (characters need not be contiguous).
Input: s = "bbbab"
Output: 4
Explanation: "bbbb".
Input: s = "cbbd"
Output: 2
Approach: dp[i][j] = length of LPS in s[i..j]. If s[i]==s[j], dp[i][j] = dp[i+1][j-1] + 2. Otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Fill diagonally bottom-up. Alternative: LCS of s and reverse(s).
Complexity: Time O(n²) · Space O(n²)
Follow-up: Minimum number of deletions to make a string palindrome.
20. Coin Change Medium
Given coin denominations and an integer amount, return the minimum number of coins to make up the amount. Return -1 if impossible.
Input: coins = [1,5,6,9], amount = 11
Output: 2
Explanation: 5 + 6 = 11.
Input: coins = [2], amount = 3
Output: -1
Approach: Bottom-up DP. dp[0]=0, rest infinity. For each amount from 1 to target, try every coin c: if c <= amount, dp[amount] = min(dp[amount], dp[amount-c] + 1).
Complexity: Time O(amount * n) · Space O(amount)
Follow-up: Total number of combinations (Coin Change 2, LeetCode #518).
21. Minimum Path Sum Medium
Given an m x n grid of non-negative numbers, find the path from top-left to bottom-right (only right or down moves) that minimises the sum.
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: 1→3→1→1→1 = 7.
Approach: Update the grid in-place. Accumulate the first row left to right and the first column top to bottom. Each remaining cell = min(cell above, cell left) + current value.
Complexity: Time O(m*n) · Space O(1)
Follow-up: Maximum path sum from top to bottom in a triangle (LeetCode #120).
22. Longest Palindromic Substring Medium
Given a string s, return the longest palindromic substring.
Input: s = "babad"
Output: "bab"
Input: s = "cbbd"
Output: "bb"
Approach: Expand around each centre. For each index, expand both odd-length (single centre) and even-length (adjacent pair) palindromes outward as long as characters match. Track the start and max length of the longest palindrome found.
Complexity: Time O(n²) · Space O(1)
Follow-up: Manacher's algorithm achieves O(n) time.
23. Maximum Subarray (Kadane's Algorithm) Medium
Given an integer array nums, find the contiguous subarray with the largest sum and return its sum.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: Subarray [4,-1,2,1] = 6.
Approach: Kadane's algorithm. Keep a running current sum. If adding the next element makes it worse than starting fresh, reset to the current element. Track the global maximum.
Complexity: Time O(n) · Space O(1)
Follow-up: Return the actual subarray indices, not just the sum.
24. Kth Largest Element in an Array Medium
Given an integer array nums and an integer k, return the kth largest element in the array (not kth distinct).
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Approach: Use a min-heap of size k. For each element, push to heap. If heap size exceeds k, pop the smallest. The heap top after all elements is the kth largest. Alternatively, QuickSelect achieves O(n) average time.
Complexity: Time O(n log k) heap · O(n) average QuickSelect · Space O(k)
Follow-up: When would you prefer QuickSelect over a heap?
25. Longest Common Subsequence Medium
Given two strings text1 and text2, return the length of their longest common subsequence. Return 0 if none exists.
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: "ace".
Input: text1 = "abc", text2 = "abc"
Output: 3
Approach: dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]. If text1[i-1] == text2[j-1], dp[i][j] = dp[i-1][j-1] + 1. Otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Space can be reduced to O(min(m,n)) using a 1D rolling array.
Complexity: Time O(m*n) · Space O(min(m,n))
Follow-up: Shortest Common Supersequence (LeetCode #1092).
26. Word Search Medium
Given an m x n grid of characters and a string word, return true if the word exists in the grid (adjacent cells horizontally or vertically, each cell used at most once).
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Approach: DFS backtracking from every cell. Mark the current cell visited (e.g., replace with '#'). Explore all 4 directions. If the recursion finds the complete word, return true. Restore the cell when backtracking.
Complexity: Time O(m*n*4^L) where L = word length · Space O(L)
Follow-up: Word Search II finding all words from a dictionary (Trie + DFS, LeetCode #212).
27. Number of Islands Medium
Given a 2D binary grid of '1' (land) and '0' (water), return the number of islands.
Input:
grid = [["1","1","0","0"],["1","1","0","0"],["0","0","1","0"],["0","0","0","1"]]
Output: 3
Approach: Iterate every cell. On finding '1', increment island count and BFS/DFS to mark all connected land cells as '0'. Continue scanning.
Complexity: Time O(m*n) · Space O(m*n)
Follow-up: Max Area of Island (LeetCode #695).
28. Sort Colors Medium
Given an array with only 0s, 1s, and 2s, sort it in-place in a single pass without using the library sort function (Dutch National Flag problem).
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Approach: Three pointers: low (boundary of 0s), mid (current), high (boundary of 2s). If nums[mid] is 0, swap with low, advance both. If 1, advance mid. If 2, swap with high, retreat high (do not advance mid since the swapped value is unprocessed).
Complexity: Time O(n) · Space O(1)
Follow-up: Generalise to k distinct values (counting sort approach).
29. Find Peak Element Medium
A peak element is one that is strictly greater than its neighbours. Given nums where nums[-1] = nums[n] = -∞, find any peak element in O(log n) time.
Input: nums = [1,2,3,1]
Output: 2 (index of peak element 3)
Input: nums = [1,2,1,3,5,6,4]
Output: 5 (index of peak element 6)
Approach: Binary search. If nums[mid] < nums[mid+1], the peak is in the right half. Otherwise it is in the left half (including mid). This works because the array is guaranteed to have a peak.
Complexity: Time O(log n) · Space O(1)
Follow-up: Find a peak in a 2D matrix (LeetCode #1901).
30. LRU Cache Medium
Design a data structure implementing LRU eviction policy with O(1) get and put.
LRUCache(2)
put(1,1), put(2,2)
get(1) → 1
put(3,3) → evicts key 2
get(2) → -1
Approach: Doubly linked list (for O(1) move-to-front and eviction from tail) + hash map (key → node). On get, move node to head. On put, add/update at head; if capacity exceeded, remove tail and delete its map entry.
Complexity: Time O(1) per operation · Space O(capacity)
Follow-up: How would you implement a distributed LRU cache shared across multiple servers?
31. Intersection of Two Linked Lists Easy
Given heads of two singly linked lists, return the node at which they intersect. Return null if they do not intersect.
Input: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
Output: node with value 8
Approach: Two pointers traversing both lists. When a pointer reaches the end, redirect it to the head of the other list. They will meet at the intersection node after at most lenA + lenB steps (or both reach null if no intersection).
Complexity: Time O(m+n) · Space O(1)
Follow-up: Why does the two-pointer redirection technique guarantee convergence at the intersection?
32. Reverse Words in a String Medium
Given an input string s, reverse the order of words. A word is a sequence of non-space characters. The output must have a single space between words and no leading or trailing spaces.
Input: s = " hello world "
Output: "world hello"
Input: s = "a good example"
Output: "example good a"
Approach: Split by whitespace, filter empty strings, reverse the array, join with a single space. In-place: trim, reverse entire string, then reverse each word in place.
Complexity: Time O(n) · Space O(n)
Follow-up: Reverse Words in a String III where only each word is reversed, not their order (LeetCode #557).
33. Print All Subsequences of a String Medium
Given a string s, print all 2^n subsequences (including the empty string). A subsequence preserves the original order but may skip characters.
Input: s = "abc"
Output: "", "c", "b", "bc", "a", "ac", "ab", "abc"
(order may vary)
Approach: Recursive inclusion-exclusion. At each index, make two recursive calls — one including the current character in the current subsequence, one excluding it. At the base case (index == length), print or collect the current subsequence.
Complexity: Time O(2^n) · Space O(n) call stack
Follow-up: Count the number of distinct subsequences (LeetCode #115).
34. String Compression Medium
Given a character array chars, compress it in-place using run-length encoding. Groups of repeated characters are replaced by the character followed by the group length (omit the length if it is 1). Return the new array length.
Input: chars = ["a","a","b","b","c","c","c"]
Output: 6, chars = ["a","2","b","2","c","3"]
Input: chars = ["a"]
Output: 1
Approach: Two pointers — read and write. Walk through consecutive groups of identical characters. Write the character, then write each digit of the count if count > 1. Advance write pointer accordingly.
Complexity: Time O(n) · Space O(1)
Follow-up: Decompress Run-Length Encoded List (LeetCode #1313).
35. Count and Say Easy
The count-and-say sequence starts with "1". Each subsequent term is the run-length encoding of the previous one. Return the nth term.
Input: n = 4
Output: "1211"
Explanation: "1"→"11"→"21"→"1211".
Approach: Iteratively build each term from the previous one. Scan for runs of consecutive identical digits, appending count then digit to the new string. Repeat n-1 times starting from "1".
Complexity: Time O(2^n) · Space O(2^n)
Follow-up: Can you decode the nth term back to the (n-1)th term?
36. Rotate List Medium
Given the head of a linked list, rotate the list to the right by k places.
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Approach: Find the length L and make the list circular by connecting tail to head. The new tail is at position L - (k % L) - 1 from the current head. Cut the circle there.
Complexity: Time O(n) · Space O(1)
Follow-up: Rotate an array to the right by k places in O(1) extra space.
37. 3Sum Closest Medium
Given an integer array nums and an integer target, find three integers whose sum is closest to target. Return the sum.
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: -1 + 2 + 1 = 2 is closest to 1.
Approach: Sort the array. Fix the first element, use two pointers for the remaining pair. At each step, compute the sum of the three elements and update the closest sum if the absolute difference from target is smaller. Move pointers based on whether the sum is too small or too large.
Complexity: Time O(n²) · Space O(1)
Follow-up: 4Sum closest to a target (LeetCode #18).
38. Maximum Depth of Binary Tree Easy
Given the root of a binary tree, return its maximum depth.
Input: root = [3,9,20,null,null,15,7]
Output: 3
Approach: Recursive DFS: return 0 for null, return 1 + max(depth(left), depth(right)) otherwise.
Complexity: Time O(n) · Space O(h)
Follow-up: Diameter of a binary tree (LeetCode #543).
39. Frequency of the Most Frequent Element Medium
Given an integer array nums and an integer k, you can increment any element by 1 at most k times in total. Return the maximum possible frequency of any element after performing these operations.
Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment 1 twice and 2 once so that all three equal 4.
Input: nums = [1,4,8,13], k = 5
Output: 2
Approach: Sort the array. Use a sliding window. The window is valid if (window size × rightmost element) − (window sum) <= k, since we can increment all elements to equal the rightmost. If invalid, shrink from the left.
Complexity: Time O(n log n) · Space O(1)
Follow-up: What if you could both increment and decrement elements?
40. Design a Payment Processing System Hard
Design PayPal's core send-money service. Users can send money to other users, check their balance, and view transaction history. The system must handle millions of transactions per day with strong consistency guarantees to prevent double charges.
Functional requirements:
- sendMoney(fromUser, toUser, amount, currency)
- getBalance(userId)
- getTransactionHistory(userId, page)
Non-functional requirements:
- Strongly consistent (no double debit)
- High availability (99.99%)
- Low latency (<200ms for payment)
Approach: Use a relational database with ACID transactions for the ledger (debit sender, credit receiver in a single transaction). Introduce an idempotency key per payment request to prevent duplicate processing on retries. For scaling, use database sharding by userId with a distributed saga pattern for cross-shard transfers. A message queue (Kafka) handles async notifications. Cache balance reads with write-through invalidation. Key Concepts: ACID, idempotency keys, distributed transactions, saga pattern, ledger double-entry bookkeeping Follow-up: How do you handle currency conversion in real time?
41. Design IRCTC — Online Ticket Booking System Hard
Design a large-scale train ticket booking system. Users can search for trains between two stations, view available seats, book tickets, and cancel bookings. The system must prevent double-booking and handle massive concurrent traffic during high-demand windows.
Functional: searchTrains, getAvailability, bookTicket, cancelTicket, getBooking
Non-functional: No double-booking, handle 100K concurrent users, <1s search latency
Approach: Separate read and write paths. Read path (search, availability) uses a cache (Redis) over a read replica. Write path (booking) uses optimistic locking or row-level locks in the database with a reservation expiry timeout (hold seat for 10 minutes). If payment fails, the hold is released. Use a distributed queue for waitlisted bookings. Database schema: Train, Coach, Seat, Booking, Payment tables. Key Concepts: Optimistic locking, read/write separation, seat hold with TTL, waitlist queue Follow-up: How do you ensure seat availability is accurate across multiple data centres?
42. Design Elevator System Medium
Design a system for a building with 8 floors and 10 elevators. Support: requesting an elevator from a floor (with direction), pressing a floor button inside the elevator, and the elevator controller dispatching the nearest available elevator.
ElevatorSystem.requestElevator(floor=3, direction=UP)
→ Dispatches elevator 2 (currently at floor 2, idle)
elevator2.pressFloor(5)
→ Elevator moves 3→5
Approach: Classes: Elevator (current floor, direction, state: IDLE/MOVING/MAINTENANCE, internal queue of destination floors), ElevatorController (list of elevators, dispatch logic). Dispatcher uses a scoring function: prefer idle elevators, then ones already moving in the requested direction toward the floor. Internal movement uses a sorted set of pending floors (SCAN/LOOK algorithm). Key Concepts: SCAN disk scheduling algorithm applied to elevators, Observer pattern for floor arrival events Follow-up: How do you handle VIP or emergency floors with priority scheduling?
43. Valid Parentheses Easy
Given a string s with '(', ')', '{', '}', '[', ']', determine if the input is valid (every open bracket closed by the same type in the correct order).
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Approach: Stack. Push opening brackets. On a closing bracket, check if the stack top is the matching opener. If not, or if empty, return false. At the end the stack must be empty.
Complexity: Time O(n) · Space O(n)
Follow-up: Minimum number of bracket reversals to make a string balanced.
44. Edit Distance Hard
Return the minimum number of operations (insert, delete, replace) to convert word1 to word2.
Input: word1 = "horse", word2 = "ros"
Output: 3
Input: word1 = "intention", word2 = "execution"
Output: 5
Approach: dp[i][j] = min ops to convert word1[0..i-1] to word2[0..j-1]. If chars match, dp[i][j] = dp[i-1][j-1]. Otherwise 1 + min of delete (dp[i-1][j]), insert (dp[i][j-1]), replace (dp[i-1][j-1]).
Complexity: Time O(m*n) · Space O(min(m,n)) with rolling array
Follow-up: Recover the actual edit sequence.
45. Binary Tree Inorder Traversal (Iterative) Easy
Given the root of a binary tree, return the inorder traversal of its nodes' values without recursion.
Input: root = [1,null,2,3]
Output: [1,3,2]
Approach: Use an explicit stack. Push all left children until null. Pop the top node, record its value. Move to its right child and repeat. This mimics the recursive call stack.
Complexity: Time O(n) · Space O(h)
Follow-up: Morris traversal achieves O(1) space by temporarily threading the tree.
46. Longest Increasing Subsequence Medium
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: [2,3,7,101].
Approach: Maintain a tails array. For each number, binary search for the leftmost tail >= current and replace it. If current is larger than all tails, append. The tails length is the LIS length.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Print the actual LIS.
47. Two Sum Easy
Given an array of integers nums and an integer target, return indices of the two numbers that add up to target.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Approach: Hash map storing value → index. For each element check if target − current is in the map. If yes, return both indices. Otherwise insert current.
Complexity: Time O(n) · Space O(n)
Follow-up: What if the array is sorted? Use two pointers for O(1) extra space.
48. Merge Intervals Medium
Given an array of intervals, merge all overlapping intervals and return an array of non-overlapping intervals.
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Approach: Sort by start time. Iterate and merge each interval with the last result interval if they overlap, otherwise append.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Insert an interval into a sorted non-overlapping list (LeetCode #57).
49. Subarray Sum Equals K Medium
Given an array nums and integer k, return the total number of subarrays whose sum equals k.
Input: nums = [1,1,1], k = 2
Output: 2
Input: nums = [1,2,3], k = 3
Output: 2
Approach: Running prefix sum with a frequency map. At each position check how many times (currentSum − k) has appeared. Add that count to the answer.
Complexity: Time O(n) · Space O(n)
Follow-up: Why does a sliding window fail here for arrays with negative numbers?
50. Design Notification System Medium
Design a notification system for PayPal that sends users transaction alerts via email, SMS, and push notifications when a payment is sent or received.
Functional: sendNotification(userId, event, channels[]), getPreferences(userId)
Non-functional: At-least-once delivery, < 5s latency, 10M users
Approach: Payment service publishes events to a message queue (Kafka topic per event type). Notification service consumes events, looks up user channel preferences, and fans out to channel-specific workers (Email via SES, SMS via Twilio, Push via FCM/APNs). Use idempotency keys to handle duplicate deliveries. Store notification history in a time-series DB for audit. Retry failed deliveries with exponential backoff. Key Concepts: Event-driven architecture, fan-out, at-least-once delivery, idempotency, channel abstraction Follow-up: How do you handle user preference updates that arrive concurrently with in-flight notifications?
Preparation Tips
PayPal interviews are heavily weighted toward Dynamic Programming and Strings — together they account for roughly half of all reported DSA questions. Prepare the House Robber family, Triangle DP, palindrome problems (both subsequence and substring), and all major string transformations (zigzag, decode, compress). For system design, always frame your PayPal-domain answers around consistency and idempotency since those are core to how a payments company thinks. The Bar Raiser round is entirely behavioural — prepare STAR-format stories around ownership and conflict resolution.
Join Telegram group to get the latest PayPal OA questions shared by candidates and connect with others preparing for PayPal interviews.