The base class library members an interview uses every day. Grouped by job, with the signature, each parameter, several ways to call it, and the trap that catches people.
The BCL (the standard .NET class library) is huge. An interview touches maybe a hundred members of it. This page lists those, grouped by the job they do. Each entry gives the signature, what each parameter means, a few real call forms, and the trap. Each group ends with a compiled demo that the test suite runs, so every claimed result is checked.
T is a type parameter. ? after a type means it may be null. A parameter with = value is optional. this before the first parameter marks an extension method, called as source.Method(...).Learn these first. They cover most lines of interview C#.
Static methods on System.Math, plus the integer facts that differ from Python.
Distance from zero. Returns the same type it gets.
value: any signed number type.Math.Abs(-5) // 5
Math.Abs(-2.5) // 2.5
Math.Abs(-7L) // 7L, a long stays a long
Math.Abs(int.MinValue) // throws OverflowException
Math.Abs((long)int.MinValue) // 2147483648, widen first
Trap. int.MinValue has no positive twin in 32 bits. Math.Abs throws. A hand-written x < 0 ? -x : x silently returns the same negative number.
The larger or smaller of exactly two numbers of the same type.
a, b: two values. Mixed types widen: int and long give a long.Math.Max(3, 9) // 9
Math.Min(3, 9) // 3
best = Math.Max(best, current); // the running-max idiom
Math.Max(Math.Max(a, b), c) // three values: nest, or use [a, b, c].Max()
Math.Max(1.0, double.NaN) // NaN: NaN wins
Trap. Only two arguments. For a collection use LINQ Max(), which throws on an empty sequence.
Pins a value into the range min to max, both ends included.
value: the input.min, max: the bounds. min greater than max throws ArgumentException.Math.Clamp(15, 0, 10) // 10
Math.Clamp(-3, 0, 10) // 0
Math.Clamp(0.5, 0.0, 1.0) // 0.5
int col = Math.Clamp(c, 0, width - 1); // keep a grid index in bounds
Power and square root. Both work on double only.
x, y: base and exponent.d: the value. A negative value gives NaN, not an exception.Math.Pow(2, 10) // 1024.0, a double
(long)Math.Pow(3, 39) // may be off by one: doubles hold 53 bits
Math.Sqrt(16) // 4.0
Math.Sqrt(-1) // NaN
Math.Cbrt(27) // 3.0
1 << 10 // 1024, exact, for powers of two
Trap. There is no integer power. Math.Pow rounds for big results. Use repeated squaring on long, or BigInteger.Pow, when you need exact digits.
Integer division truncates toward zero. The remainder takes the sign of the dividend.
a: the dividend. b: the divisor. b == 0 throws DivideByZeroException for ints.7 / 2 // 3
-7 / 2 // -3, Python gives -4
-7 % 3 // -1, Python gives 2
((-7 % 3) + 3) % 3 // 2, a always-positive mod
Math.DivRem(-7, 2) // (-3, -1), a tuple
(a + b - 1) / b // ceiling division for positive a and b
Trap. x % 2 == 1 is false for negative odd numbers. Test x % 2 != 0.
Rounds to the nearest value. Halves go to the even neighbour by default.
x: the value. A decimal overload exists too.digits: decimal places to keep.mode: MidpointRounding.AwayFromZero gives school rounding.Math.Round(2.5) // 2, banker's rounding
Math.Round(3.5) // 4
Math.Round(2.5, MidpointRounding.AwayFromZero) // 3
Math.Round(1.2345, 2) // 1.23
Math.Floor(-2.5) // -3
Math.Ceiling(2.1) // 3
Math.Truncate(-2.9) // -2
Trap. (int)2.9 is 2 and (int)-2.9 is -2. A cast truncates. It never rounds.
Logarithms and the exponential. Math.Log(x, b) takes any base.
x: positive for a real answer. 0 gives negative infinity. Below 0 gives NaN.Math.Log(Math.E) // 1.0, natural log
Math.Log2(1024) // 10.0
Math.Log10(1000) // 3.0
Math.Log(8, 2) // 3.0, any base
Math.Exp(1) // 2.718281828459045
The limits of each type. Use them as sentinels for “not found yet”.
int.MaxValue // 2147483647, about 2.1e9
long.MaxValue // 9223372036854775807, about 9.2e18
int.MaxValue + 1 // -2147483648: wraps silently
checked(int.MaxValue + 1) // throws OverflowException
int best = int.MaxValue; // a minimum search starts here
double.PositiveInfinity // a sentinel that survives + 1
Trap. int.MaxValue + edgeWeight in Dijkstra wraps to a negative number. Use long, or int.MaxValue / 2 as infinity.
Single-instruction bit tricks in System.Numerics.
v: an unsigned value. Cast an int with (uint).BitOperations.PopCount(0b1011u) // 3 set bits
BitOperations.Log2(1000u) // 9, the floor of log2
BitOperations.IsPow2(64) // true
BitOperations.TrailingZeroCount(8) // 3
int.PopCount(7) // 3, the generic-math version on int
public static class MathDemo
{
/// <summary>Python-style floor division: rounds toward negative infinity. O(1).</summary>
/// <param name="a">Dividend.</param>
/// <param name="b">Divisor, not zero.</param>
/// <returns>The floor of a / b.</returns>
/// <example>FloorDiv(-7, 2) gives -4, while -7 / 2 gives -3</example>
public static int FloorDiv(int a, int b)
{
int q = a / b; // C# truncates toward zero
// Signs differ and there is a remainder: truncation went up, so step down by 1.
if ((a % b != 0) && ((a < 0) != (b < 0)))
q--;
return q;
}
/// <summary>A modulo that is never negative for a positive m. O(1).</summary>
/// <param name="a">Any int.</param>
/// <param name="m">Modulus, above 0.</param>
/// <returns>A value from 0 to m - 1.</returns>
/// <example>Mod(-7, 3) gives 2, while -7 % 3 gives -1</example>
public static int Mod(int a, int m) => ((a % m) + m) % m; // + m lifts a negative remainder
/// <summary>Ceiling division for non-negative a and positive b. O(1).</summary>
/// <param name="a">Dividend, 0 or more.</param>
/// <param name="b">Divisor, above 0.</param>
/// <returns>The smallest q with q * b at least a.</returns>
/// <example>CeilDiv(7, 2) gives 4</example>
public static int CeilDiv(int a, int b) => (a + b - 1) / b; // b - 1: pushes any remainder up
/// <summary>Exact integer power by repeated squaring. O(log exponent).</summary>
/// <param name="b">The base.</param>
/// <param name="exponent">0 or more.</param>
/// <returns>b to the exponent. Throws on long overflow.</returns>
/// <example>IntPow(3, 4) gives 81</example>
public static long IntPow(long b, int exponent)
{
ArgumentOutOfRangeException.ThrowIfNegative(exponent);
long result = 1; // 1: the empty product
// Invariant: result * b^exponent equals the original b^exponent.
while (exponent > 0)
{
if ((exponent & 1) == 1) // & 1: the lowest bit is set
result = checked(result * b);
exponent >>= 1; // >> 1: halve the exponent
if (exponent > 0)
b = checked(b * b);
}
return result;
}
/// <summary>Absolute value that cannot overflow, by widening first. O(1).</summary>
/// <param name="x">Any int, including int.MinValue.</param>
/// <returns>|x| as a long.</returns>
/// <example>SafeAbs(int.MinValue) gives 2147483648</example>
public static long SafeAbs(int x) => Math.Abs((long)x);
/// <summary>Rounds half away from zero, the school rule. O(1).</summary>
/// <param name="x">The value.</param>
/// <returns>The nearest integer, halves away from zero.</returns>
/// <example>RoundHalfUp(2.5) gives 3, while Math.Round(2.5) gives 2</example>
public static double RoundHalfUp(double x) => Math.Round(x, MidpointRounding.AwayFromZero);
}
Turning text into numbers and back. Four families: Parse, TryParse, Convert, and casts.
Text to int. Throws on bad input. long.Parse, double.Parse and decimal.Parse work the same way.
s: the text. Leading and trailing spaces are allowed. Null throws ArgumentNullException.provider: the culture. Pass CultureInfo.InvariantCulture for decimals.int.Parse("42") // 42
int.Parse(" -7 ") // -7, spaces are fine
int.Parse("3.0") // FormatException
int.Parse("9999999999") // OverflowException
long.Parse("9999999999") // fine
int.Parse("ff", NumberStyles.HexNumber) // 255
Text to int with no exception. Returns false on bad input and sets result to 0.
s: the text. Null is allowed and returns false.result: an out variable, often declared inline.int.TryParse("42", out int n) // true, n = 42
int.TryParse("abc", out int bad) // false, bad = 0
if (!int.TryParse(token, out var v)) continue; // skip bad tokens
double.TryParse("1.5", NumberStyles.Float, CultureInfo.InvariantCulture, out double d)
Use it for. Any input you did not produce yourself. Exceptions cost microseconds each. In a loop over a million rows that adds up.
Converts many types to int. Has a base overload for 2, 8, 10 and 16.
value: a string, double, bool, char, and more.fromBase: 2, 8, 10 or 16 only.Convert.ToInt32("101", 2) // 5
Convert.ToInt32("ff", 16) // 255
Convert.ToInt32(2.5) // 2: rounds half to even, unlike a cast
Convert.ToInt32(3.5) // 4
Convert.ToInt32((string?)null) // 0, not an exception
Convert.ToString(10, 2) // "1010"
Trap. Convert.ToInt32(2.7) is 3 but (int)2.7 is 2. Convert rounds. A cast truncates. Pick on purpose.
Number to text with a format code.
format: "D5" pads digits, "X" is hex, "F2" is two decimals, "N0" adds group separators, "P1" is a percent.5.ToString("D3") // "005"
255.ToString("X") // "FF"
255.ToString("x4") // "00ff"
3.14159.ToString("F2") // "3.14"
$"{1234567:N0}" // "1,234,567" in the invariant culture
$"{x,6}" // right-aligned in 6 columns
$"{x,-6}|" // left-aligned
Explicit casts between number types. Narrowing casts lose data with no warning.
(int)3.99 // 3, truncates
(int)-3.99 // -3
(int)3_000_000_000L // -1294967296, wraps
(double)7 / 2 // 3.5: cast first, then divide
(double)(7 / 2) // 3.0: the int division already happened
(char)('a' + 2) // 'c'
(int)'A' // 65
Trap. (double)(a / b) casts too late. Cast one operand, not the result.
A digit character to its value. The subtraction is the interview idiom.
'7' - '0' // 7, an int
(char)('0' + 7) // '7'
char.GetNumericValue('7') // 7.0, a double, and -1.0 for a non-digit
int sum = s.Sum(c => c - '0'); // digit sum of "1234" is 10
using System.Globalization;
public static class ParseDemo
{
/// <summary>Parses an int or returns a fallback. Never throws. O(length).</summary>
/// <param name="text">The text, may be null.</param>
/// <param name="fallback">Returned when the text is not a valid int.</param>
/// <returns>The parsed value or the fallback.</returns>
/// <example>ParseOr("x", -1) gives -1</example>
public static int ParseOr(string? text, int fallback) =>
int.TryParse(text, out int value) ? value : fallback;
/// <summary>Sums the digits of a numeric string. O(length).</summary>
/// <param name="digits">ASCII digits only, for example "1234".</param>
/// <returns>The digit sum.</returns>
/// <example>DigitSum("1234") gives 10</example>
public static int DigitSum(string digits) => digits.Sum(c => c - '0'); // '0' is 48
/// <summary>Binary text of a non-negative int. O(log n).</summary>
/// <param name="n">The value.</param>
/// <returns>The base-2 digits.</returns>
/// <example>ToBinary(10) gives "1010"</example>
public static string ToBinary(int n) => Convert.ToString(n, 2); // 2: the base
/// <summary>Parses hex text. O(length).</summary>
/// <param name="hex">Hex digits with no "0x" prefix.</param>
/// <returns>The value.</returns>
/// <example>FromHex("ff") gives 255</example>
public static int FromHex(string hex) => Convert.ToInt32(hex, 16); // 16: the base
/// <summary>Shows cast versus Convert on the same double. O(1).</summary>
/// <param name="x">The value.</param>
/// <returns>The cast result and the Convert result.</returns>
/// <example>CastVsConvert(2.7) gives (2, 3)</example>
public static (int Cast, int Converted) CastVsConvert(double x) =>
((int)x, Convert.ToInt32(x));
/// <summary>Formats a price the same on every machine. O(1).</summary>
/// <param name="amount">The amount.</param>
/// <returns>Two decimals, a dot separator, and grouping commas.</returns>
/// <example>Price(1234.5m) gives "1,234.50"</example>
public static string Price(decimal amount) =>
amount.ToString("N2", CultureInfo.InvariantCulture); // N2: grouping plus 2 decimals
}
Static tests on System.Char. A char is one UTF-16 code unit and also a 16-bit number.
Is this a digit? IsDigit accepts every Unicode decimal digit. IsAsciiDigit accepts only 0 to 9.
c: the character. A (string s, int index) overload also exists.char.IsDigit('7') // true
char.IsDigit('٣') // true: Arabic-Indic three
char.IsAsciiDigit('٣') // false
'٣' - '0' // 1587, garbage as a digit value
Trap. IsDigit then c - '0' breaks on non-ASCII digits. Use IsAsciiDigit (.NET 7+) when you plan to subtract.
Class tests for one character.
char.IsLetter('a') // true
char.IsLetter('é') // true: e with an accent
char.IsAsciiLetter('é') // false
char.IsLetterOrDigit('_') // false
char.IsUpper('A') // true
char.IsAsciiLetterLower('q') // true
Space, tab, newline and Unicode spaces. And punctuation marks.
char.IsWhiteSpace(' ') // true
char.IsWhiteSpace('\t') // true
char.IsPunctuation('!') // true
char.IsPunctuation('+') // false: '+' is a symbol, see char.IsSymbol
Case change for one character. Returns a new char.
char.ToUpper('a') // 'A'
char.ToLowerInvariant('Q') // 'q', same on every machine
char.ToUpper('1') // '1', unchanged
(char)(c ^ 0x20) // flips ASCII case: 0x20 is the case bit
Characters are numbers. Use that for letter counts and shifts.
'c' - 'a' // 2: the letter index
(char)('a' + 2) // 'c'
var counts = new int[26]; // 26: one slot per lowercase letter
foreach (char c in s) counts[c - 'a']++;
char next = c; next++; // 'b' when c was 'a'
Trap. 'a' + 1 is an int (98), not a char. Cast back with (char).
public static class CharDemo
{
/// <summary>Counts letters a to z, ignoring case and anything else. O(n).</summary>
/// <param name="text">Any text.</param>
/// <returns>26 counts, index 0 for 'a'.</returns>
/// <example>LetterCounts("Abba!")[0] gives 2</example>
public static int[] LetterCounts(string text)
{
var counts = new int[26]; // 26: letters a..z
foreach (char raw in text)
{
char c = char.ToLowerInvariant(raw);
if (char.IsAsciiLetterLower(c)) // skip digits, accents and punctuation
counts[c - 'a']++; // - 'a': letter to index 0..25
}
return counts;
}
/// <summary>Caesar shift of ASCII letters, keeping case. O(n).</summary>
/// <param name="text">Any text. Non-letters pass through.</param>
/// <param name="shift">Any int, negative shifts left.</param>
/// <returns>The shifted text.</returns>
/// <example>Caesar("Zz", 1) gives "Aa"</example>
public static string Caesar(string text, int shift)
{
var chars = text.ToCharArray();
for (int i = 0; i < chars.Length; i++) // i: the char being shifted
{
char c = chars[i];
if (!char.IsAsciiLetter(c)) continue;
char baseChar = char.IsUpper(c) ? 'A' : 'a';
// % 26 then + 26 then % 26: a non-negative offset for any shift.
int offset = ((c - baseChar + shift) % 26 + 26) % 26;
chars[i] = (char)(baseChar + offset);
}
return new string(chars);
}
/// <summary>Shows why IsDigit is unsafe before subtracting '0'. O(1).</summary>
/// <param name="c">The character.</param>
/// <returns>Whether IsDigit and IsAsciiDigit accept it.</returns>
/// <example>DigitTests('٣') gives (true, false)</example>
public static (bool Unicode, bool Ascii) DigitTests(char c) =>
(char.IsDigit(c), char.IsAsciiDigit(c));
}
A string is immutable. Every method that “changes” it returns a new string.
The count of UTF-16 code units, and the char at an index. Both are O(1).
"hello".Length // 5
"hello"[0] // 'h'
"hello"[^1] // 'o', the last char
"hello"[5] // IndexOutOfRangeException
s[0] = 'H'; // compile error: strings are read-only
Trap. An emoji is two chars, so "😀".Length is 2. Use StringInfo or EnumerateRunes for user-visible characters.
A copy of part of the string. The second argument is a length, not an end index.
startIndex: the first index to keep.length: how many chars. Leave it out to go to the end."interview".Substring(5) // "view"
"interview".Substring(0, 5) // "inter"
"interview"[0..5] // "inter": a range takes an END index
"interview"[^4..] // "view"
"abc".Substring(2, 5) // ArgumentOutOfRangeException
s.AsSpan(1, 3) // no copy: a ReadOnlySpan<char> view
Trap. Java habit: Substring(start, end). In C# that is Substring(start, end - start) or s[start..end]. Each call copies, so substrings in a loop are O(n²).
The first position of a char or substring, or -1.
value: a char or a string.startIndex: optional, where to start looking.type: pass StringComparison.Ordinal for plain byte-by-byte matching."banana".IndexOf('n') // 2
"banana".IndexOf('n', 3) // 4, search from index 3
"banana".LastIndexOf("an") // 3
"banana".IndexOf("x") // -1
"banana".Contains("nan") // true
"Banana".Contains("ban", StringComparison.OrdinalIgnoreCase) // true
"abc".IndexOf("") // 0: the empty string is everywhere
Trap. IndexOf(string) with no comparison uses the current culture. Results can differ by machine. Pass Ordinal. The char overload is always ordinal.
Prefix and suffix tests.
"report.csv".EndsWith(".csv") // true
"Report".StartsWith("rep", StringComparison.OrdinalIgnoreCase) // true
"abc".StartsWith('a') // true, char overload
Replaces every match. Returns a new string.
"a-b-c".Replace("-", "") // "abc"
"a-b-c".Replace('-', '+') // "a+b+c"
s.Replace("x", "y"); // BUG: result thrown away, s is unchanged
s = s.Replace("x", "y"); // correct
Removes whitespace, or the given chars, from the ends.
" hi ".Trim() // "hi"
"xxhixx".Trim('x') // "hi"
"007".TrimStart('0') // "7"
"000".TrimStart('0') // "": check for empty after
"line\r\n".TrimEnd() // "line"
Case change for a whole string. The invariant forms ignore the machine’s culture.
"Hello".ToLowerInvariant() // "hello"
"Hello".ToUpper() // "HELLO" but culture-dependent
string.Equals(a, b, StringComparison.OrdinalIgnoreCase) // compare without allocating
Trap. In Turkish culture "i".ToUpper() is a dotted capital I. Lowercasing both sides just to compare also allocates two strings. Use OrdinalIgnoreCase instead.
Cuts a string into an array at each separator.
separator: a char, a string, or an array of either. Split() with no args splits on any whitespace.options: RemoveEmptyEntries drops blanks. TrimEntries trims each piece. Combine them with |.count: optional maximum number of pieces."a,b,c".Split(',') // ["a", "b", "c"]
"a,,b".Split(',') // ["a", "", "b"]
"a,,b, c".Split(',', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries)
// ["a", "b", "c"]
" two spaces ".Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries)
// ["two", "spaces"]
"k=v=w".Split('=', 2) // ["k", "v=w"], at most 2 pieces
"a\r\nb".Split(["\r\n", "\n"], StringSplitOptions.None) // either line ending
Trap. Split(' ') on "a b" gives an empty middle piece. Add RemoveEmptyEntries when the input may have runs of spaces.
Glues values into one string with a separator between them. Calls ToString on each.
separator: a string or a char.values: any sequence, or a params list.string.Join(", ", ["a", "b", "c"]) // "a, b, c"
string.Join(',', new[] { 1, 2, 3 }) // "1,2,3", ints are fine
string.Join("", chars) // char sequence to string
string.Join(" ", words.Reverse()) // reverse word order
string.Join("-", []) // "", never null
Trap. Console.WriteLine(list) prints the type name, System.Collections.Generic.List`1[...]. Join it first.
Join with no separator. Takes up to four strings directly, or a sequence.
string.Concat("ab", "cd") // "abcd"
string.Concat(["x", "y", "z"]) // "xyz"
string.Concat(s.Reverse()) // reverse a string, char sequence works
string.Concat(Enumerable.Repeat("ab", 3)) // "ababab"
a + b + c // the compiler turns this into one Concat
Build a string from repeated chars or from a char array. Pad to a width.
new string('-', 5) // "-----"
new string(['h', 'i']) // "hi"
new string(arr, 1, 2) // 2 chars starting at index 1
"7".PadLeft(3, '0') // "007"
"ab".PadRight(4) + "|" // "ab |"
Null-safe emptiness checks.
string.IsNullOrEmpty(null) // true
string.IsNullOrEmpty("") // true
string.IsNullOrEmpty(" ") // false
string.IsNullOrWhiteSpace(" ") // true
s.Length == 0 // NullReferenceException when s is null
Equality and ordering with an explicit rule.
a == b // ordinal, case-sensitive
string.Equals("A", "a", StringComparison.OrdinalIgnoreCase) // true
string.CompareOrdinal("apple", "banana") // negative: apple sorts first
string.CompareOrdinal("Z", "a") // negative: 'Z' is 90, 'a' is 97
"a".CompareTo("B") // culture rules, avoid in algorithms
Trap. Array.Sort(strings) and OrderBy(s => s) use culture comparison by default. Pass StringComparer.Ordinal to get the byte order a test expects.
A growable char buffer in System.Text. Use it when you build a string in a loop.
Append(x): any value. Returns the builder, so calls chain.Insert(index, x) and Remove(start, length): O(n) moves.Length: settable. sb.Length-- drops the last char.var sb = new StringBuilder();
sb.Append("a").Append(1).Append(','); // "a1,"
sb.Length--; // "a1": drop the trailing comma
sb.Insert(0, '[').Append(']'); // "[a1]"
sb[1] = 'b'; // "[b1]": chars are writable
sb.AppendLine("x"); // adds "x" and a newline
string result = sb.ToString();
Trap. s += piece in a loop copies the whole string each time. That is O(n²). A builder is O(n) total.
using System.Text;
public static class StringDemo
{
/// <summary>Reverses a string. O(n).</summary>
/// <param name="s">The text, BMP characters only.</param>
/// <returns>The chars in reverse order.</returns>
/// <example>Reverse("abc") gives "cba"</example>
public static string Reverse(string s)
{
char[] chars = s.ToCharArray(); // a mutable copy
Array.Reverse(chars); // in place, O(n)
return new string(chars);
}
/// <summary>Palindrome test over letters and digits only, ignoring case. O(n).</summary>
/// <param name="s">Any text.</param>
/// <returns>True if it reads the same both ways.</returns>
/// <example>IsPalindrome("A man, a plan, a canal: Panama") gives true</example>
public static bool IsPalindrome(string s)
{
int left = 0, right = s.Length - 1; // -1: last valid index
// Invariant: s[..left] and s[(right + 1)..] already match as mirror images.
while (left < right)
{
if (!char.IsLetterOrDigit(s[left])) { left++; continue; }
if (!char.IsLetterOrDigit(s[right])) { right--; continue; }
if (char.ToLowerInvariant(s[left]) != char.ToLowerInvariant(s[right]))
return false;
left++;
right--;
}
return true;
}
/// <summary>Words separated by any run of whitespace. O(n).</summary>
/// <param name="line">The text.</param>
/// <returns>The non-empty words.</returns>
/// <example>Words(" to be ") gives ["to", "be"]</example>
public static string[] Words(string line) =>
line.Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); // null: any space
/// <summary>Reverses word order, collapsing extra spaces. O(n).</summary>
/// <param name="line">The text.</param>
/// <returns>The words in reverse, one space apart.</returns>
/// <example>ReverseWords("the sky is") gives "is sky the"</example>
public static string ReverseWords(string line) =>
string.Join(' ', Words(line).Reverse());
/// <summary>Run-length encoding with a StringBuilder. O(n).</summary>
/// <param name="s">The text.</param>
/// <returns>Each run as char then count.</returns>
/// <example>Rle("aaabcc") gives "a3b1c2"</example>
public static string Rle(string s)
{
var sb = new StringBuilder();
int i = 0;
// Invariant: s[..i] is already encoded in sb.
while (i < s.Length)
{
int j = i;
while (j < s.Length && s[j] == s[i]) j++; // j: one past the run's end
sb.Append(s[i]).Append(j - i); // j - i: the run length
i = j;
}
return sb.ToString();
}
/// <summary>Shows that Substring takes a length while a range takes an end. O(n).</summary>
/// <param name="s">The text, at least end chars long.</param>
/// <param name="start">First index.</param>
/// <param name="end">One past the last index.</param>
/// <returns>Both forms, which match.</returns>
/// <example>Slice("interview", 2, 5) gives ("ter", "ter")</example>
public static (string BySubstring, string ByRange) Slice(string s, int start, int end) =>
(s.Substring(start, end - start), s[start..end]); // end - start: the length
}
Static helpers on System.Array. Arrays are fixed size, zero-based, and reference types.
Create arrays. Every slot starts at the default: 0, false, or null.
var a = new int[5]; // [0, 0, 0, 0, 0]
int[] b = [3, 1, 2]; // collection expression, C# 12
var jagged = new int[3][]; // 3 rows, each null until you set it
for (int r = 0; r < 3; r++) jagged[r] = new int[4];
var grid = new int[3, 4]; // a true 2D block
grid[1, 2] = 7;
grid.GetLength(0) // 3 rows; GetLength(1) is 4 columns
a.Length // 5; for grid it is 12, the total
Trap. new int[3][] gives null rows. Indexing one throws NullReferenceException. Fill each row first. Most interview code uses jagged arrays because rows work with LINQ and spans.
Sorts in place. Introsort: O(n log n), and not stable.
array: the array to sort.comparison: a lambda (a, b) => int. Negative means a first.keys, items: sorts two arrays together by the keys.index, length: sort only part.Array.Sort(nums); // ascending
Array.Sort(nums, (a, b) => b.CompareTo(a)); // descending
Array.Sort(intervals, (x, y) => x[0].CompareTo(y[0])); // int[][] by start
Array.Sort(words, StringComparer.Ordinal); // byte order for strings
Array.Sort(ages, names); // names follow ages
Array.Sort(nums, 2, 3); // sort nums[2..5] only
Trap. (a, b) => a - b overflows for large values of opposite sign. Use a.CompareTo(b). Need a stable sort? Use LINQ OrderBy.
Reverses in place. O(n).
Array.Reverse(arr); // whole array
Array.Reverse(arr, 1, 3); // arr[1..4] only
arr.Reverse() // LINQ: a NEW lazy sequence, arr unchanged
arr.AsSpan().Reverse(); // span version, in place
Trap. arr.Reverse(); as a statement does nothing useful. It builds a lazy sequence and throws it away. Use Array.Reverse(arr).
Sets every slot, or a range, to one value.
var dist = new int[n];
Array.Fill(dist, int.MaxValue); // "unreached" sentinel
Array.Fill(dp, -1); // -1: "not computed yet" memo marker
Array.Fill(arr, 0, 2, 3); // arr[2..5] = 0
dist.AsSpan().Fill(7); // span version
Trap. Array.Fill(rows, new List<int>()) puts the same list in every slot. Use a loop for reference types.
Copy elements between arrays. All are shallow copies.
Array.Copy(src, dst, src.Length); // first n elements
Array.Copy(src, 1, dst, 0, 3); // src[1..4] into dst[0..3]
src.CopyTo(dst, 0); // whole src into dst at 0
int[] copy = (int[])src.Clone(); // Clone returns object: cast it
int[] copy2 = [.. src]; // spread: the modern copy
int[] part = src[1..4]; // a range on an array copies
Trap. Clone on a jagged array copies the outer array only. The rows are shared.
Searches a sorted array in O(log n). Returns the index, or a negative number when absent.
array: sorted ascending by the same comparer.~result is the insertion point.int[] a = [1, 3, 5];
Array.BinarySearch(a, 5) // 2
Array.BinarySearch(a, 4) // -3
~Array.BinarySearch(a, 4) // 2: where 4 would go
int i = Array.BinarySearch(a, x);
int insertAt = i >= 0 ? i : ~i; // bisect-style position
list.BinarySearch(x) // same rules on List<T>
Trap. With duplicates it returns any matching index, not the first. Write your own lower bound when the first or last match matters.
Linear searches and a typed map. O(n).
Array.IndexOf(a, 3) // index or -1
Array.FindIndex(a, x => x > 2) // first match or -1
Array.Exists(a, x => x < 0) // true if any matches
int[] nums = Array.ConvertAll(parts, int.Parse); // string[] to int[]
Array.Resize(ref a, 10); // new array, old values copied
public static class ArrayDemo
{
/// <summary>Sorts intervals by start, then by end, in place. O(n log n).</summary>
/// <param name="intervals">Pairs [start, end].</param>
/// <returns>The same array, sorted.</returns>
/// <example>ByStart([[3, 4], [1, 9], [1, 2]]) gives [[1, 2], [1, 9], [3, 4]]</example>
public static int[][] ByStart(int[][] intervals)
{
Array.Sort(intervals, (x, y) =>
x[0] != y[0] ? x[0].CompareTo(y[0]) // [0]: start decides first
: x[1].CompareTo(y[1])); // [1]: end breaks the tie
return intervals;
}
/// <summary>Where value would go in a sorted array. O(log n).</summary>
/// <param name="sorted">Ascending values.</param>
/// <param name="value">The value to place.</param>
/// <returns>An index from 0 to Length.</returns>
/// <example>InsertionPoint([1, 3, 5], 4) gives 2</example>
public static int InsertionPoint(int[] sorted, int value)
{
int i = Array.BinarySearch(sorted, value);
return i >= 0 ? i : ~i; // ~i: the complement encodes the slot
}
/// <summary>Shows that Array.Fill shares one reference across slots. O(n).</summary>
/// <param name="n">Slots, at least 2.</param>
/// <returns>True when slot 0 and slot 1 are the same list.</returns>
/// <example>FillSharesReference(3) gives true</example>
public static bool FillSharesReference(int n)
{
var rows = new List<int>[n];
Array.Fill(rows, new List<int>()); // one list, n references
rows[0].Add(1);
return ReferenceEquals(rows[0], rows[1]); // [0], [1]: the first two slots
}
/// <summary>Builds an r by c grid filled with a value. O(r c).</summary>
/// <param name="rows">Row count.</param>
/// <param name="cols">Column count.</param>
/// <param name="value">Initial value.</param>
/// <returns>A jagged array with independent rows.</returns>
/// <example>Grid(2, 3, -1) gives [[-1, -1, -1], [-1, -1, -1]]</example>
public static int[][] Grid(int rows, int cols, int value)
{
var grid = new int[rows][];
for (int r = 0; r < rows; r++) // r: row being created
{
grid[r] = new int[cols];
Array.Fill(grid[r], value);
}
return grid;
}
/// <summary>Parses a line of numbers into an int array. O(n).</summary>
/// <param name="line">Space-separated ints.</param>
/// <returns>The values.</returns>
/// <example>ParseInts("3 1 2") gives [3, 1, 2]</example>
public static int[] ParseInts(string line) =>
Array.ConvertAll(line.Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse);
}
Extension methods in System.Linq. Lazy ones build a pipeline. Eager ones run it.
Generate sequences. The second argument of Range is a count, not an end.
Enumerable.Range(0, 5) // 0, 1, 2, 3, 4
Enumerable.Range(1, n) // 1..n
Enumerable.Range(5, 3) // 5, 6, 7: NOT 5 to 3
Enumerable.Repeat(0, 3) // 0, 0, 0
Enumerable.Repeat("ab", 2) // "ab", "ab"
Enumerable.Sequence(0, 10, 3) // .NET 10: 0, 3, 6, 9
Map and filter. Both are lazy. Both have an overload that also passes the index.
nums.Select(x => x * x) // squares
nums.Where(x => x % 2 == 0) // evens
words.Select((w, i) => $"{i}:{w}") // with index
nums.Where((x, i) => x > i) // value greater than its position
pairs.SelectMany(p => p) // flatten a list of lists
A stable sort that returns a new sequence. O(n log n). Buffers all input.
people.OrderBy(p => p.Age) // ascending by age
people.OrderBy(p => p.Age).ThenBy(p => p.Name) // tie-break
people.OrderByDescending(p => p.Score)
nums.Order() // .NET 7: sort by the value
nums.OrderDescending()
words.OrderBy(w => w, StringComparer.Ordinal)
Trap. .OrderBy(a).OrderBy(b) sorts by b only. The second call starts a new sort. Use ThenBy.
Reductions. O(n).
nums.Sum() // int sum; checked, so overflow throws
nums.Sum(x => (long)x) // sum as long to avoid that
nums.Max() // throws InvalidOperationException if empty
nums.DefaultIfEmpty().Max() // 0 on empty
nums.Average() // a double, even for ints
people.Max(p => p.Age) // the max AGE, not the person
Trap. Min and Max on an empty sequence of value types throw. On a nullable type such as int? they return null instead.
The element with the smallest or largest key. .NET 6+. Ties go to the first.
people.MaxBy(p => p.Age) // the oldest PERSON
words.MinBy(w => w.Length) // shortest word, first one on a tie
counts.MaxBy(kv => kv.Value).Key // the most common key
Counting and tests. Any and All stop early.
nums.Count(x => x > 0) // how many are positive
nums.Any() // not empty
nums.Any(x => x < 0) // at least one negative
nums.All(x => x > 0) // true for an EMPTY sequence
nums.Contains(7)
list.Count // the property: O(1), no LINQ
Trap. seq.Count() > 0 walks the whole sequence. Any() stops at the first item.
Pick one element. The OrDefault forms return default(T) instead of throwing.
nums.First() // throws if empty
nums.First(x => x > 5) // first match, throws if none
nums.FirstOrDefault(x => x > 5) // 0 if none: same as a real 0
nums.FirstOrDefault(x => x > 5, -1) // .NET 6: your own default
nums.Single(x => x == 3) // throws if zero or several match
nums.Last() // O(1) on a list, O(n) otherwise
Trap. FirstOrDefault on ints returns 0 for “not found”. You cannot tell that from a real 0. Pass an explicit default.
Set operations on sequences. They keep first-seen order. O(n) with a hash set inside.
[1, 2, 1, 3].Distinct() // 1, 2, 3
people.DistinctBy(p => p.Email) // first person per email
a.Union(b) // in a or b, no repeats
a.Intersect(b) // in both
a.Except(b) // in a, not in b
Run the pipeline and store the result.
var list = q.ToList();
var set = words.ToHashSet();
var byId = users.ToDictionary(u => u.Id); // value is the user
var ages = users.ToDictionary(u => u.Name, u => u.Age);
var index = arr.Index().ToDictionary(p => p.Item, p => p.Index); // value to position
Trap. ToDictionary throws ArgumentException on a duplicate key. With repeats, use GroupBy, ToLookup, or a loop with the indexer.
Bucket by key. CountBy (.NET 9) gives counts directly.
words.GroupBy(w => w.Length) // IGrouping per length
words.GroupBy(w => w.Length).Select(g => (g.Key, g.Count()))
s.CountBy(c => c) // char frequencies
words.GroupBy(w => string.Concat(w.Order())) // group anagrams
words.ToLookup(w => w[0])['z'] // empty if no 'z' words
A general fold. Python’s reduce.
nums.Aggregate(0, (acc, x) => acc + x) // sum
nums.Aggregate(1L, (acc, x) => acc * x) // product as long
nums.Aggregate(0, (acc, x) => acc ^ x) // XOR of all: Single Number
nums.Aggregate((a, b) => Math.Max(a, b)) // no seed: throws if empty
Pairs items by position. Stops at the shorter sequence.
a.Zip(b) // tuples (First, Second)
a.Zip(b, (x, y) => x * y).Sum() // dot product
xs.Zip(xs.Skip(1)) // neighbours: (x0, x1), (x1, x2), ...
a.Zip(b, c) // three-way, gives 3-tuples
Slicing for sequences. All lazy.
nums.Skip(2).Take(3) // items 2, 3, 4
nums.Take(1..3) // .NET 6: a range works too
nums.TakeLast(2) // the last two
nums.TakeWhile(x => x < 5) // stops at the first 5 or more
nums.Chunk(3) // arrays of 3, last may be short
Element-wise equality, and building sequences.
a.SequenceEqual(b) // true if same items in same order
a == b // arrays: reference equality only
s.Reverse() // lazy reversed copy of any sequence
a.Concat(b) // a then b
nums.Append(9).Prepend(0) // add at the ends, lazily
public sealed record Person(string Name, int Age);
public static class LinqDemo
{
/// <summary>Top k words by frequency, ties by word. O(n + d log d).</summary>
/// <param name="words">The words.</param>
/// <param name="k">How many to return.</param>
/// <returns>Up to k words.</returns>
/// <example>TopWords(["b", "a", "b", "c", "a", "b"], 2) gives ["b", "a"]</example>
public static List<string> TopWords(IEnumerable<string> words, int k) =>
words.CountBy(w => w)
.OrderByDescending(kv => kv.Value)
.ThenBy(kv => kv.Key, StringComparer.Ordinal)
.Take(k)
.Select(kv => kv.Key)
.ToList();
/// <summary>The oldest person, first on a tie. O(n).</summary>
/// <param name="people">At least one person.</param>
/// <returns>The person, not just the age.</returns>
/// <example>Oldest([new("a", 3), new("b", 9)]) gives Person { Name = b, Age = 9 }</example>
public static Person Oldest(IEnumerable<Person> people) =>
people.MaxBy(p => p.Age) ?? throw new ArgumentException("no people");
/// <summary>Groups anagrams, groups in first-seen order. O(n m log m).</summary>
/// <param name="words">The words.</param>
/// <returns>One list per anagram class.</returns>
/// <example>Anagrams(["eat", "tea", "tan"]) gives [["eat", "tea"], ["tan"]]</example>
public static List<List<string>> Anagrams(IEnumerable<string> words) =>
words.GroupBy(w => string.Concat(w.Order())) // sorted letters: the class key
.Select(g => g.ToList())
.ToList();
/// <summary>First value above a limit, or -1. Shows an explicit default. O(n).</summary>
/// <param name="nums">The values.</param>
/// <param name="limit">Strictly greater values match.</param>
/// <returns>The match, or -1 when none.</returns>
/// <example>FirstAbove([0, 5], -1) gives 0, which FirstOrDefault alone could not show</example>
public static int FirstAbove(IEnumerable<int> nums, int limit) =>
nums.FirstOrDefault(x => x > limit, -1); // -1: a "none" marker unlike any value
/// <summary>Counts how many times deferred LINQ runs its filter. O(n).</summary>
/// <param name="nums">The values.</param>
/// <returns>Filter calls when enumerated twice without ToList.</returns>
/// <example>DeferredRuns([1, 2, 3]) gives 6</example>
public static int DeferredRuns(int[] nums)
{
int calls = 0;
var evens = nums.Where(x => { calls++; return x % 2 == 0; }); // % 2: even test
_ = evens.Count(); // first full run
_ = evens.ToList(); // second full run
return calls;
}
/// <summary>XOR of all values: the number that appears once. O(n).</summary>
/// <param name="nums">Every value twice except one.</param>
/// <returns>The single value.</returns>
/// <example>SingleNumber([4, 1, 2, 1, 2]) gives 4</example>
public static int SingleNumber(IEnumerable<int> nums) =>
nums.Aggregate(0, (acc, x) => acc ^ x); // 0: XOR identity
}
The System.Collections.Generic types, the members you call, and their costs.
A growable array. Add at the end is O(1) amortised. Insert and remove in the middle are O(n).
new List<T>(capacity): pre-size to skip regrowth.Count: the property. Not Length, not Count().var list = new List<int> { 3, 1 }; // or: List<int> list = [3, 1];
list.Add(2); // O(1) amortised
list.Insert(0, 9); // O(n): shifts everything right
list.RemoveAt(list.Count - 1); // O(1): pop from the end
list.Remove(9); // O(n): first match only, returns bool
list.Sort(); // in place, unstable
list.GetRange(1, 2) // copy of 2 items from index 1
list[^1] // last item
Trap. RemoveAt(0) in a loop is O(n²). That is not a queue. Use Queue<T>. Also, changing a list inside its own foreach throws InvalidOperationException.
A hash map. Average O(1) per operation.
this[key]: get throws KeyNotFoundException if missing. Set adds or overwrites.TryGetValue(key, out value): one lookup, no exception.Add(key, value): throws on a duplicate. TryAdd returns false instead.var counts = new Dictionary<string, int>();
counts[w] = counts.GetValueOrDefault(w) + 1; // count idiom: 0 when missing
if (counts.TryGetValue(w, out int c)) { ... } // one lookup
counts.TryAdd("x", 1); // false if "x" exists
counts.Remove("x", out int old); // remove and get the value
foreach (var (key, value) in counts) { ... } // deconstruct pairs
counts.Keys, counts.Values // live views
Trap. Enumeration order is not guaranteed. It often looks like insertion order until you remove an item. Sort the keys when the output order matters.
Low-level helpers in System.Runtime.InteropServices. One hash lookup to update a value in place.
ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, w, out _);
slot++; // one lookup instead of two
Span<int> view = CollectionsMarshal.AsSpan(list); // the list's backing array
Trap. Do not add to the dictionary or list while you hold the ref or span. A resize leaves it pointing at old memory.
A hash set. Add returns false if the item was already there.
var seen = new HashSet<int>();
if (!seen.Add(x)) return true; // duplicate found, in one call
seen.Contains(5) // O(1) average
a.UnionWith(b); // a changes in place
a.IntersectWith(b);
a.SetEquals(b) // same members, any order
new HashSet<string>(StringComparer.OrdinalIgnoreCase) // custom equality
FIFO and LIFO. All operations O(1).
var q = new Queue<int>();
q.Enqueue(1);
int front = q.Dequeue(); // throws InvalidOperationException if empty
while (q.TryDequeue(out int node)) { ... } // BFS loop, no exception
var st = new Stack<char>();
st.Push('(');
if (st.TryPop(out char top)) { ... }
st.Peek() // look, do not remove; throws if empty
Trap. There is no deque. For both ends use LinkedList<T> or your own ring buffer over an array.
A binary min-heap. Smallest priority comes out first. O(log n) push and pop.
Enqueue(element, priority): the priority is separate from the element.new PriorityQueue<E, P>(comparer): pass a reversed comparer for a max-heap.EnqueueDequeue(e, p): push then pop in one step, good for top-k.var pq = new PriorityQueue<string, int>();
pq.Enqueue("b", 2);
pq.Enqueue("a", 1);
pq.Dequeue() // "a"
pq.TryDequeue(out var item, out int pri) // both out at once
var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
pq.UnorderedItems // NOT in priority order
Trap. No decrease-key and no remove. In Dijkstra, push a new entry and skip stale ones when popped. Equal priorities come out in no fixed order.
Red-black trees. O(log n) add, remove and lookup. Enumerate in sorted order.
var set = new SortedSet<int> { 5, 1, 9 };
set.Min // 1
set.Max // 9
set.GetViewBetween(2, 8) // { 5 }: a live view, both ends inclusive
set.GetViewBetween(x, int.MaxValue).Min // the ceiling of x, if the view is not empty
var sd = new SortedDictionary<string, int>(StringComparer.Ordinal);
Trap. SortedSet holds no duplicates. For a multiset, store (value, uniqueId) tuples or keep counts in a SortedDictionary.
A doubly linked list. O(1) at both ends, and O(1) removal when you hold the node.
var dq = new LinkedList<int>();
dq.AddLast(1); // push back
dq.AddFirst(0); // push front
int front = dq.First!.Value; // First is null when empty
dq.RemoveFirst(); // throws if empty
LinkedListNode<int> node = dq.AddLast(5);
dq.Remove(node); // O(1): the LRU cache trick
using System.Runtime.InteropServices;
public static class CollectionsDemo
{
/// <summary>Counts words with one hash lookup per word. O(n).</summary>
/// <param name="words">The words.</param>
/// <returns>Word to count.</returns>
/// <example>Count(["a", "b", "a"])["a"] gives 2</example>
public static Dictionary<string, int> Count(IEnumerable<string> words)
{
var counts = new Dictionary<string, int>();
foreach (string w in words)
{
// A ref to the slot. A missing key is added with default 0 first.
ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, w, out _);
slot++;
}
return counts;
}
/// <summary>The k largest values with a size-k min-heap. O(n log k).</summary>
/// <param name="nums">The values.</param>
/// <param name="k">How many, at least 1.</param>
/// <returns>The k largest, descending.</returns>
/// <example>TopK([5, 1, 9, 3, 7], 2) gives [9, 7]</example>
public static List<int> TopK(IEnumerable<int> nums, int k)
{
var heap = new PriorityQueue<int, int>(); // min-heap: the smallest kept is on top
foreach (int x in nums)
{
if (heap.Count < k) heap.Enqueue(x, x);
else if (x > heap.Peek()) heap.EnqueueDequeue(x, x); // swap out the smallest
}
var result = new List<int>(k);
while (heap.TryDequeue(out int v, out _)) result.Add(v);
result.Reverse(); // min-heap gave ascending order
return result;
}
/// <summary>Pops a max-heap built with a reversed comparer. O(n log n).</summary>
/// <param name="nums">The values.</param>
/// <returns>Values in descending order.</returns>
/// <example>MaxHeapOrder([2, 9, 4]) gives [9, 4, 2]</example>
public static List<int> MaxHeapOrder(IEnumerable<int> nums)
{
var heap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
foreach (int x in nums) heap.Enqueue(x, x);
var result = new List<int>();
while (heap.Count > 0) result.Add(heap.Dequeue());
return result;
}
/// <summary>Smallest value at least x, using a SortedSet view. O(log n).</summary>
/// <param name="set">The sorted set.</param>
/// <param name="x">The probe.</param>
/// <returns>The ceiling, or null if every value is below x.</returns>
/// <example>Ceiling({1, 5, 9}, 6) gives 9</example>
public static int? Ceiling(SortedSet<int> set, int x)
{
if (set.Count == 0 || set.Max < x) return null; // nothing at or above x
return set.GetViewBetween(x, set.Max).Min;
}
/// <summary>Sliding window max with LinkedList as a deque. O(n).</summary>
/// <param name="nums">The values.</param>
/// <param name="k">Window size, from 1 to n.</param>
/// <returns>The max of each window.</returns>
/// <example>WindowMax([1, 3, -1, -3, 5], 3) gives [3, 3, 5]</example>
public static List<int> WindowMax(int[] nums, int k)
{
var dq = new LinkedList<int>(); // indexes, values decreasing front to back
var result = new List<int>();
for (int i = 0; i < nums.Length; i++) // i: the index entering the window
{
if (dq.Count > 0 && dq.First!.Value <= i - k) dq.RemoveFirst(); // fell out
while (dq.Count > 0 && nums[dq.Last!.Value] <= nums[i]) dq.RemoveLast();
dq.AddLast(i);
if (i >= k - 1) result.Add(nums[dq.First!.Value]); // k - 1: first full window
}
return result;
}
/// <summary>Shows that a Dictionary indexer read throws on a missing key. O(1).</summary>
/// <param name="map">The dictionary.</param>
/// <param name="key">The key to read.</param>
/// <returns>The value via the indexer.</returns>
/// <example>ReadOrThrow(new() { ["a"] = 1 }, "b") throws KeyNotFoundException</example>
public static int ReadOrThrow(Dictionary<string, int> map, string key) => map[key];
}
System.Random. Upper bounds are exclusive.
A random int from minValue up to but not including maxValue.
minValue: inclusive lower bound.maxValue: exclusive upper bound.Random.Shared.Next(1, 7) // a die roll: 1 to 6
Random.Shared.Next(10) // 0 to 9
Random.Shared.NextDouble() // 0.0 up to but not 1.0
Random.Shared.NextInt64(0, 1L << 40)
Random.Shared.Next(0, int.MaxValue) // never returns int.MaxValue itself
Trap. Next(1, 6) for a die never rolls a 6. Write the bound as “one past the last value”.
A seeded instance repeats its sequence. Random.Shared is thread-safe but cannot be seeded.
var rng = new Random(42); // same sequence every run of this build
rng.Next(100)
Random.Shared.Next(100) // safe from many threads
new Random() // in a tight loop: wasteful, use Shared
Trap. A single new Random() shared across threads can corrupt its state and return only zeros. Use Random.Shared for concurrent code.
.NET 8 helpers. Fisher-Yates shuffle in place. Pick items with replacement.
Random.Shared.Shuffle(arr); // in place
Random.Shared.GetItems([1, 2, 3], 5) // 5 picks, repeats allowed
Random.Shared.GetItems<char>("abc", 4) // random string of a, b, c
public static class RandomDemo
{
/// <summary>A die roll. Shows the exclusive upper bound. O(1).</summary>
/// <param name="rng">The random source.</param>
/// <returns>1 to 6 inclusive.</returns>
/// <example>Die(Random.Shared) gives a value from 1 to 6</example>
public static int Die(Random rng) => rng.Next(1, 7); // 7: one past the top face
/// <summary>A shuffled copy. The input is not changed. O(n).</summary>
/// <param name="items">The values.</param>
/// <param name="rng">The random source.</param>
/// <returns>A permutation of the input.</returns>
/// <example>Shuffled([1, 2, 3], new Random(1)) gives some order of 1, 2, 3</example>
public static T[] Shuffled<T>(IReadOnlyList<T> items, Random rng)
{
T[] copy = [.. items];
rng.Shuffle(copy);
return copy;
}
/// <summary>Hand-written Fisher-Yates, the version to write on a whiteboard. O(n).</summary>
/// <param name="a">Shuffled in place.</param>
/// <param name="rng">The random source.</param>
/// <example>FisherYates([1, 2, 3], rng) leaves a permutation in the array</example>
public static void FisherYates(int[] a, Random rng)
{
// Invariant: a[(i + 1)..] is a uniform random arrangement, already final.
for (int i = a.Length - 1; i > 0; i--) // -1: last index; > 0: index 0 is forced
{
int j = rng.Next(0, i + 1); // + 1: j may equal i, the "stay" case
(a[i], a[j]) = (a[j], a[i]);
}
}
}
For online judges and take-home tasks. Interviews on a whiteboard rarely need it.
One line without its terminator. Returns null at end of input.
string? line = Console.ReadLine();
int n = int.Parse(Console.ReadLine()!); // ! says "trust me, not null"
int[] nums = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
while (Console.ReadLine() is { } row) { ... } // read until end of input
Trap. With nullable on, ReadLine returns string?. Handle null or the compiler warns. Reading a token at a time, like Java’s Scanner, does not exist. Split the line yourself.
Read all input at once. Faster than many ReadLine calls for big inputs.
string all = Console.In.ReadToEnd();
var tokens = all.Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries);
using var input = new StreamReader(Console.OpenStandardInput(), bufferSize: 1 << 16);
Print a value and a newline. Interpolated strings are the normal form.
Console.WriteLine(42);
Console.WriteLine($"{name}: {score:F2}");
Console.Write("no newline");
Console.WriteLine(string.Join(' ', nums)); // print a list
Console.Error.WriteLine("debug"); // stderr: judges ignore it
Buffered output for a million lines. Each Console.WriteLine flushes, which is slow.
using var output = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
foreach (int x in results) output.WriteLine(x);
// The using disposes the writer at the end, which flushes it.
Trap. Forget to flush or dispose and the last buffer never prints. The judge sees missing lines.
public static class IoDemo
{
/// <summary>Reads "n" then n lines of two ints, writes each sum. O(n).</summary>
/// <param name="input">Any TextReader: Console.In in a judge, StringReader in tests.</param>
/// <param name="output">Any TextWriter: a buffered StreamWriter in a judge.</param>
/// <example>Input "2\n1 2\n3 4\n" writes "3\n7\n"</example>
public static void PairSums(TextReader input, TextWriter output)
{
int n = int.Parse(input.ReadLine() ?? "0"); // "0": empty input means no pairs
for (int i = 0; i < n; i++) // i: the pair being read
{
string[] parts = (input.ReadLine() ?? "").Split(' ',
StringSplitOptions.RemoveEmptyEntries);
output.WriteLine(long.Parse(parts[0]) + long.Parse(parts[1])); // long: no overflow
}
}
/// <summary>Runs PairSums on a string, for tests. O(n).</summary>
/// <param name="text">The whole input.</param>
/// <returns>The whole output.</returns>
/// <example>Run("1\n5 6\n") gives "11\n"</example>
public static string Run(string text)
{
var output = new StringWriter { NewLine = "\n" }; // "\n": same on every OS
PairSums(new StringReader(text), output);
return output.ToString();
}
}
How sorts, heaps, sets and dictionaries decide order and equality.
Negative if a sorts first, 0 if equal, positive if a sorts after. Only the sign matters.
3.CompareTo(5) // negative
"b".CompareTo("a") // positive, culture rules
x.CompareTo(y) * -1 // reverse order; or swap: y.CompareTo(x)
(a.Age, a.Name).CompareTo((b.Age, b.Name)) // tuples compare item by item
Trap. Never test CompareTo(...) == -1. The contract only promises a sign. Test < 0.
Turn a lambda into an IComparer<T>. Heaps, sorted sets and sorts all take one.
Comparer<int>.Default.Compare(1, 2) // negative
var desc = Comparer<int>.Create((a, b) => b.CompareTo(a));
new SortedSet<int>(desc) // largest first
new PriorityQueue<int, int>(desc) // max-heap
Array.Sort(arr, desc);
A subtraction comparator is wrong when the difference overflows.
int a = int.MinValue, b = 1;
a - b // 2147483647: positive, so "a after b". Wrong.
a.CompareTo(b) // negative. Right.
Ready-made comparers for strings. They work as both IComparer and IEqualityComparer.
Array.Sort(words, StringComparer.Ordinal);
new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase)
words.Distinct(StringComparer.OrdinalIgnoreCase)
Dictionaries and sets call GetHashCode then Equals. Classes compare by reference unless you override both. Records and tuples compare by value.
record Point(int X, int Y);
new Point(1, 2) == new Point(1, 2) // true: records have value equality
(1, 2) == (1, 2) // true: tuples too
new[] { 1, 2 }.Equals(new[] { 1, 2 }) // false: arrays compare references
var seen = new HashSet<(int, int)>(); // grid cells as tuple keys
Trap. An int[] or List<int> as a dictionary key uses reference equality. Two equal arrays are two keys. Use a tuple, a record, or string.Join(",", arr) as the key.
Mixes several field hashes into one well-spread hash.
public override int GetHashCode() => HashCode.Combine(X, Y);
var h = new HashCode();
foreach (int x in items) h.Add(x); // any number of values
int code = h.ToHashCode();
Trap. Hash codes are randomised per process. Never save them to disk or send them over the network.
public sealed record Cell(int Row, int Col);
public sealed class Version3(int major, int minor, int patch) : IComparable<Version3>
{
public int Major { get; } = major;
public int Minor { get; } = minor;
public int Patch { get; } = patch;
/// <summary>Orders by major, then minor, then patch. O(1).</summary>
/// <param name="other">The version to compare to. Null sorts first.</param>
/// <returns>Negative, zero or positive.</returns>
/// <example>new Version3(1, 2, 0).CompareTo(new Version3(1, 10, 0)) is negative</example>
public int CompareTo(Version3? other) =>
other is null ? 1 // 1: any version sorts after null
: (Major, Minor, Patch).CompareTo((other.Major, other.Minor, other.Patch));
/// <summary>Value equality to match CompareTo.</summary>
/// <param name="obj">The other object.</param>
/// <returns>True when all three parts match.</returns>
/// <example>new Version3(1, 0, 0).Equals(new Version3(1, 0, 0)) gives true</example>
public override bool Equals(object? obj) => obj is Version3 v && CompareTo(v) == 0;
/// <summary>Hash of all three parts, consistent with Equals.</summary>
/// <returns>The combined hash.</returns>
/// <example>Equal versions give equal hashes</example>
public override int GetHashCode() => HashCode.Combine(Major, Minor, Patch);
/// <summary>Dotted form.</summary>
/// <returns>For example "1.2.3".</returns>
/// <example>new Version3(1, 2, 3).ToString() gives "1.2.3"</example>
public override string ToString() => $"{Major}.{Minor}.{Patch}";
}
public static class CompareDemo
{
/// <summary>Shows the subtraction comparator getting the sign wrong. O(1).</summary>
/// <param name="a">First value.</param>
/// <param name="b">Second value.</param>
/// <returns>The sign from a - b and the sign from CompareTo.</returns>
/// <example>Signs(int.MinValue, 1) gives (1, -1)</example>
public static (int BySubtraction, int ByCompareTo) Signs(int a, int b) =>
(Math.Sign(unchecked(a - b)), Math.Sign(a.CompareTo(b)));
/// <summary>Sorts versions with their IComparable order. O(n log n).</summary>
/// <param name="versions">Dotted versions.</param>
/// <returns>Sorted dotted strings.</returns>
/// <example>SortVersions(["1.10.0", "1.2.0"]) gives ["1.2.0", "1.10.0"]</example>
public static List<string> SortVersions(IEnumerable<string> versions) =>
versions.Select(s => s.Split('.').Select(int.Parse).ToArray())
.Select(p => new Version3(p[0], p[1], p[2])) // [0..2]: the three parts
.Order()
.Select(v => v.ToString())
.ToList();
/// <summary>Counts distinct keys when arrays, tuples or records are used. O(n).</summary>
/// <returns>Distinct counts for two equal points stored three ways.</returns>
/// <example>KeyKinds() gives (2, 1, 1)</example>
public static (int Arrays, int Tuples, int Records) KeyKinds()
{
var arrays = new HashSet<int[]> { new[] { 1, 2 }, new[] { 1, 2 } }; // two references
var tuples = new HashSet<(int, int)> { (1, 2), (1, 2) }; // value equality
var records = new HashSet<Cell> { new(1, 2), new(1, 2) }; // value equality
return (arrays.Count, tuples.Count, records.Count);
}
}
System.Index and System.Range, written ^n and a..b.
^1 is the last element, ^2 the one before. ^0 is one past the end.
int[] a = [10, 20, 30];
a[^1] // 30
a[^3] // 10
a[^0] // IndexOutOfRangeException: ^0 is the length
list[^1], str[^1] // works on List<T> and string too
Index i = ^2; a[i] // 20, an Index is a value you can store
A slice. On arrays and strings it copies. On spans it is a free view.
int[] a = [0, 1, 2, 3, 4];
a[1..3] // [1, 2], a new array
a[..2] // [0, 1]
a[^2..] // [3, 4]
a[..] // full copy
"hello"[1..^1] // "ell"
a.AsSpan()[1..3] // no copy: a Span<int> over a
list[1..3] // List<T>: a new List via Slice (.NET 8+)
Trap. a[1..3][0] = 99 changes the copy, not a. In a recursive split, slicing arrays costs O(n) per call. Pass indexes or spans instead.
public static class IndexRangeDemo
{
/// <summary>Everything except the first and last element, as a copy. O(n).</summary>
/// <param name="a">At least two elements.</param>
/// <returns>a[1..^1].</returns>
/// <example>Middle([1, 2, 3, 4]) gives [2, 3]</example>
public static int[] Middle(int[] a) => a[1..^1]; // 1: skip first; ^1: stop before last
/// <summary>Shows that a range on an array copies, while a span slice does not. O(n).</summary>
/// <returns>a[0] after writing through each kind of slice.</returns>
/// <example>CopyVsView() gives (0, 99)</example>
public static (int AfterRangeWrite, int AfterSpanWrite) CopyVsView()
{
int[] a = [0, 1, 2];
int[] copy = a[0..2]; // 0..2: first two, copied
copy[0] = 99;
int afterRange = a[0]; // unchanged: 0
Span<int> view = a.AsSpan(0, 2); // 0, 2: start and length
view[0] = 99;
return (afterRange, a[0]); // a[0] now 99
}
/// <summary>Sum by halving with spans: no copies at any level. O(n).</summary>
/// <param name="values">The numbers.</param>
/// <returns>The total.</returns>
/// <example>SplitSum([1, 2, 3, 4, 5]) gives 15</example>
public static long SplitSum(ReadOnlySpan<int> values)
{
if (values.Length == 0) return 0; // empty: nothing to add
if (values.Length == 1) return values[0]; // one item: itself
int mid = values.Length / 2; // /2: split near the middle
return SplitSum(values[..mid]) + SplitSum(values[mid..]);
}
/// <summary>The last n items of a list. O(n).</summary>
/// <param name="list">The list.</param>
/// <param name="n">How many, at most Count.</param>
/// <returns>A new list.</returns>
/// <example>LastN([1, 2, 3, 4], 2) gives [3, 4]</example>
public static List<int> LastN(List<int> list, int n) => list[^n..];
}
Substring(start, length) vs s[start..end]. The method takes a length. The range takes an end index.Array.Sort vs OrderBy. Array.Sort is in place and unstable. OrderBy returns a new, stable sequence.Array.Reverse(a) vs a.Reverse(). The first reverses in place. The second is lazy LINQ and leaves a alone.Count vs Count() vs Length. Length on arrays and strings. Count on collections. Count() is LINQ and may walk the sequence.(int)x vs Convert.ToInt32(x) vs Math.Round. The cast truncates. Convert and Math.Round round half to even.Parse vs TryParse. Parse throws on bad input. TryParse returns false.dict[key] vs TryGetValue. The indexer read throws on a missing key. TryGetValue does not.First vs FirstOrDefault vs Single. First throws on none. OrDefault returns default. Single throws on none or many.== on strings vs on arrays. Strings compare by value. Arrays compare by reference. Use SequenceEqual.Enumerable.Range(start, count) vs a range a..b. The method takes a count. The range takes an end.These Python tools have no direct match. Here is what to use instead.
collections.deque. No deque type. Use LinkedList<T>, or an array ring buffer with head and count.collections.Counter. Use CountBy, or a Dictionary<T, int> with GetValueOrDefault(k) + 1.collections.defaultdict. No auto-insert. Use CollectionsMarshal.GetValueRefOrAddDefault, or TryGetValue then add.heapq. Use PriorityQueue<TElement, TPriority>. It is a min-heap with no decrease-key and no ordered walk.bisect. Array.BinarySearch and List<T>.BinarySearch return ~insertionPoint when absent. Duplicates give any match, so write lower bound by hand.functools.cache. No attribute. Memoise with a Dictionary or an array.itertools.permutations and combinations. Not in the BCL. Write the backtracking from Pattern 10.int is 32-bit. Use long, checked, or System.Numerics.BigInteger.Substring and Enumerable.Range take a count. Ranges a..b take an end.Convert and Math.Round round half to even./ truncates toward zero and % follows the dividend’s sign. Python differs on negatives.StringComparison.Ordinal or StringComparer.Ordinal for string work in algorithms.Array.Sort is unstable and in place. OrderBy is stable and returns a copy.CompareTo, never a - b. Hash with HashCode.Combine, and use tuples or records as keys.Random.Next(min, max) excludes max. Use Random.Shared across threads.