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.
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
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
- Check for doubles, and if there are it’s not consistent, so break
- 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
- Build the array from the previous data set and merge into current so we can keep the results
- Create an array the we gonna use to compare
- Check if the keys are present in the array
- Break if we detected a match
- 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;
}
}
}
}