Skip to content
Tutorials Center
My learning

Topics

Lesson 133 of 134 ยท Practice

Practice Problems: Collections and Strings

Seven interview-style Kotlin exercises on collections and strings: word counts, anagrams, palindromes, run-length encoding, two-sum, brackets and sliding windows, with solutions.

Collections and strings make up most of the everyday code you write and most of the questions you get in a coding interview. The language gives you strong tools for them (groupBy, associateWith, windowed, ArrayDeque, buildString), but knowing a tool exists is different from reaching for it at the right moment. These seven exercises build that reflex.

Work like this: read the task, hide the solution and write your own version in a scratch file, then run the solution and compare. If your answer differs, check whether it is wrong or just different; in Kotlin there are often three correct ways. Where an exercise needs a concept you want to revise, follow the links to collection transformations, maps, strings, sets and lists. Every solution is a complete program with its real output, and an interviewer would also ask you for the time complexity, so each explanation states it.

Exercise 1: top words

Task. Given a sentence, count how often each word appears (ignore case and punctuation) and print the top three words. If two words have the same count, the alphabetically smaller word comes first.

Hint. Split on anything that is not a letter, drop empty parts, then use groupingBy { it }.eachCount(). Sort with sortedWith(compareByDescending<...> { count }.thenBy { word }).

Kotlin Solution 1: word frequencies

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 readln()), it gets the next line from this box.

groupingBy(...).eachCount() counts without building a list for each group, which groupBy { it }.mapValues { it.value.size } would do. The sort is the expensive part: the time is O(n + k log k) for n words and k distinct words. A frequent follow-up asks for the top n of millions of words; then a priority queue of size n gives O(n log n) in the output size instead of sorting all words. Here "the" appears four times, "cat" three times, and "dog" and "saw" twice each, so "dog" takes the third place because it comes first alphabetically.

Exercise 2: group the anagrams

Task. Group the words that are anagrams of each other, such as "listen", "silent" and "enlist". Return the groups in order of first appearance, with the words in each group sorted alphabetically.

Hint. All anagrams have the same letters when sorted. Use the sorted letters as a map key.

Kotlin Solution 2: a canonical key

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 readln()), it gets the next line from this box.

groupBy returns a LinkedHashMap, so groups appear in the order their key first showed up. The idea of a canonical form (a value that is equal for all members of a group) solves many grouping problems. With words of length L, this takes O(n ยท L log L). If the alphabet is small you can replace the sort with a letter-count array, getting O(n ยท L).

Exercise 3: a forgiving palindrome

Task. Return true if a sentence reads the same forwards and backwards when you ignore case, spaces and punctuation: "A man, a plan, a canal: Panama".

Hint. The easy way creates a cleaned string and compares it with its reverse. The memory-friendly way uses two indexes that move towards each other.

Kotlin Solution 3: two pointers

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 readln()), it gets the next line from this box.

Both run in O(n) time. The first allocates two extra strings, so it uses O(n) memory; the second uses O(1) extra memory. An empty string is a palindrome by convention. In an interview, write the simple version first, say that you know the two-pointer variant, and write it if asked; correct and clear beats clever.

Exercise 4: run-length encoding

Task. Compress a string by replacing runs of the same character with the character and the run length: "aaabccdddd" becomes "a3b1c2d4". Then write the decoder and show that decode(encode(s)) == s.

Hint. Walk the string while tracking the current character and its count. For decoding, buildString and repeat are enough, because the counts can have more than one digit.

Kotlin Solution 4: encode and decode

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 readln()), it gets the next line from this box.

Both functions run in O(n) time. The format only works when the original text contains no digits, which is a good follow-up question: how would you encode the string "a1b"? (Answer: add an escape character, or store counts in a separate list.) Spotting the limits of your own solution is what interviewers look for.

Exercise 5: two numbers that add up

Task. Given a list of integers and a target, return the indexes of two different elements whose sum equals the target, or null if none exist. Do it in one pass.

Hint. For each number, the partner you need is target - number. Keep a map from numbers already seen to their index.

Kotlin Solution 5: a map of seen values

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 readln()), it gets the next line from this box.

The brute force solution compares every pair in O(nยฒ). The map version needs one pass: O(n) time and O(n) memory, a classic trade of space for time. The partner is looked up before the current value is stored, so an element can never pair with itself (the third call, [3, 3], still works because the two threes are different elements). The if (partner != null) check matters because index 0 is a valid result; writing if (partner) is not possible in Kotlin, and ?: 0 would hide the "not found" case (see null safety).

Exercise 6: balanced brackets

Task. Check whether a string of ()[]{} characters (other characters are ignored) is balanced: every opener has a matching closer, in the correct order.

Hint. Push openers on a stack. When you see a closer, the top of the stack must be its opener.

flowchart LR
    A["next char"] --> B{"opener?"}
    B -- yes --> C["push onto stack"]
    B -- no --> D{"closer?"}
    D -- yes --> E{"stack top matches?"}
    E -- yes --> F["pop"]
    E -- no --> G["not balanced"]
    D -- no --> H["ignore"]

Each character either pushes, pops after a check, or is ignored. The string is balanced if the stack is empty at the end.

Kotlin Solution 6: a stack

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 readln()), it gets the next line from this box.

ArrayDeque is Kotlin's resizable double-ended queue and the right choice for stacks (the old java.util.Stack is synchronized and discouraged). removeLastOrNull() returns null on an empty stack, which never equals a bracket, so a closer without an opener fails without a special case. Time is O(n), memory is O(n) in the worst case. Note that < and > in the last input are not treated as brackets here, which is a requirement you should confirm in an interview.

Exercise 7: the longest substring without repeats

Task. Find the length of the longest substring in which no character appears twice. For "abcabcbb" the answer is 3 ("abc"), for "bbbbb" it is 1.

Hint. Slide a window across the string. Remember the last index of each character. When the new character was seen inside the current window, move the window's start just past that earlier occurrence.

Kotlin Solution 7: a sliding window

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 readln()), it gets the next line from this box.

A naive solution checks every substring for repeats in O(nยณ) or O(nยฒ). The window moves only forward, so each character is handled once, giving O(n) time and O(k) memory for k distinct characters. The check previous >= start is the bug people forget: a character seen before the window began must not move start backwards. The input "dvdf" tests exactly this case, and "pwwkew" shows that the answer is not unique ("wke" and "kew" are both length 3; the code returns the first).

Patterns to take with you

Seven different problems used only a few ideas, and they come back in almost every interview:

  • Count or group with a map (groupingBy, groupBy, HashMap): exercises 1, 2, 5 and 7.
  • A canonical form as a key: exercise 2.
  • Two pointers or a sliding window for sequences: exercises 3 and 7.
  • A stack for nested structure: exercise 6.
  • Trade memory for time with a lookup table: exercises 5 and 7.
  • Say the complexity out loud, and state your assumptions about empty input, case and characters.

For more practice, the same style continues in Practice Problems: Coroutines and Flow, and the interview questions lesson covers the theory questions that go with these.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the two-sum solution check the map before it stores the current value?

    If the current value were stored first, target - value could find the same element. Checking first means a partner always comes from an earlier index.
  2. 2. What is the time complexity of the sliding-window solution for the longest substring without repeats?

    Each character is visited once and the start index never moves backwards, so the work is linear in the length of the string.
  3. 3. Which collection is the best fit for a stack of brackets in Kotlin?

    ArrayDeque supports adding and removing at the end in constant time and grows as needed. removeLastOrNull is safe on an empty stack.
  4. 4. What does groupingBy { it }.eachCount() return?

    eachCount counts elements per key and returns Map<K, Int>, without building a list for each group.
  5. 5. In the anagram solution, why does sorting the letters of each word work as a map key?

    Anagrams contain the same letters in a different order, so sorting gives one canonical form for the whole group.

Summary

  • groupingBy().eachCount(), groupBy and HashMap solve most counting and grouping tasks; sort afterwards with sortedWith and thenBy for stable tie-breaking.
  • A canonical key (sorted letters) groups equivalent values.
  • Two pointers and sliding windows turn quadratic scans into linear ones.
  • ArrayDeque is the stack of choice; removeLastOrNull avoids special cases.
  • A map from seen values to indexes replaces nested loops (two-sum).
  • Always state time and memory complexity and your assumptions about empty input and characters.

Next: Practice Problems: Coroutines and Flow