Interview Q&A

rray.Fill(dp, 1);

int maxLen = 1;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (nums[i] > nums[j])
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
maxLen = Math.Max(maxLen, dp[i]);
}
return maxLen;
}

Explanation:

For each element, find LIS ending there by checking previous smaller elements.

Follow on:

public int FindMissingNumber(int[] nums, int n) {
int xor = 0;
for (int i = 1; i <= n; i++) {
xor ^= i;
}
foreach (int num in nums) {
xor ^= num;
}
return xor;
}

Follow on:

Explanation:

XOR all numbers from 1 to n and XOR all elements in array; duplicates cancel out, leaving

missing number.

public int MaximumTotal(IList<IList<int>> triangle) {
int n = triangle.Count;
int[] dp = new int[n];
for (int i = 0; i < n; i++) dp[i] = triangle[n - 1][i];
for (int layer = n - 2; layer >= 0; layer--) {
for (int i = 0; i <= layer; i++) {
dp[i] = triangle[layer][i] + Math.Max(dp[i], dp[i + 1]);
}
}
return dp[0];
}

Explanation:

Start from bottom row, keep updating max path sums up to the top.

public bool IsPerfectSquare(int num) {
if (num < 0) return false;
int left = 0, right = num;

while (left <= right) {

int mid = left + (right - left) / 2;
long sq = (long)mid * mid;
if (sq == num) return true;
else if (sq < num) left = mid + 1;
else right = mid - 1;
}
return false;
}

Explanation:

Binary search for integer square root and check if square equals num.

public int CountPartitions(int[] nums) {
int sum = 0;
foreach (int num in nums) sum += num;
if (sum % 2 != 0) return 0;
int target = sum / 2;
int[] dp = new int[target + 1];
dp[0] = 1;

Follow on:

foreach (int num in nums) {
for (int j = target; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[target];
}

Explanation:

Classic subset sum DP. dp[j] = ways to get sum j. Counting subsets summing to half the

total.

int LongestPalindromeSubseq(string s) {
int n = s.Length;
int[,] dp = new int[n, n];
for (int i = n - 1; i >= 0; i--) {
dp[i, i] = 1;
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j])

Follow on:

dp[i, j] = dp[i + 1, j - 1] + 2;

else

dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j - 1]);
}
}
return dp[0, n - 1];
}

List<List<int>> TarjanSCC(Dictionary<int, List<int>> graph) {
int time = 0;
var stack = new Stack<int>();
var onStack = new HashSet<int>();
var low = new Dictionary<int, int>();
var disc = new Dictionary<int, int>();
var visited = new HashSet<int>();
var sccList = new List<List<int>>();

void DFS(int u) {

disc[u] = time;

Follow on:

low[u] = time;

time++;

stack.Push(u);

onStack.Add(u);

visited.Add(u);

foreach (var v in graph[u]) {
if (!disc.ContainsKey(v)) {

DFS(v);

low[u] = Math.Min(low[u], low[v]);

} else if (onStack.Contains(v)) {

low[u] = Math.Min(low[u], disc[v]);
}
}
if (low[u] == disc[u]) {
var scc = new List<int>();
int w;

do {

w = stack.Pop();

onStack.Remove(w);

scc.Add(w);

} while (w != u);

sccList.Add(scc);

}
}
foreach (var node in graph.Keys) {
if (!disc.ContainsKey(node))

DFS(node);

}
return sccList;
}

Explanation:

Tarjan's algorithm finds SCCs using low-link values and DFS stack.

Follow on:

bool IsIdentical(TreeNode p, TreeNode q) {

if (p == null && q == null) return true;
if (p == null || q == null) return false;
if (p.val != q.val) return false;
return IsIdentical(p.left, q.left) && IsIdentical(p.right,

q.right);

}

Explanation:

Recursive check values and structure for equality.

element in constant time

public class MinStack {
private Stack<int> stack = new Stack<int>();
private Stack<int> minStack = new Stack<int>();

Follow on:

public void Push(int x) {

stack.Push(x);

if (minStack.Count == 0 || x <= minStack.Peek())

minStack.Push(x);

}
public void Pop() {
if (stack.Peek() == minStack.Peek())

minStack.Pop();

stack.Pop();

}
public int Top() {
return stack.Peek();
}
public int GetMin() {
return minStack.Peek();
}
}

Explanation:

Use two stacks: one normal stack, one for minimum values. When pushing a smaller or

equal value, push it on minStack; when popping, pop minStack if needed.

Answer: headB : a.next; b = (b == null) ? headA : b.next; return a; // either intersection or null Explanation: Two pointers traverse both lists; if no intersection, both will reach null simultaneously.

What interviewers expect

• A clear definition tied to Coding in C# Coding Interview projects
• Trade-offs (performance, maintainability, security, cost)
• When you would and would not use it in production

Real-world example

In a production C# Coding Interview application, teams apply this when handling user-facing features or integration boundaries. For example, you might use it during a sprint where reliability and observability matter—logging metrics, validating edge cases, and documenting the decision in an ADR so future developers understand why the approach was chosen.

How to explain in the interview

1. Define the concept in one or two sentences.
2. Context — where it fits in C# Coding Interview architecture.
3. Example — a specific project, bug, or performance win.
4. Trade-off — what you gain vs what you sacrifice.

Tip: Practice aloud on Toolliyo mock interview or the Interview Q&A section before your real interview.

String
Dictionary<char, int> CountCharacters(string s)
{
var dict = new Dictionary<char, int>();
foreach (char c in s)
{
if (dict.ContainsKey(c))

dict[c]++;

else

dict[c] = 1;
}
return dict;
}

Explanation:

Simple frequency map using Dictionary.

List<List<string>> SolveNQueens(int n)
{
List<List<string>> results = new List<List<string>>();
int[] board = new int[n]; // board[i] = column position of queen

in row i

Solve(0, board, results, n);

return results;
}

void Solve(int row, int[] board, List<List<string>> results, int n)

{
if (row == n)
{

results.Add(GenerateBoard(board, n));

return;
}
for (int col = 0; col < n; col++)
{
if (IsSafe(row, col, board))
{
board[row] = col;

Solve(row + 1, board, results, n);

}
}
}

bool IsSafe(int row, int col, int[] board)

{
for (int i = 0; i < row; i++)

Follow on:

{
if (board[i] == col || Math.Abs(board[i] - col) ==

Math.Abs(i - row))

return false;
}
return true;
}
List<string> GenerateBoard(int[] board, int n)
{
List<string> res = new List<string>();
for (int i = 0; i < n; i++)
{
char[] row = new char[n];
for (int j = 0; j < n; j++)
row[j] = '.';
row[board[i]] = 'Q';

res.Add(new string(row));

}
return res;
}

Explanation:

Backtracking places queens row by row while checking columns and diagonals.

Eratosthenes)

List<int> GeneratePrimes(int n)
{
bool[] isPrime = new bool[n + 1];
for (int i = 2; i <= n; i++) isPrime[i] = true;
for (int i = 2; i * i <= n; i++)
{
if (isPrime[i])
{
for (int j = i * i; j <= n; j += i)
isPrime[j] = false;
}
}
List<int> primes = new List<int>();
for (int i = 2; i <= n; i++)
{
if (isPrime[i]) primes.Add(i);
}
return primes;
}

Explanation:

Mark multiples of each prime as non-prime starting from its square.

Follow on:

int FindPeakElement(int[] nums)
{
int left = 0, right = nums.Length - 1;

while (left < right)

{
int mid = (left + right) / 2;
if (nums[mid] > nums[mid + 1])
right = mid;

else

left = mid + 1;
}
return left;
}

Explanation:

Binary search comparing mid element with right neighbor to find peak.

int LIS(int[] nums)

int n = nums.Length;

int[] dp = new int[n];

Array.Fill(dp, 1);

int maxLen = 1;

for (int i = 1; i < n; i++)

for (int j = 0; j < i; j++)

if (nums[i] > nums[j])

dp[i] = Math.Max(dp[i], dp[j] + 1);

maxLen = Math.Max(maxLen, dp[i]);

return maxLen;

Explanation:

For each element, find LIS ending there by checking previous smaller elements.

Follow on:

Logic

• Track highest and second highest in one loop.

int[] arr = { 10, 5, 20, 8 };
int first = int.MinValue, second = int.MinValue;
foreach (int num in arr)
{
if (num > first)
{
second = first;
first = num;
}

else if (num > second && num != first)

{
second = num;
}
}

Answer: ^= b; b ^= a; ^= b; } } Explanation: XOR swap algorithm exchanges values without extra storage. (Check a != b to avoid zeroing when both are same.)

What interviewers expect

• A clear definition tied to Coding in C# Coding Interview projects
• Trade-offs (performance, maintainability, security, cost)
• When you would and would not use it in production

Real-world example

In a production C# Coding Interview application, teams apply this when handling user-facing features or integration boundaries. For example, you might use it during a sprint where reliability and observability matter—logging metrics, validating edge cases, and documenting the decision in an ADR so future developers understand why the approach was chosen.

How to explain in the interview

1. Define the concept in one or two sentences.
2. Context — where it fits in C# Coding Interview architecture.
3. Example — a specific project, bug, or performance win.
4. Trade-off — what you gain vs what you sacrifice.

Tip: Practice aloud on Toolliyo mock interview or the Interview Q&A section before your real interview.

Answer: = temp; } return a; } public int LCM(int a, int b) { return (a / GCD(a, b)) * b; } Explanation: GCD uses Euclidean algorithm. LCM calculated via LCM(a,b) = (a*b)/GCD(a,b).

What interviewers expect

• A clear definition tied to Coding in C# Coding Interview projects
• Trade-offs (performance, maintainability, security, cost)
• When you would and would not use it in production

Real-world example

In a production C# Coding Interview application, teams apply this when handling user-facing features or integration boundaries. For example, you might use it during a sprint where reliability and observability matter—logging metrics, validating edge cases, and documenting the decision in an ADR so future developers understand why the approach was chosen.

How to explain in the interview

1. Define the concept in one or two sentences.
2. Context — where it fits in C# Coding Interview architecture.
3. Example — a specific project, bug, or performance win.
4. Trade-off — what you gain vs what you sacrifice.

Tip: Practice aloud on Toolliyo mock interview or the Interview Q&A section before your real interview.

Answer: public void Swap(ref int a, ref int b) { if (a != b) { a ^= b; b ^= a; a ^= b; Explanation: XOR swap algorithm exchanges values without extra storage. (Check a != b to avoid zeroing when both are same.)

What interviewers expect

• A clear definition tied to Coding in C# Coding Interview projects
• Trade-offs (performance, maintainability, security, cost)
• When you would and would not use it in production

Real-world example

In a production C# Coding Interview application, teams apply this when handling user-facing features or integration boundaries. For example, you might use it during a sprint where reliability and observability matter—logging metrics, validating edge cases, and documenting the decision in an ADR so future developers understand why the approach was chosen.

How to explain in the interview

1. Define the concept in one or two sentences.
2. Context — where it fits in C# Coding Interview architecture.
3. Example — a specific project, bug, or performance win.
4. Trade-off — what you gain vs what you sacrifice.

Tip: Practice aloud on Toolliyo mock interview or the Interview Q&A section before your real interview.

public int FindCelebrity(int n, Func<int, int, bool> knows) {
int candidate = 0;
for (int i = 1; i < n; i++) {
if (knows(candidate, i)) candidate = i;
}
for (int i = 0; i < n; i++) {
if (i != candidate && (knows(candidate, i) || !knows(i,

candidate)))

return -1;
}
return candidate;
}

Explanation:

First find candidate by elimination, then verify candidate.

Follow on:

public int GCD(int a, int b) {

Follow on:

while (b != 0) {

int temp = b;

b = a % b;

a = temp;

return a;

public int LCM(int a, int b) {

return (a / GCD(a, b)) * b;

Explanation:

GCD uses Euclidean algorithm. LCM calculated via LCM(a,b) = (a*b)/GCD(a,b).

Answer: ppears twice except one public int SingleNumber(int[] nums) { int result = 0; foreach (var num in nums) { result ^= num; } return result; } Explanation: XOR of all elements cancels duplicates, leaving the single unique element.

What interviewers expect

• A clear definition tied to Coding in C# Coding Interview projects
• Trade-offs (performance, maintainability, security, cost)
• When you would and would not use it in production

Real-world example

In a production C# Coding Interview application, teams apply this when handling user-facing features or integration boundaries. For example, you might use it during a sprint where reliability and observability matter—logging metrics, validating edge cases, and documenting the decision in an ADR so future developers understand why the approach was chosen.

How to explain in the interview

1. Define the concept in one or two sentences.
2. Context — where it fits in C# Coding Interview architecture.
3. Example — a specific project, bug, or performance win.
4. Trade-off — what you gain vs what you sacrifice.

Tip: Practice aloud on Toolliyo mock interview or the Interview Q&A section before your real interview.

int MinPathSum(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
for (int i = 1; i < m; i++) grid[i][0] += grid[i - 1][0];
for (int j = 1; j < n; j++) grid[0][j] += grid[0][j - 1];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] += Math.Min(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[m - 1][n - 1];
}

int[] Dijkstra(Dictionary<int, List<(int neighbor, int weight)>>

graph, int source, int vertices) {

int[] dist = new int[vertices];
for (int i = 0; i < vertices; i++) dist[i] = int.MaxValue;
dist[source] = 0;
var pq = new SortedSet<(int dist, int node)>();

pq.Add((0, source));

while (pq.Count > 0) {

var current = pq.Min;

pq.Remove(current);

int u = current.node;
foreach (var (v, w) in graph[u]) {
if (dist[u] + w < dist[v]) {
if (dist[v] != int.MaxValue)

pq.Remove((dist[v], v));

dist[v] = dist[u] + w;

pq.Add((dist[v], v));

}
}
}
return dist;
}

Explanation:

Uses a priority queue to pick node with min dist; relax edges.

TreeNode LCA(TreeNode root, int n1, int n2) {

if (root == null) return null;
if (root.val == n1 || root.val == n2) return root;
TreeNode left = LCA(root.left, n1, n2);

Follow on:

TreeNode right = LCA(root.right, n1, n2);
if (left != null && right != null) return root;
return left ?? right;
}
int FindLevel(TreeNode root, int val, int level) {
if (root == null) return -1;
if (root.val == val) return level;
int left = FindLevel(root.left, val, level + 1);
if (left != -1) return left;
return FindLevel(root.right, val, level + 1);
}
int DistanceBetweenNodes(TreeNode root, int n1, int n2) {
TreeNode lca = LCA(root, n1, n2);
int d1 = FindLevel(lca, n1, 0);
int d2 = FindLevel(lca, n2, 0);
return d1 + d2;
}

Explanation:

Find Lowest Common Ancestor (LCA) then sum distances from LCA to each node.