QA coding round: strings with worked solutions

This is a coding-round rehearsal, not a list of language definitions. Start each exercise by stating the input contract, work one example on paper, then explain why the output is correct. Python blocks below are self-contained and were executed with Python 3.14.4. They do not establish Java behaviour.

Clarify before coding

1. What does “reverse a string” mean?

Ask whether reversal means characters, words or displayed symbols. For the ASCII test identifier QA-12, character reversal produces 21-AQ; word reversal is a different problem. Python string slicing operates on code points, so a combining accent can become detached from its base letter. Do not present this exercise as a production solution for every writing system.

2. How do you reverse without a reverse helper?

Collect characters from the final index down to zero and join once. This visits each code point once and uses linear additional space for the result. Repeatedly prepending to an immutable string can create many intermediate copies.

def reverse_text(text):
    chars = []
    for i in range(len(text) - 1, -1, -1):
        chars.append(text[i])
    return ''.join(chars)

assert reverse_text('QA-12') == '21-AQ'
assert reverse_text('') == ''
assert reverse_text('x') == 'x'

Likely follow-up: Can it be in place? Not with an immutable Python string. A mutable character buffer changes the contract and may allow swaps.

3. How would you test reversal beyond one example?

Include empty input, one character, repeated letters and spaces that must be preserved. Reversing twice should recover the original sequence, but that property alone is insufficient: a function that always returns its input also satisfies it. Pair properties with known outputs such as ab becoming ba.

Equality problems

4. How do you check a palindrome without making a reversed copy?

Compare the outer characters and move inward; stop at the first mismatch. This version treats punctuation, spaces and case literally, and defines the empty string as a palindrome. It takes linear time in the worst case and constant auxiliary space.

def palindrome(text):
    left, right = 0, len(text) - 1
    while left < right:
        if text[left] != text[right]:
            return False
        left += 1
        right -= 1
    return True

assert palindrome('abba')
assert palindrome('')
assert not palindrome('Aba')
assert not palindrome('abca')

5. What changes when punctuation and case should be ignored?

Specify normalization as a separate requirement; do not silently make every comparison forgiving. For this exercise, retain alphanumeric code points and case-fold them before applying the palindrome check. A punctuation-only input then normalizes to empty, so ask whether the product should reject it instead of accepting it.

def normalized(text):
    return ''.join(c for c in text.casefold() if c.isalnum())

value = normalized('Never odd, or even!')
assert value == 'neveroddoreven'
assert value == value[::-1]
assert normalized('!!!') == ''

6. How do you decide whether two strings are anagrams?

Require equal character multiplicities, not merely equal sets. Here comparisons are literal: aab and aba match, but aab and abb do not. A frequency table is expected linear time under ordinary hash-table assumptions, with space proportional to the distinct characters.

from collections import Counter

def anagram(left, right):
    return Counter(left) == Counter(right)

assert anagram('aab', 'aba')
assert not anagram('aab', 'abb')
assert anagram('', '')
assert not anagram('Tea', 'eat')

Likely follow-up: What if hash maps are forbidden? Sort both character sequences and compare them, explaining the usual O(n log n) sorting cost.

7. Why can visually identical strings compare differently?

A letter plus combining accent can differ from its precomposed representation. NFC normalization can align canonically equivalent forms; it does not mean that every visually similar symbol should become equal. For identifiers or passwords, follow the product's documented policy instead of applying normalization just to make a test pass.

import unicodedata

composed = '\u00e9'
decomposed = 'e\u0301'
assert composed != decomposed
assert unicodedata.normalize('NFC', composed) == unicodedata.normalize('NFC', decomposed)

Counting and preserving order

8. How do you return duplicate characters with their counts?

Count every character, then keep counts greater than one. Decide whether spaces count and whether output order matters; this example includes spaces and follows first appearance. Saying that banana has “three duplicates” is ambiguous: it has two distinct repeated characters and three occurrences beyond the first copies.

from collections import Counter

def duplicates(text):
    return [(char, count) for char, count in Counter(text).items() if count > 1]

assert duplicates('banana') == [('a', 3), ('n', 2)]
assert duplicates('abc') == []
assert duplicates('  ') == [(' ', 2)]

9. How do you find the first non-repeating character?

Build the counts, then scan the original string to find the first count of one. Returning an arbitrary key from a set loses the meaning of “first.” Use None when no answer exists, keeping that result distinct from a valid character.

from collections import Counter

def first_unique(text):
    counts = Counter(text)
    return next((c for c in text if counts[c] == 1), None)

assert first_unique('swiss') == 'w'
assert first_unique('aabb') is None
assert first_unique('') is None

10. How do you remove duplicates while keeping first occurrence?

Track seen characters separately from the output. Sorting first would change cabca into a different order, violating the contract even if duplicates disappeared. The set is for membership; the list determines output order.

def unique_characters(text):
    seen, output = set(), []
    for char in text:
        if char not in seen:
            seen.add(char)
            output.append(char)
    return ''.join(output)

assert unique_characters('cabca') == 'cab'
assert unique_characters('') == ''

11. How do you reverse word order while preserving words?

First ask whether whitespace must be preserved. Splitting without an explicit separator collapses runs of whitespace, so the implementation below deliberately normalizes spaces. If a UI snapshot requires original spacing, this contract is unsuitable and needs tokenization that retains separators.

def reverse_words(text):
    return ' '.join(text.split()[::-1])

assert reverse_words('  test\tAPI now ') == 'now API test'
assert reverse_words('   ') == ''

12. How should you explain a solution when time runs out?

State the working contract, walk the current code with one failing edge case and describe the smallest fix. For an anagram solution that uses sets, use aab versus abb to expose the defect, then propose counts. Avoid claiming broad Unicode support when you tested only ASCII; precise limits are part of a correct answer.

Practise it

Choose three exercises and write them without looking. Add an assertion that would catch a plausible wrong solution, then explain its time and space costs. Use fake search strings from ShopLite as data; these algorithms are interview practice, not evidence that the app has those behaviours.