مسائل Coding بالحل

#طريقة الحل في 6 خطواتA six-step interview method

الهدف إنك توصل لحل صحيح وتشرح ليه صحيح، مش تحفظ شكل الكود. اتكلم عن القرارات المهمة وإنت بتحل.

1. أعد السؤال واسأل عن constraints: input فاضي؟ negatives؟ duplicates؟ حجم الأرقام؟ مسموح mutation؟ وإيه ناتج عدم وجود حل؟
2. اكتب مثال عادي وحالات حدودية، واتفق على output.
3. اشرح brute force وتعقيده كـ baseline.
4. حسّن باستخدام invariant أو recurrence واضحة؛ قول الـ trade-off في memory.
5. اكتب كود بأسماء مفهومة، واشرح قراراتك من غير قراءة كل سطر بصوت عالي.
6. امشِ على المثال والحالات الحدية، وحدد time وauxiliary space والـ output space.

#1. Two Sum

المسألة: رجّع zero-based indices لعنصرين مختلفين مجموعهم target، أو array فاضية. [2,7,11,15], 9 → [0,1]. الفكرة: خزّن الأرقام السابقة، ولكل رقم دوّر على المكمل بدل تجربة كل زوج O(n²).

جرّب بنفسك قبل ما تفتح الحل: الإدخال [2,7,11,15] وtarget = 9، والناتج المتوقع [0,1]. اختبر كمان array فاضية، مفيش حل، وقيم مكررة زي [3,3], 6.

int[] TwoSum(int[] values, int target)
{
    var seen = new Dictionary<long, int>();
    for (int i = 0; i < values.Length; i++)
    {
        long need = (long)target - values[i]; // (1)
        if (seen.TryGetValue(need, out int previous)) return [previous, i];
        seen[values[i]] = i; // (2)
    }
    return [];
}

#2. Duplicates و first unique character2. Duplicates and first unique character

المسائل: اكتشف تكرار رقم، وحدد أول index لحرف مش مكرر أو -1. مثال [1,2,1] → true و"aabbc" → 4. الفكرة: membership للـ duplicate، وfrequency ثم مرور بالترتيب للـ unique. الحروف هنا lowercase English بس.

bool ContainsDuplicate(int[] values)
{
    var seen = new HashSet<int>();
    foreach (int value in values)
        if (!seen.Add(value)) return true; // (1)
    return false;
}
int FirstUniqueChar(string text)
{
    var count = new int[26];
    foreach (char c in text) count[c - 'a']++;
    for (int i = 0; i < text.Length; i++)
        if (count[text[i] - 'a'] == 1) return i; // (2)
    return -1;
}

التعقيد: duplicates expected O(n) وقت وO(u) مساحة لعدد القيم المختلفة. Unique O(n) وقت وO(1) مساحة لأن alphabet ثابتة. اختبر فاضي وكله مكرر؛ لحروف أوسع غيّر frequency structure واتفق على معنى character.

#3. Valid anagram و group anagrams3. Valid anagram and group anagrams

المسائل: هل كلمتين نفس تكرارات الحروف؟ وجمّع الكلمات المتشابهة. listen وsilent anagrams، و[eat,tea,tan] → [[eat,tea],[tan]]. الفكرة: counts للتحقق من lowercase English، وsorted signature للتجميع case-sensitive على char.

bool IsAnagram(string first, string second)
{
    if (first.Length != second.Length) return false;
    var count = new int[26];
    for (int i = 0; i < first.Length; i++)
    {
        count[first[i] - 'a']++;
        count[second[i] - 'a']--; // (1)
    }
    return count.All(value => value == 0);
}
List<List<string>> GroupAnagrams(string[] words)
{
    var groups = new Dictionary<string, List<string>>(StringComparer.Ordinal);
    foreach (string word in words)
    {
        char[] letters = word.ToCharArray();
        Array.Sort(letters);
        string key = new(letters); // (2)
        if (!groups.TryGetValue(key, out var group)) groups[key] = group = [];
        group.Add(word);
    }
    return groups.Values.ToList();
}

التعقيد: التحقق O(n) وقت وO(1) مساحة. التجميع expected O(w × k log k) وقت للكلمات بطول أقصى k، مع O(wk) لتخزين signatures والمجموعات كحد أعلى. Count signature ممكن تقلل sorting مع alphabet ثابتة. اختبر empty strings وduplicates.

#4. Top K frequent elements

المسألة: رجّع أكتر k قيم تكراراً؛ [1,1,1,2,2,3], 2 → [1,2]. الفكرة: احسب frequency، وخلي min-heap بحجم k. عند التعادل أي اختيار صحيح، وترتيب الناتج مش مضمون. العقد: k بين صفر وعدد القيم المختلفة.

int[] TopKFrequent(int[] values, int k)
{
    var counts = new Dictionary<int, int>();
    foreach (int value in values)
        counts[value] = counts.GetValueOrDefault(value) + 1; // (1)
    if (k < 0 || k > counts.Count) throw new ArgumentOutOfRangeException(nameof(k));
    if (k == 0) return [];
    var heap = new PriorityQueue<int, int>();
    foreach (var (value, count) in counts)
    {
        heap.Enqueue(value, count);
        if (heap.Count > k) heap.Dequeue(); // (2)
    }
    var result = new int[k];
    for (int i = 0; i < k; i++) result[i] = heap.Dequeue();
    return result;
}

التعقيد: expected O(n + u log(k + 1)) وقت وO(u + k) مساحة، u عدد القيم المختلفة. Sorting counts أبسط لكنه O(u log u). Frequency buckets توصل expected O(n) مع O(n + u) مساحة. اختبر k=0 وk=u والتعادل.

#5. Product of array except self

المسألة: كل مكان ياخد حاصل ضرب الباقي من غير قسمة؛ [1,2,3,4] → [24,12,8,6]. الفكرة: prefix product قبل المكان × suffix product بعده. العقد: كل intermediate products تناسب long؛ checked يكشف التجاوز.

long[] ProductExceptSelf(int[] values)
{
    var result = new long[values.Length];
    long prefix = 1;
    for (int i = 0; i < values.Length; i++)
    {
        result[i] = prefix; // (1)
        if (i < values.Length - 1) prefix = checked(prefix * values[i]);
    }
    long suffix = 1;
    for (int i = values.Length - 1; i >= 0; i--)
    {
        result[i] = checked(result[i] * suffix); // (2)
        if (i > 0) suffix = checked(suffix * values[i]);
    }
    return result;
}

التعقيد: O(n) وقت وO(1) extra غير output O(n). فاضي يرجع فاضي؛ عنصر واحد يرجع 1 كـ empty product. اختبر صفر واحد وصفرين وnegatives. BigInteger لو مطلوب أرقام أكبر، بس ساعتها الضرب مش constant cost.

#6. Maximum subarray وstock profit6. Maximum subarray and stock profit

المسائل: أكبر مجموع subarray غير فاضية، وأكبر ربح شراء ثم بيع مرة واحدة بسعر يومي non-negative. مثال Kadane [-2,1,-3,4,-1,2,1] → 6، والأسعار [7,1,5,3,6,4] → 5. الفكرة: احتفظ بأحسن حالة تنتهي هنا، أو أقل سعر سابق.

جرّب بنفسك قبل ما تفتح الحل: أكبر مجموع subarray للإدخال [-2,1,-3,4,-1,2,1,-5,4] هو 6، وأكبر ربح للأسعار [7,1,5,3,6,4] هو 5. اختبر كمان كل القيم السالبة (النتيجة أكبر قيمة سالبة) والأسعار التنازلية أو الفاضية (الربح صفر).

long MaxSubarray(int[] values)
{
    if (values.Length == 0) throw new ArgumentException("Nonempty input required");
    long current = values[0], best = current;
    for (int i = 1; i < values.Length; i++)
    {
        current = Math.Max(values[i], current + values[i]); // (1)
        best = Math.Max(best, current);
    }
    return best;
}
long MaxProfit(int[] prices)
{
    int minimum = int.MaxValue;
    long best = 0;
    foreach (int price in prices)
    {
        minimum = Math.Min(minimum, price);
        best = Math.Max(best, (long)price - minimum); // (2)
    }
    return best;
}

#7. Move zeroes وmissing number وremove duplicates7. In-place array patterns

المسائل: حرّك zeros للآخر مع حفظ ترتيب الباقي؛ لاقي الرقم الناقص من distinct numbers بين 0 وn؛ واضغط duplicates في sorted array وارجع طول البداية الفريدة. أمثلة: [0,1,0,3] → [1,3,0,0]، و[3,0,1] → 2، و[1,1,2] → length 2.

void MoveZeroes(int[] values)
{
    int write = 0;
    for (int read = 0; read < values.Length; read++)
        if (values[read] != 0) values[write++] = values[read]; // (1)
    while (write < values.Length) values[write++] = 0;
}
int MissingNumber(int[] values)
{
    int missing = values.Length;
    for (int i = 0; i < values.Length; i++) missing ^= i ^ values[i]; // (2)
    return missing;
}
int RemoveDuplicates(int[] sorted)
{
    if (sorted.Length == 0) return 0;
    int write = 1;
    for (int read = 1; read < sorted.Length; read++)
        if (sorted[read] != sorted[write - 1]) sorted[write++] = sorted[read]; // (3)
    return write;
}

الفكرة والتعقيد: read/write pointers أو XOR؛ التلاتة O(n) وقت وO(1) extra. الأول والتالت بيعدلوا input، والتاني محتاج distinct valid range. اختبر فاضي وكله zeros وكله نفس الرقم؛ empty missing input ترجع 0.

#8. Merge intervals

المسألة: ادمج closed intervals المتداخلة؛ [[1,3],[2,6],[8,10]] → [[1,6],[8,10]]. البداية أصغر من أو تساوي النهاية. الفكرة: رتّب بالبداية وقارن بآخر interval في الناتج. هنا touching endpoints بتتدمج؛ لو bookings بـ half-open intervals اتفق على شرط مختلف.

int[][] MergeIntervals(int[][] intervals)
{
    var sorted = intervals.OrderBy(item => item[0]).ToArray();
    var result = new List<int[]>();
    foreach (var item in sorted)
    {
        if (result.Count == 0 || item[0] > result[^1][1])
            result.Add([item[0], item[1]]); // (1)
        else result[^1][1] = Math.Max(result[^1][1], item[1]); // (2)
    }
    return result.ToArray();
}

التعقيد: O(n log n) وقت وO(n) مساحة للـ sorting والناتج. اختبر touching وnested وغير مترتبة. مقارنة كل زوج أصعب وأغلى من scan بعد sorting.

#9. Palindrome وreverse string وreverse words9. Palindromes and string reversal

المسائل: افحص palindrome مع تجاهل non-alphanumeric والـ case، واقلب char array in place، واقلب ترتيب كلمات مفصولة بمسافات. "A man, a plan, a canal: Panama" → true و" hello world " → "world hello". الفكرة: two pointers من الطرفين، أو split وreverse للكلمات.

bool IsPalindrome(string text)
{
    int left = 0, right = text.Length - 1;
    while (left < right)
    {
        if (!char.IsLetterOrDigit(text[left])) { left++; continue; }
        if (!char.IsLetterOrDigit(text[right])) { right--; continue; }
        if (char.ToLowerInvariant(text[left]) != char.ToLowerInvariant(text[right]))
            return false; // (1)
        left++; right--;
    }
    return true;
}
void Reverse(char[] text)
{
    for (int left = 0, right = text.Length - 1; left < right; left++, right--)
        (text[left], text[right]) = (text[right], text[left]); // (2)
}
string ReverseWords(string text) =>
    string.Join(' ', text.Split(' ', StringSplitOptions.RemoveEmptyEntries).Reverse());

التعقيد: palindrome وchar reverse O(n) وقت وO(1) مساحة. ReverseWords O(n) وقت وO(n) مساحة وبيطبّع المسافات لواحدة؛ tabs مش separators في الكود ده. اختبر فاضي وعلامات فقط وكلمة واحدة.

#10. Longest substring without repetition

المسألة: طول أطول substring من غير char متكرر؛ abcabcbb → 3. الفكرة: نافذة invariant بتاعها إن كل char مختلف، وdictionary لآخر ظهور. مش بنرتب لأن ترتيب النص أساسي.

int LongestUniqueSubstring(string text)
{
    var last = new Dictionary<char, int>();
    int left = 0, best = 0;
    for (int right = 0; right < text.Length; right++)
    {
        if (last.TryGetValue(text[right], out int previous))
            left = Math.Max(left, previous + 1); // (1)
        last[text[right]] = right;
        best = Math.Max(best, right - left + 1); // (2)
    }
    return best;
}

التعقيد: expected O(n) وقت وO(min(n, alphabet)) مساحة. فاضي صفر، وحروف متساوية طولها واحد. الحل على char؛ لو المطلوب perceived characters لازم تقسيم مختلف مع حفظ positions المناسبة.

#11. Sorted Two Sum وcontainer with most water11. Sorted Two Sum and container with most water

المسائل: رجّع one-based indices لعنصرين مجموعهم target في sorted array، أو فاضي؛ ولاقِ أكبر مساحة بين ارتفاعين non-negative. [2,7,11,15], 9 → [1,2]، و[1,8,6,2,5,4,8,3,7] → 49. الفكرة: استبعد طرف آمن بدل كل الأزواج.

int[] TwoSumSorted(int[] sorted, int target)
{
    int left = 0, right = sorted.Length - 1;
    while (left < right)
    {
        long sum = (long)sorted[left] + sorted[right];
        if (sum == target) return [left + 1, right + 1];
        if (sum < target) left++; else right--; // (1)
    }
    return [];
}
long MaxArea(int[] heights)
{
    int left = 0, right = heights.Length - 1;
    long best = 0;
    while (left < right)
    {
        long area = (long)Math.Min(heights[left], heights[right]) * (right - left);
        best = Math.Max(best, area);
        if (heights[left] < heights[right]) left++; else right--; // (2)
    }
    return best;
}

التعقيد: الاتنين O(n) وقت وO(1) مساحة، بدل O(n²). long يحمي الجمع والمساحة لقيم int non-negative. اختبر أقل من عنصرين، وتساوي الارتفاعات، وغياب حل للمجموع.

#12. Valid parentheses

المسألة: هل الأقواس متوازنة وبالترتيب الصحيح؟ ([]{}) صح، و(] غلط. الفكرة: آخر فتح لازم يقفله أول قفل، فStack. أي character خارج الأنواع الستة بيترفض في العقد ده.

bool ValidParentheses(string text)
{
    var stack = new Stack<char>();
    foreach (char c in text)
    {
        if (c is '(' or '[' or '{') { stack.Push(c); continue; }
        char expected = c switch { ')' => '(', ']' => '[', '}' => '{', _ => '\0' };
        if (expected == '\0' || !stack.TryPop(out char open) || open != expected)
            return false; // (1)
    }
    return stack.Count == 0; // (2)
}

التعقيد: O(n) وقت وO(n) مساحة لأسوأ nesting. اختبر )( و(( وnested صحيح. لو input برنامج كامل، parser لازم يتعامل مع strings وcomments بدل عد الأقواس بس.

#13. FizzBuzz وcompression وword count وprime13. Warm-ups: FizzBuzz, compression, word count and primes

المسائل: FizzBuzz من 1 لـn غير سالب؛ run-length compression يرجع الأصل لو النتيجة مش أقصر؛ عدّ الكلمات case-insensitive بفواصل محددة؛ وافحص عدد prime. أمثلة 15 → FizzBuzz، وaaabbc → a3b2c1 لكن الأصل يفضل لأنه مش أقصر، و29 → true. الفكرة: معالجة حالات التقاطع أولاً، ومسح runs، وتجميع tokens، وقسمة لحد الجذر.

IEnumerable<string> FizzBuzz(int n)
{
    for (long i = 1; i <= n; i++)
        yield return (i % 3, i % 5) switch
        {
            (0, 0) => "FizzBuzz", (0, _) => "Fizz", // (1)
            (_, 0) => "Buzz", _ => i.ToString()
        };
}
string Compress(string text)
{
    var buffer = new StringBuilder();
    for (int i = 0; i < text.Length;)
    {
        int end = i + 1;
        while (end < text.Length && text[end] == text[i]) end++;
        buffer.Append(text[i]).Append(end - i); // (2)
        i = end;
    }
    return buffer.Length < text.Length ? buffer.ToString() : text;
}
Dictionary<string, int> WordCount(string text)
{
    var counts = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);
    char[] separators = [' ', '\t', '\r', '\n', '.', ','];
    foreach (string word in text.Split(separators, StringSplitOptions.RemoveEmptyEntries))
        counts[word] = counts.GetValueOrDefault(word) + 1;
    return counts;
}
bool IsPrime(int value)
{
    if (value < 2) return false;
    for (int divisor = 2; (long)divisor * divisor <= value; divisor++) // (3)
        if (value % divisor == 0) return false;
    return true;
}

التعقيد: FizzBuzz O(n) iterator steps وO(1) iterator state غير strings الناتجة؛ مجموع أحجام الأرقام يتأثر بعدد digits. Compression O(n) وقت وspace. WordCount expected O(L) وقت وO(L) مساحة مع Split، L طول النص. Prime O(√value) وقت وO(1) space. اختبر 0 و1 و2 وsquare زي 49؛ tokenizer ده مش تحليل لغوي كامل.

#14. Reverse list وcycle وmiddle14. Reverse a list, detect cycles and find the middle

المسائل: اقلب singly linked list، واكشف cycle، ورجّع middle. في even length نختار الـ middle التاني. 1 → 2 → 3 تتقلب لـ3 → 2 → 1. Reverse وMiddle بيفترضوا قائمة من غير cycle. الفكرة: حفظ next قبل تغيير السهم، أو slow/fast pointers.

public sealed class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}
ListNode? ReverseList(ListNode? head)
{
    ListNode? previous = null;
    while (head is not null)
    {
        var next = head.Next; // (1)
        head.Next = previous;
        previous = head;
        head = next;
    }
    return previous;
}
bool HasCycle(ListNode? head)
{
    ListNode? slow = head, fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        if (ReferenceEquals(slow, fast)) return true; // (2)
    }
    return false;
}
ListNode? Middle(ListNode? head)
{
    ListNode? slow = head, fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
    }
    return slow; // (3)
}

التعقيد: التلاتة O(n) وقت وO(1) space. Cycle detection n عدد nodes المختلفة اللي يمكن الوصول لها. Reverse recursive محتاجة O(n) stack، فمش أحسن مساحة. اختبر self-cycle وعنصر واحد وقائمتين بطول فردي وزوجي.

#15. Merge two sorted lists

المسألة: ادمج قائمتين مرتبتين ascending في قائمة واحدة؛ [1,3] و[2,4] → [1,2,3,4]. القائمتان acyclic ومش بيشاركوا nodes. الفكرة: كل مرة اختار أصغر head، مع dummy لتجنب special case أول node.

// Uses ListNode from problem 14; reuses and rewires input nodes.
ListNode? MergeTwoLists(ListNode? first, ListNode? second)
{
    var dummy = new ListNode(0);
    var tail = dummy;
    while (first is not null && second is not null)
    {
        if (first.Value <= second.Value)
        {
            tail.Next = first; first = first.Next; // (1)
        }
        else { tail.Next = second; second = second.Next; }
        tail = tail.Next;
    }
    tail.Next = first ?? second; // (2)
    return dummy.Next;
}

التعقيد: O(n + m) وقت وO(1) extra؛ الحل بيعدل links الأصلية. لو مطلوب input immutable، انسخ nodes بـO(n + m) output space. اختبر null للقائمتين وواحدة فاضية وقيم متساوية.

#16. LRU cache16. An LRU cache

المسألة: cache بسعة موجبة؛ get وput expected O(1)، وعند الامتلاء نحذف الأقل استخداماً مؤخراً. الفكرة: Dictionary يوصلنا للـ node، وdoubly linked list تحفظ recency. بعد put A وB، ثم get A، ثم put C بسعة 2، يتشال B.

public sealed class LruCache<TKey, TValue> where TKey : notnull
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>> _map =
        new();
    private readonly LinkedList<(TKey Key, TValue Value)> _order = new();
    public LruCache(int capacity)
    {
        ArgumentOutOfRangeException.ThrowIfNegativeOrZero(capacity);
        _capacity = capacity;
    }
    public bool TryGet(TKey key, out TValue value)
    {
        if (!_map.TryGetValue(key, out var node))
        {
            value = default!;
            return false;
        }
        _order.Remove(node);
        _order.AddFirst(node); // (1)
        value = node.Value.Value;
        return true;
    }
    public void Put(TKey key, TValue value)
    {
        if (_map.TryGetValue(key, out var existing))
        {
            existing.Value = (key, value);
            _order.Remove(existing);
            _order.AddFirst(existing);
            return;
        }
        if (_map.Count == _capacity)
        {
            var oldest = _order.Last!;
            _map.Remove(oldest.Value.Key);
            _order.RemoveLast(); // (2)
        }
        _map[key] = _order.AddFirst((key, value));
    }
}

التعقيد: expected O(1) لكل عملية، وO(capacity) مساحة مع keys ثابتة hashing. مش thread-safe؛ لو shared احمِ العمليتين بنفس lock. مفيش TTL أو size-by-bytes. استخدم cache library في التطبيق حسب متطلبات eviction؛ ماتفرضش إنها exact LRU. اختبر update existing وcapacity 1 وmiss وinvalid capacity.

#17. Queue باثنين stacks وMin Stack17. Queue using two stacks and a Min Stack

المسائل: اعمل FIFO باستخدام stacks، وstack فيها minimum الحالي في O(1). الفكرة: اقلب incoming لـoutgoing بس لما outgoing تفضى؛ وفي MinStack خزّن minimum لحد كل entry. مثال push 3 ثم1 ثم2 يدي minimum 1 حتى بعد pop 2.

public sealed class StackQueue<T>
{
    private readonly Stack<T> _incoming = new(), _outgoing = new();
    public void Enqueue(T value) => _incoming.Push(value);
    public T Dequeue()
    {
        if (_outgoing.Count == 0)
            while (_incoming.Count > 0) _outgoing.Push(_incoming.Pop()); // (1)
        return _outgoing.Pop();
    }
}
public sealed class MinStack
{
    private readonly Stack<(int Value, int Minimum)> _entries = new();
    public void Push(int value) => _entries.Push((value,
        _entries.Count == 0 ? value : Math.Min(value, _entries.Peek().Minimum))); // (2)
    public int Pop() => _entries.Pop().Value;
    public int GetMin() => _entries.Peek().Minimum;
}

التعقيد: queue operations O(1) amortized، لكن dequeue واحدة ممكن O(n). MinStack push O(1) amortized للـ backing storage، وpop وGetMin O(1). الاتنين O(n) مساحة ومش thread-safe. Empty pop أوdequeue أوminimum ترمي InvalidOperationException؛ ممكن تعرض Try API لو العقد عايز.

#18. Kth largest وmerge K sorted sequences18. Kth largest and merging K sorted sequences

المسائل: لاقي kth largest مع حساب duplicates؛ وادمج k arrays مرتبة. [3,2,1,5,6,4], k=2 → 5. الفكرة: heap بحجم k للأكبر، أو heap فيها أصغر عنصر لسه مستني من كل sequence.

int KthLargest(int[] values, int k)
{
    if (k < 1 || k > values.Length) throw new ArgumentOutOfRangeException(nameof(k));
    var heap = new PriorityQueue<int, int>();
    foreach (int value in values)
    {
        heap.Enqueue(value, value);
        if (heap.Count > k) heap.Dequeue(); // (1)
    }
    return heap.Peek();
}
IEnumerable<int> MergeKSorted(int[][] sequences)
{
    var heap = new PriorityQueue<(int Row, int Index), int>();
    for (int row = 0; row < sequences.Length; row++)
        if (sequences[row].Length > 0) heap.Enqueue((row, 0), sequences[row][0]);
    while (heap.TryDequeue(out var item, out int value))
    {
        yield return value; // (2)
        int next = item.Index + 1;
        if (next < sequences[item.Row].Length)
            heap.Enqueue((item.Row, next), sequences[item.Row][next]);
    }
}

التعقيد: kth O(n log(k + 1)) وقت وO(k) مساحة. Merge O(k + N log(k + 1)) وقت وO(k) auxiliary غير الـ output لو اتحوّل لـlist، N إجمالي العناصر. Quickselect بديل expected O(n) للـ kth لكنه عادة يعدّل input وممكن worst O(n²). اختبر empty sequences وduplicates وinvalid k.

#19. Depth وinvert وlevel order وvalidate BST19. Depth, inversion, level order and BST validation

المسائل: احسب أقصى depth، واقلب left وright، واعرض كل مستوى، وتأكد من strict BST من غير duplicates. Tree لازم acyclic ومن غير shared child nodes. الفكرة: recursion للـ subtrees، وqueue للـ levels، وحدود موروثة لكل subtree. شجرة root 2 وأطفال 1 و3: depth 2 وlevels [[2],[1,3]].

public sealed class TreeNode(int value)
{
    public int Value = value;
    public TreeNode? Left, Right;
}
int MaxDepth(TreeNode? node) => node is null ? 0
    : 1 + Math.Max(MaxDepth(node.Left), MaxDepth(node.Right));
TreeNode? Invert(TreeNode? node)
{
    if (node is null) return null;
    (node.Left, node.Right) = (Invert(node.Right), Invert(node.Left)); // (1)
    return node;
}
List<List<int>> LevelOrder(TreeNode? root)
{
    var result = new List<List<int>>();
    if (root is null) return result;
    var queue = new Queue<TreeNode>([root]);
    while (queue.Count > 0)
    {
        var level = new List<int>();
        for (int remaining = queue.Count; remaining > 0; remaining--) // (2)
        {
            var node = queue.Dequeue();
            level.Add(node.Value);
            if (node.Left is not null) queue.Enqueue(node.Left);
            if (node.Right is not null) queue.Enqueue(node.Right);
        }
        result.Add(level);
    }
    return result;
}
bool IsValidBst(TreeNode? node, long minimum = long.MinValue,
    long maximum = long.MaxValue) => node is null
    || (node.Value > minimum && node.Value < maximum // (3)
        && IsValidBst(node.Left, minimum, node.Value)
        && IsValidBst(node.Right, node.Value, maximum));

التعقيد: كل عملية O(n) وقت. Recursion O(h) stack، وlevel order O(w) queue غير O(n) output، w أقصى عرض. اختبر null وskewed tree وdescendant يخالف جد أعلى. للعمق الكبير استخدم iterative traversal.

#20. Number of islands

المسألة: عدّ مجموعات '1' المتصلة أفقياً أو رأسياً في rectangular grid من '0' و'1'. القُطري مش اتصال. ["110","010","001"] → 2. الفكرة: كل أرض لسه ماتزارتش تبدأ جزيرة، واعمل flood fill. بنستخدم BFS بدل recursion العميق.

int NumberOfIslands(char[][] grid)
{
    if (grid.Length == 0) return 0;
    int rows = grid.Length, columns = grid[0].Length, islands = 0;
    (int Dr, int Dc)[] directions = [(1, 0), (-1, 0), (0, 1), (0, -1)];
    var queue = new Queue<(int Row, int Column)>();
    for (int row = 0; row < rows; row++)
        for (int column = 0; column < columns; column++)
        {
            if (grid[row][column] != '1') continue;
            islands++;
            grid[row][column] = '0';
            queue.Enqueue((row, column)); // (1)
            while (queue.TryDequeue(out var cell))
                foreach (var (dr, dc) in directions)
                {
                    int r = cell.Row + dr, c = cell.Column + dc;
                    if (r < 0 || c < 0 || r >= rows || c >= columns) continue;
                    if (grid[r][c] != '1') continue;
                    grid[r][c] = '0'; // (2)
                    queue.Enqueue((r, c));
                }
        }
    return islands;
}

التعقيد: O(RC) وقت وO(RC) worst-case queue space. بيعدل grid؛ لو ده ممنوع استخدم visited بـO(RC) مساحة إضافية. اختبر فاضية، وصف فاضي، وكله مية، وكله أرض. Jagged rows محتاجة validation أو contract تاني.

#21. Climbing stairs وHouse Robber21. Climbing stairs and House Robber

المسائل: عدد طرق صعود n درجات بخطوة أو اثنين؛ وأكبر مجموع non-adjacent values غير سالبة. التانية معروفة باسم House Robber، وممكن تمثل اختيار bookings من slots غير متجاورة. n=3 → 3، و[2,7,9,3,1] → 12. الفكرة: state تعتمد على آخر حالتين.

long ClimbStairs(int n)
{
    if (n < 0 || n > 91) throw new ArgumentOutOfRangeException(nameof(n));
    long previous = 1, current = 1; // ways(0), ways(1)
    for (int i = 2; i <= n; i++)
        (previous, current) = (current, checked(previous + current)); // (1)
    return current;
}
long MaxNonAdjacent(int[] values)
{
    long previous2 = 0, previous1 = 0;
    foreach (int value in values)
        (previous2, previous1) =
            (previous1, Math.Max(previous1, previous2 + value)); // (2)
    return previous1;
}

التعقيد: O(n) وقت وO(1) space، بدل recursion أُسية من غير memoization. اختبر n=0 و1 وempty values وsingle value. لو مطلوب reconstruct الاختيارات، احتفظ بالقرارات أو states بمساحة O(n).

#22. Coin change وlongest common subsequence22. Coin change and longest common subsequence

المسائل: أقل عدد عملات موجبة لتكوين amount غير سالب أو -1؛ وطول أطول subsequence مشتركة بين نصين، مش شرط متصلة. [1,3,4], 6 → 2، وabcde وace → 3. الفكرة: عرّف state وbase cases وrecurrence قبل الـ loops.

int CoinChange(int[] coins, int amount)
{
    ArgumentOutOfRangeException.ThrowIfNegative(amount);
    if (coins.Any(coin => coin <= 0)) throw new ArgumentException("Positive coins only");
    var best = new int[checked(amount + 1)];
    Array.Fill(best, int.MaxValue);
    best[0] = 0;
    for (int value = 1; value <= amount; value++)
        foreach (int coin in coins)
            if (coin <= value && best[value - coin] != int.MaxValue)
                best[value] = Math.Min(best[value], best[value - coin] + 1); // (1)
    return best[amount] == int.MaxValue ? -1 : best[amount];
}
int Lcs(string first, string second)
{
    var length = new int[first.Length + 1, second.Length + 1];
    for (int i = 1; i <= first.Length; i++)
        for (int j = 1; j <= second.Length; j++)
            length[i, j] = first[i - 1] == second[j - 1]
                ? length[i - 1, j - 1] + 1 // (2)
                : Math.Max(length[i - 1, j], length[i, j - 1]);
    return length[first.Length, second.Length];
}

التعقيد: Coin change O(amount × c) وقت وO(amount) space؛ array لازم تناسب memory، والوقت pseudo-polynomial في تمثيل amount. LCS O(nm) وقت وspace، وممكن O(min(n,m)) space لو عايز الطول فقط. اختبر amount=0 وunreachable وempty strings؛ greedy مش مضمون للعملات العامة.

#23. Rate limiter وdebounce وretry23. Rate limiting, debounce and retry

المسائل: اسمح بحد أقصى N requests لكل client في rolling window؛ نفّذ آخر قيمة بعد فترة هدوء؛ وأعد محاولة read مؤقت الفشل بحد معلوم. الفكرة: timestamp queue، وcancellation للانتظار السابق، وbounded backoff مع jitter. مثال limiter بسعة 2 يرفض الطلب التالت في نفس النافذة. Debounce بيقلل التكرار أثناء burst؛ مش rate limiter.

// Also requires System.Collections.Concurrent.
public sealed class SlidingWindowLimiter
{
    private readonly int _limit;
    private readonly TimeSpan _window;
    private readonly TimeProvider _clock;
    private readonly ConcurrentDictionary<string, Queue<long>> _hits = new();
    public SlidingWindowLimiter(int limit, TimeSpan window, TimeProvider clock)
    {
        ArgumentOutOfRangeException.ThrowIfNegativeOrZero(limit);
        if (window <= TimeSpan.Zero) throw new ArgumentOutOfRangeException(nameof(window));
        _limit = limit; _window = window; _clock = clock;
    }
    public bool Allow(string client)
    {
        var hits = _hits.GetOrAdd(client, _ => new Queue<long>());
        lock (hits) // (1)
        {
            long now = _clock.GetTimestamp();
            while (hits.Count > 0 && _clock.GetElapsedTime(hits.Peek(), now) >= _window)
                hits.Dequeue();
            if (hits.Count >= _limit) return false;
            hits.Enqueue(now);
            return true;
        }
    }
}

// Single-caller async stream; inputs yield promptly and honor cancellation.
async Task DebounceAsync<T>(IAsyncEnumerable<T> source, TimeSpan quiet,
    Func<T, CancellationToken, Task> apply, CancellationToken ct)
{
    if (quiet <= TimeSpan.Zero) throw new ArgumentOutOfRangeException(nameof(quiet));
    using var stop = CancellationTokenSource.CreateLinkedTokenSource(ct);
    await using var iterator = source.GetAsyncEnumerator(stop.Token);
    Task<bool>? next = null;
    try
    {
        next = iterator.MoveNextAsync().AsTask();
        while (await next)
        {
            T latest = iterator.Current;
            next = iterator.MoveNextAsync().AsTask();
            while (true)
            {
                using var timer = CancellationTokenSource.CreateLinkedTokenSource(ct);
                Task delay = Task.Delay(quiet, timer.Token);
                Task winner = await Task.WhenAny(next, delay); // (2)
                if (winner == delay)
                {
                    await delay; // observe cancellation before invoking the handler
                    await apply(latest, ct);
                    break;
                }
                if (!await next)
                {
                    await delay; // finish the existing quiet period, without restarting it
                    await apply(latest, ct); // flush final value after quiet period
                    return;
                }
                timer.Cancel();
                latest = iterator.Current;
                next = iterator.MoveNextAsync().AsTask();
            }
        }
    }
    finally
    {
        stop.Cancel();
        if (next is not null)
        {
            try { await next; }
            catch (OperationCanceledException) when (stop.IsCancellationRequested) { }
        }
    }
}

// The delegate must classify failures: true only for safe transient retries.
async Task<T> RetryReadAsync<T>(Func<CancellationToken, Task<T>> read,
    Func<Exception, bool> isTransient, int attempts, CancellationToken ct)
{
    if (attempts < 1 || attempts > 8)
        throw new ArgumentOutOfRangeException(nameof(attempts));
    for (int attempt = 1; ; attempt++)
    {
        ct.ThrowIfCancellationRequested();
        try { return await read(ct); }
        catch (Exception error) when (error is not OperationCanceledException
            && attempt < attempts && isTransient(error)) // (3)
        {
            int milliseconds = 100 * (1 << (attempt - 1)) + Random.Shared.Next(100);
            await Task.Delay(milliseconds, ct);
        }
    }
}

التعقيد: limiter expected amortized O(1) لكل call، وO(C × limit) memory؛ call واحدة ممكن تشيل O(limit) timestamps. المثال مش بينضف inactive clients، فمش مناسب client IDs بلا حد؛ cleanup محتاج تنسيق يمنع إنشاء queues متوازية لنفس المفتاح. Debounce O(n) scheduling وO(1) extra غير buffering المصدر والـ handler. Retry O(attempts × تكلفة read) مع delays وO(1) state.

دي تمارين مش بدائل جاهزة للبنية التشغيلية: limiter محلي مش موزّع، وRedis fixed counter مش نفس rolling window الدقيق. للتطبيق قيّم ASP.NET Core rate limiting، وdebounce library أوpipeline لها lifecycle واضح، وMicrosoft.Extensions.Http.Resilience للـ HTTP مع سياسة متوافقة مع idempotency. اختبر boundary الوقت وcancellation وtransient ثم نجاح وpermanent failure.

#24. توزيع خصم من غير فقد قروش24. Allocate a discount without losing cents

المسألة: وزّع خصم على invoice lines بنسبة قيمها، والمجموع لازم يساوي الخصم بالظبط. كل الأرقام في المثال بالسنت: [100,200,300], 100 → [17,33,50]. الفكرة: largest remainder بوحدات العملة الصغرى بدل تصحيح كامل الفرق في سطر واحد؛ ده كمان يمنع سهم سالب في حالات التقريب. العقد: كل line والخصم non-negative بوحدات cents صحيحة ومجموعهم يناسب long، والخصم لا يزيد عن الإجمالي.

// Requires System.Numerics for exact integer products.
long[] AllocateCents(long[] lines, long discount)
{
    if (discount < 0 || lines.Any(value => value < 0))
        throw new ArgumentException("Non-negative amounts required");
    long total = 0;
    foreach (long value in lines) total = checked(total + value);
    if (discount > total) throw new ArgumentException("Discount exceeds total");
    var shares = new long[lines.Length];
    if (total == 0) return shares;
    var remainders = new System.Numerics.BigInteger[lines.Length];
    long allocated = 0;
    for (int i = 0; i < lines.Length; i++)
    {
        var product = (System.Numerics.BigInteger)discount * lines[i];
        shares[i] = (long)System.Numerics.BigInteger.DivRem(
            product, total, out remainders[i]); // (1)
        allocated += shares[i];
    }
    int[] order = Enumerable.Range(0, lines.Length)
        .OrderByDescending(i => remainders[i]).ThenBy(i => i).ToArray();
    long remaining = discount - allocated;
    for (int i = 0; i < remaining; i++) shares[order[i]]++; // (2)
    return shares;
}

التعقيد: O(n log n) وقت وO(n) مساحة؛ المنتجات هنا bounded بضرب longين. استخدم decimal على حدود عرض وإدخال الفلوس مع conversion متحقق؛ cents تفترض عملة بدقتين، مش كل العملات. اختبر zero total وdiscount كامل وكثير من السطور الصغيرة، وتأكد إن المجموع صحيح وكل share بين صفر وقيمة سطرها. سياسة التوزيع قرار business لازم يتوثق.

#25. Group orders وduplicates في ملف كبير25. Group orders and duplicate keys in a large file

المسائل: أعلى 3 customers بإيراد paid orders في آخر 30 يوم لحد now؛ واكشف تكرار SKUs من ملف أكبر من RAM. الفكرة: filter ثمgroup وaggregate وsort؛ أوstream مع set للمفاتيح. مثال paid orders بقيم 10 و20 لنفس customer يتجمعوا 30. الملف هنا key واحد في كل سطر، مش CSV عام.

public record Order(int CustomerId, DateTimeOffset CreatedAt,
    string Status, decimal Total);
public record CustomerRevenue(int CustomerId, decimal Revenue);
List<CustomerRevenue> TopCustomers(IEnumerable<Order> orders, DateTimeOffset now) =>
    orders.Where(order => order.Status == "Paid"
        && order.CreatedAt >= now.AddDays(-30) && order.CreatedAt <= now)
    .GroupBy(order => order.CustomerId)
    .Select(group => new CustomerRevenue(group.Key, group.Sum(order => order.Total)))
    .OrderByDescending(customer => customer.Revenue)
    .ThenBy(customer => customer.CustomerId).Take(3).ToList(); // (1)

async IAsyncEnumerable<string> DuplicateSkus(string path,
    [System.Runtime.CompilerServices.EnumeratorCancellation] CancellationToken ct = default)
{
    var seen = new HashSet<string>(StringComparer.Ordinal);
    using var reader = new StreamReader(path);
    while (await reader.ReadLineAsync(ct) is { } sku)
        if (!seen.Add(sku)) yield return sku; // (2)
}

التعقيد: group query O(n + u log u) وقت وO(n + u) مساحة بسبب LINQ GroupBy اللي بيحتفظ بالعناصر. Streaming expected O(B) processing لعدد الحروف B، لكنه لسه بيحتفظ بكل distinct key: O(total distinct-key characters) memory. لو مش بتكفي، external merge sort أوhash partition بhash ثابت واتفاق equality موحد ثم عالج كل partition؛ skew ممكن يحتاج إعادة تقسيم. Bloom filter لوحده مش exact answer. CSV الحقيقي محتاج parser يدعم quotes وembedded newlines، وحدود طول السطر لازم تتحدد.

#26. Rotate matrix26. Rotate a matrix

المسألة: لف n×n matrix تسعين درجة clockwise في مكانها؛ [[1,2],[3,4]] → [[3,1],[4,2]]. الفكرة: transpose، وبعدها reverse لكل row. لو rectangular مش square، الناتج dimensions مختلفة ومحتاج contract أوallocation تاني.

void RotateMatrix(int[][] matrix)
{
    int n = matrix.Length;
    if (matrix.Any(row => row.Length != n))
        throw new ArgumentException("Square matrix required");
    for (int row = 0; row < n; row++)
        for (int column = row + 1; column < n; column++)
            (matrix[row][column], matrix[column][row]) =
                (matrix[column][row], matrix[row][column]); // (1)
    foreach (var row in matrix) Array.Reverse(row); // (2)
}

التعقيد: O(n²) وقت وO(1) extra. بيعدل input، ويفترض rows مستقلة مش نفس array متكررة. اختبر 0×0 و1×1 و3×3؛ counterclockwise محتاجة ترتيب عكس مختلف.

#27. Subarray sum equals K

المسألة: احسب عدد nonempty contiguous subarrays مجموعها k، مع السماح بـnegatives وzeros. [1,1,1], 2 → 2، و[0,0], 0 → 3. الفكرة: لو currentPrefix - previousPrefix = k، يبقى كل ظهور سابق لـcurrentPrefix-k بداية صالحة.

long SubarraySum(int[] values, long k)
{
    var frequency = new Dictionary<long, long> { [0] = 1 }; // (1)
    long prefix = 0, count = 0;
    foreach (int value in values)
    {
        prefix += value;
        // (2) A difference outside long cannot be a stored prefix.
        bool safe = k >= 0 ? prefix >= long.MinValue + k
            : prefix <= long.MaxValue + k;
        if (safe) count += frequency.GetValueOrDefault(prefix - k);
        frequency[prefix] = frequency.GetValueOrDefault(prefix) + 1; // (3)
    }
    return count;
}

التعقيد: expected O(n) وقت وO(n) مساحة، بدل O(n²) باستخدام كل بداية ونهاية. long count يشيل عدد subarrays لمصفوفة ذات int length. Sliding window المعتادة مش صحيحة مع negatives. اختبر empty، وk سالب، وzeros، وprefix مكرر.

#28. Course schedule

المسألة: عندك courses من 0 لـn-1، وكل pair [course, prerequisite] معناها الثاني لازم يسبق الأول. هل ينفع تخلص الكل؟ n=2, [[1,0]] → true؛ إضافة [0,1] تعمل cycle وتخليها false. الفكرة: Kahn topological sort على directed graph.

bool CanFinish(int n, int[][] prerequisites)
{
    ArgumentOutOfRangeException.ThrowIfNegative(n);
    var graph = Enumerable.Range(0, n).Select(_ => new List<int>()).ToArray();
    var degree = new int[n];
    foreach (var pair in prerequisites)
    {
        int course = pair[0], prerequisite = pair[1];
        graph[prerequisite].Add(course); // (1)
        degree[course]++;
    }
    var ready = new Queue<int>();
    for (int course = 0; course < n; course++)
        if (degree[course] == 0) ready.Enqueue(course);
    int completed = 0;
    while (ready.TryDequeue(out int course))
    {
        completed++;
        foreach (int dependent in graph[course])
            if (--degree[dependent] == 0) ready.Enqueue(dependent); // (2)
    }
    return completed == n; // (3)
}

التعقيد: O(V + E) وقت وspace شامل graph. n=0 يرجع true لو مفيش edges. اختبر self-loop وdisconnected courses وduplicate pairs. لو مطلوب الترتيب نفسه، خزّن nodes الخارجة؛ الترتيب مش شرط وحيد.