Developer interview questions shared by candidates
Find all anagrams in a file. Improve the running time to O(n).
for each work in the file, sort the letters in the work and add the result into a stack, if there is a collision, the original word is part of set whose words in that set is an anagram. Since adding to a stack only take O(1) and you must visit each word once, the complexity is O(n).
The way I approach anagrams is that I assign a prime number to each letter and then multiply the letters. In theory, ABC gives you say 3 * 5 * 7 = 105 Any anagram will have letters that when multiplied give you 105. In the solution above, it's far more than O(n) because of the sort step which depending on how you're trying to sort could wind up nlogn or n2 or something like that.
I should note that this is generally good to about 9 characters, at which point overflowing becomes an issue and you'll probably want to go to some construct such as BigInteger in Java or go with what Anonymous presented.
See Interview Questions for Similar Jobs
- Software Engineer
- Software Developer
- Senior Software Engineer
- Software Development Engineer II
- Software Development Engineer I
- Software Engineer Intern
- Senior Software Development Engineer
- Software Engineer II
- Software Development Engineer In Test
- Software Engineering
- Data Scientist
- Java Developer
- Senior Software Developer
- Program Manager
- Product Manager
- Associate Software Engineer