Alien dictionary
You have been given a sorted (lexical order) dictionary of an alien language. Write a function that finds the order of characters in the alien language. This dictionary will be given to you in the form of an array of strings called 'dictionary,' of size 'N.'

Example :

If the dictionary consists of the following words:- ["caa", "aaa", "aab"] then, the order of alphabets are - ['c', 'a', 'b']

Note:

If the language consists of four letters, the four letters should be the starting four letters of the English language. However, their order might differ in the alien language.

Input format :

The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case or query contains an integer 'N' representing the size of the alien dictionary. The second line contains 'N' single space-separated strings representing the words in the alien dictionary.

Output Format :

For each test case, return an array of characters representing the order in which they will appear in the alien language. The first element of the array shall represent the first letter of the alien language. The second one will represent the second letter of the language, so on and so forth. You do not need to print anything, just return the array of letters as they will appear in the language. Output for every test case will be printed in a separate line.

Note :

If your order is correct, the output will be true. Otherwise, it will be false.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given functions.

Constraints :

1

Question

Alien dictionary

You have been given a sorted (lexical order) dictionary of an alien language. Write a function that finds the order of characters in the alien language. This dictionary will be given to you in the form of an array of strings called 'dictionary,' of size 'N.'

Example :

If the dictionary consists of the following words:-
["caa", "aaa", "aab"]
then, the order of alphabets are -
['c', 'a', 'b']

Note:

If the language consists of four letters, the four letters should be the starting four letters of the English language. However, their order might differ in the alien language.

Input format :

The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the alien dictionary.

The second line contains 'N' single space-separated strings representing the words in the alien dictionary.

Output Format :

For each test case, return an array of characters representing the order in which they will appear in the alien language. The first element of the array shall represent the first letter of the alien language. The second one will represent the second letter of the language, so on and so forth. 

You do not need to print anything, just return the array of letters as they will appear in the language. 

Output for every test case will be printed in a separate line.

Note :

If your order is correct, the output will be true. Otherwise, it will be false.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given functions.

Constraints :

1 <= t <= 100
0 <= N <= 10^5
0 <= Length of ARR[i] <= 10^5

Time Limit: 1 sec

Note :

The alien language consists of only lower case letters. However, their order might not be the same as the English language.

Accepted Answer

The task is to find the order of characters in an alien language given a sorted dictionary.

The order of characters can be determined by comparing adjacent words in the dictionary.
Create a graph where each character is a node and there is a directed edge from character A to character B if A comes before B in the alien language.
Perform a topological sort on the graph to get the order of characters.

Accepted Answer

Permutations Approach

Approach:

Find all the distinct characters present in all the words.
Generate all permutations of these distinct characters.
Treat each of the permutations as a correct sequence of alphabets. Now check if the given words are sorted according to this sequence. In order to do this, we will:-
- For all words from 1 to n - 1, let the current word be ‘currWord’ and the next word be ‘nextWord’.
- One by one compare characters of both words and find the first mismatching character. In case there was no mismatching character, we continue to the next word.
- Let us say that the mismatching characters were ‘ch1’ and ‘ch2’ in ‘currWord’ and ‘nextWord’ respectively.
- Now, if these words(currWord and nextWord) follow the dictionary, ‘ch1’ will occur before ‘ch2’ in the sequence.
In case the words are sorted according to the current sequence, we will return this sequence.

Space Complexity: OtherExplanation:

O(K) where K is the number of distinct characters

Since we are storing K distinct characters

Time Complexity: OtherExplanation:

O(K! * N * L), where K is the number of distinct characters, N is the number of words in the dictionary, and L is the maximum length of a word in the dictionary.

This is because we generate all possible permutations which costs K! operations for each word in the dictionary leading to a complexity of K! * N. Also, for each permutation we compare L characters which gives us an overall time complexity of K! * N * L.

Accepted Answer

Topological Sort

Approach: Here, if we consider ["wrt", “wrf”, ….] the first two of the words of the alien dictionary then by looking at the first mismatch in the characters tells us vital information on the order they occur!

That means, in from the above two words, we can say ‘t’ comes before ‘f’! We can denote this relation by, ‘t’ → ‘f’.

We can represent this relation using a directed graph!

Hence,

Iterate over all the words and make the graph representing the above relation. All the distinct characters will be the vertices of the graph whereas, the relation, mapping which character comes before another character will be the directed edge.
Do a Topological Sort over the built graph and return one of the possible orders for the same.

Space Complexity: OtherExplanation:

O(K), where K represents the total number of unique characters.

Since we are storing K distinct characters

Time Complexity: OtherExplanation:

O(N + K), Where N is the total number of words and K is the total number of unique characters present in the list of N words.

The time complexity of Topological Sort is O(V + E) where V is the number of vertices and E is the number of edges, which is O(K + N).

You have been given a sorted (lexical order) dictionary of an alien language. Write a function that finds the order of characters in the alien language. This dictionary will be given to you in the form of an array of strings called 'dictionary,' of size 'N.'

Example :

Note:

Input format :

Output Format :

Note :

Note:

Constraints :

Note :

Top AVL Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern