wa Flashcards
(16 cards)
Two Sum — Given an array of integers and a target value return the indices of the two numbers that add up to the target.
Use a HashMap<i32, usize> to track seen values and their indices as you iterate a Vec<i32> with .iter().enumerate(). For each element compute its complement (target - num) and check the map with .get(). If present, return an Option<(usize, usize)>; otherwise insert the current number into the map. Rust’s ownership isn’t a concern here since keys and indices are copied into the map.</i32>
Palindrome Number — Determine if an integer reads the same backward as forward.
Reject negative integers immediately (they aren’t palindromic). Reverse the digits by repeatedly taking num % 10 and building a new integer, dividing num by 10 each loop. Compare the reversed value with the original; return a bool. No heap allocation is needed—everything stays in primitive i32.
Roman to Integer — Convert a Roman numeral string into its integer value.
Create a HashMap<char, i32> mapping Roman symbols to values. Convert the input &str to a Vec<char> and iterate with indexed access; subtract when a smaller value precedes a larger one, otherwise add. Return the accumulated sum as an i32. Using a map lookup (map[&c]) is O(1) thanks to hashing.</char>
Longest Common Prefix — Find the longest common starting substring among an array of strings.
Start with the first string (String) as the candidate prefix and iterate over the rest as &str. Use .starts_with(&prefix) in a while loop, shrinking the prefix via .pop() until it matches. Return an owned String at the end. This avoids repeated allocations by mutating one String.
Valid Parentheses — Check if a string of brackets is properly closed and nested.
Maintain a Vec<char> as a stack. Push opening brackets and pop on closing ones, checking matches via a small HashMap<char, char>. If the stack is empty after processing, return true; otherwise false. Rust’s pattern matching on Option (from .pop()) elegantly handles missing-opening cases.</char>
Merge Two Sorted Lists — Merge two sorted linked lists into one sorted linked list.
Use Option<Box<ListNode>> to represent linked lists. Create a dummy head (Box<ListNode>) and a mutable tail pointer. Repeatedly compare values via .as_ref().unwrap().val, take ownership of the smaller node with .take(), and advance pointers. Rust’s ownership rules ensure no aliasing or double‑free.</ListNode></ListNode>
Remove Duplicates from Sorted Array — Remove duplicates in-place in a sorted array and return the new length.
Work in place on a mutable Vec<i32> with two index pointers: a write index and a read index. When a new unique element is found, assign it to nums[write] and increment write. Return the final length (i32). No extra memory is used beyond the original vector.</i32>
Remove Element — Remove all instances of a given value in-place and return the new length of the array.
Similar two-pointer in-place pattern on &mut Vec<i32>. Skip over values equal to val, copying all others forward. Return the new length. Rust’s slice indexing and mutable borrowing ensure safety without allocation.</i32>
Find the Index of the First Occurrence in a String — Return the starting index of the first occurrence of a substring in a string or -1 if not found.
Use slicing on the &str and a simple loop from 0..=haystack.len()-needle.len(). Compare substrings with &haystack[i..i+needle.len()] == needle. Return the index as i32 or -1 if not found. Rust string slicing guarantees valid UTF-8 boundaries here because both inputs are ASCII-compatible.
Search Insert Position — Given a sorted array and a target return the index if found or the insert position.
Perform a binary search over a Vec<i32> using index arithmetic (left, right, mid). Compare nums[mid] to target, adjusting boundaries until left == right. Return left as an i32. No extra allocations; runs in O(log n) time.</i32>
Length of Last Word — Return the length of the last word in a string.
Trim trailing whitespace from the input &str, then call .split_whitespace().last(). Map the resulting Option<&str> to its .len() or 0. Rust’s iterator adapters make this both concise and allocation-free.
Plus One — Given a non‑empty array of digits representing a non-negative integer add one to the integer.
Iterate a mutable Vec<i32> in reverse (for i in (0..n).rev()). Handle carry by setting digits to 0 when hitting 9, otherwise increment and return. If a carry remains after the loop, prepend 1 to a new Vec. Ownership of the vector is mutated in place.</i32>
Add Binary — Add two binary strings and return their sum as a binary string.
Walk two &str inputs from end to start with indices, accumulating bits into a String (using insert(0,…)). Manage carry with integer arithmetic. No heavy data structures—just indexing into chars() and building the result string.
Sqrt(x) — Compute and return the integer square root of x.
Use binary search between 1 and x/2 (for x ≥ 2). Compare mid with x/mid to avoid overflow. Track the last valid mid in a result variable and return it as i32. Pure integer math, O(log x).
Climbing Stairs — Count distinct ways to climb n stairs when you can take 1 or 2 steps at a time.
Compute the nth Fibonacci number iteratively with two i32 variables (first, second). Loop from 2 to n, updating via tuple destructuring or a temporary variable. Constant space, linear time.
FizzBuzz — Print numbers 1 to n replacing multiples of 3 with Fizz, multiples of 5 with Buzz, and both with FizzBuzz.
Iterate 1..=n, pushing to a Vec<String>. Use % to test divisibility: check i % 15 == 0 first, then 3, then 5, otherwise push i.to_string(). Simple loop with no allocations beyond the result vector.</String>
