Ngân hàng câu hỏi
Ngân hàng DSA và Coding (C#)
30+ bài coding interview hay gặp với fresher .NET — giải bằng C#, kèm Big O và follow-up.
Cách dùng phần này
Mỗi bài có đề → cách tiếp cận → code C# → Big O → follow-up interviewer hay hỏi. Đừng đọc đáp án trước — tự code 15 phút rồi so sánh.
A. Array
1. Two Sum — LC 1
Đề: Cho int[] nums, int target. Trả về 2 index sao cho nums[i] + nums[j] == target.
Tiếp cận: HashMap lưu value → index. Lúc duyệt, tìm target - nums[i].
public int[] TwoSum(int[] nums, int target) {
var map = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++) {
int need = target - nums[i];
if (map.TryGetValue(need, out int j)) return new[] { j, i };
map[nums[i]] = i;
}
return Array.Empty<int>();
}
Big O: time O(n), space O(n).
Follow-up: nếu mảng đã sorted? → Two pointers, O(1) space.
2. Best Time to Buy and Sell Stock — LC 121
Đề: Mảng giá, mua 1 lần bán 1 lần, max profit.
Tiếp cận: tracking min đã thấy + max profit.
public int MaxProfit(int[] prices) {
int min = int.MaxValue, profit = 0;
foreach (var p in prices) {
min = Math.Min(min, p);
profit = Math.Max(profit, p - min);
}
return profit;
}
Big O: O(n) / O(1).
3. Maximum Subarray (Kadane) — LC 53
Đề: Tìm subarray contiguous có tổng lớn nhất.
public int MaxSubArray(int[] nums) {
int cur = nums[0], best = nums[0];
for (int i = 1; i < nums.Length; i++) {
cur = Math.Max(nums[i], cur + nums[i]);
best = Math.Max(best, cur);
}
return best;
}
Big O: O(n) / O(1).
4. Move Zeroes — LC 283
Đề: Di chuyển tất cả số 0 về cuối, giữ thứ tự số khác. In-place.
public void MoveZeroes(int[] nums) {
int w = 0;
for (int i = 0; i < nums.Length; i++)
if (nums[i] != 0) nums[w++] = nums[i];
while (w < nums.Length) nums[w++] = 0;
}
Big O: O(n) / O(1).
5. Contains Duplicate — LC 217
public bool ContainsDuplicate(int[] nums) {
var set = new HashSet<int>();
foreach (var n in nums)
if (!set.Add(n)) return true;
return false;
}
Big O: O(n) avg / O(n).
Follow-up: nếu hạn chế memory? → sort + check adjacent, O(n log n) / O(1).
6. Rotate Array — LC 189
Đề: Xoay mảng phải k bước, in-place.
Tiếp cận: reverse 3 lần.
public void Rotate(int[] nums, int k) {
k %= nums.Length;
Reverse(nums, 0, nums.Length - 1);
Reverse(nums, 0, k - 1);
Reverse(nums, k, nums.Length - 1);
}
private void Reverse(int[] a, int l, int r) {
while (l < r) { (a[l], a[r]) = (a[r], a[l]); l++; r--; }
}
Big O: O(n) / O(1).
7. Merge Two Sorted Arrays — LC 88
Đề: Merge nums2 vào nums1, nums1 đủ chỗ.
Tiếp cận: ghi từ cuối tránh ghi đè.
public void Merge(int[] a, int m, int[] b, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
a[k--] = (i >= 0 && a[i] > b[j]) ? a[i--] : b[j--];
}
}
Big O: O(m+n) / O(1).
B. String
8. Reverse a String — LC 344
public void ReverseString(char[] s) {
int l = 0, r = s.Length - 1;
while (l < r) { (s[l], s[r]) = (s[r], s[l]); l++; r--; }
}
Big O: O(n) / O(1).
9. Valid Anagram — LC 242
public bool IsAnagram(string s, string t) {
if (s.Length != t.Length) return false;
var cnt = new int[26];
foreach (var c in s) cnt[c - 'a']++;
foreach (var c in t) if (--cnt[c - 'a'] < 0) return false;
return true;
}
Big O: O(n) / O(1) (alphabet cố định).
Follow-up: nếu Unicode? → Dictionary<char, int>.
10. Valid Palindrome — LC 125
Đề: Bỏ qua non-alphanumeric, không phân biệt hoa thường.
public bool IsPalindrome(string s) {
int l = 0, r = s.Length - 1;
while (l < r) {
while (l < r && !char.IsLetterOrDigit(s[l])) l++;
while (l < r && !char.IsLetterOrDigit(s[r])) r--;
if (char.ToLower(s[l]) != char.ToLower(s[r])) return false;
l++; r--;
}
return true;
}
Big O: O(n) / O(1).
11. First Unique Character — LC 387
public int FirstUniqChar(string s) {
var cnt = new int[26];
foreach (var c in s) cnt[c - 'a']++;
for (int i = 0; i < s.Length; i++)
if (cnt[s[i] - 'a'] == 1) return i;
return -1;
}
Big O: O(n) / O(1).
12. Longest Common Prefix — LC 14
public string LongestCommonPrefix(string[] strs) {
if (strs.Length == 0) return "";
var prefix = strs[0];
for (int i = 1; i < strs.Length; i++) {
while (!strs[i].StartsWith(prefix)) {
prefix = prefix[..^1];
if (prefix == "") return "";
}
}
return prefix;
}
Big O: O(S) — S là tổng ký tự.
13. Group Anagrams — LC 49
public IList<IList<string>> GroupAnagrams(string[] strs) {
var map = new Dictionary<string, List<string>>();
foreach (var s in strs) {
var arr = s.ToCharArray();
Array.Sort(arr);
var key = new string(arr);
if (!map.ContainsKey(key)) map[key] = new();
map[key].Add(s);
}
return map.Values.Cast<IList<string>>().ToList();
}
Big O: O(n * k log k) (k = max length).
C. Stack & Queue
14. Valid Parentheses — LC 20
public bool IsValid(string s) {
var st = new Stack<char>();
var pair = new Dictionary<char, char> { {')','('}, {']','['}, {'}','{'} };
foreach (var c in s) {
if (pair.ContainsValue(c)) st.Push(c);
else if (pair.TryGetValue(c, out char open)) {
if (st.Count == 0 || st.Pop() != open) return false;
}
}
return st.Count == 0;
}
Big O: O(n) / O(n).
15. Min Stack — LC 155
Đề: Push/Pop/Top/GetMin đều O(1).
Tiếp cận: 2 stack, hoặc stack lưu pair (value, min-so-far).
public class MinStack {
private readonly Stack<(int val, int min)> _st = new();
public void Push(int x) {
int m = _st.Count == 0 ? x : Math.Min(x, _st.Peek().min);
_st.Push((x, m));
}
public void Pop() => _st.Pop();
public int Top() => _st.Peek().val;
public int GetMin() => _st.Peek().min;
}
16. Implement Queue using Stacks — LC 232
public class MyQueue {
private readonly Stack<int> _in = new(), _out = new();
public void Push(int x) => _in.Push(x);
public int Pop() { Peek(); return _out.Pop(); }
public int Peek() {
if (_out.Count == 0) while (_in.Count > 0) _out.Push(_in.Pop());
return _out.Peek();
}
public bool Empty() => _in.Count == 0 && _out.Count == 0;
}
D. Linked List
public class ListNode {
public int Val;
public ListNode? Next;
public ListNode(int v = 0, ListNode? n = null) { Val = v; Next = n; }
}
17. Reverse Linked List — LC 206
public ListNode? ReverseList(ListNode? head) {
ListNode? prev = null;
var curr = head;
while (curr != null) {
var nxt = curr.Next;
curr.Next = prev;
prev = curr;
curr = nxt;
}
return prev;
}
Big O: O(n) / O(1).
18. Merge Two Sorted Lists — LC 21
public ListNode? MergeTwoLists(ListNode? a, ListNode? b) {
var dummy = new ListNode();
var tail = dummy;
while (a != null && b != null) {
if (a.Val <= b.Val) { tail.Next = a; a = a.Next; }
else { tail.Next = b; b = b.Next; }
tail = tail.Next;
}
tail.Next = a ?? b;
return dummy.Next;
}
19. Linked List Cycle — LC 141
Floyd's tortoise & hare.
public bool HasCycle(ListNode? head) {
var slow = head; var fast = head;
while (fast != null && fast.Next != null) {
slow = slow!.Next;
fast = fast.Next.Next;
if (slow == fast) return true;
}
return false;
}
20. Remove Nth Node From End — LC 19
Tiếp cận: 2 pointers cách nhau N.
public ListNode? RemoveNthFromEnd(ListNode head, int n) {
var dummy = new ListNode(0, head);
var fast = dummy; var slow = dummy;
for (int i = 0; i < n; i++) fast = fast.Next!;
while (fast.Next != null) { fast = fast.Next; slow = slow.Next!; }
slow.Next = slow.Next!.Next;
return dummy.Next;
}
E. Tree (cơ bản)
public class TreeNode {
public int Val;
public TreeNode? Left, Right;
public TreeNode(int v = 0) => Val = v;
}
21. Max Depth of Binary Tree — LC 104
public int MaxDepth(TreeNode? root) =>
root == null ? 0 : 1 + Math.Max(MaxDepth(root.Left), MaxDepth(root.Right));
22. Invert Binary Tree — LC 226
public TreeNode? InvertTree(TreeNode? root) {
if (root == null) return null;
(root.Left, root.Right) = (InvertTree(root.Right), InvertTree(root.Left));
return root;
}
23. Same Tree — LC 100
public bool IsSameTree(TreeNode? a, TreeNode? b) {
if (a == null && b == null) return true;
if (a == null || b == null) return false;
return a.Val == b.Val && IsSameTree(a.Left, b.Left) && IsSameTree(a.Right, b.Right);
}
24. Binary Tree Inorder Traversal — LC 94
public IList<int> InorderTraversal(TreeNode? root) {
var res = new List<int>();
void Go(TreeNode? n) {
if (n == null) return;
Go(n.Left); res.Add(n.Val); Go(n.Right);
}
Go(root);
return res;
}
F. Search & DP cơ bản
25. Binary Search — LC 704
public int Search(int[] nums, int target) {
int l = 0, r = nums.Length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (nums[m] == target) return m;
if (nums[m] < target) l = m + 1; else r = m - 1;
}
return -1;
}
Big O: O(log n).
26. First Bad Version — LC 278
public int FirstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int m = l + (r - l) / 2;
if (IsBadVersion(m)) r = m;
else l = m + 1;
}
return l;
}
27. Climbing Stairs — LC 70
public int ClimbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) (a, b) = (b, a + b);
return b;
}
Big O: O(n) / O(1).
28. Fibonacci — LC 509
public int Fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) (a, b) = (b, a + b);
return b;
}
29. House Robber — LC 198
Đề: chọn tập không kề nhau, tổng lớn nhất.
public int Rob(int[] nums) {
int prev = 0, curr = 0;
foreach (var n in nums) {
(prev, curr) = (curr, Math.Max(curr, prev + n));
}
return curr;
}
G. C# / LINQ scenario
30. Cho List<Order>, tính tổng doanh thu mỗi tháng — LINQ?
var monthly = orders
.GroupBy(o => new { o.Date.Year, o.Date.Month })
.Select(g => new {
g.Key.Year, g.Key.Month,
Total = g.Sum(o => o.Amount)
})
.OrderBy(x => x.Year).ThenBy(x => x.Month)
.ToList();
31. Tìm 3 user có nhiều đơn nhất
var top3 = orders
.GroupBy(o => o.UserId)
.Select(g => new { UserId = g.Key, Count = g.Count() })
.OrderByDescending(x => x.Count)
.Take(3)
.ToList();
32. Cho int[], in ra phần tử xuất hiện nhiều nhất
public int MostFrequent(int[] arr) =>
arr.GroupBy(x => x).OrderByDescending(g => g.Count()).First().Key;
Hoặc dùng Dictionary cho hiệu năng tốt hơn dữ liệu lớn:
public int MostFrequent(int[] arr) {
var d = new Dictionary<int, int>();
foreach (var x in arr) d[x] = d.GetValueOrDefault(x) + 1;
return d.OrderByDescending(kv => kv.Value).First().Key;
}
33. Viết extension method IsNullOrEmpty<T> cho IEnumerable<T>
public static class EnumerableExt {
public static bool IsNullOrEmpty<T>(this IEnumerable<T>? src) =>
src == null || !src.Any();
}
34. Implement Singleton thread-safe
public sealed class Logger {
private static readonly Lazy<Logger> _instance = new(() => new Logger());
public static Logger Instance => _instance.Value;
private Logger() {}
public void Log(string m) {}
}
35. Viết retry async helper
public static async Task<T> RetryAsync<T>(
Func<Task<T>> action, int times = 3, int delayMs = 500) {
for (int i = 0; i < times; i++) {
try { return await action(); }
catch when (i < times - 1) { await Task.Delay(delayMs); }
}
throw new InvalidOperationException();
}
H. Hỏi nhanh phân tích Big O
36. Big O của các thao tác phổ biến
- Truy cập
arr[i]: O(1) List<T>.Addcuối: O(1) amortizedList<T>.Insert(0, x): O(n)Dictionary.TryGetValue: O(1) avg, O(n) worst (collision)HashSet.Contains: O(1) avg- Sort
Array.Sort/OrderBy: O(n log n) - Binary search trên mảng sorted: O(log n)
- BFS/DFS trên đồ thị (V + E): O(V + E)
37. Tại sao QuickSort có thể tệ O(n²)?
Khi pivot luôn là min hoặc max (mảng đã sorted, mọi phần tử bằng nhau). Khắc phục: random pivot, median-of-three.
38. MergeSort có in-place không?
Không. Cần O(n) extra space cho mảng tạm. Nếu cần O(1) → dùng QuickSort hoặc HeapSort.
➡️ Tiếp theo: Câu hỏi HR & Soft skill