Coding Problem - Phone List

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:

Emergency 911
Alice 97 625 999
Bob 91 12 54 26

In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1≤t≤40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1≤n≤10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

NO
YES

Solution

Lets see how we would go about solving this.

Since the maximum length of a number is 10 digits, we would iterate over the list backwards, and check for doubles.

To be able to detect if the list is consistent or not, the algorithm would be something along these lines.

Algorithm 1

Group the numbers by length in an array (Hash tree)
Check for doubles, if there is a double then it’s not consistent, don’t proceed with the test, even though it says it’s unique, you never know what could happen, so it doesn’t hurt to try, and it doesn’t hurt the performance too much
Iterate over the the array backwards from the biggest available number length
1. Check for doubles, and if there are it’s not consistent, so break
2. If MAX_NUMBER_LENGTH = CURRENT_NUMBER_LENGTH or CURRENT_NUMBER_LENGTH == MAX_NUMBER_LENGTH_IN_LIST, then we continue as it’s consistent and there are no duplicates
3. Build the array from the previous data set and merge into current so we can keep the results
4. Create an array the we gonna use to compare
5. Check if the keys are present in the array
6. Break if we detected a match
7. Add the values to current index, so we can compare with previous one on the next run

This is implemented in PHP

Algorithm 2

Another way to do this is to use a Tree, and each of the Nodes needs to have 10 leafs (one for each digit of a number), and you build the Tree by appending another Tree onto the leaf. If it’s a new leaf (the node is consistent if the digit position of the processing number equals the length of the number). If it’s not a new leaf, but the node is consistent, then the list of number is not consistent, also the same applies if the digit position of the processing number equals the length of the number.

This is implemented in Java

Implementations

There are a lot of ways to do this, some faster some slower, a slower one would be to use a sort algorithm, but this is not good for really big values.

The input sample provided by the problem is OK, but we need better one, so here is firstly a script that will generate random test cases, for us to test. Simplest is here in PHP, but we can use it for testing in the other languages too.

<?php
$test = rand(1, 40);
$testname = utime();
file_put_contents("rt-$testname", "$test\n");

$line = 1;

for ($i = 0; $i < $test; $i++) {
    $numbers = rand(1, 10000);
    file_put_contents("rt-$testname", "$numbers\n", FILE_APPEND);
    $line++;
    for ($n = 0; $n < $numbers; $n++) {
        $number = rand(100, 9999999999);
        file_put_contents("rt-$testname", "$number\n", FILE_APPEND);
        $line++;
    }
}

PHP

<?php

$output = array();

$stdin = fopen('php://stdin', 'r');
$totalTests = trim(fgets($stdin));
$maxLengthNumber = 10;

for ($i = 0; $i < $totalTests; $i++) {

    $totalNumbers = trim(fgets($stdin));

    $list = array();
    $numbers = array();

    // 1. Group the numbers by length in an array
    for ($a = 0; $a < $totalNumbers; $a++) {
        $phone = trim(fgets($stdin));
        $numbers[] = $phone;
        $digits = strlen($phone);
        $list[$digits][] = $phone;
    }

    if ($totalNumbers != count(array_flip($numbers))) {
        // 2. Check for doubles, if there is a double then it's not consistent
        $isConsistent = false;
    } else {
        $isConsistent = true;
        // 3. Iterate over the the array
        $keys = array_keys($list);
        sort($keys);
        $keys = array_reverse($keys, SORT_NUMERIC);
        $max_key = max($keys);
        foreach ($keys as $index => $key) {

            $totalItems = count($list[$key]);

            // 3.1. Check for doubles, and if there are it's not consistent, so break
            if ($totalItems != count(array_flip($list[$key]))) {
                $isConsistent = false;
                break;
            }

            // 3.2. If MAX_NUMBER_LENGTH = CURRENT_NUMBER_LENGTH || $key == $max_key, then we continue as it's consistent and there are no duplicates
            if ($maxLengthNumber == $key || $key == $max_key) {
                $isConsistent = true;
                continue;
            }

            // 3.3. Build the array from the previous data set and merge into current so we can keep the results
            $prevCut = array();
            $prev = array();
            $currentListIndex = $keys[$index];
            $prevListIndex = $keys[$index + 1];

            // 3.4. Create an array the we gonna use to compare
            foreach ($list[$prevListIndex] as $idx => &$val) {
                $prevCut[$idx] = substr($val, 0, $key);
                $prev[$idx] = $val; // point it as a reference for faster memory access
            }

            // 3.5. Check if the keys are present in the array
            $prevCutKeys = array_flip($prevCut);
            foreach ($list[$currentListIndex] as $idx => $val) {

                if (isset($prevCutKeys[$val])) {
                    $isConsistent = false;
                    break;
                } else {
                    $isConsistent = true;
                }

            }

            // 3.6. Break if we detected a match
            if (!$isConsistent) {
                break;
            }

            // 3.7. Add the values to current index, so we can compare with previous one on the next run
            foreach ($prev as $val) {
                $list[$currentListIndex][] = $val;
            }

        }
    }
    array_push($output, $isConsistent ? "YES" : "NO");

}

$out = fopen('php://output', 'w'); //output handler
fputs($out, join("\n", $output) . "\n"); //writing output operation
fclose($out);

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class PhoneList {

    public static final String YES = "YES";
    public static final String NO = "NO";
    private static Tree tree = new Tree();
    private static boolean isConsistent = true;

    private static class Tree {
        int node = 0;
        boolean isCons = false;
        Tree[] next = new Tree[10];

        public void setNext(int index, Tree t) {
            next[index] = t;
        }

        public Tree getTree(int index) {
            return next[index];
        }
    }

    // Should be on a separate class
    public static void main(String[] args) {
        PhoneList phoneList = new PhoneList();
        try {
            phoneList.build();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void build() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(reader.readLine());
        for (int i = 0; i < t; ++i) {
            int n = Integer.parseInt(reader.readLine());
            tree = new Tree();
            isConsistent = true;
            for (int j = 0; j < n; ++j) {
                String phone = reader.readLine();
                if (isConsistent)
                    buildTree(phone);
            }
            if (isConsistent)
                System.out.println(YES);
            else
                System.out.println(NO);
        }
    }

    private void buildTree(String s) {
        int len = s.length();
        Tree auxTree = tree;
        for (int i = 0; i < len; ++i) {
            int ch = Integer.parseInt(s.substring(i, i + 1));
            Tree aux = auxTree.next[ch];
            if (aux == null) {
                aux = new Tree();
                aux.node = 1;
                if (i == len - 1)
                    aux.isCons = true;
                auxTree.setNext(ch, aux);
                auxTree = aux;
            } else {
                if (aux.isCons) {
                    isConsistent = false;
                    break;
                }
                if (i == len - 1) {
                    isConsistent = false;
                    break;
                }
                auxTree = aux;
            }
        }
    }

}