ItTechGenie-Subject - DSA with C# (Warm-up + 10 Questions) ItTechGenie

0

Warm‑up: Choose the Right Data Structure + Big‑O (with answer)

Big‑OHashSetDictionaryLinkedListLRU patternWarm-up

Warm‑up (with answer): Given operations from an "Order-Search" screen, choose the best data structure and explain time complexity. Operations: 1) Add orderId 2) Check if orderId exists 3) Retrieve most-recent N orderIds quickly 4) Remove an orderId ✅ Warm-up answer covers: HashSet/Dictionary for existence, LinkedList/Queue/Stack for recency, and typical Big‑O reasoning.

Sample Input (student: edit/replace with your own complex input)

✅ Sample input includes spaces, quotes, unicode α/β, emoji ✅, and special chars to test parsing and edge cases.

DSA scenario (students implement ONLY TODO methods) Ctrl+C

using System;                                                     // Console
using System.Collections.Generic;                                    // HashSet, LinkedList

namespace ItTechGenie.M1.DSA.WarmUp
{
    public static class Warmup
    {
        // ✅ Warm-up TODO: Student must implement only this method
        public static void ChooseDsAndExplain()
        {
            // TODO:
            // - Write short explanation in Console about:
            //   a) HashSet<string> for Exists / Remove (avg O(1))
            //   b) LinkedList<string> to keep recency (O(1) add to front, O(1) remove if node known)
            //   c) Combine with Dictionary<string, LinkedListNode<string>> for O(1) remove in LRU style
            throw new NotImplementedException();
        }
    }

    internal class Program
    {
        static void Main()
        {
            Warmup.ChooseDsAndExplain();                               // prints explanation
        }
    }
}

Warm‑up Answer (Reasoning + Big‑O)

Best practical combination: - For fast existence & delete: HashSet<string> or Dictionary<string, ...> (average O(1)). - For "most recent N": LinkedList<string> (add to front O(1); take first N by traversal). - For remove by id in O(1): Dictionary<string, LinkedListNode<string>> + LinkedList (classic LRU pattern). Complexities (average): - Add: O(1) - Exists: O(1) - Get recent N: O(N) to read N nodes - Remove: O(1) if you have node reference; otherwise O(N) to search list.

// One valid printed explanation:
Console.WriteLine("Use Dictionary<string, LinkedListNode<string>> + LinkedList<string> (LRU pattern).");
Console.WriteLine("Exists/Remove/Move-to-front are avg O(1), get recent N is O(N).");

1

Two Sum Detector — Dictionary (Hash Map)

ArraysHash MapTwo SumModerate

Scenario: You process a list of transaction amounts and must detect if any pair sums to a target. Amounts may be negative and can repeat. Implement: - TwoSumSolver.FindPairIndices(int[] amounts, int target) -> (i,j) or (-1,-1) Rules: - Return first pair found scanning left-to-right (stable) - Use O(n) average time using dictionary - Handle duplicates correctly ✅ Students implement ONLY the TODO method.

Sample Input (student: edit/replace with your own complex input)

✅ Sample input includes spaces, quotes, unicode α/β, emoji ✅, and special chars to test parsing and edge cases.

DSA scenario (students implement ONLY TODO methods) Ctrl+C

using System;                                                     // Console
using System.Collections.Generic;                                    // Dictionary

namespace ItTechGenie.M1.DSA.Q1
{
    public static class TwoSumSolver
    {
        // ✅ TODO: Student must implement only this method
        public static (int i, int j) FindPairIndices(int[] amounts, int target)
        {
            // TODO:
            // - dictionary: value -> index
            // - for each index i:
            //   need = target - amounts[i]
            //   if need exists => return (storedIndex, i)
            //   else store amounts[i] if not already stored (to keep first occurrence)
            throw new NotImplementedException();
        }
    }

    internal class Program
    {
        static void Main()
        {
            int[] amounts = { 12, -3, 7, 7, 15, 0, 5 };                // sample amounts
            int target = 14;                                           // target sum

            var pair = TwoSumSolver.FindPairIndices(amounts, target);  // compute
            Console.WriteLine($"{pair.i},{pair.j}");                   // sample output
        }
    }
}

Answer (Logic + Code)

Approach (O(n) average): Maintain a dictionary of amount -> first index where it appeared. Scan i from 0..n-1: - need = target - amounts[i] - if need is already in dictionary, you've found the earliest pair for this scan. - otherwise store amounts[i] only if not present (keeps earliest index for duplicates).

public static (int i, int j) FindPairIndices(int[] amounts, int target)
{
    var seen = new Dictionary<int, int>();                            // amount -> first index
    for (int i = 0; i < amounts.Length; i++)                          // scan left-to-right
    {
        int need = target - amounts[i];                               // complement
        if (seen.TryGetValue(need, out int j))                        // found earlier complement
            return (j, i);                                            // return stable pair

        if (!seen.ContainsKey(amounts[i]))                            // store first occurrence only
            seen[amounts[i]] = i;                                     // remember index
    }
    return (-1, -1);                                                  // not found
}

2

Balanced Brackets Validator — Stack

StringsStackParsingModerate

Scenario: A templating engine receives strings containing (), {}, [] and must validate balanced brackets. Ignore all non-bracket characters (letters, spaces, emoji). Implement: - BracketValidator.IsValid(string text) -> bool Rules: - Use Stack<char> - ')' matches '(' etc. - Return true only if fully balanced ✅ Students implement ONLY the TODO method.

Sample Input (student: edit/replace with your own complex input)

✅ Sample input includes spaces, quotes, unicode α/β, emoji ✅, and special chars to test parsing and edge cases.

DSA scenario (students implement ONLY TODO methods) Ctrl+C

using System;                                                     // Console
using System.Collections.Generic;                                    // Stack

namespace ItTechGenie.M1.DSA.Q2
{
    public static class BracketValidator
    {
        // ✅ TODO: Student must implement only this method
        public static bool IsValid(string text)
        {
            // TODO:
            // - create stack
            // - push opening brackets
            // - when closing bracket appears:
            //   - if stack empty => false
            //   - pop and verify matching pair
            // - ignore other characters
            // - at end, stack must be empty
            throw new NotImplementedException();
        }
    }

    internal class Program
    {
        static void Main()
        {
            Console.WriteLine(BracketValidator.IsValid("Hello (World ✅) {items:[1,2,(3)]}"));
            Console.WriteLine(BracketValidator.IsValid("Bad ( [ ) ] !@#"));
        }
    }
}

Answer (Logic + Code)

Use a stack: push openings, pop on closings, validate pairs, ignore others, stack must end empty.

public static bool IsValid(string text)
{
    var st = new Stack<char>();                                       // holds openings
    foreach (char ch in text)                                         // scan chars
    {
        if (ch is '(' or '{' or '[')                                  // opening
            st.Push(ch);                                              // push
        else if (ch is ')' or '}' or ']')                             // closing
        {
            if (st.Count == 0) return false;                          // nothing to match
            char open = st.Pop();                                     // last opening
            if ((ch == ')' && open != '(') ||
                (ch == '}' && open != '{') ||
                (ch == ']' && open != '['))
                return false;                                         // mismatch
        }
    }
    return st.Count == 0;                                             // all matched
}

3

Max Sum in K‑Window — Sliding Window

ArraysTwo pointersSliding windowModerate

Scenario: You receive per-minute CPU usage values and must find the maximum sum in any window of size K. Implement: - WindowAnalytics.MaxWindowSum(int[] values, int k) -> int Rules: - Use sliding window O(n) - Validate k (1..n) - Works with negative numbers too ✅ Students implement ONLY the TODO method.

Sample Input (student: edit/replace with your own complex input)

✅ Sample input includes spaces, quotes, unicode α/β, emoji ✅, and special chars to test parsing and edge cases.

DSA scenario (students implement ONLY TODO methods) Ctrl+C

using System;                                                     // Console

namespace ItTechGenie.M1.DSA.Q3
{
    public static class WindowAnalytics
    {
        // ✅ TODO: Student must implement only this method
        public static int MaxWindowSum(int[] values, int k)
        {
            // TODO:
            // - validate inputs
            // - compute initial window sum (0..k-1)
            // - slide: add values[i], remove values[i-k]
            // - track max
            throw new NotImplementedException();
        }
    }

    internal class Program
    {
        static void Main()
        {
            int[] v = { 5, -2, 3, 10, -1, 4, 2 };
            Console.WriteLine(WindowAnalytics.MaxWindowSum(v, 3));
        }
    }
}

Answer (Logic + Code)

Sliding window: keep running sum for last k items and update max; O(n).

public static int MaxWindowSum(int[] values, int k)
{
    if (values == null) throw new ArgumentNullException(nameof(values));
    if (k <= 0 || k > values.Length) throw new ArgumentOutOfRangeException(nameof(k));

    int sum = 0;                                                      // current window sum
    for (int i = 0; i < k; i++) sum += values[i];                     // initial sum
    int max = sum;                                                    // best so far

    for (int i = k; i < values.Length; i++)                           // slide window
    {
        sum += values[i];                                             // add new element
        sum -= values[i - k];                                         // remove old element
        if (sum > max) max = sum;                                     // update best
    }
    return max;
}

4

Merge Two Sorted Arrays — Two Pointers

ArraysMergingTwo pointersModerate

Scenario: A reporting module receives two sorted lists of order amounts and must merge them into a single sorted list. Implement: - MergeUtil.MergeSorted(int[] a, int[] b) -> int[] Rules: - Use two pointers (i,j) - Stable merge - O(n+m) ✅ Students implement ONLY the TODO method.

Sample Input (student: edit/replace with your own complex input)

✅ Sample input includes spaces, quotes, unicode α/β, emoji ✅, and special chars to test parsing and edge cases.

DSA scenario (students implement ONLY TODO methods) Ctrl+C

using System;                                                     // Console

namespace ItTechGenie.M1.DSA.Q4
{
    public static class MergeUtil
    {
        // ✅ TODO: Student must implement only this method
        public static int[] MergeSorted(int[] a, int[] b)
        {
            // TODO:
            // - allocate result length a+b
            // - use i, j, k pointers
            // - copy remaining items
            throw new NotImplementedException();
        }
    }

    internal class Program
    {
        static void Main()
        {
            int[] a = { -3, 0, 7, 7, 15 };
            int[] b = { -2, 7, 10, 20 };
            var m = MergeUtil.MergeSorted(a, b);
            Console.WriteLine(string.Join(", ", m));
        }
    }
}

Answer (Logic + Code)

Two pointers merge: take smaller each step (stable on tie), append remaining tail.

public static int[] MergeSorted(int[] a, int[] b)
{
    if (a == null) throw new ArgumentNullException(nameof(a));
    if (b == null) throw new ArgumentNullException(nameof(b));

    int[] r = new int[a.Length + b.Length];
    int i = 0, j = 0, k = 0;

    while (i < a.Length && j < b.Length)
    {
        if (a[i] <= b[j]) r[k++] = a[i++];                             // stable on tie
        else r[k++] = b[j++];
    }
    while (i < a.Length) r[k++] = a[i++];
    while (j < b.Length) r[k++] = b[j++];
    return r;
}

5

Shortest Connection Hops — BFS (Queue)

GraphsBFSQueueModerate

Scenario: A social feature needs to find the shortest number of hops between two users. Graph is unweighted (friend connections). Implement: - SocialGraph.ShortestHops(string start, string end) -> int (or -1) Rules: - Use BFS (Queue) - Case-insensitive user ids (normalize trim) - Return 0 if start==end - Return -1 if unreachable ✅ Students implement ONLY the TODO method.

Sample Input (student: edit/replace with your own complex input)

✅ Sample input includes spaces, quotes, unicode α/β, emoji ✅, and special chars to test parsing and edge cases.

DSA scenario (students implement ONLY TODO methods) Ctrl+C

using System;                                                     // Console
using System.Collections.Generic;                                    // Dictionary, List, Queue

namespace ItTechGenie.M1.DSA.Q5
{
    public class SocialGraph
    {
        private readonly Dictionary<string, List<string>> _adj =
            new(StringComparer.OrdinalIgnoreCase);

        public void AddEdge(string a, string b)
        {
            if (!_adj.ContainsKey(a)) _adj[a] = new List<string>();
            if (!_adj.ContainsKey(b)) _adj[b] = new List<string>();
            _adj[a].Add(b);
            _adj[b].Add(a);
        }

        // ✅ TODO: Student must implement only this method
        public int ShortestHops(string start, string end)
        {
            // TODO:
            // - normalize start/end (trim)
            // - BFS using Queue<(node, depth)>
            // - visited HashSet
            // - return depth when end found
            throw new NotImplementedException();
        }
    }

    internal class Program
    {
        static void Main()
        {
            var g = new SocialGraph();
            g.AddEdge("u-α12 ✅", "u-β77");
            g.AddEdge("u-β77", "u- 001 ");

            Console.WriteLine(g.ShortestHops(" u-α12 ✅ ", "u- 001 "));
        }
    }
}

Answer (Logic + Code)

BFS explores level-by-level; first time you reach end is shortest distance.

public int ShortestHops(string start, string end)
{
    start = start?.Trim() ?? "";
    end   = end?.Trim() ?? "";
    if (start.Length == 0 || end.Length == 0) throw new ArgumentException("Empty id");
    if (start.Equals(end, StringComparison.OrdinalIgnoreCase)) return 0;

    var q = new Queue<(string node, int depth)>();
    var vis = new HashSet<string>(StringComparer.OrdinalIgnoreCase);

    q.Enqueue((start, 0));
    vis.Add(start);

    while (q.Count > 0)
    {
        var (node, d) = q.Dequeue();
        if (!_adj.TryGetValue(node, out var nbrs)) continue;

        foreach (var nb in nbrs)
        {
            var n = nb.Trim();
            if (vis.Contains(n)) continue;
            if (n.Equals(end, StringComparison.OrdinalIgnoreCase)) return d + 1;
            vis.Add(n);
            q.Enqueue((n, d + 1));
        }
    }
    return -1;
}

6

Top‑K Frequent Keywords — Dictionary + Sorting

Hash MapSortingFrequencyComplex

Scenario: A support chatbot logs tags/keywords from tickets. You must return the Top-K frequent keywords. Implement: - KeywordAnalytics.TopK(string[] words, int k) -> List<string> Rules: - Normalize words: trim + case-insensitive - Ignore empty words - If tie in frequency: sort lexicographically (ordinal) - Use Dictionary for counts - Final result should be in descending frequency order ✅ Students implement ONLY the TODO method.

Sample Input (student: edit/replace with your own complex input)

✅ Sample input includes spaces, quotes, unicode α/β, emoji ✅, and special chars to test parsing and edge cases.

DSA scenario (students implement ONLY TODO methods) Ctrl+C

using System;
using System.Collections.Generic;
using System.Linq;

namespace ItTechGenie.M1.DSA.Q6
{
    public static class KeywordAnalytics
    {
        // ✅ TODO: Student must implement only this method
        public static List<string> TopK(string[] words, int k)
        {
            // TODO:
            // - count normalized words
            // - sort by count desc, word asc
            // - return first k
            throw new NotImplementedException();
        }
    }

    internal class Program
    {
        static void Main()
        {
            var words = new[] { " login ✅ ", "Login", "  refund !@# ", "Refund", "refund", "shipping", "Shipping", "α/β", "α/β", "α/β" };
            var top = KeywordAnalytics.TopK(words, 3);
            Console.WriteLine(string.Join(" | ", top));
        }
    }
}

Answer (Logic + Code)

Count using Dictionary, then sort pairs by count descending and word ascending, take k.

public static List<string> TopK(string[] words, int k)
{
    if (words == null) throw new ArgumentNullException(nameof(words));
    if (k <= 0) throw new ArgumentOutOfRangeException(nameof(k));

    var freq = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);
    foreach (var w in words)
    {
        var key = (w ?? "").Trim();
        if (key.Length == 0) continue;
        freq[key] = freq.TryGetValue(key, out var c) ? c + 1 : 1;
    }

    return freq
        .OrderByDescending(p => p.Value)
        .ThenBy(p => p.Key, StringComparer.Ordinal)
        .Take(k)
        .Select(p => p.Key)
        .ToList();
}

7

Search in Rotated Sorted Array — Modified Binary Search

Binary searchArraysLog nComplex

Scenario: A search index stores sorted IDs but the array is rotated due to sharding. Find the index of a target in a rotated sorted array (no duplicates). Implement: - RotatedSearch.Find(int[] arr, int target) -> index or -1 Rules: - O(log n) using modified binary search ✅ Students implement ONLY the TODO method.

Sample Input (student: edit/replace with your own complex input)

✅ Sample input includes spaces, quotes, unicode α/β, emoji ✅, and special chars to test parsing and edge cases.

DSA scenario (students implement ONLY TODO methods) Ctrl+C

using System;

namespace ItTechGenie.M1.DSA.Q7
{
    public static class RotatedSearch
    {
        // ✅ TODO: Student must implement only this method
        public static int Find(int[] arr, int target)
        {
            // TODO:
            // - identify sorted half each iteration
            // - decide which side to search
            throw new NotImplementedException();
        }
    }

    internal class Program
    {
        static void Main()
        {
            int[] a = { 10, 15, 20, -3, 0, 7, 9 };
            Console.WriteLine(RotatedSearch.Find(a, -3));
        }
    }
}

Answer (Logic + Code)

Modified binary search: one half is sorted; decide which half contains target.

public static int Find(int[] arr, int target)
{
    if (arr == null) throw new ArgumentNullException(nameof(arr));
    int lo = 0, hi = arr.Length - 1;

    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;

        if (arr[lo] <= arr[mid]) // left sorted
        {
            if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
            else lo = mid + 1;
        }
        else // right sorted
        {
            if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

8

Cycle Detection in Linked List — Floyd’s Algorithm

Linked listTwo pointersCycleComplex

Scenario: A workflow engine maintains a linked list of steps. Bad configuration may introduce a cycle. Detect if a cycle exists. Implement: - LinkedListUtil.HasCycle(Node head) -> bool Rules: - Floyd's tortoise-hare (O(1) memory) ✅ Students implement ONLY the TODO method.

Sample Input (student: edit/replace with your own complex input)

✅ Sample input includes spaces, quotes, unicode α/β, emoji ✅, and special chars to test parsing and edge cases.

DSA scenario (students implement ONLY TODO methods) Ctrl+C

using System;

namespace ItTechGenie.M1.DSA.Q8
{
    public class Node
    {
        public string Label;
        public Node? Next;
        public Node(string label) { Label = label; }
    }

    public static class LinkedListUtil
    {
        // ✅ TODO: Student must implement only this method
        public static bool HasCycle(Node? head)
        {
            // TODO:
            // - slow=head, fast=head
            // - move slow 1 step, fast 2 steps
            // - if meet => cycle
            throw new NotImplementedException();
        }
    }

    internal class Program
    {
        static void Main()
        {
            var a = new Node("A ✅");
            var b = new Node("B !@#");
            var c = new Node("C α/β");

            a.Next = b; b.Next = c; c.Next = b;                       // create cycle

            Console.WriteLine(LinkedListUtil.HasCycle(a));
        }
    }
}

Answer (Logic + Code)

Two pointers: if fast pointer catches slow pointer, a cycle exists.

public static bool HasCycle(Node? head)
{
    Node? slow = head, fast = head;
    while (fast != null && fast.Next != null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        if (slow == fast) return true;
    }
    return false;
}

9

Minimum Coupons to Reach Target — Dynamic Programming

DPOptimizationUnbounded knapsackComplex

Scenario: A checkout system must return the minimum number of coupons to reach a discount target. Coupons can be reused (unbounded). Implement: - CouponDp.MinCoupons(int[] coupons, int target) -> min count or -1 Rules: - Bottom-up DP ✅ Students implement ONLY the TODO method.

Sample Input (student: edit/replace with your own complex input)

✅ Sample input includes spaces, quotes, unicode α/β, emoji ✅, and special chars to test parsing and edge cases.

DSA scenario (students implement ONLY TODO methods) Ctrl+C

using System;

namespace ItTechGenie.M1.DSA.Q9
{
    public static class CouponDp
    {
        // ✅ TODO: Student must implement only this method
        public static int MinCoupons(int[] coupons, int target)
        {
            // TODO:
            // - dp[0]=0, dp[others]=INF
            // - dp[x]=min(dp[x], dp[x-coin]+1)
            throw new NotImplementedException();
        }
    }

    internal class Program
    {
        static void Main()
        {
            int[] c = { 1, 3, 4 };
            Console.WriteLine(CouponDp.MinCoupons(c, 6));
        }
    }
}

Answer (Logic + Code)

DP over sums: dp[x] = minimum coupons to make x; return dp[target] or -1 if INF.

public static int MinCoupons(int[] coupons, int target)
{
    if (coupons == null) throw new ArgumentNullException(nameof(coupons));
    if (target < 0) throw new ArgumentOutOfRangeException(nameof(target));

    const int INF = 1_000_000;
    int[] dp = new int[target + 1];
    for (int i = 1; i <= target; i++) dp[i] = INF;
    dp[0] = 0;

    for (int x = 1; x <= target; x++)
    {
        foreach (var coin in coupons)
        {
            if (coin <= 0) continue;
            if (x - coin >= 0 && dp[x - coin] != INF)
                dp[x] = Math.Min(dp[x], dp[x - coin] + 1);
        }
    }
    return dp[target] == INF ? -1 : dp[target];
}

10

Merge Overlapping Intervals — Sorting + Scan

SortingIntervalsGreedyComplex

Scenario: You receive booking intervals (start,end) and must merge overlaps to compute occupied time blocks. Implement: - IntervalUtil.Merge(List<Interval> items) -> List<Interval> Rules: - Sort by start then end - Merge if next.Start <= current.End ✅ Students implement ONLY the TODO method.

Sample Input (student: edit/replace with your own complex input)

✅ Sample input includes spaces, quotes, unicode α/β, emoji ✅, and special chars to test parsing and edge cases.

DSA scenario (students implement ONLY TODO methods) Ctrl+C

using System;
using System.Collections.Generic;

namespace ItTechGenie.M1.DSA.Q10
{
    public record Interval(int Start, int End, string Label);

    public static class IntervalUtil
    {
        // ✅ TODO: Student must implement only this method
        public static List<Interval> Merge(List<Interval> items)
        {
            // TODO:
            // - sort
            // - scan and merge overlaps
            throw new NotImplementedException();
        }
    }

    internal class Program
    {
        static void Main()
        {
            var list = new List<Interval>
            {
                new Interval(1,3,"Room A ✅"),
                new Interval(2,6,"Room A !@#"),
                new Interval(8,10,"Room α/β"),
                new Interval(9,12,"Room α/β ✅"),
            };

            var merged = IntervalUtil.Merge(list);
            foreach (var i in merged) Console.WriteLine($"[{i.Start},{i.End}] {i.Label}");
        }
    }
}

Answer (Logic + Code)

Sort then scan; extend current interval when overlap, else push to result and start new.

public static List<Interval> Merge(List<Interval> items)
{
    if (items == null) throw new ArgumentNullException(nameof(items));
    if (items.Count == 0) return new List<Interval>();

    items.Sort((a,b) => a.Start != b.Start ? a.Start.CompareTo(b.Start) : a.End.CompareTo(b.End));

    var res = new List<Interval>();
    var cur = items[0] with { Label = (items[0].Label ?? "").Trim() };

    for (int idx = 1; idx < items.Count; idx++)
    {
        var nxt = items[idx] with { Label = (items[idx].Label ?? "").Trim() };
        if (nxt.Start <= cur.End)
            cur = cur with { End = Math.Max(cur.End, nxt.End) };
        else
        {
            res.Add(cur);
            cur = nxt;
        }
    }
    res.Add(cur);
    return res;
}

ItTechGenie-Subject - DSA with C# (Warm-up + 10 Questions)

C# Question Bank

Warm‑up Answer (Reasoning + Big‑O)

Answer (Logic + Code)

Answer (Logic + Code)

Answer (Logic + Code)

Answer (Logic + Code)

Answer (Logic + Code)

Answer (Logic + Code)

Answer (Logic + Code)

Answer (Logic + Code)

Answer (Logic + Code)

Answer (Logic + Code)