Dil

Mülakatlar için C#

Deyimler, koleksiyonlar, ListNode/TreeNode ve şablonların gerçekten çalıştırdığı heap. .NET 10.

Çözüm testleri .NET 10’da çalışır; bu çitler de o derleyiciyle (dotnet run --file) koşuldu. Her çit kendi programıdır.

int 32-bit iki’nin tümleyeni. long 64-bit. Varsayılan bağlam taşmada dolar. Bu genişliğe bağlı bit kalıpları bit-manipülasyonu kalıp sayfasında.

Bölme, kalan, taşma

if (-3 / 2 != -1) throw new InvalidOperationException("div");
if (-3 % 2 != -1) throw new InvalidOperationException("mod");
if (unchecked(-int.MinValue) != int.MinValue) throw new InvalidOperationException("wrap");

int min = int.MinValue;
bool threw = false;
try {
    checked { int x = -min; _ = x; }
} catch (OverflowException) {
    threw = true;
}
if (!threw) throw new InvalidOperationException("checked");

if ((1L << 31) != 2147483648L) throw new InvalidOperationException("wide");

Tamsayı / sıfıra doğru keser. Kalan, bölünenin işaretini alır. Python // alta yuvarlar, % bölenin işaretini alır; Python parçası taşırken negatif girdilere ikinci kez bak.

int.MinValue’i negatife çevirmek taşar: checked fırlatır, unchecked int.MinValue’de kalır. Geniş pozitif kaydırma long ister: 1L << 31.

Dizgiler ve StringBuilder

string s = "ab,cd";
if (s[0] != 'a' || s[^1] != 'd') throw new InvalidOperationException("index");
if (s[1..4] != "b,c") throw new InvalidOperationException("slice");
if (string.Join("", s.Reverse()) != "dc,ba") throw new InvalidOperationException("rev");
if (s.Split(',')[0] != "ab" || s.Split(',')[1] != "cd") throw new InvalidOperationException("split");
if (string.Join(" ", new[] { "ab", "cd" }) != "ab cd") throw new InvalidOperationException("join");
if (s.Replace("ab", "xy") != "xy,cd") throw new InvalidOperationException("replace");
if (!s.StartsWith("ab") || !s.EndsWith("cd")) throw new InvalidOperationException("ends");
if (s.IndexOf('z') != -1) throw new InvalidOperationException("indexof");
if (s.Contains("cd") == false) throw new InvalidOperationException("contains");

var sb = new System.Text.StringBuilder();
sb.Append("ab");
sb.Append('c');
if (sb.ToString() != "abc") throw new InvalidOperationException("sb");

string name = "ada";
if ($"{name} {2}" != "ada 2") throw new InvalidOperationException("interp");

s[^1] son karakter. s[1..4] yarı açık aralık. Parça yoksa IndexOf -1 döner. Dizgiler değişmez; Replace yeni dizgi döner ve her eşleşmeyi değiştirir. Döngüde ekliyorsan tampon StringBuilder.

Interpolasyon $"{expr}". İki noktadan sonraki biçim bir .NET format dizgisidir.

Dictionary, HashSet ve two-sum

Bu, hashing şablonunun şeklidir. Anahtar yoksa TryGetValue false döner. Eksik anahtarı indekslemek fırlatır.

int[] TwoSum(int[] nums, int target) {
    var seen = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++) {
        int need = target - nums[i];
        if (seen.TryGetValue(need, out int j)) return [j, i];
        seen[nums[i]] = i;
    }
    throw new InvalidOperationException("no solution");
}

int[] pair = TwoSum([2, 7, 11, 15], 9);
if (pair[0] != 0 || pair[1] != 1) throw new InvalidOperationException("two sum");

var set = new HashSet<int> { 1, 1, 2 };
if (set.Count != 2 || !set.Contains(2)) throw new InvalidOperationException("set");
set.Add(3);
set.Remove(1);
if (set.Contains(1) || !set.Contains(3)) throw new InvalidOperationException("mut");

var ordered = new SortedSet<int> { 3, 1, 2 };
if (ordered.Min != 1 || ordered.Max != 3) throw new InvalidOperationException("sorted");

HashSet sırasız üyelik. SortedSet değerleri sırada tutar ve Min / Max sunar. Değere ihtiyacın yoksa Dictionary üyelik testi ContainsKey.

Listeler, sıralama ve jagged satırlar

var nums = new List<int> { 10, 2, 1 };
nums.Sort();
if (nums[0] != 1 || nums[1] != 2 || nums[2] != 10) throw new InvalidOperationException("sort");

int[] row = [0, 0];
int[][] shared = [row, row];
shared[0][0] = 1;
if (shared[1][0] != 1) throw new InvalidOperationException("shared");

int[][] grid = [[0, 0], [0, 0]];
grid[0][0] = 1;
if (grid[1][0] != 0) throw new InvalidOperationException("jagged");

int[] arr = [1, 2, 3];
if (arr.Length != 3) throw new InvalidOperationException("len");
nums.Add(4);
if (nums[^1] != 4) throw new InvalidOperationException("add");

List<int>.Sort sayısal değere göre sıralar. int[] sabit Length taşır; List<int> Add ile büyür. Her new satır kendi dizisidir. Aynı dizi nesnesini yeniden kullanmak, onu tutan her satırda yazıyı gösterir. Şablonlardaki LeetCode tarzı matrisler jagged int[][].

foreach, yield ve yerel fonksiyonlar

var seen = new List<int>();
foreach (var value in new[] { 1, 2, 3 }) seen.Add(value);
if (!seen.SequenceEqual([1, 2, 3])) throw new InvalidOperationException("foreach");

IEnumerable<int> Range(int n) {
    for (int i = 0; i < n; i++) yield return i;
}
if (!Range(3).SequenceEqual([0, 1, 2])) throw new InvalidOperationException("yield");

int Add(int a, int b = 0) => a + b;
if (Add(1) != 1 || Add(1, 2) != 3) throw new InvalidOperationException("local");

(int x, int y) = (3, 4);
if (x != 3 || y != 4) throw new InvalidOperationException("deconstruct");
(x, y) = (y, x);
if (x != 4 || y != 3) throw new InvalidOperationException("swap");

foreach IEnumerable olan her şeyi gezer. yield return bir iterator kurar; gövde çağıran değer çektikçe çalışır. Dosya tabanlı programda yerel fonksiyon üst düzey ifadelerin yanında durabilir. Tuple deconstruction geçici değişkene gerek kalmadan iki bağlamayı takas eder.

İndeks biçimi for (int i = 0; i < n; i++). while ve do vardır. break döngüyü bırakır; continue gövdenin kalanını atlar.

Sınıflar, record ve nullability

var c = new Counter();
if (c.Inc() != 1 || c.Value != 1) throw new InvalidOperationException("class");
if (new Point(1, 2) != new Point(1, 2)) throw new InvalidOperationException("eq");
if (new Point(1, 2) == new Point(1, 3)) throw new InvalidOperationException("neq");

string? missing = null;
if ((missing ?? "default") != "default") throw new InvalidOperationException("coal");
if (missing?.Length != null) throw new InvalidOperationException("cond");

class Counter {
    public int Value { get; private set; }
    public int Inc() => ++Value;
}
record Point(int X, int Y);

class referansla karşılaştırır. record değerle karşılaştırır ve parametrelerine deconstruct olur. string? nullable referanstır; ?? yedek verir, ?. kısa devre yapar. Eksik Dictionary anahtarını indekslemek fırlatır; TryGetValue fırlatmaz.

Heap

PriorityQueue<TElement, TPriority> en küçük önceliği önce çıkarır. Heap top-K şablonu değeri hem eleman hem öncelik olarak saklar, kuyruk k’yı geçince en küçüğü atar.

int FindKthLargest(int[] nums, int k) {
    var pq = new PriorityQueue<int, int>();
    foreach (var x in nums) {
        pq.Enqueue(x, x);
        if (pq.Count > k) pq.Dequeue();
    }
    return pq.Peek();
}

if (FindKthLargest([3, 2, 1, 5, 6, 4], 2) != 5) throw new InvalidOperationException("kth");

var max = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
max.Enqueue(3, 3);
max.Enqueue(1, 1);
if (max.Dequeue() != 3) throw new InvalidOperationException("max");

Ters comparer aynı kuyruğu max-heap yapar. Önceliği negatife çevirmek de int.MinValue’e kadar çalışır; onun negatifi taşar.

Deque

Kayan pencere şablonu LinkedList<int> kullanır; iki uç da O(1). Queue<T> yalnızca arka ve ön sunar. Stack<T> tek uçtur.

int[] MaxSlidingWindow(int[] nums, int k) {
    var dq = new LinkedList<int>();
    var res = new List<int>();
    for (int i = 0; i < nums.Length; i++) {
        while (dq.Count > 0 && dq.First!.Value <= i - k) dq.RemoveFirst();
        while (dq.Count > 0 && nums[dq.Last!.Value] <= nums[i]) dq.RemoveLast();
        dq.AddLast(i);
        if (i >= k - 1) res.Add(nums[dq.First!.Value]);
    }
    return res.ToArray();
}

int[] got = MaxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3);
int[] want = [3, 3, 5, 5, 6, 7];
if (!got.SequenceEqual(want)) throw new InvalidOperationException("window");

var stack = new Stack<int>();
stack.Push(1);
if (stack.Pop() != 1) throw new InvalidOperationException("stack");
var queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
if (queue.Dequeue() != 1) throw new InvalidOperationException("queue");

İkili arama

Şablon lo + ((hi - lo) >> 1) kullanır. Önce çıkarma, negatif olmayan indekslerde toplamı int içinde tutar. İki uç da büyükken (lo + hi) >> 1 int taşır.

int BinarySearch(int[] nums, int target) {
    int lo = 0, hi = nums.Length;
    while (lo < hi) {
        int mid = lo + ((hi - lo) >> 1);
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo < nums.Length && nums[lo] == target ? lo : -1;
}

if (BinarySearch([1, 3, 3, 7], 3) != 1) throw new InvalidOperationException("hit");
if (BinarySearch([1, 3, 3, 7], 4) != -1) throw new InvalidOperationException("miss");
if (BinarySearch([], 1) != -1) throw new InvalidOperationException("empty");

LINQ

int[] nums = [1, 2, 3, 4];
int sum = nums.Where(x => x % 2 == 0).Sum();
if (sum != 6) throw new InvalidOperationException("sum");
if (nums.Count(x => x > 2) != 2) throw new InvalidOperationException("count");
if (nums.Max() != 4) throw new InvalidOperationException("max");

Where sonra Sum bir kez tarar. for döngüsü içindeki Where veya Any her iterasyonda yeniden tarar. Elle yazılmış döngü bu maliyeti görünür tutar.

Matematik

if (Math.Abs(-3) != 3) throw new InvalidOperationException("abs");
if (Math.Max(1, 4) != 4) throw new InvalidOperationException("max");
if (Math.Clamp(9, 0, 5) != 5) throw new InvalidOperationException("clamp");
if (Math.DivRem(7, 3) != (2, 1)) throw new InvalidOperationException("divrem");
if (int.IsPositive(4) == false) throw new InvalidOperationException("sign");
if (Math.Min(1L, 2L) != 1L) throw new InvalidOperationException("long");

checked bağlamında Math.Abs(int.MinValue) taşar. DivRem sıfıra doğru bölmeyle (bölüm, kalan) çiftini döner. Çarpım int.MaxValue’i geçebiliyorsa long yeğle.

Bağlı listeler

Bağlı liste şablonu bu düğüm artı reverse ve dummy-head birleştirmesidir.

var a = new ListNode(1, new ListNode(2, new ListNode(3)));
var rev = ReverseList(a);
if (ToList(rev) is not [3, 2, 1]) throw new InvalidOperationException("rev");

ListNode ReverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        var nxt = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}

List<int> ToList(ListNode head) {
    var outList = new List<int>();
    while (head != null) {
        outList.Add(head.val);
        head = head.next;
    }
    return outList;
}

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) { this.val = val; this.next = next; }
}

while (cur != null) ile yürü. Dummy head, birleştirme döngüsünün ilk düğümü özel saymasını engeller. Boş liste null. Dosya tabanlı programda tipler üst düzey ifadelerden sonra durur.

Ağaçlar

var root = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4)));
if (MaxDepth(root) != 3) throw new InvalidOperationException("depth");
var levels = LevelOrder(root);
if (levels.Count != 3 || levels[0][0] != 1 || levels[2][0] != 4)
    throw new InvalidOperationException("level");

int MaxDepth(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.Max(MaxDepth(node.left), MaxDepth(node.right));
}

List<List<int>> LevelOrder(TreeNode node) {
    var res = new List<List<int>>();
    if (node == null) return res;
    var q = new Queue<TreeNode>();
    q.Enqueue(node);
    while (q.Count > 0) {
        int size = q.Count;
        var level = new List<int>();
        for (int i = 0; i < size; i++) {
            var n = q.Dequeue();
            level.Add(n.val);
            if (n.left != null) q.Enqueue(n.left);
            if (n.right != null) q.Enqueue(n.right);
        }
        res.Add(level);
    }
    return res;
}

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

left ve right üzerinde özyineleme DFS şablonudur. Seviye sırası q.Count anlık görüntüsü alır; böylece yeni kuyruğa alınan çocuklar mevcut seviyeyi bozmaz.

Graflar

Graf-DFS şablonu yönsüz kenarları List<int>[] olarak saklar. Izgara flood fill (r, c) hücrelerinin yığınıdır.

if (CountComponents(4, [[0, 1], [2, 3]]) != 2) throw new InvalidOperationException("cc");
int[][] filled = FloodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2);
if (filled[0][0] != 2 || filled[2][1] != 0 || filled[2][2] != 1)
    throw new InvalidOperationException("fill");

int CountComponents(int n, int[][] edges) {
    var adj = new List<int>[n];
    for (int i = 0; i < n; i++) adj[i] = new List<int>();
    foreach (var e in edges) { adj[e[0]].Add(e[1]); adj[e[1]].Add(e[0]); }
    var visited = new bool[n];
    int count = 0;
    for (int v = 0; v < n; v++) {
        if (!visited[v]) { Dfs(v); count++; }
    }
    return count;
    void Dfs(int v) {
        visited[v] = true;
        foreach (var u in adj[v]) if (!visited[u]) Dfs(u);
    }
}

int[][] FloodFill(int[][] image, int sr, int sc, int newColor) {
    int orig = image[sr][sc];
    if (orig == newColor) return image;
    int rows = image.Length, cols = image[0].Length;
    var stack = new Stack<(int r, int c)>();
    stack.Push((sr, sc));
    while (stack.Count > 0) {
        var (r, c) = stack.Pop();
        if (r < 0 || c < 0 || r >= rows || c >= cols || image[r][c] != orig) continue;
        image[r][c] = newColor;
        stack.Push((r + 1, c)); stack.Push((r - 1, c));
        stack.Push((r, c + 1)); stack.Push((r, c - 1));
    }
    return image;
}

orig == newColor aynı rengi sonsuz yeniden yazmayı kesen erken dönüştür. Yerel fonksiyon (Dfs) visited ve adj üzerine kapanır.

Union-Find

Path compression artı rank’e göre birleştirme. Union, iki düğümün farklı bileşenlerde olup olmadığını döner.

var uf = new UnionFind(4);
if (!uf.Union(0, 1) || !uf.Union(2, 3)) throw new InvalidOperationException("union");
if (uf.Union(0, 1)) throw new InvalidOperationException("dup");
if (uf.Components != 2) throw new InvalidOperationException("cc");

class UnionFind {
    readonly int[] parent;
    readonly int[] rank;
    public int Components { get; private set; }
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        Components = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int Find(int x) => parent[x] == x ? x : parent[x] = Find(parent[x]);
    public bool Union(int a, int b) {
        int ra = Find(a), rb = Find(b);
        if (ra == rb) return false;
        if (rank[ra] < rank[rb]) (ra, rb) = (rb, ra);
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        Components--;
        return true;
    }
}

Trie

var t = new Trie();
t.Insert("apple");
if (!t.Search("apple") || t.Search("app")) throw new InvalidOperationException("search");
if (!t.StartsWith("app")) throw new InvalidOperationException("prefix");

class TrieNode {
    public Dictionary<char, TrieNode> Children = new();
    public bool IsWord;
}
class Trie {
    readonly TrieNode root = new();
    public void Insert(string word) {
        var node = root;
        foreach (var ch in word) {
            if (!node.Children.TryGetValue(ch, out var next)) {
                next = new TrieNode();
                node.Children[ch] = next;
            }
            node = next;
        }
        node.IsWord = true;
    }
    public bool Search(string word) {
        var node = Walk(word);
        return node != null && node.IsWord;
    }
    public bool StartsWith(string prefix) => Walk(prefix) != null;
    TrieNode Walk(string s) {
        var node = root;
        foreach (var ch in s) {
            if (!node.Children.TryGetValue(ch, out node)) return null;
        }
        return node;
    }
}

Search IsWord ister. StartsWith yalnızca yürüyüşün hayatta kalmasını ister.