Copy<\/button><\/div>\n\nimport java.util.*;\npublic class MajorityElements {\n\n public static List<Integer> findMajority(int[] nums, int k) {\n\n Map<Integer, Integer> candidates = new HashMap<>();\n for (int num : nums) {\n\n if (candidates.containsKey(num)) {\n\n candidates.put(num, candidates.get(num) + 1);\n\n } else if (candidates.size() < k \u2013 1) {\n\n candidates.put(num, 1);\n\n } else {\n\n List<Integer> toRemove = new ArrayList<>();\n\n for (Map.Entry<Integer, Integer> e : candidates.entrySet()) {\n\n if (e.getValue() == 1) toRemove.add(e.getKey());\n\n else candidates.put(e.getKey(), e.getValue() \u2013 1);\n\n }\n\n toRemove.forEach(candidates::remove);\n\n }\n\n }\n \/\/ Verification pass\n\n Map<Integer, Integer> counts = new HashMap<>();\n\n for (int num : nums) counts.merge(num, 1, Integer::sum);\n List<Integer> result = new ArrayList<>();\n\n int threshold = nums.length \/ k;\n\n for (int c : candidates.keySet()) {\n\n if (counts.getOrDefault(c, 0) > threshold) result.add(c);\n\n }\n\n return result;\n\n }\n\n}\n<\/code><\/pre><\/div>Longest palindromic substring<\/span>Dynamic Programming<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Expand around center. For each index i, expand outward checking both odd-length palindromes (center at i) and even-length palindromes (center between i and i+1). Track the longest expansion found. This runs in O(n^2) time and O(1) space, which is the expected answer in interviews. Manacher’s algorithm achieves O(n) but interviewers rarely expect it unless they ask for the optimal solution explicitly.<\/p>\n
Reported in multiple OA write-ups from 2024 to 2025. Candidates who submitted the DP table approach (O(n^2) time and space) were asked in follow-up whether they could reduce space. The expand-around-center approach is the right answer to that question.<\/p>\n
<\/div><\/div><\/div>\n
Search in a rotated sorted array<\/span>Binary Search<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Modified binary search. At each step determine which half is sorted by comparing the midpoint to the left boundary. If the left half is sorted and the target falls within it, search left. Otherwise search right. One pass, O(log n).<\/p>\n
Reported from a PayPal HackerRank OA and a separate phone screen. The standard follow-up: how does this change with duplicates? With duplicates you can’t determine which half is sorted when nums[left] == nums[mid], so you fall back to incrementing left and decrementing right, which degrades to O(n) in the worst case.<\/p>\n
<\/div><\/div><\/div>\n
Word search in a 2D grid<\/span>Backtracking<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
DFS with backtracking from each cell that matches the first character. Mark cells as visited in-place (set to a sentinel like ‘#’) before recursing, restore on backtrack. Return true as soon as the full word is matched. Pruning: if the remaining word is longer than remaining unvisited cells, abort early.<\/p>\n
Reported in PayPal OA write-ups from 2025. The follow-up sometimes asks: “what if you need to find all occurrences?” That changes the logic: instead of returning true on first match, you collect all starting positions and continue searching.<\/p>\n
<\/div><\/div><\/div>\n
Minimum path sum in a triangle<\/span>Dynamic Programming<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Bottom-up DP starting from the second-to-last row. For each element, it equals its value plus the minimum of the two elements directly below it. After processing all rows from bottom to top, the answer is at the top element. Runs in O(n^2) time and O(n) space if you modify the triangle in place or use a 1D DP array of size n.<\/p>\n
Reported from a 2025 PayPal OA. The in-place modification trick, using the triangle itself as the DP table, is the kind of space optimization that interviewers note positively in the OA scoring rubric.<\/p>\n
<\/div><\/div><\/div>\n
Print a given matrix in spiral order<\/span>Arrays<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
Track four shrinking boundaries: top, bottom, left, right. Walk left to right across the top row, top to bottom down the right column, right to left across the bottom row, and bottom to top up the left column, moving each boundary inward by one after its pass. Stop once top exceeds bottom or left exceeds right. The whole traversal runs in O(rows × cols) time and needs no extra space beyond the output list.<\/p>\n
Reported in PayPal OA write-ups on GeeksForGeeks as the second, harder question after an easier warm-up problem. Most point loss happens at the boundary checks, specifically forgetting to re-check top <= bottom before the final left-moving pass on a single remaining row, which either duplicates a row or walks off the matrix.<\/p>\n
java<\/span>Copy<\/button><\/div>\n\nimport java.util.*;\npublic class SpiralMatrix {\n\n public static List<Integer> spiralOrder(int[][] matrix) {\n\n List<Integer> result = new ArrayList<>();\n\n if (matrix.length == 0) return result;\n int top = 0, bottom = matrix.length \u2013 1;\n\n int left = 0, right = matrix[0].length \u2013 1;\n while (top <= bottom && left <= right) {\n\n for (int c = left; c <= right; c++) result.add(matrix[top][c]);\n\n top++;\n\n for (int r = top; r <= bottom; r++) result.add(matrix[r][right]);\n\n right\u2013;\n\n if (top <= bottom) {\n\n for (int c = right; c >= left; c\u2013) result.add(matrix[bottom][c]);\n\n bottom\u2013;\n\n }\n\n if (left <= right) {\n\n for (int r = bottom; r >= top; r\u2013) result.add(matrix[r][left]);\n\n left++;\n\n }\n\n }\n\n return result;\n\n }\n\n}\n<\/code><\/pre><\/div>How many rectangles can be formed on an n by n chessboard?<\/span>Math \/ Combinatorics<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
A rectangle on the grid is fully determined by choosing 2 of the n+1 horizontal grid lines and 2 of the n+1 vertical grid lines. That’s C(n+1, 2) ways to pick the horizontal pair times C(n+1, 2) for the vertical pair, so the total rectangle count is C(n+1, 2) squared. On a standard 8 by 8 board that’s 36 squared, 1,296 rectangles. Squares are a separate count: the number of k by k squares on an n by n board is (n – k + 1) squared, summed over k from 1 to n.<\/p>\n
Reported as a PayPal OA and phone screen brainteaser in 2025 candidate write-ups. It’s less an algorithm problem than a combinatorics identity, and the interviewer is really checking whether you reach for the closed-form choose-2 pattern or start writing a brute-force loop over four coordinates, which works but signals you didn’t recognize the structure underneath.<\/p>\n
<\/div><\/div><\/div>\n
Lowest common ancestor in a binary tree using parent pointers<\/span>Trees<\/span>Medium<\/span><\/span><\/span><\/button><\/p>\n
The standard approach with a HashSet: traverse from node p upward to the root, storing each node in a set. Then traverse from node q upward; the first node already in the set is the LCA. This runs in O(h) time and O(h) space where h is the height of the tree.<\/p>\n
Reported from the PayPal SDE II round on GeeksForGeeks (2024). The interviewer specifically asked for space optimization. The O(1) space approach: find depths of p and q, bring the deeper node up to the same level, then move both upward in lockstep until they meet.<\/p>\n
java<\/span>Copy<\/button><\/div>\n\nimport java.util.*;\nclass TreeNode {\n\n int val;\n\n TreeNode parent, left, right;\n\n TreeNode(int val) { this.val = val; }\n\n}\npublic class LCA {\n\n public TreeNode findLCA(TreeNode p, TreeNode q) {\n\n Set<TreeNode> visited = new HashSet<>();\n\n while (p != null) {\n\n visited.add(p);\n\n p = p.parent;\n\n }\n\n while (q != null) {\n\n if (visited.contains(q)) return q;\n\n q = q.parent;\n\n }\n\n return null;\n\n }\n\n}\n<\/code><\/pre><\/div>Print the right view of a binary tree<\/span>