Master foundational data structures that power modern programming. Learn array fundamentals, dynamic lists, multi-dimensional arrays, string manipulation, and algorithm patterns that solve real interview problems.
Arrays allocate contiguous memory blocks storing elements of the same type. Understanding memory layout, indexing, and static vs dynamic arrays is crucial for writing efficient code.
Arrays store elements sequentially in memory. Each element occupies fixed size based on type. You access elements by 0-based index.
// Array memory: contiguous block int[] arr = new int[5]; // 5 ints, each 4 bytes = 20 bytes // [arr[0]][arr[1]][arr[2]][arr[3]][arr[4]] arr[0] = 10; arr[4] = 50; Console.WriteLine(arr[0]); // O(1) access - contiguous memory
Key insight: Random access is O(1) because memory is contiguous. Any element accessed instantly regardless of position.
* Amortized for dynamic arrays; requires reallocation occasionally
The Array class provides built-in methods for manipulation. Master these to write clean, efficient code.
// Explicit size int[] arr1 = new int[5]; // Uninitialized: [0,0,0,0,0] // Array initializer int[] arr2 = new int[] { 1, 2, 3, 4, 5 }; // Implicit size int[] arr3 = { 10, 20, 30 }; string[] names = new string[3]; double[] prices = { 9.99, 19.99, 29.99 }; int length = arr2.Length; // 5
Sorts in-place using introsort. Average O(n log n), worst O(n log n).
int[] nums = { 5, 2, 8, 1, 9 }; Array.Sort(nums); // [1, 2, 5, 8, 9] // Descending with custom comparator Array.Sort(nums, Comparer<int>.Create((a, b) => b.CompareTo(a))); // Sort range: index 1, length 3 Array.Sort(nums, 1, 3);
int[] arr = { 1, 2, 3, 4, 5 }; Array.Reverse(arr); // [5, 4, 3, 2, 1] // Copy: defensive copying int[] original = { 1, 2, 3, 4, 5 }; int[] copy = new int[5]; Array.Copy(original, copy, 5); // O(n) copy[0] = 999; // original unchanged // Partial copy int[] partial = new int[3]; Array.Copy(original, 1, partial, 0, 3); // [2,3,4]
// Fill with value int[] arr = new int[5]; Array.Fill(arr, 7); // [7,7,7,7,7] // Search: linear O(n) int[] nums = { 5, 2, 8, 2, 9 }; int idx = Array.IndexOf(nums, 2); // 1 (first) int lastIdx = Array.LastIndexOf(nums, 2); // 3 // Binary search on sorted array: O(log n) Array.Sort(nums); int pos = Array.BinarySearch(nums, 8); // Index of 8
int[] nums = { 1, 2, 3, 4, 5 }; // Transform (map) var squared = nums.Select(x => x * x).ToArray(); // [1,4,9,16,25] // Filter var evens = nums.Where(x => x % 2 == 0).ToArray(); // [2,4] // Reduce int sum = nums.Aggregate(0, (acc, x) => acc + x); // 15 // First/Last/Any/All int first = nums.First(); bool hasEven = nums.Any(x => x % 2 == 0); // true bool allPos = nums.All(x => x > 0); // true
List<T> provides dynamic resizing. Internally uses arrays with auto-reallocation when capacity exceeded.
// Create list var list = new List<int>(); // Empty var list2 = new List<int> { 1, 2, 3 }; // With values var list3 = new List<int>(10); // Capacity hint // Properties int count = list.Count; // Number of elements int capacity = list.Capacity; // Allocated space // Access int first = list[0]; // O(1) list[0] = 99; // Modify in-place
var list = new List<int>(); // Add: amortized O(1) list.Add(1); list.Add(2); list.Add(3); // Insert: O(n) - shifts elements list.Insert(1, 99); // Insert 99 at index 1 // [1, 99, 2, 3] // Remove: O(n) - shifts elements list.Remove(99); // Remove first occurrence list.RemoveAt(0); // Remove at index // Clear list.Clear(); // Empty list, count=0
var list = new List<int> { 5, 2, 8, 2, 9 }; // Contains: O(n) bool has5 = list.Contains(5); // true // IndexOf: O(n) int idx = list.IndexOf(2); // 1 (first) int lastIdx = list.LastIndexOf(2); // 3 // FindIndex with predicate: O(n) int evenIdx = list.FindIndex(x => x % 2 == 0); // 1 // Find single element int found = list.Find(x => x > 5); // 8
var list = new List<int> { 5, 2, 8, 1, 9 }; // Sort in-place: O(n log n) list.Sort(); // [1, 2, 5, 8, 9] // Custom sort list.Sort((a, b) => b.CompareTo(a)); // Descending // Binary search on sorted list: O(log n) list.Sort(); // Must be sorted first int pos = list.BinarySearch(5); // Index of 5 // Capacity management list.TrimExcess(); // Reduce capacity to count
When capacity is exceeded, list doubles it (typical strategy). This enables amortized O(1) append.
var list = new List<int>(2); // Initial capacity: 2 list.Add(1); // Count: 1, Capacity: 2 list.Add(2); // Count: 2, Capacity: 2 list.Add(3); // Reallocation! Count: 3, Capacity: 4 list.Add(4); // Count: 4, Capacity: 4 list.Add(5); // Reallocation! Count: 5, Capacity: 8
2D arrays represent matrices. Jagged arrays provide flexible dimensions. Both have distinct memory layouts.
// Rectangular 2D array: 3x4 matrix int[,] matrix = new int[3, 4]; // With initializer int[,] mat2 = new int[,] { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } }; // Access int val = mat2[0, 0]; // 1 mat2[1, 2] = 99; // Set to 99 // Dimensions int rows = mat2.GetLength(0); // 3 int cols = mat2.GetLength(1); // 4 // Iteration for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) Console.Write(mat2[i, j] + " ");
Array of arrays - each row can have different length. More flexible, non-rectangular.
// Jagged array: array of arrays int[][] jagged = new int[3][]; // 3 rows, variable columns // Initialize each row jagged[0] = new int[2]; // Row 0: 2 elements jagged[1] = new int[3]; // Row 1: 3 elements jagged[2] = new int[4]; // Row 2: 4 elements // Or with initializer int[][] jagged2 = new int[][] { new int[] { 1, 2 }, new int[] { 3, 4, 5 }, new int[] { 6, 7, 8, 9 } }; // Access int val = jagged2[1][2]; // 5 jagged2[0][0] = 99; // Row lengths differ int row1Len = jagged2[1].Length; // 3 int row2Len = jagged2[2].Length; // 4
Strings are immutable sequences of characters. Understanding immutability is crucial for performance.
Once created, strings cannot be changed. Operations return new strings.
string s = "hello"; string s2 = s.ToUpper(); // "HELLO" - new string Console.WriteLine(s); // Still "hello" - original unchanged // Concatenation creates new string string msg = s + " world"; // New string // String interning: identical literals share memory string a = "hello"; string b = "hello"; bool same = ReferenceEquals(a, b); // true - same reference
string s = "hello"; int len = s.Length; // 5 // Index: O(1) char c = s[0]; // 'h' char last = s[s.Length - 1]; // 'o' // Enumerate characters foreach (char ch in s) Console.Write(ch); // Convert to char array char[] chars = s.ToCharArray(); // O(n) string reversed = new string(chars.Reverse()); // Wrong! Reverse in-place // Correct reversal Array.Reverse(chars); string rev = new string(chars);
Strings use Unicode (UTF-16 internally). Each char is 2 bytes, supporting emoji and international characters.
// Unicode support string emoji = "😊"; int len = emoji.Length; // 2! (surrogate pair) // UTF-8 encoding for bytes byte[] utf8 = Encoding.UTF8.GetBytes("hello"); string decoded = Encoding.UTF8.GetString(utf8); // ASCII byte[] ascii = Encoding.ASCII.GetBytes("hello");
Master common string operations. All return new strings (immutable).
string s = "hello world"; // Substring: O(n) where n is substring length string sub = s.Substring(0, 5); // "hello" string rest = s.Substring(6); // "world" // Search: O(nm) naive, optimized internally int idx = s.IndexOf("world"); // 6 int lastIdx = s.LastIndexOf("o"); // 7 // Case-insensitive search int idx2 = s.IndexOf("WORLD", StringComparison.OrdinalIgnoreCase); // 6 // Contains: O(nm) bool has = s.Contains("world"); // true bool starts = s.StartsWith("hello"); // true bool ends = s.EndsWith("world"); // true
string s = "hello world hello"; // Replace all occurrences: O(nm) string replaced = s.Replace("hello", "hi"); // "hi world hi" // Case-insensitive replace string csv = "a,b,c,d"; string[] parts = csv.Split(','); // ["a","b","c","d"] // Split with options string spaced = "a, b, c, d"; string[] clean = spaced.Split( new[] { ',' }, StringSplitOptions.RemoveEmptyEntries ); // ["a", "b", "c", "d"] // Split by multiple delimiters string mixed = "a,b;c:d"; string[] split = mixed.Split(new[] { ',', ';', ':' });
string s = " hello world "; // Trim: remove whitespace string trimmed = s.Trim(); // "hello world" string left = s.TrimStart(); // "hello world " string right = s.TrimEnd(); // " hello world" // Case conversion string upper = s.ToUpper(); // " HELLO WORLD " string lower = s.ToLower(); // " hello world " // Comparison: O(n) int cmp = s.CompareTo("hello"); // > 0 (s is greater) bool equal = s.Equals("hello", StringComparison.OrdinalIgnoreCase); // String.Concat & String.Join string concat = String.Concat("hello", " ", "world"); string joined = String.Join(",", new[] { "a", "b", "c" }); // "a,b,c"
StringBuilders efficiently accumulate strings. Use when repeatedly concatenating in loops.
String concatenation with + creates new strings each time (O(n) each). StringBuilder uses a buffer for O(1) append.
// Create StringBuilder var sb = new StringBuilder(); var sb2 = new StringBuilder(1000); // Capacity hint // Append: O(1) amortized sb.Append("hello"); sb.Append(" "); sb.Append("world"); sb.AppendLine(); // Add newline // Insert: O(n) sb.Insert(0, "prefix:"); // Insert at index 0 // Remove: O(n) sb.Remove(0, 7); // Remove 7 chars starting at 0 // Replace sb.Replace("world", "universe"); // Properties int len = sb.Length; int cap = sb.Capacity; // Convert to string: O(n) string result = sb.ToString();
var sb = new StringBuilder(); var data = new[] { "a", "b", "c", "d" }; // Efficient loop: O(n) for (int i = 0; i < data.Length; i++) { sb.Append(data[i]); if (i < data.Length - 1) sb.Append(","); } string csv = sb.ToString(); // "a,b,c,d" // Compare to inefficient way: string result = ""; // O(n²) - don't do this! for (int i = 0; i < data.Length; i++) result = result + data[i] + ",";
Four powerful techniques solve most array/string interview problems efficiently.
Precompute cumulative sums for O(1) range queries.
// Build prefix sum array: O(n) int[] nums = { 1, 2, 3, 4, 5 }; int[] prefix = new int[nums.Length + 1]; for (int i = 0; i < nums.Length; i++) prefix[i + 1] = prefix[i] + nums[i]; // prefix: [0, 1, 3, 6, 10, 15] // Query range [i, j): O(1) int sum = prefix[4] - prefix[1]; // Sum of nums[1..3] = 2+3+4 = 9
Use indices moving toward each other. Optimal for sorted arrays.
public bool IsPalindrome(string s) { int left = 0, right = s.Length - 1; while (left < right) { while (left < right && !char.IsLetterOrDigit(s[left])) left++; while (left < right && !char.IsLetterOrDigit(s[right])) right--; if (char.ToLower(s[left]) != char.ToLower(s[right])) return false; left++; right--; } return true; }
Maintain dynamic window with two pointers. Expand/contract to track condition.
public int FindMaxConsecutiveOnes(int[] nums) { int maxCount = 0, currentCount = 0; foreach (int num in nums) { if (num == 1) currentCount++; else { maxCount = Math.Max(maxCount, currentCount); currentCount = 0; } } return Math.Max(maxCount, currentCount); }
Find maximum subarray sum. Greedy approach: track max ending here and global max.
public int MaxSubArray(int[] nums) { int maxSum = nums[0], currentSum = 0; foreach (int num in nums) { // Either extend current subarray or start new currentSum = Math.Max(num, currentSum + num); // Update global maximum maxSum = Math.Max(maxSum, currentSum); } return maxSum; } // Example: [-2,1,-3,4,-1,2,1,-5,4] // Max subarray: [4,-1,2,1] = 6
15+ problems with complete C# solutions. Master patterns through practice.
public int[] TwoSum(int[] nums, int target) { var map = new Dictionary<int, int>(); for (int i = 0; i < nums.Length; i++) { int complement = target - nums[i]; if (map.ContainsKey(complement)) return new[] { map[complement], i }; map[nums[i]] = i; } return new int[0]; // No solution }
public int MaxProfit(int[] prices) { int minPrice = int.MaxValue, maxProfit = 0; foreach (int price in prices) { if (price < minPrice) minPrice = price; else maxProfit = Math.Max(maxProfit, price - minPrice); } return maxProfit; }
public bool ContainsDuplicate(int[] nums) { var seen = new HashSet<int>(); foreach (int num in nums) { if (seen.Contains(num)) return true; seen.Add(num); } return false; }
public int[] ProductExceptSelf(int[] nums) { int n = nums.Length; int[] result = new int[n]; // result[i] = product of all left result[0] = 1; for (int i = 1; i < n; i++) result[i] = result[i - 1] * nums[i - 1]; // Multiply by product of all right int rightProduct = 1; for (int i = n - 1; i >= 0; i--) { result[i] *= rightProduct; rightProduct *= nums[i]; } return result; }
public void MoveZeroes(int[] nums) { int pos = 0; // Position to place non-zero for (int i = 0; i < nums.Length; i++) { if (nums[i] != 0) { // Swap non-zero to position pos int temp = nums[pos]; nums[pos] = nums[i]; nums[i] = temp; pos++; } } }
public void Rotate(int[] nums, int k) { k %= nums.Length; // Handle k > length Reverse(nums, 0, nums.Length - 1); // Reverse all Reverse(nums, 0, k - 1); // Reverse first k Reverse(nums, k, nums.Length - 1); // Reverse rest } private void Reverse(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } }
public void ReverseString(char[] s) { int left = 0, right = s.Length - 1; while (left < right) { char temp = s[left]; s[left] = s[right]; s[right] = temp; left++; right--; } }
public bool IsAnagram(string s, string t) { if (s.Length != t.Length) return false; var counts = new int[26]; for (int i = 0; i < s.Length; i++) { counts[s[i] - 'a']++; counts[t[i] - 'a']--; } return counts.All(c => c == 0); }
public IList<IList<string>> GroupAnagrams(string[] strs) { var map = new Dictionary<string, List<string>>(); foreach (string s in strs) { char[] chars = s.ToCharArray(); Array.Sort(chars); string key = new string(chars); if (!map.ContainsKey(key)) map[key] = new List<string>(); map[key].Add(s); } return map.Values.ToList<List<string>>(); }
public void Merge(int[] nums1, int m, int[] nums2, int n) { int p1 = m - 1, p2 = n - 1, p = m + n - 1; while (p1 >= 0 && p2 >= 0) { if (nums1[p1] > nums2[p2]) nums1[p--] = nums1[p1--]; else nums1[p--] = nums2[p2--]; } // If p2 remains, copy rest (p1 already in place) while (p2 >= 0) nums1[p--] = nums2[p2--]; }
public string LongestCommonPrefix(string[] strs) { if (strs.Length == 0) return ""; for (int i = 0; i < strs[0].Length; i++) { char c = strs[0][i]; for (int j = 1; j < strs.Length; j++) { if (i >= strs[j].Length || strs[j][i] != c) return strs[0].Substring(0, i); } } return strs[0]; }
public int MyAtoi(string s) { s = s.Trim(); if (s.Length == 0) return 0; int sign = 1, result = 0, i = 0; if (s[0] == '-' || s[0] == '+') { sign = s[0] == '-' ? -1 : 1; i++; } while (i < s.Length && char.IsDigit(s[i])) { int digit = s[i] - '0'; if (result > int.MaxValue / 10 || (result == int.MaxValue / 10 && digit > 7)) return sign == 1 ? int.MaxValue : int.MinValue; result = result * 10 + digit; i++; } return result * sign; }
public string LongestPalindrome(string s) { string longest = ""; for (int i = 0; i < s.Length; i++) { // Odd length palindromes (single center) string odd = ExpandAroundCenter(s, i, i); if (odd.Length > longest.Length) longest = odd; // Even length palindromes (two centers) string even = ExpandAroundCenter(s, i, i + 1); if (even.Length > longest.Length) longest = even; } return longest; } private string ExpandAroundCenter(string s, int left, int right) { while (left >= 0 && right < s.Length && s[left] == s[right]) { left--; right++; } return s.Substring(left + 1, right - left - 1); }
Choose the right data structure for performance. Understand trade-offs.
| Structure | Access | Insert | Delete | Search | Use Case |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | Random access, known size |
| List<T> | O(1) | O(n) | O(n) | O(n) | Dynamic array, frequent append |
| LinkedList | O(n) | O(1)* | O(1)* | O(n) | Frequent insert/delete in middle |
| Stack | O(1) | O(1) | O(1) | O(n) | LIFO, backtracking, undo |
| Queue | O(1) | O(1) | O(1) | O(n) | FIFO, BFS, task scheduling |
| HashSet | N/A | O(1) | O(1) | O(1) | Unique elements, membership test |
| HashMap | O(1) | O(1) | O(1) | O(1) | Key-value pairs, frequency count |
* Assumes you have reference to the node
Understanding which pattern applies is the key to solving quickly. Here's how to recognize each:
Beyond basic API, several specialized string algorithms appear in interviews:
Find pattern in text in O(n+m) time (vs naive O(nm)). Uses failure function to avoid redundant comparisons.
// Build KMP failure function int[] BuildFailure(string pattern) { int m = pattern.Length; int[] failure = new int[m]; int j = 0; for (int i = 1; i < m; i++) { while (j > 0 && pattern[i] != pattern[j]) j = failure[j - 1]; if (pattern[i] == pattern[j]) j++; failure[i] = j; } return failure; } // KMP Search: Find all occurrences of pattern in text public IList<int> KMPSearch(string text, string pattern) { var result = new List<int>(); if (pattern.Length == 0) return result; int[] failure = BuildFailure(pattern); int j = 0; for (int i = 0; i < text.Length; i++) { while (j > 0 && text[i] != pattern[j]) j = failure[j - 1]; if (text[i] == pattern[j]) j++; if (j == pattern.Length) { result.Add(i - pattern.Length + 1); j = failure[j - 1]; } } return result; }
public int LengthOfLongestSubstring(string s) { var lastSeen = new Dictionary<char, int>(); int maxLen = 0, left = 0; for (int right = 0; right < s.Length; right++) { char c = s[right]; // If char seen in current window, move left if (lastSeen.ContainsKey(c) && lastSeen[c] >= left) left = lastSeen[c] + 1; // Update last position of char lastSeen[c] = right; // Track max window size maxLen = Math.Max(maxLen, right - left + 1); } return maxLen; }
public string MinWindow(string s, string t) { if (t.Length > s.Length) return ""; var targetCount = new Dictionary<char, int>(); foreach (char c in t) targetCount[c] = targetCount.GetValueOrDefault(c) + 1; int required = targetCount.Count, formed = 0; var windowCount = new Dictionary<char, int>(); int left = 0, minLen = int.MaxValue, minStart = 0; for (int right = 0; right < s.Length; right++) { char c = s[right]; windowCount[c] = windowCount.GetValueOrDefault(c) + 1; if (targetCount.ContainsKey(c) && windowCount[c] == targetCount[c]) formed++; while (formed == required && left <= right) { if (right - left + 1 < minLen) { minLen = right - left + 1; minStart = left; } char leftChar = s[left]; windowCount[leftChar]--; if (targetCount.ContainsKey(leftChar) && windowCount[leftChar] < targetCount[leftChar]) formed--; left++; } } return minLen == int.MaxValue ? "" : s.Substring(minStart, minLen); }
Interview questions often ask: "Can you do this in O(1) space?" Here are key techniques:
Interview problems usually have constraints hinting at expected complexity. Here's guidance:
These data structures and patterns appear constantly in production systems:
You cannot memorize 15+ problems. Instead, understand patterns deeply:
Some problems are easier as char arrays, others stay as strings. Here's the decision tree:
Beyond big-O notation, understand practical constants and hidden costs:
Master these fundamentals and you'll solve majority of array/string interview problems: