Samsung Previous Year Coding Questions
Samsung R&D Institute India (SRIB, Bangalore/Noida) and Samsung Semiconductor India Research (SSIR) are among the most competitive R&D campuses of a multinational in India, typically hiring from the top IITs, NITs, and BITS Pilani. The interview process is renowned for its exceptionally hard Online Assessment — Samsung's OA is consistently rated harder than FAANG OAs, featuring grid-simulation problems that require careful reading and bug-free implementation under time pressure. Technical rounds probe deep OS knowledge (memory management, scheduling), DBMS (indexing, transactions), and CN (TCP/IP, socket programming) in addition to DSA. For senior roles (2+ years), LLD and HLD rounds assess design thinking around Samsung's product lines: SmartTV, Galaxy SmartHome, Samsung Pay, and Bixby AI.
Hiring Process
Step 1: Resume Screening Samsung SRIB prioritises candidates from IITs, NITs, BITS, and VIT with strong academic records. Relevant projects in systems, embedded, or product domains help. CGPA cut-off is typically 7.5+.
Step 2: Online Assessment (HackerEarth / Samsung Internal) Duration: 3 hours. 2 problems — but don't be fooled. The problems are long, complex simulation scenarios (think: a delivery robot navigating a grid with obstacles, portals, and batteries). Partial scoring is available, but the full solution requires edge-case-tight code. This is the most common rejection point.
Step 3: Technical Round 1 — DSA 60 minutes. 1–2 medium-to-hard DSA problems. Expect follow-up questions on time/space complexity, edge cases, and alternative approaches. OS/DBMS fundaments may be tested at the end.
Step 4: Technical Round 2 — DSA + CS Fundamentals 60 minutes. A harder algorithm or a system-level CS question. Interviewers often ask about process synchronisation, deadlocks, B+ trees, TCP handshake, or virtual memory.
Step 5: Technical Round 3 — Projects + Design 60–90 minutes. Deep dive into resume projects, LLD (for SDE-1), or HLD (for SDE-2+). Candidates who cannot clearly explain the design decisions in their own projects are rejected here.
Step 6: HR Round Compensation negotiation, relocation preferences (Bangalore vs. Noida), work culture fit.
Tips: The single most important thing for Samsung's OA is practice grid/matrix simulation. Past OA problems include: robot navigating a warehouse, Bixby routing queries through a network of AI nodes, home delivery path optimisation with portal cells. For technical rounds, revise OS scheduling algorithms, DBMS transaction isolation levels, and TCP/IP. For LLD, a Vending Machine is a Samsung classic — know it cold.
Preparation Resources
Part 1 — OA Questions
1. Shortest Path in a Binary Matrix Medium
Find the shortest clear path from the top-left to the bottom-right of an n×n grid. A clear path moves through cells with value 0 in 8 directions. Samsung OA wraps this as a robot/delivery-agent navigating a warehouse grid.
Input: grid = [[0,1],[1,0]]
Output: 2
Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Approach: BFS from (0,0) tracking distance. Visit all 8 neighbours. Return distance when (n-1,n-1) is reached.
Complexity: Time O(n²) · Space O(n²)
Follow-up: Samsung OA variant adds portals — cells that teleport the robot to a paired cell. Handle these as zero-weight edges in the BFS queue.
2. Maximum Size Rectangle of All 1s Hard
Given a binary matrix, find the area of the largest rectangle containing only 1s.
Input: matrix=[["1","0","1","0","0"],["1","0","1","1","1"],
["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Approach: Build a histogram of heights row by row. For each row, run Largest Rectangle in Histogram (LC #84) using a monotonic stack. The overall maximum is the answer.
Complexity: Time O(m*n) · Space O(n)
Follow-up: Maximal Square (LC #221) — find the largest square sub-matrix of 1s, solvable with O(m*n) DP instead of a stack.
3. Longest Increasing Path in a Matrix Hard
Find the length of the longest strictly increasing path in an m×n integer matrix. Movement is 4-directional.
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: [1,2,6,9]
Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: [3,4,5,6]
Approach: DFS from each cell with memoization. dp[i][j] = longest path starting at (i,j). Since paths are strictly increasing, there are no cycles — the implicit DAG can be memoized safely.
Complexity: Time O(m*n) · Space O(m*n)
Follow-up: What changes if paths can go through equal values as well (non-strictly increasing)?
4. Word Break Medium
Given a string s and a dictionary of words, return true if s can be segmented into a space-separated sequence of dictionary words.
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Approach: dp[i] = true if s[0..i-1] can be segmented. For each position i, check all j < i where dp[j] is true and s[j..i-1] is in the dictionary (use a hash set for O(1) lookup).
Complexity: Time O(n² * k) where k = avg word length · Space O(n)
Follow-up: Word Break II (LC #140) — return all valid segmentations using backtracking + memoization.
5. Jump Game II Medium
Find the minimum number of jumps to reach the last index. Each element indicates the maximum jump length.
Input: nums = [2,3,1,1,4]
Output: 2
Input: nums = [2,3,0,1,4]
Output: 2
Approach: Greedy. Track current reach and farthest reachable position. When the pointer reaches the current end, increment jump count and extend the current end to the farthest position seen so far.
Complexity: Time O(n) · Space O(1)
Follow-up: Jump Game (LC #55) — just determine reachability, not minimum jumps.
6. N-Queens Hard
Place n queens on an n×n chessboard such that no two queens attack each other. Return all distinct solutions.
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Input: n = 1
Output: [["Q"]]
Approach: Backtracking row by row. For each row, try each column. A placement is safe if no previous queen shares the column, or either diagonal. Use three boolean sets (cols, diag1 = row-col, diag2 = row+col) for O(1) conflict checking.
Complexity: Time O(n!) · Space O(n)
Follow-up: N-Queens II (LC #52) — count solutions only. How would bit manipulation speed up conflict checks?
Part 2 — Phone Screen Questions
7. Sliding Window Maximum Hard
Return the maximum of each sliding window of size k over an integer array.
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Approach: Monotonic decreasing deque of indices. Remove indices that fall outside the current window. Remove indices from the back whose values are ≤ current (they can never be maximum). Front of deque = current window maximum.
Complexity: Time O(n) · Space O(k)
Follow-up: Constrained Subsequence Sum (LC #1425) — same sliding window maximum DP pattern.
8. Minimum Window Substring Hard
Find the minimum window in s that contains all characters of t (including duplicates).
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Input: s = "a", t = "a"
Output: "a"
Approach: Two-pointer sliding window. Expand right until all t characters are covered. Then shrink left while the window is still valid. Track minimum window length and position.
Complexity: Time O(|s| + |t|) · Space O(|t|)
Follow-up: Find All Anagrams in a String (LC #438) — same sliding window with fixed size.
9. Serialize and Deserialize Binary Tree Hard
Design an algorithm to serialize a binary tree to a string and deserialize it back to the original tree.
serialize([1,2,3,null,null,4,5]) → "1,2,3,null,null,4,5"
deserialize("1,2,3,null,null,4,5") → [1,2,3,null,null,4,5]
Approach: BFS level-order for both. Serialize: enqueue root, output value or "null", enqueue children. Deserialize: split by comma, use a queue of parent nodes, assign left and right children from the values list.
Complexity: Time O(n) · Space O(n)
Follow-up: Serialize and Deserialize BST (LC #449) — more compact encoding using BST property (no nulls needed).
10. Find Median from Data Stream Hard
Design a data structure supporting addNum(num) and findMedian() on a running data stream.
MedianFinder.addNum(1), addNum(2), findMedian()→1.5, addNum(3), findMedian()→2.0
Approach: Two heaps — a max-heap for the lower half and a min-heap for the upper half. After each insertion, rebalance so sizes differ by at most 1. Median is the top of the larger heap (or average of both tops if equal size).
Complexity: Time O(log n) per add · O(1) per findMedian · Space O(n)
Follow-up: Sliding Window Median (LC #480) — maintain the two-heap structure as the window slides, removing the outgoing element.
11. Wildcard Matching Hard
Implement wildcard pattern matching with '?' (matches any single character) and '*' (matches any sequence, including empty).
Input: s = "aab", p = "c*a*b" → false
Input: s = "adceb", p = "*a*b" → true
Input: s = "acdcb", p = "a*c?b" → false
Approach: dp[i][j] = true if s[0..i-1] matches p[0..j-1]. Transitions: if p[j-1]'*', dp[i][j] = dp[i][j-1] (star matches empty) OR dp[i-1][j] (star matches one more char). If p[j-1]'?' or p[j-1]==s[i-1], dp[i][j] = dp[i-1][j-1].
Complexity: Time O(m*n) · Space O(m*n)
Follow-up: Regular Expression Matching (LC #10) — harder because '*' means zero or more of the preceding element, not any sequence.
12. Task Scheduler Medium
Given a list of CPU tasks with a cooldown n (same task must wait n intervals), find the minimum total intervals to complete all tasks.
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A→B→idle→A→B→idle→A→B
Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Approach: Formula: (maxCount - 1) (n + 1) + numTasksWithMaxCount. Also solvable with a max-heap + cooldown queue simulation.
*Complexity: Time O(n) · Space O(1)
Follow-up: Rearrange String k Distance Apart (LC #358) — same idea, physically rearrange the string.
13. Course Schedule II Medium
Return a valid course order given prerequisites (or an empty array if impossible due to a cycle).
Input: numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Input: numCourses=2, prerequisites=[[1,0],[0,1]]
Output: []
Approach: Kahn's BFS topological sort. Build an in-degree array and adjacency list. Enqueue all zero-in-degree nodes. Pop, add to result, reduce neighbours' in-degrees; enqueue newly zero-in-degree nodes. If result size < numCourses, a cycle exists.
Complexity: Time O(V+E) · Space O(V+E)
Follow-up: Parallel Courses (LC #1136) — find the minimum number of semesters (longest path in the DAG).
Part 3 — Onsite Questions
14. Sudoku Solver Hard
Solve a 9×9 Sudoku puzzle by filling in empty cells ('.'). Each digit 1–9 must appear exactly once in each row, column, and 3×3 box.
Input: [["5","3",".",".","7",".",...],...]
Output: [["5","3","4","6","7","8",...],...]
Approach: Backtracking. For each empty cell, try digits 1–9. Check row, column, and 3×3 box validity using three sets. If valid, place the digit and recurse. Backtrack if no digit works.
Complexity: Time O(9^m) where m = empty cells · Space O(m)
Follow-up: Constraint propagation (naked singles, hidden singles) dramatically prunes the search space — explain how.
15. Largest Rectangle in Histogram Hard
Find the area of the largest rectangle that can be formed within a histogram.
Input: heights = [2,1,5,6,2,3]
Output: 10
Input: heights = [2,4]
Output: 4
Approach: Monotonic increasing stack. For each bar, pop the stack when the current bar is shorter than the top. The popped bar is the shortest in a rectangle bounded by the current index and the new stack top. Append a sentinel 0 to flush the stack.
Complexity: Time O(n) · Space O(n)
Follow-up: This is the subroutine used in LC #85 (Maximal Rectangle). Can you explain how they compose?
16. Edit Distance Hard
Find the minimum number of insert, delete, or replace operations to transform word1 into word2.
Input: word1 = "horse", word2 = "ros"
Output: 3
Input: word1 = "intention", word2 = "execution"
Output: 5
Approach: dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1]. If word1[i-1]==word2[j-1], dp[i][j]=dp[i-1][j-1]. Else min(dp[i-1][j]+1 delete, dp[i][j-1]+1 insert, dp[i-1][j-1]+1 replace).
Complexity: Time O(m*n) · Space O(m*n), optimisable to O(n)
Follow-up: One Edit Distance (LC #161) — check if two strings are exactly one edit apart.
17. Decode Ways Medium
Count the number of ways to decode a digit string where 'A'=1, 'B'=2, ..., 'Z'=26.
Input: s = "12"
Output: 2
Explanation: "AB" (1 2) or "L" (12)
Input: s = "226"
Output: 3
Explanation: "BZ" (2 26), "VF" (22 6), "BBF" (2 2 6)
Approach: dp[i] = number of ways to decode s[0..i-1]. Single digit: valid if s[i-1]!='0'. Two digits: valid if s[i-2..i-1] is between "10" and "26". dp[i] += dp[i-1] if single valid, += dp[i-2] if two-digit valid.
Complexity: Time O(n) · Space O(1)
Follow-up: Decode Ways II (LC #639) — '*' can represent any digit 1–9.
18. Gas Station Medium
Given gas[i] at each station and cost[i] to travel to the next, find the starting station index to complete a circular tour (or -1 if impossible).
Input: gas=[1,2,3,4,5], cost=[3,4,5,1,2]
Output: 3
Input: gas=[2,3,4], cost=[3,4,3]
Output: -1
Approach: If total gas < total cost, return -1. Otherwise, a solution always exists. Traverse: track running tank; if tank goes negative, the starting point must be after the current position. Reset tank and update start.
Complexity: Time O(n) · Space O(1)
Follow-up: Prove that the greedy choice of starting after a failure always gives the correct answer.
19. Critical Connections in a Network Hard
Find all critical connections (bridges) — edges whose removal disconnects the graph.
Input: n=4, connections=[[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Approach: Tarjan's bridge-finding algorithm. DFS assigning each node a discovery time and a low value (lowest discovery reachable via back edges in its subtree). Edge (u,v) is a bridge if low[v] > disc[u] — meaning v cannot reach u or any ancestor of u without going through (u,v).
Complexity: Time O(V+E) · Space O(V+E)
Follow-up: Articulation Points — similar algorithm but checks low[v] >= disc[u] for non-root nodes.
20. Reconstruct Itinerary Hard
Given a list of airline tickets [from, to], reconstruct the itinerary in lexicographic order starting from "JFK". All tickets must be used exactly once.
Input: [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Approach: Hierholzer's algorithm for Eulerian path. Build adjacency lists sorted in lexicographic order (min-heap). DFS: for each node, greedily visit the smallest destination. After all outgoing edges are used, prepend the node to the result.
Complexity: Time O(E log E) · Space O(E)
Follow-up: Why does prepending (rather than appending) work here? It reverses the post-order DFS to get the correct forward itinerary.
21. Palindrome Partitioning II Hard
Find the minimum cuts needed so every substring in the partition is a palindrome.
Input: s = "aab"
Output: 1
Explanation: ["aa","b"]
Input: s = "a"
Output: 0
Approach: Precompute isPalindrome[i][j] (expand-around-centre in O(n²)). dp[i] = min cuts for s[0..i]. For each i, if s[0..i] is a palindrome, dp[i]=0. Else dp[i] = min over all j where s[j..i] is palindrome of dp[j-1]+1.
Complexity: Time O(n²) · Space O(n²)
Follow-up: Palindrome Partitioning (LC #131) — enumerate all valid partitions using backtracking.
22. Count Vowels Permutation Hard
Count strings of length n where each vowel follows specific adjacency rules: 'a' must be followed by 'e', 'e' by 'a' or 'i', etc. (full rules in the problem).
Input: n = 1
Output: 5
Input: n = 2
Output: 10
Input: n = 5
Output: 68
Approach: dp[vowel] = count of strings of current length ending in that vowel. Transition matrix derived from rules. At each step compute the next dp array from the current one. Sum all dp values at length n.
Complexity: Time O(n) · Space O(1)
Follow-up: Optimise to O(log n) using matrix exponentiation on the 5×5 transition matrix.
23. Distinct Subsequences Hard
Count the number of distinct ways to form string t as a subsequence of string s.
Input: s = "rabbbit", t = "rabbit"
Output: 3
Input: s = "babgbag", t = "bag"
Output: 5
Approach: dp[i][j] = ways to form t[0..j-1] from s[0..i-1]. If s[i-1]==t[j-1], dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (use or skip). Else dp[i][j] = dp[i-1][j].
Complexity: Time O(m*n) · Space O(m*n), optimisable to O(n)
Follow-up: Interleaving String (LC #97) — two-string DP, similar structure but different recurrence.
24. Expression Add Operators Hard
Insert '+', '-', '*' between digits of a numeric string to make its value equal to target. Return all valid expressions.
Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Approach: Backtracking. Track current expression, evaluated value, and the last multiplicand. On '', backtrack: new value = (current - lastMultiply) + lastMultiply nextNum. Handle leading zeros.
Complexity: Time O(4^n * n) · Space O(n)
Follow-up: Basic Calculator (LC #224) — evaluate an expression string with parentheses.
25. Minimum Cost to Connect All Points Medium
Given points on a 2D plane, find the minimum cost to connect all points. Cost between two points = Manhattan distance.
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Approach: Prim's algorithm. Start from any point, maintain a min-heap of (cost, point). Greedily pick the cheapest unvisited point, update distances to all remaining points. Total cost = sum of picked edge weights.
Complexity: Time O(n² log n) · Space O(n)
Follow-up: Kruskal's approach — generate all O(n²) edges, sort, and apply Union-Find. Which is better for dense graphs?
26. Network Delay Time Medium
Given a directed weighted graph and a source node k, find how long it takes for all nodes to receive a signal. Return -1 if not all nodes receive it.
Input: times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2
Output: 2
Approach: Dijkstra's algorithm from source k. The answer is the maximum shortest-path distance across all nodes. If any node is unreachable (distance = infinity), return -1.
Complexity: Time O(E log V) · Space O(V+E)
Follow-up: Bellman-Ford handles negative weights — explain when you'd use it over Dijkstra.
27. Find All Anagrams in a String Medium
Find all start indices of anagram substrings of p in s.
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Input: s = "abab", p = "ab"
Output: [0,1,2]
Approach: Sliding window of size |p|. Use two frequency arrays. Track a 'matches' counter (how many characters have matching counts). Slide: update the counter when frequencies equalise or diverge.
Complexity: Time O(n) · Space O(1)
Follow-up: Permutation in String (LC #567) — just return true/false (same algorithm).
28. Trapping Rain Water Hard
Calculate the total water that can be trapped after raining given a height map.
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. Maintain leftMax and rightMax. The pointer with the smaller max determines the water level at that position: water = max - height[pointer]. Move that pointer inward.
Complexity: Time O(n) · Space O(1)
Follow-up: Trapping Rain Water II (LC #407) — 3D version using a min-heap priority queue.
29. Merge k Sorted Lists Hard
Merge k sorted linked lists into one sorted linked list.
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Approach: Min-heap of size k. Initialize with each list's head. Pop the minimum, append to result, push that node's next if it exists.
Complexity: Time O(N log k) where N = total nodes · Space O(k)
Follow-up: Divide and conquer approach: pair-wise merge lists using the merge-two-sorted-lists primitive in O(log k) rounds — same asymptotic complexity but avoids heap overhead.
30. Maximum Sum Rectangle in 2D Matrix Hard
Find the submatrix with the maximum sum. This is a direct Samsung OA variant — they provide a 2D grid and ask for the max-sum sub-rectangle.
Input: matrix = [[1,2,-1,-4,-20],[-8,-3,4,2,1],[3,8,10,1,3],[-4,-1,1,7,-6]]
Output: 29
Explanation: (1,1) to (3,3): rows 1-3, cols 1-3.
Approach: Fix left and right column boundaries (O(n²) pairs). Compress each row into a 1D array using column sums. Run Kadane's algorithm on that 1D array to get the max subarray sum for this column pair. Track global max.
Complexity: Time O(n² * m) · Space O(m)
Follow-up: This extends Kadane's algorithm from 1D to 2D — explain how adding the column-fixing step achieves this.
31. Integer to Roman Medium
Convert an integer to a Roman numeral string.
Input: num = 3749
Output: "MMMDCCXLIX"
Approach: Greedy. Define an ordered table of value-symbol pairs (including subtractives like 900="CM", 400="CD"). For each pair, append the symbol as many times as the value fits into num and subtract.
Complexity: Time O(1) (bounded input) · Space O(1)
Follow-up: Roman to Integer (LC #13) — scan left to right, subtract when a smaller value precedes a larger one.
32. Find the Celebrity Medium
A celebrity is someone known by everyone but knows nobody. Using only the knows(a,b) API, find the celebrity in O(n) calls.
knows(0,1)=true, knows(1,0)=false, knows(1,2)=false, knows(0,2)=true → celebrity=1
Approach: Candidate elimination. Start with candidate=0. For each person i, if candidate knows i, update candidate=i. After one pass, verify the candidate: ensure everyone knows them and they know nobody.
Complexity: Time O(n) API calls · Space O(1)
Follow-up: What if there are multiple celebrities (impossible by definition — explain why)?
33. Kth Largest Element in an Array Medium
Find the kth largest element in an unsorted array without fully sorting it.
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: QuickSelect (partition-based). Choose a pivot, partition around it. If pivot index == n-k, return it. Recurse only on the relevant half. Average O(n), worst O(n²) — randomise pivot to fix worst case.
Complexity: Time O(n) average · Space O(1)
Follow-up: Min-heap of size k achieves O(n log k) — when would you prefer it over QuickSelect?
34. Redundant Connection Medium
Return the last edge that, when added to an undirected tree, creates a cycle.
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Approach: Union-Find. Process edges one by one. If both endpoints are already in the same component (find returns the same root), this edge is the redundant one. Otherwise, union the two components.
Complexity: Time O(n * α) · Space O(n)
Follow-up: Redundant Connection II (LC #685) — directed graph variant, harder edge case analysis.
35. Design In-Memory File System (LLD) Hard
Design an in-memory file system supporting: ls (list contents of a path), mkdir (create a directory), addContentToFile (create/append), and readContentFromFile.
FileSystem.mkdir("/a/b/c")
FileSystem.addContentToFile("/a/b/c/d","hello")
FileSystem.ls("/") → ["a"]
FileSystem.ls("/a/b/c") → ["d"]
FileSystem.readContentFromFile("/a/b/c/d") → "hello"
Approach: Trie of TrieNode objects. Each node has: Map<String, TrieNode> children, String content (non-null means it's a file), boolean isFile. ls navigates to the path node — if it's a file, return [name]; if it's a dir, return sorted list of children. mkdir creates nodes along the path. addContentToFile navigates/creates the path and appends to content. Key Design Principles: Unified file/dir node (isFile flag), no separate File/Directory classes, sorted children keys for ls Follow-up: Support delete and move operations. How does the Trie structure simplify these?
36. Design Vending Machine (LLD) Medium
Design a Vending Machine with states: IDLE → HAS_MONEY → ITEM_SELECTED → DISPENSING → CHANGE_RETURNED. Support insertCoin, selectItem, dispenseItem, returnChange, and refund.
vm.insertCoin(10) → "Inserted 10 coins. Total: 10"
vm.selectItem("A1") → "Item A1 selected. Price: 8"
vm.dispenseItem() → "Dispensed A1. Change: 2"
vm.returnChange() → "Returned 2 coins"
Approach: State pattern. VendingMachine holds a currentState reference. Each concrete state (IdleState, HasMoneyState, etc.) implements the full set of operations — most throw InvalidOperationException except the valid ones for that state. State transitions update the machine's currentState. Key Design Principles: State pattern eliminates if-else chains, each state is responsible only for its own transitions, inventory tracked separately from state Follow-up: How would you extend the machine to support multiple currencies (different coin denominations with exchange rates)?
37. Design Traffic Light Controller (LLD) Medium
Design a traffic light system for a four-way intersection. Each direction (North, South, East, West) cycles through RED → GREEN → YELLOW → RED. The controller must support normal timed cycles and an emergency override (all lights turn red immediately).
TrafficLightController.start()
TrafficLightController.emergencyOverride()
TrafficLightController.resume()
TrafficLight.getState() → RED | GREEN | YELLOW
Approach: Classes: TrafficLight (id, currentState, durations map), Intersection (list of TrafficLights), TrafficLightController (scheduler + emergency flag). Controller runs a scheduler that transitions lights on a timer. Observer pattern: VehicleSensor notifies the controller to extend green phase based on traffic density. Emergency override: controller sets all lights to RED and pauses the scheduler. Key Design Principles: State machine per light, Observer for sensor events, Command pattern for override actions Follow-up: How would you coordinate lights across 20 intersections in a city for a green wave (Dijkstra on intersection graph to propagate green signals)?
38. Design Samsung SmartTV Content Recommendation (HLD) Hard
Design the content recommendation system for Samsung SmartTV's home screen. 100M active TVs, each showing a personalised content rail updated daily. Content comes from Netflix, YouTube, Prime, and Samsung TV Plus.
Functional: getRecommendations(deviceId, context) → [ContentItem], recordEvent(deviceId, event)
Non-functional: <200ms latency at TV boot, 100M devices, personalised per device, content from multiple providers
Approach: Write path: TV events (play, pause, finish, skip) → Kafka → Event Processor → Feature Store (device embedding updated incrementally). Batch path: every night, a Recommendation Job runs collaborative filtering on the Feature Store to generate top-500 content items per device, stored in a key-value store (DynamoDB) keyed by deviceId. Read path: TV boots → SmartTV App → Recommendation Service → DynamoDB lookup → CDN-cached content metadata → rendered home screen in <200ms. Cold start (new TV): use region's trending content + genre preferences collected during setup. Content from different providers is unified by a Content Aggregation Service that normalises metadata and applies content-provider rules (parental controls, DRM). Key Concepts: Pre-computed recommendations per device, Feature Store for real-time embedding updates, DynamoDB for low-latency reads, CDN for content metadata, normalised content catalogue Follow-up: How do you handle 100M TVs all booting between 8–9PM (prime time spike)?
39. Design IoT Device Management Platform (HLD) Hard
Design Samsung SmartThings — an IoT platform managing 500M connected devices (TVs, fridges, washing machines, Galaxy phones, smart bulbs). Support device registration, status monitoring, remote command execution, and firmware OTA updates.
Functional: registerDevice(deviceId, type, userId), getDeviceStatus(deviceId), sendCommand(deviceId, command), pushFirmwareUpdate(deviceId, version)
Non-functional: 500M devices, millions of concurrent connections, <1s command delivery, reliable OTA at scale
Approach: Connectivity: MQTT broker (HiveMQ/EMQ) for persistent, low-power device connections. Each device subscribes to a topic like /devices/{deviceId}/commands. Device Registry: metadata in DynamoDB (deviceId, type, userId, firmwareVersion, lastSeen). Status monitoring: devices publish heartbeats every 60s to Kafka → Status Aggregator updates Redis with latest state. Commands: Backend publishes to /devices/{deviceId}/commands topic; MQTT broker delivers within 1s. OTA Firmware: new firmware stored in S3. Firmware Update Service creates update jobs for eligible devices (same firmware family), queues tasks in a Priority Queue. Devices pull the firmware from S3 pre-signed URLs in small chunks with rollback support. Tenancy: each Samsung account has a namespace; commands are authorised against device ownership. Key Concepts: MQTT for IoT persistent connections, Kafka for event streaming, Redis for device state, S3 for firmware blobs, chunked OTA with rollback Follow-up: How do you handle a firmware bug that bricks devices after OTA — what's your rollback strategy at 10M devices?
40. Design Samsung Pay (HLD) Hard
Design Samsung Pay — a mobile payment system supporting NFC tap-to-pay, in-app purchases, and peer-to-peer transfers. 50M active users, 10M transactions/day.
Functional: addCard(userId, cardDetails), pay(userId, merchantId, amount), p2pTransfer(fromUser, toUser, amount), getTransactionHistory(userId)
Non-functional: <500ms NFC payment latency, PCI DSS compliance, idempotent transactions, fraud detection
Approach: Card Storage: card details encrypted with Samsung Knox HSM, tokenised (token stored, not PAN). NFC Payment: phone generates a cryptogram with a one-time token → Merchant POS reads → acquirer sends to network → issuer authorises → response in <500ms. Online payment: Payment Service validates token, calls issuer API (Visa/Mastercard) via a payment gateway, handles 3DS for SCA. Idempotency: each transaction has a clientTransactionId; Payment Service deduplicates using Redis within a 24h TTL. P2P: Saga pattern — debit sender, credit receiver, compensate on failure. Fraud Detection: real-time ML scoring via Kafka stream within 50ms (feature: device fingerprint, location, amount, velocity). Ledger: append-only MySQL + read replicas for history. Regulatory: PCI DSS scoped microservices, all card data in a separate PCI zone. Key Concepts: Tokenisation + HSM for card security, idempotency via Redis, Saga for P2P, real-time fraud ML, PCI DSS scoped architecture Follow-up: How do you handle the payment succeeds on the issuer side but Samsung Pay crashes before saving the result?
41. The Skyline Problem Hard
Return the key points that define the skyline formed by a list of buildings.
Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Approach: Sweep line with a max-heap. Create events: (x, -h) for start, (x, h) for end. Process events sorted by x (tie-break: start before end for same x). Maintain a max-heap of active building heights. When the max height changes, add a key point.
Complexity: Time O(n log n) · Space O(n)
Follow-up: How do you handle buildings that start or end at the same x coordinate? The sort order matters.
42. Count Smaller Numbers After Self Hard
For each element in an array, count how many elements to its right are smaller.
Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Input: nums = [-1,-1]
Output: [0,0]
Approach: Modified merge sort — during the merge phase, when taking an element from the right half over the left half, all remaining left-half elements have a smaller element to their right. Accumulate counts with an index array.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Binary Indexed Tree (Fenwick Tree) approach — compress values, process right to left, query prefix sums.
43. Alien Dictionary Hard
Given a sorted list of words in an alien language, derive the character ordering (or return "" if invalid).
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Input: words = ["z","x","z"]
Output: "" (cycle)
Approach: Compare adjacent words to extract ordering constraints (edges in a directed graph). Run topological sort (Kahn's BFS). If the result doesn't include all characters, a cycle exists — return "".
Complexity: Time O(total chars) · Space O(unique chars)
Follow-up: How do you detect a prefix-pair constraint violation (word A is a prefix of word B but appears after it)?
44. Burst Balloons Hard
Burst balloons to collect coins. Bursting balloon i gives coins nums[i-1]*nums[i]*nums[i+1]. Maximise total coins.
Input: nums = [3,1,5,8]
Output: 167
Explanation: 3*1*5=15, then 3*5*8=120, then 1*3*8=24, then 1*8*1=8 → total 167
Input: nums = [1,5]
Output: 10
Approach: Interval DP. Think in reverse: dp[i][j] = max coins from bursting all balloons in (i,j) with i and j as boundary sentinels (not burst). For each balloon k in (i,j) chosen as the last to burst: dp[i][j] = max(nums[i]nums[k]nums[j] + dp[i][k] + dp[k][j]).
**Complexity: Time O(n³) · Space O(n²)
Follow-up: Strange Printer (LC #664) — same interval DP template with a different state transition.
45. Minimum Number of Refueling Stops Hard
A car starts with startFuel and travels to target. At each gas station it can optionally refuel. Find the minimum refueling stops to reach the target.
Input: target=100, startFuel=10, stations=[[10,60],[20,30],[30,30],[60,40]]
Output: 2
Input: target=100, startFuel=1, stations=[]
Output: -1
Approach: Greedy with a max-heap. Traverse all stations reachable with current fuel, adding their fuel to the heap. When you can't proceed, pop the station with the most fuel from the heap (retroactively refuel there). Increment stop count. If the heap is empty and you can't reach the target, return -1.
Complexity: Time O(n log n) · Space O(n)
Follow-up: Prove why the greedy choice of always picking the largest available fuel is optimal.
46. Concatenated Words Hard
Find all words in the dictionary that can be formed by concatenating two or more shorter words from the same dictionary.
Input: words=["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Approach: Sort by length. For each word, run Word Break dp using only shorter words (already processed) as the dictionary. If dp[len] is true, it's a concatenated word.
Complexity: Time O(n * L³) where L = max word length · Space O(n * L)
Follow-up: Trie-based Word Break is faster in practice — how does it reduce unnecessary dictionary lookups?
47. Maximum Frequency Stack Hard
Design a stack supporting push(x) and pop() where pop returns the most frequent element (ties broken by most recently pushed).
push(5),push(7),push(5),push(7),push(4),push(5)
pop()→5, pop()→7, pop()→5, pop()→4
Approach: Two maps — freq (element → frequency) and group (frequency → stack of elements). maxFreq variable. push: increment freq, push x onto group[freq], update maxFreq. pop: pop from group[maxFreq], decrement freq of that element, if group[maxFreq] becomes empty decrement maxFreq.
Complexity: Time O(1) push and pop · Space O(n)
Follow-up: How does the group map act as a multi-level stack indexed by frequency?
48. Basic Calculator II Medium
Evaluate a string expression with +, -, *, / (integer division). No parentheses, no leading zeros.
Input: s = "3+2*2"
Output: 7
Input: s = " 3/2 "
Output: 1
Input: s = " 3+5 / 2 "
Output: 5
Approach: Scan with a prevOp variable. For + and -, push the number (positive/negative) onto the stack. For and /, pop the stack top, compute with the current number, push result. Sum the stack at the end.
*Complexity: Time O(n) · Space O(n)
Follow-up: Basic Calculator III (LC #772) — adds parentheses; recursive descent or two-stack approach.
49. Design Bixby AI Query Routing System (HLD) Hard
Design Samsung Bixby's query routing system. User speaks a command → voice is transcribed → intent is classified → routed to the correct skill (SmartHome control, Calendar, Navigation, Web Search). 500M devices, <2s end-to-end.
Functional: processQuery(deviceId, audioBlob) → action, registerSkill(skillId, intentPatterns), executeAction(deviceId, action)
Non-functional: <2s E2E, 500M devices, multi-language, extensible skill registry
Approach: Pipeline: Audio → ASR Service (on-device or Samsung cloud) → Text. Text → NLU Service (intent classification + entity extraction using a fine-tuned transformer). Intent → Skill Router (hash map from intent to skill handler). Skill executes → Device Command Service (MQTT to device). Skills: SmartHomeSkill (controls IoT devices via SmartThings API), CalendarSkill, NavigationSkill (calls HERE Maps), FallbackSkill (Bing/Google web search). On-device inference for common intents (SmartHome on/off) for <200ms. Cloud fallback for complex queries. Skill Registry: skills register their intent patterns at startup; Router uses a prefix trie for fast pattern matching. Multi-language: per-language ASR and NLU models, language detected from device locale. Key Concepts: ASR + NLU pipeline, intent-based skill routing, on-device vs cloud hybrid, MQTT for device actuation, skill registry with trie-based pattern matching Follow-up: How do you handle ambiguous intents (e.g., "turn on the light" when there are 10 lights in the home)?
50. Minimum Cost to Make Array Equal Hard
You have an array of integers nums and a cost array. Incrementing or decrementing nums[i] by 1 costs cost[i]. Find the minimum total cost to make all elements equal.
Input: nums = [1,3,5,2], cost = [2,3,1,14]
Output: 8
Input: nums = [2,2,2,2,2], cost = [4,2,8,1,3]
Output: 0
Approach: Binary search on the target value. The cost function is convex (unimodal), so binary search for the valley. For a given target t, compute total cost using prefix sums of cost × position. The optimal target is the weighted median — the value where cumulative weight crosses half of total weight.
Complexity: Time O(n log V) where V = value range · Space O(n)
Follow-up: Minimum Moves to Equal Array Elements II (LC #462) — same problem without weights; optimal target is the median.
Preparation Tips
Samsung SRIB's OA is the hardest filter — practice grid/matrix simulation problems daily for at least two weeks before the assessment. Past OA problems require you to simulate a robot navigating a complex grid with obstacles, portals, and limited battery (multi-constraint BFS). In technical rounds, Samsung uniquely tests OS (memory management, scheduling, virtual memory) and DBMS (B+ trees, isolation levels, deadlocks) alongside DSA. For LLD, the Vending Machine and In-Memory File System are canonical Samsung problems — practice both. For HLD, IoT device management (MQTT, OTA firmware at scale) is specific to Samsung's product lines and rarely asked at other companies — it's a strong differentiator in the SRIB interview.
Join Telegram group to get the latest Samsung SRIB OA questions and connect with candidates currently in the Samsung interview process.