Domanda di colloquio

Colloquio per Research Scientist

-

Amazon

How to build a dictionary in such a way that it'd be efficient to search for all valid words which are permutations of a given string?

Risposta

Risposte di colloquio

4 risposte

1

For each word in a dictionary as a value, build a key which is composed of lexicographically ordered characters. For example, value = apple key = aelpp. value = ocotopus key = cooopstu Then build an index from the keys, and you'll have all of the words that can be generated from re-ordering the elements. The result is efficient at run-time because it's constant run time. The construction of the index is also efficient because it only needs to run linearly, once.

Anonimo su

0

Perhaps use a function of the sum of the string's char codes (and its length?) as a key in a first hashtable. This key should link to a second hashtable that would directly index each particular permutation of the word.

Lord Henry Wotton su

1

Hash table

Anonimo su

0

void print_in_order(Node* node) { std::stack nodes; nodes.push(node); while(!nodes.empty()) { Node* temp = nodes.top(); if (temp) { cout value left); nodes.push(node->right); } nodes.pop(); } }

filipinorockstar su

Aggiungi risposte o commenti

Per lasciare un commento, accedi o registrati.