Amazon Interview Question
Java DevelopersCountry: India
Interview Type: In-Person
Should an array not sufficient for this?
While storing we just need to process the words & find out the relations between two alphabets
take the case where following relation has been established:
L->N->T
and S->X. How will you store it this information in single array. If you will use two different array then how will you manage multiple arrays. In the worst case you will have C(26,2) relations. Thus merging all these information will be a challenge.
an array indexed by the letter, whose value is the index of the next letter:
In C:
#define CNT 26
struct {
int next;
int prev;
} x[CNT];
int count = 0;
void init() {
int i;
for(i=0; i<CNT; i++)
x[i].prev = x[i].next = -1;
}
/* when findseq returns CNT, the mapping is completed */
void findseq(char *w1, char *w2) {
int i;
for(i=0; w1[i] != '\0'; i++) {
char c1 = w1[i];
char c2 = w2[i];
if (c1 != c2 && c2 != '\0' && x[c1-'A'].next == -1) {
x[c1-'A'].next = c2-'A';
x[c2-'A'].prev = c1-'A';
count++;
return count;
}
}
}
/* when findseq returned CNT, call this function: */
void print_result() {
int i;
for(i=0; i<CNT; i++) {
if (x[i].prev == -1)
break;
}
while(x[i].next != -1) {
print("%c\n", i+'A');
i = x[i].next;
}
consider the sequence {LMOSS,NMOSS},{LMOSS,KMOSS}.When the first pair arrives , then for x['L'] (or x[11]) next will have integer value for N. When the next pair arrives x['L'] will not be updated to K( since x[c1-'A'].next == -1 will fail) . There can be more than 1 alphabet which occur after L. similarly more than 1 alphabet can occur before any character. I guess this information is not being captured. Moreoever, we need to design merging process with this strategy
We can use graph. Edge A->B means B is after A in the alphabet. After we build it we do:
1. Find the node with only outcoming edges
2. If there are a few such nodes or no such a node we can't restore alphabet
3. Otherwise output this letter
4. Repeat steps 1-3 till the end
Note: only last node can have no edges, otherwise we can't restore alphabet.
Using an array to implement the adjacency matrix.
Half of the code is to generate random pair of letters for training.
<?php
$s = 'abcdefghijklmnopqrstuvwxyz';
$d = '';
for ($i = 25; $i >= 0; $i--) {
$p = rand(0, $i); $d .= $s[$p]; $s = join('', explode($s[$p], $s));
}
var_dump($d);
function pair($d) {
$i = rand(0, 25);
if ($i == 0) return [$d[0], $d[rand(1,25)]];
if ($i == 25) return [$d[rand(0, 24)], $d[25]];
if (rand(0, 1) == 0) return [$d[$i], $d[rand($i+1, 25)]];
return [$d[rand(0, $i-1)], $d[$i]];
}
$dist = [];
function get($p, &$dist) {
$a = $p[0]; $b = $p[1];
if (!isset($dist[$a])) $dist[$a] = [ 0 => [], 1 => []];
if (!isset($dist[$b])) $dist[$b] = [ 0 => [], 1 => []];
if (!in_array($b, $dist[$a][1])) {
$dist[$a][1][] = $b;
foreach ($dist[$a][0] as $c) get([$c, $b], $dist);
}
if (!in_array($a, $dist[$b][0])) {
$dist[$b][0][] = $a;
foreach ($dist[$b][1] as $c) get([$a, $c], $dist);
}
}
function check($dist) {
if (count($dist) != 26) return false;
foreach ($dist as $i => $co) {
if (count($dist[$i][0]) + count($dist[$i][1]) != 25) return false;
}
return true;
}
while (check($dist) == false) {
$p = pair($d);
print '(' . $p[0] . ',' . $p[1] . ") ";
get($p, $dist);
}
$k = [];
foreach ($dist as $l => $co) {
$k[count($co[0])] = $l;
}
ksort($k);
var_dump(join('', $k));
can we map relation comes after using edge between character and then use topological sort
- Anonymous September 17, 2014