'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before', 'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before',
Update appNew update is available. Click here to update.
Topics

Longest Common Prefix

Moderate
0/80
Average time to solve is 30m
12 upvotes
Asked in company
Google

Problem statement

Vidit is frequently among the "Wrong-doers" list. To curb his menace, Ms. Manisha, his algorithms teacher, gave him an assignment to keep him busy.

Ms. Manisha coins a term "longest common prefix", which is defined as longest word with which both words start with. For example: the longest common prefix of words: "notify" and "notification" is the word "notif".

Now, Ms. Manisha gives a database of N words to Vidit. Ms. Manisha also gives an algorithm to search a word X in the database. The algorithm is simple and is written as:

1. Compare the word X with each word in the database. We keep on comparing till we find a mismatching letter or end of one of the words is reached.

2. After that it is established either words are equal/unequal or that one is longer than the other.

3. When the algorithm finds the word X in the database, it terminates.

Analysing the algorithm, it shows that the number of steps needed to find a word W is equal to the sum of the lengths of the longest common prefixes of X and each of the words it was compared to.

Vidit comes to you and asks you to write a program that calculates the number of steps the algorithm uses to find each of the Q query words.

Detailed explanation ( Input/output format, Notes, Images )
Constraints:
 Time Limit: 2 seconds
Output Format:
 Output one integer per line for each query word, the number of steps the algorithm uses when searching for the word.   
Sample Test Cases:

Sample Input 1:

8
majmunica
majmun
majka
malina
malinska
malo
maleni
malesnica
3
krampus
malnar
majmun

Sample Output 1:

8
29
14

Explanation:

In the first test case, the number of steps to search for the word "krampus" is 8 because the algorithm only needs to compare its first letter to each word in the database.
When searching for the word "malnar", we need three steps for each of the first three words, and four steps for each of the remaining five words, for a total of 29 steps.
To find the word "majmun" we use a total of 14 steps. For the first word in the database, we have six successful comparisons and one step in which we determine that the word "majmunica" is longer than the query word. For the second word, we also have six successful comparisons and a final step in which it is established that the words are equal. After finding the word, the algorithm terminates with great joy
Full screen
Console