Geek asks and answers

Order a list of characters given a dictionary

I was asked this question in an interview. Suppose you have an ordered dictionary and you are given a list of unordered characters - how would you order these characters by priority? This dictionary contains words in which all 26 characters will be displayed. However, note that the size of the dictionary can be any. The dictionary can be either small or not contain separate sections for each character, for example, there can be no sections for words starting with a; although it awill appear as part of another word, for example, "bat".

The dictionary can be "ordered" (/ sarcasm) as such, "zebra", "apple", "cat", "rough", and if you are given a list of { a, z, r}, the correct procedure would be { z, a, r}. Since the "zebra" in front of the "apple" in the dictionary, we know what zprecedes athe presumption. Since the "apple" appears before the "cat", we know what aprecedes c. Since cat precedes crass, we know what aprecedes r. This ordering reserves cand rwith ambitious presendece, but as a list of letters was { a, z, r}, we know that the decision will be { z,a, r}.

+3
source share
3 answers

Use a directed graph with 26 vertices; each vertex represents a symbol. The edge from vertex A to vertex B means in the alphabet B before A.

The first step is to establish such a graph only with vertices, but without edges.

Secondly, you scan the input dictionary, word for word. And compare each word with the previous word. You need to find the exact relationship for every word you crawled. This way you add an edge to this graph. Suppose the dictionary is correct, there should be no conflict.

After you have finished the dictionary, you display the alphabet in

  • select a random vertex, go through its path until you find one symbol that indicates nothing. This is the first character in the alphabet. Bring it out and remove it from the chart.
  • 1 , .

EDIT: , .

: { "", "", "", "" }

0 1, , z a, a- > z

1 2, , , c- > a

Word 2 Word 3, "c", -, , a r, r- > a

. , (, c), c- > a- > z . z z ( NULL). (, r), ​​ r- > a . a a . (, c), , c . , r, , r . , .

: z, a, c, r. "c" "r" , .

+11

, "" < "" < "cat" < "crass", , N- , N 0, "z" < "a" < "c". (N + 1) - ( <= N). N == 1 "cat" "crass" "a" < "r".

x < y.

y\x a b c...r...z
a   -   N   N   Y
b     -
c   Y   -       Y
r   Y       -
z   N   N       -

, (.. {a, z, r} → az, ar, zr), a<z, a<r, z<r: - , . , , . .

, : , , "z" < "a" "c" "a" "r", , "z" < "". , "" , , (, z<a z<c)), , . , , , , .

+1

Depending on how you describe the problem, your example is incorrect. Your answer should be {z,r,a}. However, it may be lower, this is the code that solves the problem. You can change it to return an order different from my intended one {z,r,a}.

Set<Character> charPrecedence(List<String> dictionary, char[] letters){
    Set<Character> result = new HashSet<Character>();
    //since your characters are the 26 letters instead of the 256 chars
    // a bit vector won't do; you need a map or set
    Set<Character> alphabets = new HashSet<Character>();
    for(char c: letters)
       alphabets.add(c);

    //now get to work
    for(String word: dictionary){
       if(alphabets.isEmpty()) return result;
       for(char c: word.toCharArray()){
          if(alphabets.remove(c))
           result.add(c);
       }
    }
    //since the dictionary is guaranteed to contain all the 26 letters,
    //per the problem statement, then at this point your work is done.
    return result;
}

best case O (1); the worst case is O (n), where n is the number of characters in the dictionary, that is, one particular letter appears only once and is the last character you check.

-3
source

More articles:


All Articles