Word Finder Challenge

Solution for the Qu developer challenge: given a character matrix (up to 64x64) and a large stream of words, find the top 10 most repeated words from the stream that appear in the matrix, horizontally (left to right) or vertically (top to bottom).

public class WordFinder
{
    public WordFinder(IEnumerable<string> matrix) { ... }
    public IEnumerable<string> Find(IEnumerable<string> wordstream) { ... }
}

Quick start

dotnet test                                          # build + run the 27 tests
dotnet test --collect:"XPlat Code Coverage"          # same, collecting coverage
dotnet tool restore                                  # one time, installs ReportGenerator
dotnet reportgenerator -reports:coverage/**/coverage.cobertura.xml -targetdir:coverage/report -reporttypes:Html

Requires the .NET 8 SDK (or newer).

Solution design

The statement gives two strong hints: the matrix is small and immutable (capped at 64x64) while the word stream is large. So the design moves all the heavy work to the constructor and makes each stream query as cheap as possible:

1. Constructor: builds a SubstringOccurrenceIndex, a dictionary from every possible horizontal and vertical substring of the matrix to the number of times it occurs (overlapping occurrences included). Worst case that is 128 lines (64 rows + 64 columns) of length 64, about 266k insertions performed exactly once, a few MB of memory.
2. Find: streams through the words with a single pass. Each word goes through two cheap pre-filters (empty or longer than any matrix line), a HashSet that discards stream duplicates, and finally one O(1) average dictionary lookup. The cost of consuming the stream is therefore independent of the matrix contents, which is exactly what you want when the stream is the unbounded side of the problem.
3. The matched words are ranked by their occurrence count in the matrix, ties are broken ordinally for deterministic output, and the top 10 is returned.

Why not scan the matrix per word?

Scanning the matrix for each word costs O(S * R * C) with S the stream size. With a huge stream that is orders of magnitude slower than paying O((R + C) * L^2) once and answering each word in O(1). An Aho-Corasick automaton over the stream words was also considered; it wins when the matrix is much larger than this challenge's 64x64 cap or when memory is severely constrained, but for the given bounds the precomputed index is simpler, faster per query and keeps Find free of any matrix work. The trade-off is documented in the code.

Structure and SOLID

Piece	Responsibility
WordFinder	Public contract required by the challenge: filtering, dedupe, ranking, top 10.
ISearchIndex	Abstraction over the lookup strategy (dependency inversion seam).
SubstringOccurrenceIndex	Precomputed substring index, the performance core.
MatrixValidator	Structural invariants of the matrix (size, jagged rows, null rows).

Single responsibility: each class has one reason to change. Open/closed and dependency inversion: WordFinder depends on ISearchIndex, so the strategy can be replaced (and is replaced by a fake in the tests) without touching the ranking logic. Interfaces were kept internal on purpose: the challenge fixes the public surface, and exposing extension points nobody asked for would be speculative complexity, not design.

Complexity summary

Operation	Time	Notes
Constructor	O((R + C) * L^2)	R, C, L <= 64. ~266k substring insertions worst case, done once.
Find	O(S) average	S = stream size. One dictionary lookup per unique word.
Memory	O(distinct substrings)	Bounded by the 64x64 cap, a few MB worst case.

Assumptions (documented decisions)

The statement leaves a few points open. The choices, all covered by tests:

• "Top 10 most repeated" is interpreted as repetitions inside the matrix, since the statement explicitly says repeated words in the stream must be counted only once.
• Overlapping occurrences count: in a row "aaaa", the word "aa" occurs 3 times.
• Matching is ordinal and case sensitive. A case-insensitive variant is a one-line change (the comparer passed to the index).
• Ties are broken by ordinal order so the output is deterministic.
• Null or empty stream entries are ignored (a huge real-world stream is rarely clean); a null stream or an invalid matrix throws ArgumentNullException / ArgumentException.

Tests and coverage

27 tests cover the statement example, ranking, stream dedupe, overlaps, verticals, case sensitivity, tie-breaking, the 64x64 + 200k-words stress path, input validation and the index in isolation (plus the WordFinder ranking logic against a fake index).

Line coverage:   100%  (95 of 95 lines)
Branch coverage: 97.3% (37 of 38 branches)
Method coverage: 100%  (10 of 10 methods)

The build treats warnings as errors with the latest-recommended .NET analyzers enabled, and CI (GitHub Actions) builds, tests and publishes the coverage report on every push.

Possible next steps

• SearchValues / span-based lookups (.NET 9 alternate lookup) to avoid allocations on the query side if profiling ever shows pressure there.
• Aho-Corasick strategy behind ISearchIndex if the matrix cap grows significantly.
• BenchmarkDotNet suite to put numbers on the constructor/query trade-off.