Question Banks
Multi-Language Solutions (Python · C++ · Java · Go)
Top 20 interview problems with complete solutions in Python, C++, Java, and Go. Side-by-side comparison for language-specific interviews.
Each problem solved in all 4 languages. Use these for language-specific rounds where the interviewer expects idiomatic code in a particular language.
1. Two Sum
Problem: Return indices of two numbers that add up to target. O(n) required.
Python
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
if target - num in seen:
return [seen[target - num], i]
seen[num] = iC++
#include <unordered_map>
#include <vector>
std::vector<int> twoSum(std::vector<int>& nums, int target) {
std::unordered_map<int, int> seen;
for (int i = 0; i < nums.size(); ++i) {
int complement = target - nums[i];
if (seen.count(complement)) {
return {seen[complement], i};
}
seen[nums[i]] = i;
}
return {};
}Java
import java.util.HashMap;
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) {
return new int[]{seen.get(complement), i};
}
seen.put(nums[i], i);
}
return new int[]{};
}Go
func twoSum(nums []int, target int) []int {
seen := make(map[int]int)
for i, num := range nums {
if j, ok := seen[target-num]; ok {
return []int{j, i}
}
seen[num] = i
}
return nil
}2. Merge Intervals
Python
def merge(intervals):
intervals.sort()
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return mergedC++
std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
std::sort(intervals.begin(), intervals.end());
std::vector<std::vector<int>> merged;
for (auto& iv : intervals) {
if (!merged.empty() && iv[0] <= merged.back()[1]) {
merged.back()[1] = std::max(merged.back()[1], iv[1]);
} else {
merged.push_back(iv);
}
}
return merged;
}Java
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
for (int[] iv : intervals) {
if (!merged.isEmpty() && iv[0] <= merged.get(merged.size()-1)[1]) {
merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], iv[1]);
} else {
merged.add(iv);
}
}
return merged.toArray(new int[0][]);
}Go
func merge(intervals [][]int) [][]int {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
merged := [][]int{intervals[0]}
for _, iv := range intervals[1:] {
last := merged[len(merged)-1]
if iv[0] <= last[1] {
if iv[1] > last[1] { last[1] = iv[1] }
} else {
merged = append(merged, iv)
}
}
return merged
}3. LRU Cache
Python
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.cap = capacity
def get(self, key):
if key not in self.cache: return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache: self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False)C++
class LRUCache {
int cap;
std::list<std::pair<int,int>> dll; // front=most recent
std::unordered_map<int, std::list<std::pair<int,int>>::iterator> map;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
if (!map.count(key)) return -1;
dll.splice(dll.begin(), dll, map[key]);
return map[key]->second;
}
void put(int key, int value) {
if (map.count(key)) {
dll.splice(dll.begin(), dll, map[key]);
map[key]->second = value;
} else {
if (dll.size() == cap) {
map.erase(dll.back().first);
dll.pop_back();
}
dll.emplace_front(key, value);
map[key] = dll.begin();
}
}
};Java
class LRUCache extends LinkedHashMap<Integer, Integer> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}Go
type LRUCache struct {
cap int
list *list.List
m map[int]*list.Element
}
type entry struct { key, val int }
func Constructor(capacity int) LRUCache {
return LRUCache{cap: capacity, list: list.New(), m: make(map[int]*list.Element)}
}
func (c *LRUCache) Get(key int) int {
if el, ok := c.m[key]; ok {
c.list.MoveToFront(el)
return el.Value.(*entry).val
}
return -1
}
func (c *LRUCache) Put(key, value int) {
if el, ok := c.m[key]; ok {
c.list.MoveToFront(el)
el.Value.(*entry).val = value
return
}
if c.list.Len() == c.cap {
back := c.list.Back()
c.list.Remove(back)
delete(c.m, back.Value.(*entry).key)
}
el := c.list.PushFront(&entry{key, value})
c.m[key] = el
}4. 3Sum
Python
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]: continue
lo, hi = i+1, len(nums)-1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0: lo += 1
else: hi -= 1
return resultC++
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> result;
for (int i = 0; i < (int)nums.size()-2; ++i) {
if (i > 0 && nums[i] == nums[i-1]) continue;
int lo = i+1, hi = nums.size()-1;
while (lo < hi) {
int s = nums[i] + nums[lo] + nums[hi];
if (s == 0) {
result.push_back({nums[i], nums[lo], nums[hi]});
while (lo < hi && nums[lo] == nums[lo+1]) lo++;
while (lo < hi && nums[hi] == nums[hi-1]) hi--;
lo++; hi--;
} else if (s < 0) lo++;
else hi--;
}
}
return result;
}Java
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
int lo = i+1, hi = nums.length-1;
while (lo < hi) {
int s = nums[i] + nums[lo] + nums[hi];
if (s == 0) {
result.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
while (lo < hi && nums[lo] == nums[lo+1]) lo++;
while (lo < hi && nums[hi] == nums[hi-1]) hi--;
lo++; hi--;
} else if (s < 0) lo++;
else hi--;
}
}
return result;
}Go
func threeSum(nums []int) [][]int {
sort.Ints(nums)
var result [][]int
for i := 0; i < len(nums)-2; i++ {
if i > 0 && nums[i] == nums[i-1] { continue }
lo, hi := i+1, len(nums)-1
for lo < hi {
s := nums[i] + nums[lo] + nums[hi]
if s == 0 {
result = append(result, []int{nums[i], nums[lo], nums[hi]})
for lo < hi && nums[lo] == nums[lo+1] { lo++ }
for lo < hi && nums[hi] == nums[hi-1] { hi-- }
lo++; hi--
} else if s < 0 { lo++ } else { hi-- }
}
}
return result
}5. Container With Most Water
Python
def max_area(height):
l, r, best = 0, len(height)-1, 0
while l < r:
best = max(best, min(height[l], height[r]) * (r - l))
if height[l] < height[r]: l += 1
else: r -= 1
return bestC++
int maxArea(std::vector<int>& height) {
int l = 0, r = height.size()-1, best = 0;
while (l < r) {
best = std::max(best, std::min(height[l], height[r]) * (r - l));
if (height[l] < height[r]) l++;
else r--;
}
return best;
}Java
public int maxArea(int[] height) {
int l = 0, r = height.length-1, best = 0;
while (l < r) {
best = Math.max(best, Math.min(height[l], height[r]) * (r - l));
if (height[l] < height[r]) l++;
else r--;
}
return best;
}Go
func maxArea(height []int) int {
l, r, best := 0, len(height)-1, 0
for l < r {
h := min(height[l], height[r])
area := h * (r - l)
if area > best { best = area }
if height[l] < height[r] { l++ } else { r-- }
}
return best
}6. Valid Parentheses
Python
def is_valid(s):
stack = []
openers = "([" + chr(123)
closers = ")]" + chr(125)
for c in s:
if c in openers:
stack.append(c)
elif c in closers:
if not stack: return False
if closers.index(c) != openers.index(stack.pop()): return False
return not stackC++
bool isValid(std::string s) {
std::stack<char> st;
for (char c : s) {
if (c == '(') st.push(')');
else if (c == '[') st.push(']');
else if (c == 123) st.push(125); // ASCII for curly braces
else {
if (st.empty() || st.top() != c) return false;
st.pop();
}
}
return st.empty();
}Java
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '[') stack.push(']');
else if (c == 123) stack.push((char)125); // curly braces
else if (stack.isEmpty() || stack.pop() != c) return false;
}
return stack.isEmpty();
}Go
func isValid(s string) bool {
stack := []rune{}
pairs := map[rune]rune{')': '(', ']': '[', 125: 123}
for _, c := range s {
if open, ok := pairs[c]; ok {
if len(stack) == 0 || stack[len(stack)-1] != open { return false }
stack = stack[:len(stack)-1]
} else {
stack = append(stack, c)
}
}
return len(stack) == 0
}7. Largest Rectangle in Histogram
Python
def largest_rectangle(heights):
stack, max_area = [], 0
for i, h in enumerate(heights + [0]):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_areaC++
int largestRectangleArea(std::vector<int>& heights) {
heights.push_back(0);
std::stack<int> st;
int maxArea = 0;
for (int i = 0; i < heights.size(); ++i) {
while (!st.empty() && heights[st.top()] > heights[i]) {
int h = heights[st.top()]; st.pop();
int w = st.empty() ? i : i - st.top() - 1;
maxArea = std::max(maxArea, h * w);
}
st.push(i);
}
return maxArea;
}Java
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int maxArea = 0, n = heights.length;
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!stack.isEmpty() && heights[stack.peek()] > h) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}Go
func largestRectangleArea(heights []int) int {
heights = append(heights, 0)
stack := []int{}
maxArea := 0
for i, h := range heights {
for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
width := i
if len(stack) > 0 { width = i - stack[len(stack)-1] - 1 }
area := heights[top] * width
if area > maxArea { maxArea = area }
}
stack = append(stack, i)
}
return maxArea
}8. Search in Rotated Sorted Array
Python
def search(nums, target):
lo, hi = 0, len(nums)-1
while lo <= hi:
mid = (lo+hi)//2
if nums[mid] == target: return mid
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]: hi = mid-1
else: lo = mid+1
else:
if nums[mid] < target <= nums[hi]: lo = mid+1
else: hi = mid-1
return -1C++
int search(std::vector<int>& nums, int target) {
int lo = 0, hi = nums.size()-1;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) {
if (nums[lo] <= target && target < nums[mid]) hi = mid-1;
else lo = mid+1;
} else {
if (nums[mid] < target && target <= nums[hi]) lo = mid+1;
else hi = mid-1;
}
}
return -1;
}Java
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length-1;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) {
if (nums[lo] <= target && target < nums[mid]) hi = mid-1;
else lo = mid+1;
} else {
if (nums[mid] < target && target <= nums[hi]) lo = mid+1;
else hi = mid-1;
}
}
return -1;
}Go
func search(nums []int, target int) int {
lo, hi := 0, len(nums)-1
for lo <= hi {
mid := lo + (hi-lo)/2
if nums[mid] == target { return mid }
if nums[lo] <= nums[mid] {
if nums[lo] <= target && target < nums[mid] { hi = mid-1 } else { lo = mid+1 }
} else {
if nums[mid] < target && target <= nums[hi] { lo = mid+1 } else { hi = mid-1 }
}
}
return -1
}9. Reverse Linked List
Python
def reverse_list(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
return prevC++
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
while (head) {
ListNode* nxt = head->next;
head->next = prev;
prev = head;
head = nxt;
}
return prev;
}Java
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode nxt = head.next;
head.next = prev;
prev = head;
head = nxt;
}
return prev;
}Go
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
nxt := head.Next
head.Next = prev
prev = head
head = nxt
}
return prev
}10. Lowest Common Ancestor of BST
Python
def lca(root, p, q):
while root:
if p.val < root.val and q.val < root.val: root = root.left
elif p.val > root.val and q.val > root.val: root = root.right
else: return rootC++
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while (root) {
if (p->val < root->val && q->val < root->val) root = root->left;
else if (p->val > root->val && q->val > root->val) root = root->right;
else return root;
}
return nullptr;
}Java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (p.val < root.val && q.val < root.val) root = root.left;
else if (p.val > root.val && q.val > root.val) root = root.right;
else return root;
}
return null;
}Go
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
for root != nil {
if p.Val < root.Val && q.Val < root.Val { root = root.Left }
else if p.Val > root.Val && q.Val > root.Val { root = root.Right }
else { return root }
}
return nil
}11. Coin Change
Python
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1C++
int coinChange(std::vector<int>& coins, int amount) {
std::vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int coin : coins)
for (int x = coin; x <= amount; ++x)
if (dp[x - coin] != INT_MAX)
dp[x] = std::min(dp[x], dp[x - coin] + 1);
return dp[amount] == INT_MAX ? -1 : dp[amount];
}Java
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins)
for (int x = coin; x <= amount; x++)
dp[x] = Math.min(dp[x], dp[x - coin] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}Go
func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
for i := range dp { dp[i] = amount + 1 }
dp[0] = 0
for _, coin := range coins {
for x := coin; x <= amount; x++ {
if dp[x-coin]+1 < dp[x] { dp[x] = dp[x-coin] + 1 }
}
}
if dp[amount] > amount { return -1 }
return dp[amount]
}12. Dijkstra's Shortest Path
Python
import heapq
def dijkstra(graph, src, n):
dist = [float('inf')] * n
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return distC++
std::vector<int> dijkstra(std::vector<std::vector<std::pair<int,int>>>& graph, int src) {
int n = graph.size();
std::vector<int> dist(n, INT_MAX);
dist[src] = 0;
std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>, std::greater<>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : graph[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}Java
public int[] dijkstra(List<List<int[]>> graph, int src) {
int n = graph.size();
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, src});
while (!pq.isEmpty()) {
int[] top = pq.poll();
int d = top[0], u = top[1];
if (d > dist[u]) continue;
for (int[] edge : graph.get(u)) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}
}
}
return dist;
}Go
type Edge struct { to, weight int }
type Item struct { dist, node int }
type MinHeap []Item
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() interface{} {
old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x
}
func dijkstra(graph [][]Edge, src int) []int {
n := len(graph)
dist := make([]int, n)
for i := range dist { dist[i] = math.MaxInt }
dist[src] = 0
h := &MinHeap{Item{0, src}}
heap.Init(h)
for h.Len() > 0 {
item := heap.Pop(h).(Item)
if item.dist > dist[item.node] { continue }
for _, e := range graph[item.node] {
if dist[item.node]+e.weight < dist[e.to] {
dist[e.to] = dist[item.node] + e.weight
heap.Push(h, Item{dist[e.to], e.to})
}
}
}
return dist
}Problems 13–20 (Task Scheduler, N-Queens, Rotting Oranges, Edit Distance, Top K Frequent, Word Break, Longest Consecutive, Median from Stream) follow the same pattern see the DSA Advanced page for Python solutions. C++/Java/Go translations follow identical logic with language-specific idioms shown above.
Language Comparison: Key Idioms
| Concept | Python | C++ | Java | Go |
|---|---|---|---|---|
| HashMap | dict / Counter | unordered_map | HashMap | map[K]V |
| Min Heap | heapq | priority_queue + greater | PriorityQueue | container/heap |
| Sort | list.sort() / sorted() | std::sort | Arrays.sort / Collections.sort | sort.Slice |
| Stack | list (append/pop) | std::stack | Deque (ArrayDeque) | slice (append/slice) |
| Linked List | class Node | struct ListNode* | class ListNode | type ListNode struct |
| Queue (BFS) | deque | std::queue | LinkedList / ArrayDeque | slice (shift via [1:]) |
| Set | set() | unordered_set | HashSet | map[T]struct{} |
| Integer max | float('inf') | INT_MAX | Integer.MAX_VALUE | math.MaxInt |