How do you find a contact by a partial phone number?

Reported. A November 2020 Codility report gave a full statement for this task.

Problem. Contacts are stored as two arrays of the same length: names[k] is the name of contact k and phones[k] is that contact's phone number, stored as a string. Given a typed prefix or fragment P, return the name of a contact whose phone number contains P as a contiguous substring. If several contacts match, return the alphabetically smallest name. If none match, return "NO CONTACT".

The report's own examples:

• names = ["pim", "pom"], phones = ["999999999", "777888999"], P = "88999" → "pom"
• names = ["sander", "amy", "ann", "michael"], phones = ["123456789", "234567890", "789123456", "123123123"], P = "1" → "ann" (sander, ann and michael all contain "1", and "ann" is the smallest name)
• The statement also notes that "436800143" contains "6800" but not "3614"

Inferred constraints (not in the report): treat numbers as strings, not integers, so leading zeros stay meaningful; names and phones have equal length; P may be empty (every string contains the empty substring, so you would return the alphabetically smallest name — worth confirming in the interview).

Approach. Scan the contacts once. Whenever phones[i].contains(P), keep the lexicographically smaller of the names seen so far. You can also drop matching names into a TreeSet and return first(). Java's String.contains is a substring search, which is exactly what the statement asks for. Time is O(N × (L + M)) with a standard substring scan, where L is a number's length and M is |P|. Extra space is O(1) if you keep a single best name, or O(K log K) if you collect K matches in a tree. A trie of the phone numbers is an Inferred alternative that helps only if you expect many queries over a fixed contact list; the report did not ask for it.

public class ContactSearch {
    static String contactByPhone(String[] names, String[] phones, String partial) {
        if (names == null || phones == null || partial == null) return "NO CONTACT";
        if (names.length != phones.length) {
            throw new IllegalArgumentException("names and phones must be the same length");
        }
        String best = null;
        for (int i = 0; i < phones.length; i++) {
            if (phones[i] != null && phones[i].contains(partial)) {
                if (best == null || names[i].compareTo(best) < 0) best = names[i];
            }
        }
        return best == null ? "NO CONTACT" : best;
    }

    public static void main(String[] args) {
        System.out.println(contactByPhone(
                new String[] {"pim", "pom"},
                new String[] {"999999999", "777888999"},
                "88999")); // pom
        System.out.println(contactByPhone(
                new String[] {"sander", "amy", "ann", "michael"},
                new String[] {"123456789", "234567890", "789123456", "123123123"},
                "1")); // ann
        System.out.println(contactByPhone(
                new String[] {"x"}, new String[] {"436800143"}, "3614")); // NO CONTACT
    }
}

Verified with OpenJDK 21.0.13: it prints pom, ann and NO CONTACT.

Edge cases and follow-ups. No match; several matches (must pick the smallest name, not the first in input order); P in the middle of a number, not only as a prefix; a fragment that is a subsequence but not a substring; duplicate names; clarifying what to do if P is empty.