Domanda di colloquio

Colloquio per Research Scientist



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?


Risposte di colloquio

4 risposte


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


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


Hash table

Anonimo su


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

filipinorockstar su

Aggiungi risposte o commenti

Per lasciare un commento, accedi o registrati.