Amazon Interview Question for Java Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 3 vote

can we map relation comes after using edge between character and then use topological sort

- Anonymous September 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Should an array not sufficient for this?

While storing we just need to process the words & find out the relations between two alphabets

- Anonymous September 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Anonymous September 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- acoder September 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Rather use 
struct {
  int [CNT-1]next;
  int [CNT-1]prev;
} x[CNT];

We need to analyze merging process with this approach

- Anonymous September 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The bit matrix with letters naming the columns and rows can be representing the relations between letters. For example the relation L->N can be represented by one in position {L, N}.

Using this matrix we can just sort the letters to get the character sequence in this new language

- borisshr September 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Dmitry September 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

- paul4156 September 20, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More