SAP Previous Year Coding Questions
SAP SE is Germany's largest software company and one of the most prestigious enterprise tech employers for Indian engineers. With a massive R&D centre in Bengaluru and significant presence in Hyderabad and Gurugram, SAP India hires hundreds of engineers annually. Freshers join as Developer Associate (campus) and experienced candidates join as Software Engineer or Senior Software Engineer. SAP's hiring culture values structured problem-solving and clean code — interviewers expect candidates to communicate their thought process clearly before writing a single line of code. The OA is on HackerRank (2–3 problems, 90 minutes) and targets medium-difficulty problems. Technical rounds lean toward fundamental DSA and OOP rather than competitive programming tricks. For experienced roles, Low-Level Design (LLD) and brief system discussions are included. SAP's business domain (ERP, CRM, supply chain) means questions about interval scheduling, resource allocation, and tree-based data hierarchies appear frequently in onsite rounds.
Hiring Process
Step 1: Resume Screening SAP shortlists from IITs, NITs, BITS, VIT, PESIT, and other top colleges. A CGPA of 7.5+ is preferred. Projects in enterprise software, web development, or cloud platforms (AWS, Azure) stand out. Knowledge of Java, Python, or JavaScript is expected.
Step 2: Online Assessment (HackerRank) Duration: 90 minutes. Format: 2–3 DSA coding problems (Easy to Medium), plus 10–15 MCQs covering algorithms, data structures, OOP concepts, and basic OS/DBMS. Partial scoring is offered — pass at least 70% of test cases per problem to advance. Problems often involve arrays, strings, sorting, and basic DP.
Step 3: Technical Interview 1 — DSA (45–60 mins) Conversational round. Starts with a brief project discussion, then one or two coding problems on arrays, strings, or trees. Interviewer may ask about time/space complexity and alternative approaches. Clean variable naming and edge-case awareness are scored.
Step 4: Technical Interview 2 — DSA + OOP/Design (60 mins) One medium coding problem followed by OOP design questions (design a Library Management System, Elevator Simulator, or similar). Experienced candidates (2+ years) may get a system design or database design question. SOLID principles are a common topic.
Step 5: Managerial / HR Round (30 mins) Behavioural round focusing on SAP's cultural fit — teamwork, innovation, and customer focus. Discussion of past projects, challenges, and career goals. MTS candidates may also be asked about Agile/Scrum practices.
Tips: SAP interviewers explicitly reward candidates who think out loud. Narrate your approach before coding. Arrays, strings, and trees are the highest-frequency topics — particularly Kadane's algorithm, sliding window, and binary tree traversals. For OOP/LLD, practice designing at least 3 systems from scratch (Library, Parking Lot, Hospital). Brush up on Java collections (HashMap, TreeMap, PriorityQueue) as many SAP interviewers ask Java-specific follow-ups. Basic SQL joins and normalization are fair game in round 2.
Preparation Resources
Part 1 — OA Questions
1. Maximum Subarray Easy
Find the contiguous subarray with the largest sum. The most frequently reported SAP OA problem — appears in nearly every campus batch from 2022 to 2025.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6 (subarray [4,-1,2,1])
Input: nums = [1]
Output: 1
Approach: Kadane's algorithm. Track currentSum = max(num, currentSum + num) and update globalMax at each step. Reset currentSum when adding the current element is worse than starting fresh.
Complexity: Time O(n) · Space O(1)
Follow-up: Maximum Product Subarray (LC #152) — track both currentMax and currentMin to handle negatives.
2. Longest Palindromic Substring Medium
Find the longest palindromic substring in a string. Commonly reported in SAP HackerRank OAs.
Input: s = "babad"
Output: "bab" (or "aba")
Input: s = "cbbd"
Output: "bb"
Approach: Expand-around-centre. For each index (and between each pair), expand outward while characters match. Track the longest expansion found. Handles both odd-length and even-length palindromes.
Complexity: Time O(n²) · Space O(1)
Follow-up: Manacher's algorithm finds all palindromes in O(n) — mention it as an optimisation if asked.
3. Jump Game Medium
Given an array where each element is the maximum jump length from that position, determine if you can reach the last index.
Input: nums = [2,3,1,1,4]
Output: true
Input: nums = [3,2,1,0,4]
Output: false
Approach: Greedy. Track the furthest reachable index (maxReach). At each position, if i > maxReach, return false — you're stuck. Otherwise update maxReach = max(maxReach, i + nums[i]).
Complexity: Time O(n) · Space O(1)
Follow-up: Jump Game II (LC #45) — find the minimum number of jumps to reach the end using a BFS-like greedy.
4. Longest Common Subsequence Medium
Find the length of the longest common subsequence of two strings. A classic SAP OA problem — tests fundamental 2D DP understanding.
Input: text1 = "abcde", text2 = "ace"
Output: 3 ("ace")
Input: text1 = "abc", text2 = "def"
Output: 0
Approach: 2D DP. dp[i][j] = LCS length for text1[0..i) and text2[0..j). If characters match: dp[i][j] = dp[i-1][j-1] + 1. Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Complexity: Time O(m*n) · Space O(m*n) (reducible to O(n))
Follow-up: Edit Distance (LC #72) — closely related DP where you count minimum insertions, deletions, and substitutions.
5. Pascal's Triangle Easy
Generate the first numRows rows of Pascal's Triangle. Reported as a warm-up problem in SAP campus OAs.
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Approach: Each row starts and ends with 1. Interior element at position j = previous_row[j-1] + previous_row[j]. Build row by row.
Complexity: Time O(n²) · Space O(n²)
Follow-up: Pascal's Triangle II (LC #119) — return just the kth row using O(k) space by updating in reverse.
6. Container With Most Water Medium
Find two vertical lines that together with the x-axis form a container holding the most water. Reported in SAP OA rounds.
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Approach: Two pointers starting at both ends. Area = min(height[left], height[right]) (right - left). Always move the pointer with the shorter line inward — moving the taller one can only decrease the area.
*Complexity: Time O(n) · Space O(1)
Follow-up: Trapping Rain Water (LC #42) — sum up water trapped at each individual cell using the same two-pointer insight.
Part 2 — Phone Screen Questions
7. Valid Parentheses Easy
Determine if a string of brackets is valid — every open bracket must close 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, return false. Return true only if the stack is empty at the end.
Complexity: Time O(n) · Space O(n)
Follow-up: Minimum Remove to Make Valid Parentheses (LC #1249) — remove the minimum characters to make the string valid.
8. Reverse Linked List Easy
Reverse a singly linked list. Reported in almost every SAP technical round as a warm-up. Interviewers ask for both iterative and recursive solutions.
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Approach: Iterative — three pointers: prev (null), curr (head), next. At each step: store next = curr.next, point curr.next = prev, advance prev = curr, curr = next. Return prev.
Complexity: Time O(n) · Space O(1) iterative | O(n) recursive
Follow-up: Reverse Linked List II (LC #92) — reverse only the nodes between positions left and right.
9. Merge Two Sorted Lists Easy
Merge two sorted linked lists into one sorted list and return it.
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Approach: Dummy head node. Compare heads of both lists; attach the smaller node and advance its pointer. Attach any remaining nodes. Return dummy.next.
Complexity: Time O(m+n) · Space O(1)
Follow-up: Merge K Sorted Lists (LC #23) — use a min-heap holding one node per list for O(N log k) time.
10. Balanced Binary Tree Easy
Determine if a binary tree is height-balanced (left and right subtrees of every node differ in height by at most 1).
Input: root = [3,9,20,null,null,15,7]
Output: true
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Approach: Post-order DFS. For each node, compute height. If left or right subtree returns -1 (unbalanced), propagate -1 upward immediately. Otherwise check if |leftHeight - rightHeight| > 1.
Complexity: Time O(n) · Space O(h)
Follow-up: Minimum depth (LC #111) — similar DFS but stops at the first leaf node.
11. Number of 1 Bits Easy
Return the number of set bits (1s) in the binary representation of a number. SAP interviewers frequently follow this up with bit-manipulation puzzles.
Input: n = 11 (binary: 1011)
Output: 3
Input: n = 128 (binary: 10000000)
Output: 1
Approach: Brian Kernighan's algorithm. n & (n-1) clears the lowest set bit. Count iterations until n = 0.
Complexity: Time O(set bits) · Space O(1)
Follow-up: Counting Bits (LC #338) — return an array where answer[i] = number of 1 bits in i, for i = 0 to n; use DP with answer[i] = answer[i >> 1] + (i & 1).
12. Best Time to Buy and Sell Stock Easy
Find the maximum profit from buying and selling a stock once (buy before sell).
Input: prices = [7,1,5,3,6,4]
Output: 5 (buy day 2 at 1, sell day 5 at 6)
Input: prices = [7,6,4,3,1]
Output: 0
Approach: Single pass. Track minPrice seen so far and maxProfit = max(maxProfit, price - minPrice).
Complexity: Time O(n) · Space O(1)
Follow-up: Best Time to Buy and Sell Stock II (LC #122) — unlimited transactions; sum all positive consecutive differences.
13. First Bad Version Easy
Find the first bad version in n versions using a provided isBadVersion(version) API, minimising API calls. Directly relevant to SAP's CI/CD build pipeline scenarios.
Input: n = 5, bad = 4
Output: 4 (isBadVersion(3) = false, isBadVersion(4) = true)
Approach: Binary search. If isBadVersion(mid) is true, the first bad version is at mid or earlier — set right = mid. Otherwise set left = mid + 1. Return left when loop ends.
Complexity: Time O(log n) · Space O(1)
Follow-up: Find Minimum in Rotated Sorted Array (LC #153) — same left-biased binary search pattern.
Part 3 — Onsite Questions
14. Invert Binary Tree Easy
Invert a binary tree (mirror it). Classic SAP onsite warm-up — interviewers use it to see how candidates handle recursive tree problems.
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Approach: Recursive post-order. Swap root.left and root.right, then recursively invert both subtrees. BFS alternative: level-order traversal, swapping children at each node.
Complexity: Time O(n) · Space O(h)
Follow-up: Symmetric Tree (LC #101) — check if a tree is its own mirror using the same recursive structure.
15. Flood Fill Easy
Given a starting pixel in an image, perform flood fill — replace the starting colour and all 4-directionally connected same-colour pixels with the new colour.
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, color=2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Approach: DFS from (sr, sc). If the current pixel has the original colour, paint it and recurse in 4 directions. Handle the edge case where the original colour equals the new colour (return immediately).
Complexity: Time O(m*n) · Space O(m*n)
Follow-up: Number of Islands (LC #200) — same DFS grid traversal to count connected components.
16. Missing Number Easy
Find the one missing number from an array containing n distinct numbers in the range [0, n].
Input: nums = [3,0,1]
Output: 2
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Approach: Math: expectedSum = n(n+1)/2. Return expectedSum - sum(nums). XOR alternative: XOR all indices and all values — the missing number XORs out everything else.
*Complexity: Time O(n) · Space O(1)
Follow-up: Find All Numbers Disappeared in an Array (LC #448) — multiple missing values using sign-negation technique.
17. Single Number Easy
Find the one number that appears once; all others appear exactly twice. Must run in O(n) time and O(1) space.
Input: nums = [4,1,2,1,2]
Output: 4
Approach: XOR all elements. Any number XORed with itself cancels to 0. The single number remains.
Complexity: Time O(n) · Space O(1)
Follow-up: Single Number II (LC #137) — every element appears 3 times except one; use bit counting with modulo 3.
18. Move Zeroes Easy
Move all zeroes to the end of an array in-place while preserving the relative order of non-zero elements.
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Approach: Two-pointer snowball. Maintain a writePointer. For each non-zero element, write it at writePointer and increment. Fill remaining positions with 0.
Complexity: Time O(n) · Space O(1)
Follow-up: Remove Duplicates from Sorted Array (LC #26) — same two-pointer overwrite pattern without zeroing.
19. Majority Element Easy
Find the element that appears more than n/2 times. Assume it always exists.
Input: nums = [3,2,3]
Output: 3
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Approach: Boyer-Moore Voting. Maintain a candidate and count. When count = 0, set candidate = current element. Increment count if current equals candidate, else decrement.
Complexity: Time O(n) · Space O(1)
Follow-up: Majority Element II (LC #229) — find all elements appearing more than n/3 times; use two candidate slots.
20. Power of Two Easy
Determine if an integer is a power of two. SAP interviewers use this to probe bit manipulation knowledge.
Input: n = 16
Output: true
Input: n = 3
Output: false
Approach: n > 0 && (n & (n-1)) == 0. Powers of two have exactly one bit set; n-1 flips all bits below it, so ANDing gives 0.
Complexity: Time O(1) · Space O(1)
Follow-up: Power of Three (LC #326) / Power of Four (LC #342) — similar one-liners using modular arithmetic or bit patterns.
21. Binary Tree Inorder Traversal Easy
Return the inorder traversal (left → root → right) of a binary tree. SAP interviewers ask for both recursive and iterative solutions.
Input: root = [1,null,2,3]
Output: [1,3,2]
Approach: Iterative using an explicit stack. Go as far left as possible, pushing nodes. Pop a node, visit it, then move to its right child and repeat.
Complexity: Time O(n) · Space O(h)
Follow-up: Morris traversal achieves O(1) space inorder traversal by temporarily modifying tree pointers.
22. Number of Islands Medium
Count connected groups of '1's (islands) in a binary grid. One of the most frequently reported SAP onsite problems.
Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output: 3
Approach: DFS from each unvisited '1'. Mark visited cells by setting them to '0'. Each new DFS call increments the island counter.
Complexity: Time O(m*n) · Space O(m*n)
Follow-up: Max Area of Island (LC #695) — return the area (number of cells) of the largest island.
23. Search in Rotated Sorted Array Medium
Search for a target in a rotated sorted array in O(log n).
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Approach: Modified binary search. Identify which half is sorted at each step by comparing nums[left] with nums[mid]. Check if target falls in the sorted half; otherwise search the other half.
Complexity: Time O(log n) · Space O(1)
Follow-up: Find Minimum in Rotated Sorted Array (LC #153) — binary search for the pivot point directly.
24. Binary Tree Level Order Traversal Medium
Return a list of lists containing values at each level of a binary tree.
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Approach: BFS with a queue. At each level, snapshot the queue size, process that many nodes, enqueue their children, and collect values into a level list.
Complexity: Time O(n) · Space O(n)
Follow-up: Binary Tree Zigzag Level Order (LC #103) — alternate append direction per level.
25. Product of Array Except Self Medium
Return output[i] = product of all elements except nums[i], without using division.
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Approach: Left pass: output[i] = product of all to the left. Right pass: multiply by running right product.
Complexity: Time O(n) · Space O(1) (excluding output)
Follow-up: Handle zeros explicitly — one zero means only output[zeroIndex] is non-zero; two or more zeros means all outputs are zero.
26. Sort Colors Medium
Sort an array containing only 0s, 1s, and 2s in-place in one pass without library sort. Also known as the 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]=0, swap with nums[low] and advance both. If 1, advance mid. If 2, swap with nums[high] and decrement high.
Complexity: Time O(n) · Space O(1)
Follow-up: Generalise to k colours using a counting sort approach in O(n + k) time.
27. Top K Frequent Elements Medium
Return the k most frequent elements from an array.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Approach: Frequency map + min-heap of size k. After all insertions, the heap contains the k most frequent. Bucket sort alternative: O(n) — buckets indexed by frequency.
Complexity: Heap: Time O(n log k) | Bucket: Time O(n)
Follow-up: Sort Characters By Frequency (LC #451) — sort all characters by frequency descending.
28. Minimum Path Sum Medium
Find the path from top-left to bottom-right of a grid (only moving right or down) with the minimum sum.
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7 (1→3→1→1→1)
Approach: In-place DP. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). First row and column have only one choice each.
Complexity: Time O(m*n) · Space O(1) (in-place)
Follow-up: Unique Paths (LC #62) — count paths instead of minimising sum; same DP recurrence without costs.
29. Longest Increasing Subsequence Medium
Find the length of the longest strictly increasing subsequence. Reported in multiple SAP onsite rounds — tests advanced DP knowledge.
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4 ([2,3,7,101])
Approach: DP: dp[i] = length of LIS ending at i. dp[i] = max(dp[j]+1 for all j < i where nums[j] < nums[i]). Patience sorting with binary search achieves O(n log n).
Complexity: DP: Time O(n²) | Patience Sort: Time O(n log n) · Space O(n)
Follow-up: Russian Doll Envelopes (LC #354) — 2D LIS with envelopes; sort by width ascending, height descending, then find LIS on heights.
30. Word Break Medium
Determine if string s can be segmented into words from a given dictionary. Reported in SAP onsite rounds — tests DP on strings.
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Approach: DP. dp[i] = true if s[0..i) can be segmented. For each i, check all j < i: if dp[j] is true and s[j..i) is in the dictionary, set dp[i] = true.
Complexity: Time O(n²) · Space O(n)
Follow-up: Word Break II (LC #140) — return all possible segmentations; use memoised recursion.
31. Course Schedule Medium
Determine if all courses can be finished given prerequisite dependencies (detect a cycle in a directed graph).
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Approach: DFS with 3-state coloring (unvisited, in-progress, done) or Kahn's BFS using in-degree counts. A cycle means you cannot finish all courses.
Complexity: Time O(V+E) · Space O(V+E)
Follow-up: Course Schedule II (LC #210) — return the topological order of courses.
32. Subsets Medium
Return all possible subsets (the power set) of an array of distinct integers.
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Approach: Backtracking — at each index, choose to include or exclude the element. Alternatively, iterative: start with [[]], and for each num append it to every existing subset.
Complexity: Time O(n * 2^n) · Space O(n * 2^n)
Follow-up: Subsets II (LC #90) — input has duplicates; sort first and skip duplicates at the same recursion level.
33. Combination Sum Medium
Find all combinations of candidates that sum to a target, where each candidate may be used unlimited times.
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Approach: Backtracking. At each step, try adding each candidate starting from the current index (allowing reuse). If sum equals target, record the combination. If it exceeds, prune.
Complexity: Time O(N^(T/M)) · Space O(T/M)
Follow-up: Combination Sum II (LC #40) — no reuse; sort and skip duplicates.
34. Permutations Medium
Return all permutations of an array of distinct integers.
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Approach: Backtracking with a visited array or by swapping in-place. At each position, try all unused elements; recurse for the remaining positions; backtrack.
Complexity: Time O(n * n!) · Space O(n)
Follow-up: Permutations II (LC #47) — with duplicates; sort and skip same-value elements at each level.
35. Kth Largest Element in an Array Medium
Find the kth largest element in an unsorted array.
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Approach: Min-heap of size k — push each element; if size > k, pop the minimum. The heap's top is the answer. Quickselect gives O(n) average time.
Complexity: Heap: Time O(n log k) | Quickselect: Time O(n) avg
Follow-up: Find Median from Data Stream (LC #295) — maintain two heaps to find the median after each insertion.
36. Find Peak Element Medium
Find a peak element (greater than its neighbours) in an array. Must run in O(log n).
Input: nums = [1,2,3,1]
Output: 2 (index of element 3)
Approach: Binary search. If nums[mid] < nums[mid+1], the peak is to the right — set left = mid+1. Otherwise set right = mid. When left == right, that's a peak index.
Complexity: Time O(log n) · Space O(1)
Follow-up: Find Peak Index in a Mountain Array (LC #852) — guaranteed single peak; same binary search.
37. 3Sum Medium
Find all unique triplets summing to zero.
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Approach: Sort. Fix first element at index i; two-pointer the rest. Skip duplicates of i and after each match.
Complexity: Time O(n²) · Space O(1)
Follow-up: 4Sum (LC #18) — add an outer loop; same two-pointer logic for the inner triple.
38. Evaluate Reverse Polish Notation Medium
Evaluate a Reverse Polish Notation expression. Reported in SAP onsite rounds as a stack-design problem.
Input: tokens = ["2","1","+","3","*"]
Output: 9 ((2+1)*3)
Input: tokens = ["4","13","5","/","+"]
Output: 6 (4+(13/5))
Approach: Stack. For each token: if it's a number push it. If it's an operator, pop two numbers, apply the operation, push the result. Return the stack's top.
Complexity: Time O(n) · Space O(n)
Follow-up: Basic Calculator (LC #224) — infix expression with parentheses; requires tracking operator precedence.
39. House Robber Medium
Maximise total amount robbed from houses in a line without robbing two adjacent houses.
Input: nums = [2,7,9,3,1]
Output: 12
Approach: Two rolling variables. newVal = max(prev1, prev2 + nums[i]). No array needed.
Complexity: Time O(n) · Space O(1)
Follow-up: House Robber II (LC #213) — circular arrangement; run linear DP twice (exclude first or last house).
40. Group Anagrams Medium
Group all anagrams from an array of strings together.
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Approach: Hash map keyed by sorted characters of each string. Append each string to its group.
Complexity: Time O(n * k log k) · Space O(nk)
Follow-up: Use a 26-integer frequency tuple as the key for O(nk) time without sorting.
41. Spiral Matrix Medium
Return all matrix elements in spiral order (right → down → left → up, layer by layer).
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Approach: Shrinking boundaries (top, bottom, left, right). Traverse each boundary in order, then shrink it. Validate boundaries before each direction.
Complexity: Time O(m*n) · Space O(1)
Follow-up: Spiral Matrix II (LC #59) — fill an n×n matrix with 1 to n² in spiral order.
42. Coin Change Medium
Find the minimum number of coins to make a given amount.
Input: coins = [1,5,11], amount = 15
Output: 3 (5+5+5)
Approach: Bottom-up DP. dp[i] = minimum coins for amount i. For each amount, try every coin: dp[i] = min(dp[i], dp[i-coin]+1).
Complexity: Time O(amount * n) · Space O(amount)
Follow-up: Coin Change II (LC #518) — count combinations, not minimum coins.
43. LRU Cache Medium
Design an LRU Cache with O(1) get and O(1) put. The most frequently asked LLD question in SAP onsite rounds across all campuses.
LRUCache cache = new LRUCache(2);
cache.put(1,1); cache.put(2,2);
cache.get(1); // 1
cache.put(3,3); // evicts key 2
cache.get(2); // -1
Approach: Doubly linked list + hash map. On get: move node to front. On put: insert at front; if over capacity, remove the tail and evict its key from the map.
Complexity: Time O(1) per operation · Space O(capacity)
Follow-up: Design a distributed cache (SAP HANA context) — discuss consistent hashing, replication, and eviction policies at scale.
44. Implement Trie (Prefix Tree) Medium
Implement a Trie with insert, search, and startsWith. SAP interviewers ask this in the context of building autocomplete for SAP Fiori search bars.
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // true
trie.search("app"); // false
trie.startsWith("app"); // true
Approach: Each TrieNode holds 26 children and an isEnd flag. insert: traverse/create nodes per character and mark the last as end. search: traverse and check isEnd. startsWith: traverse and return true if all nodes exist.
Complexity: Time O(L) per operation · Space O(total chars)
Follow-up: Design Add and Search Words (LC #211) — support '.' wildcard using DFS.
45. Daily Temperatures Medium
Return an array where answer[i] = number of days to wait for a warmer temperature; 0 if none. Reported in SAP onsite rounds as a monotonic stack problem.
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Approach: Monotonic decreasing stack of indices. Pop indices whose temperature is lower than the current — their answer = current index - popped index.
Complexity: Time O(n) · Space O(n)
Follow-up: Next Greater Element I (LC #496) — use a hash map to look up results for a subset of elements.
46. Clone Graph Medium
Return a deep copy of an undirected graph. Relevant to SAP's data model duplication (cloning organisation structures in SAP ERP).
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: deep copy with same structure
Approach: BFS with a hash map (original → clone). For each dequeued node, iterate its neighbours; create clones for new ones and enqueue them. Append cloned neighbours to the current clone.
Complexity: Time O(V+E) · Space O(V)
Follow-up: Discuss how to deep-clone a cyclic object graph in Java using a visited map — directly asked in SAP Java interviews.
47. Lowest Common Ancestor of a Binary Tree Medium
Find the lowest common ancestor of two nodes in a binary tree.
Input: root = [3,5,1,6,2,0,8], p = 5, q = 1
Output: 3
Approach: Post-order DFS. Return root if root == null/p/q. Recurse left and right. If both sides return non-null, current root is the LCA.
Complexity: Time O(n) · Space O(h)
Follow-up: LCA in BST (LC #235) — use BST property to navigate without traversing the whole tree.
48. Rotate Image Medium
Rotate an n×n matrix 90° clockwise in-place.
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Approach: Transpose (swap matrix[i][j] with matrix[j][i]), then reverse each row.
Complexity: Time O(n²) · Space O(1)
Follow-up: Counter-clockwise rotation — reverse each column instead of each row after transposing.
49. Path Sum II Medium
Find all root-to-leaf paths where the sum of values equals the target.
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Approach: DFS backtracking. Maintain current path and running sum. At leaves, if sum equals target, record a copy of the path. Remove the last node before returning.
Complexity: Time O(n) · Space O(h)
Follow-up: Path Sum III (LC #437) — count paths summing to target (any start/end); use prefix sum hash map for O(n) time.
50. Edit Distance Hard
Find the minimum number of operations (insert, delete, replace) to convert word1 to word2. Directly relevant to SAP's spell-check and fuzzy search features. Reported in senior SAP onsite rounds.
Input: word1 = "horse", word2 = "ros"
Output: 3
Input: word1 = "intention", word2 = "execution"
Output: 5
Approach: 2D DP. dp[i][j] = minimum edits to convert word1[0..i) to word2[0..j). If characters match: dp[i][j] = dp[i-1][j-1]. Otherwise: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) for delete, insert, and replace respectively.
Complexity: Time O(m*n) · Space O(m*n) (reducible to O(n))
Follow-up: Minimum ASCII Delete Sum (LC #712) — delete characters from both strings to make them equal, minimising total ASCII cost.
Preparation Tips
SAP interviews lean toward fundamental DSA and clear communication over competitive-level tricks. The highest-priority topics are: arrays (Kadane's, two-pointer, sliding window), strings (palindromes, anagrams, DP), trees (all traversals — both recursive and iterative), and basic DP (LCS, LIS, coin change, house robber). For the LLD round, master LRU Cache and Library Management System from scratch. Understand Java generics and collections (HashMap, PriorityQueue, TreeMap) as most SAP interviewers use Java as the reference language. Brush up on one round of basic SQL (inner join, group by, having) and OS concepts (deadlock, memory management) — they occasionally appear in round 2 MCQs. Practise verbalising your approach before coding: SAP's scorecard explicitly includes "Thought Process" as a dimension.
Join our Telegram group for SAP interview experiences, OA question sets, and placement resources shared by students placed at SAP India.