Skip to content
Tutorials Center
My learning

Topics

Lesson 133 of 134 ยท Practice

Practice Problems: Arrays, Strings and Hashes

Eight interview-style Ruby exercises on arrays, strings and hashes - two sum, anagrams, parentheses, sliding window, intervals - with hints, tested solutions and complexity notes.

Reading about map, group_by and each_with_object is one thing. Reaching for the right one with a blank editor and a clock running is another. This lesson gives you eight problems of the kind interviewers love, all built from arrays, strings and hashes. Each one has a statement, a hint, a solution you can run, and a few lines of tests so you can see it works.

Try to solve every problem yourself before you open the solution. Write your attempt in the editor, run it, and only then compare. The solutions are not the only correct answers; they favor clear, idiomatic Ruby with a good running time. After each pair of problems you will find the time and memory cost, because interviewers nearly always ask for it.

How to approach these problems

Most array and string questions are solved by one of a handful of ideas. Decide which one fits before you write code.

flowchart TD
  A["Read the problem"] --> B{"Need to find or count<br/>things quickly?"}
  B -- "yes" --> C["Hash: lookup, count, group"]
  B -- "no" --> D{"Contiguous range<br/>of items?"}
  D -- "yes" --> E["Sliding window<br/>or each_cons"]
  D -- "no" --> F{"Order matters<br/>for the answer?"}
  F -- "yes" --> G["Sort first,<br/>then scan"]
  F -- "no" --> H["Stack, set<br/>or plain iteration"]

A quick way to pick a data structure before you start typing.

A hash turns a "have I seen this?" question from a full scan into a single lookup. Sorting is worth its O(n log n) cost when it makes the rest of the work a single pass. Keep these two moves in mind as you read the problems.

Problems 1 and 2: Two Sum and Anagram Groups

Problem 1: Two Sum. Given an array of integers and a target, return the indexes of the two numbers that add up to the target. Assume exactly one answer exists and you may not use the same element twice.

Hint: for each number you only need to know whether target - number appeared earlier. Store each number and its index in a hash as you go.

Problem 2: Group anagrams. Given a list of words, group together the words that are anagrams of each other. Return the groups sorted so the output is predictable.

Hint: two words are anagrams when their sorted letters are equal, so the sorted letters make a perfect hash key.

Ruby Two sum and group anagrams

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

two_sum is O(n) time and O(n) memory: one pass, one hash lookup per element. The brute-force version with two nested loops is O(n^2) and is the answer you give first, before improving it. group_anagrams costs O(n * k log k) for n words of length k, dominated by sorting each word's letters.

Notice return ... if inside the block: return in a block exits the whole method, which is exactly what we want here. If you are shaky on that rule, review Blocks and Procs and Lambdas.

Problems 3 and 4: Valid Parentheses and Run-Length Encoding

Problem 3: Balanced brackets. Given a string containing only ()[]{}, decide whether every opener is closed by the right closer in the right order.

Hint: a stack. Push openers; when you see a closer, the top of the stack must be its matching opener. At the end the stack must be empty.

Problem 4: Run-length encoding. Compress a string by replacing runs of the same character with the character and the run length, such as "aaabcc" becoming "a3b1c2". Then write the decoder and check that decoding an encoding gives back the original.

Hint: String#scan with a back-reference finds the runs, and chunk_while is another good tool.

Ruby Brackets and run-length encoding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

balanced? runs in O(n) time and uses O(n) memory in the worst case, for example "(((((". The early return false is the important detail: a closer that arrives when the stack is empty makes pop return nil, which never equals a real opener.

The decoder assumes the original text has no digits. Say that out loud in an interview; stating your assumptions is part of a good answer. For more on patterns like \2*, see Regular Expressions.

Problems 5 and 6: Longest Unique Substring and Word Frequency

Problem 5: Longest substring without repeating characters. Return the length of the longest stretch of a string in which no character appears twice.

Hint: a sliding window. Keep the index where each character was last seen. When the current character was seen inside the window, move the window's left edge just past that earlier position.

Problem 6: Top words. Given a paragraph, return the three most common words, ignoring case and punctuation. Break ties alphabetically so the result is the same every run.

Hint: scan(/[a-z']+/) extracts words, tally counts them, and a two-key sort_by handles the tie rule.

Ruby Sliding window and word counts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The window never moves left, so longest_unique is O(n); the hash holds at most one entry per distinct character. The >= start check matters: a character seen before the window began is no longer a duplicate. Delete that condition and run "abba" to see the bug.

top_words sorts the distinct words, so it costs O(d log d) for d distinct words. For very large inputs you could use max_by(count), but sorting is clear and fast enough for a paragraph. Sorting by [-times, word] compares arrays element by element, a trick you will use again and again; see Sorting and Searching Arrays.

Problems 7 and 8: Merge Intervals and Rotate

Problem 7: Merge intervals. Given a list of [start, finish] pairs in any order, merge the ones that overlap or touch and return the result sorted.

Hint: sort by start. Then each interval either extends the last merged one (when its start is no later than the last finish) or begins a new one.

Problem 8: Rotate an array. Rotate an array right by k places without using Array#rotate. Make it work when k is bigger than the array or negative.

Hint: the modulo operator in Ruby takes the sign of the divisor, so k % size is always a valid offset, even for negative k.

Ruby Intervals and rotation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Merging costs O(n log n) because of the sort; the scan afterwards is O(n). Note that the block parameters |(start, finish), merged| destructure the pair directly, a feature covered in Blocks. The mutation of merged.last[1] is safe here because we built that inner array ourselves with [start, finish].

rotate_right is O(n) and builds a new array, leaving numbers untouched. Returning items.dup for an empty input avoids a division by zero in steps % 0, which raises ZeroDivisionError. Edge cases like the empty array and a huge k are exactly what an interviewer will probe next.

Habits that make solutions better

Whatever problem you get, a few habits pay off.

  • Restate the problem and ask about edge cases. Empty input, one element, duplicates, negative numbers, and Unicode text are the usual suspects.
  • Start with the obvious solution, then improve it. Saying "brute force is O(n^2), but a hash gets it to O(n)" shows you can reason about cost.
  • Prefer the standard library. tally, group_by, each_cons, partition and sum say what you mean in a line. See Enumerable and Hashes.
  • Do not mutate input unless asked. Methods like sort_by and + return new arrays; sort! and << change the caller's data.
  • Test with small examples out loud. Walk through "abba" or [3, 3] by hand before you declare victory.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the two_sum solution store numbers in a hash while scanning?

    A hash lookup takes constant time on average, so one pass over the array is enough. Searching an array for the complement would make the whole solution quadratic.
  2. 2. In the sliding window solution, why is the check last_seen[char] >= start needed?

    last_seen keeps old positions forever. If the previous position is left of start, that character is outside the current window and must not move the window.
  3. 3. What does -7 % 5 return in Ruby, and why does that help rotate_right?

    Ruby's modulo takes the sign of the right operand, so steps % size lands in 0...size even for negative steps. Many other languages return a negative remainder here.
  4. 4. What is the time complexity of merge_intervals?

    Sorting by start costs O(n log n). The merge scan is a single O(n) pass, so sorting dominates.
  5. 5. Why is balanced?("(]") false?

    The stack holds ( when ] arrives, but ] needs [ on top. Matching types in the right order is what the stack enforces; counting alone would accept this string.

Summary

  • Pick the tool by the shape of the question: a hash for lookups, counts and groups; a sliding window for contiguous ranges; sorting when order simplifies the scan; a stack for nesting.
  • tally, group_by, each_with_object, each_cons and sort_by with array keys solve most of these problems in a few lines.
  • Always state time and memory cost, and name your edge cases: empty input, duplicates, negative numbers, huge values.
  • Ruby's % follows the divisor's sign, which makes wrap-around arithmetic safe.
  • Avoid mutating arguments unless the problem asks for it, and write a few quick checks for each solution.

Next: Practice Problems: OOP and Metaprogramming