Array & String Algorithms
Algorithmic techniques over sequences in Go — two pointers, a stack, bracket matching, interval merging, and in-place compaction.
11 questions
JuniorCodeVery commonImplement FizzBuzz for 1..n
Implement FizzBuzz for 1..n
Loop i from 1 to n with a tagless switch: check i%15 == 0 → FizzBuzz first, then i%3 == 0 → Fizz, then i%5 == 0 → Buzz, else print i. The %15 case must be first, or i%3 would match multiples of 15 and FizzBuzz never prints. O(n) time.
Common mistakes
- ✗Checking
i%3ori%5beforei%15, soFizzBuzznever prints - ✗Assuming Go
switchfalls through to later cases by default - ✗Forgetting that 15 is the LCM that must be tested first
Follow-up questions
- →Why does Go's
switchstop at the first matching case withoutfallthrough? - →How would you make the divisor/word pairs configurable instead of hard-coded?
MiddleCodeVery commonCheck a bracket string ()[]{} is balanced
Check a bracket string ()[]{} is balanced
Push each opener onto a stack; on a closer, pop and verify it matches the expected opener — bail out early on mismatch or empty stack. The string is valid only if every closer matched and the stack is empty at the end. Runs in O(n) time and O(n) space.
Open full question →Common mistakes
- ✗Returning true at the end without checking the stack is empty — leaves unmatched openers
- ✗Popping from an empty stack when a closer arrives first, causing an index panic
- ✗Comparing closer-to-closer instead of mapping each closer to its expected opener
Follow-up questions
- →How would you adapt this to report the index of the first unmatched bracket?
- →Why does early return on mismatch keep the worst case at O(n)?
JuniorCodeCommonRemove every zero from an int slice in place, returning the trimmed slice
Remove every zero from an int slice in place, returning the trimmed slice
Use a write index j starting at 0. Scan with a read index i; whenever in[i] != 0, copy it to in[j] and advance j. After the pass, the first j elements are the non-zeros, so return in[:j]. This compacts in place with one pass — O(n) time and O(1) extra space — and works for the empty and all-zero cases.
Common mistakes
- ✗Splicing with
appendper zero, which is O(n²) not O(n) - ✗Allocating a new slice and calling that in place
- ✗Forgetting to return
in[:j]and returning the full slice
Follow-up questions
- →How would you also zero out the trailing elements to release references?
- →How does this two-pointer compaction generalize to removing by a predicate?
JuniorCodeCommonReverse a string so multi-byte UTF-8 characters stay intact
Reverse a string so multi-byte UTF-8 characters stay intact
Convert the string to []rune first, then two-pointer swap from both ends and return string(r). Operating on runes keeps multi-byte characters whole — reversing the raw bytes would split a rune like é and corrupt it. The algorithm is O(n) time and O(n) space.
Common mistakes
- ✗Reversing
[]byteinstead of[]rune, splitting multi-byte characters - ✗Assuming
rangeiterates a string in reverse - ✗Indexing
s[i]and treating each byte as a character
Follow-up questions
- →Why does reversing the byte slice of
hélloproduce invalid UTF-8? - →How would you reverse by grapheme cluster (e.g. an emoji with combining marks)?
JuniorCodeCommonImplement zip pairing two int slices up to the shorter length
Implement zip pairing two int slices up to the shorter length
Compute minLen as the smaller of the two lengths, preallocate the result with make([][]int, 0, minLen), then loop i from 0 to minLen appending []int{s1[i], s2[i]}. Stopping at the shorter length avoids an out-of-range panic, and preallocating capacity avoids repeated regrowth. It is O(minLen) time.
Common mistakes
- ✗Looping to the longer length and indexing out of range
- ✗Thinking an out-of-range slice index returns zero instead of panicking
- ✗Flattening into one slice instead of producing pairs
Follow-up questions
- →How would you make a variadic
zip(s ...[]int)for any number of slices? - →How would generics let
zipwork on slices of any element type?
JuniorTheoryOccasionalWhat is a stack, and why does its LIFO order fit bracket matching?
What is a stack, and why does its LIFO order fit bracket matching?
A stack is a LIFO collection — the last value pushed is the first popped. In Go you model it with a slice: push is append, pop reslices off the last element. It fits bracket matching because the most recently opened bracket is the one that must close first.
Common mistakes
- ✗Confusing LIFO with FIFO order — popping the oldest element instead of the newest
- ✗Reaching for
container/listwhen a plain slice is the idiomatic Go stack - ✗Forgetting to check for an empty stack before popping, causing an index panic
Follow-up questions
- →How do you implement push and pop on a Go slice without leaking memory?
- →Why is a slice faster than
container/listfor a stack in Go?
MiddleCodeOccasionalReturn the k-th node from the end of a singly linked list in one pass
Return the k-th node from the end of a singly linked list in one pass
Use two pointers with a gap of k. Advance a lead pointer k steps ahead first; if it runs off the list before that, k is out of range — return nil. Then move lead and a trail pointer (starting at head) together until lead reaches the last node. trail is now k from the end. One pass, O(n) time, O(1) space — no length precount and no second traversal.
Common mistakes
- ✗Precounting length and traversing twice instead of one two-pointer pass
- ✗Forgetting to return
nilwhenkexceeds the list length - ✗Claiming a stack or recursion gives O(1) space when it is O(n)
Follow-up questions
- →How do you detect that
kis out of range during the lead pointer's head start? - →Why is the gap-of-k invariant preserved as both pointers advance together?
MiddleCodeOccasionalMerge all overlapping intervals in a slice of [start, end] pairs
Merge all overlapping intervals in a slice of [start, end] pairs
Sort the intervals by start time, then sweep once: keep the last interval in the result; for each next interval, if its start ≤ the last interval's end they overlap, so extend the last end to max(lastEnd, end); otherwise append it as a new interval. The result is the minimal set of non-overlapping intervals. O(n log n) for the sort, O(n) for the sweep.
Common mistakes
- ✗Skipping the sort and assuming a single unsorted pass merges everything
- ✗Comparing only adjacent originals, missing a transitive chain merged through a running end
- ✗Taking the intersection instead of the union when extending the merged interval
Follow-up questions
- →Why is touching (
start == lastEnd) treated as overlapping here, and when might you exclude it? - →How would you insert one new interval into an already-merged, sorted list in O(n)?
MiddleCodeOccasionalDetermine whether an int slice is monotonic in O(n)
Determine whether an int slice is monotonic in O(n)
Track two booleans, isUp and isDown, both true at the start. Walk adjacent pairs once: keep isUp true only while in[i-1] <= in[i], and isDown true only while in[i-1] >= in[i]. Return isUp || isDown. A flat run keeps both true, and any direction change clears one. It is O(n) time, O(1) space, single pass.
Common mistakes
- ✗Locking in a direction from the first pair instead of tracking both flags
- ✗Treating equal adjacent elements as breaking monotonicity
- ✗Deciding from only the endpoints, missing a dip in the middle
Follow-up questions
- →How would you change it to require strict monotonicity (no equal neighbours)?
- →Can you early-return as soon as both flags become false?
MiddleCodeOccasionalCheck a string is a palindrome, ignoring case and non-letters
Check a string is a palindrome, ignoring case and non-letters
Lower-case the string and convert to []rune, then two pointers walk inward: skip non-letter/digit runes via unicode.IsLetter/IsDigit, compare r[i] != r[j] → false, and step both. If they cross, it is a palindrome. O(n) time, O(n) space for the rune slice.
Common mistakes
- ✗Comparing bytes via
s[i]instead of runes, mishandling multi-byte input - ✗Filtering only letters and dropping digits that should count
- ✗Assuming string
==ignores case and punctuation
Follow-up questions
- →Why does the byte-index approach fail on a string with multi-byte runes?
- →How would you do it in O(1) extra space without the
[]runeconversion?
SeniorCodeRareFind the longest valid () substring in O(n)
Find the longest valid () substring in O(n)
Push a sentinel index -1, then for each ( push its index and for each ) pop. After a pop, if the stack is non-empty the current valid run length is i - stack[top]; if it emptied, push i as the new base. Track the running maximum — O(n) time, O(n) space.
Common mistakes
- ✗Storing characters instead of indices — length cannot be computed without positions
- ✗Forgetting the
-1sentinel, which is what makesi - stack[top]give the right length - ✗Pushing the index after an emptying pop instead of using it as the new base offset
Follow-up questions
- →How does the two-counter left-and-right pass solve this in O(1) space?
- →Why must the index of an unmatched
)become the new stack base?
