In this session, we will be covering a few string based questions. These questions are deceptively simple, but have quite a few ways to throw you off!
- isAnagram: Given two strings, check if they are anagrams are not.
boolean isAnagram(String word1, String word2)
- FirstUniqueLetter: Given a string, print the first unique (non-repeated) letter in it.
char firstUniqueLetter(String word)
- Rearrangements: Given a string, print all the rearrangements of letters, keeping the vowels together.
void printArrangementsVowelsTogether(String word)
Note: If the question were, keep the consonants together is that the same?
- Given a string that contains only series of letters a or b. Write a function to compress the sequence of strings by encoding repetitions.
baaaaaab => ba6b(b followed by a 6 times, followed by b).
Also write a function to decompress the string
ba6b => baaaaaab.
- Given a string write a program to find the longest palindrome in a string?
Easy: O(n2) time & O(1) space, Hard: O(n) time & O(1) space.
- You are given a list of words that are in MixedCaseClassNameNotation, representing all the token names in your project. Write a function that accepts the “search keyword” and returns a list of tokens that match the search keyword. Capital letters are matched different from
Search => List
A => [full list]
Asp => [“AspectCloneMapperAdapter”, “AspectDecoratorFactory”]
AspD => [“AspectDecoratorFactory”]
AA => [“AbstractAdapterInfoPrototype”, “AnnotationAdapterComparator”]
- What is the character set? only letters, a-z, ascii or UTF-8?
- Are they only lower case characters? What if capitalization:
Solution Approaches: Should take about 2 minutes to narrow down to the algorithm and 5 minutes to implement it.
- Sort both words and compare. Works, but most interviewers will forbid you from modifying the string.
- Char counting?
- How about using a Set? Terrible idea. Set can only tell you if a letter is there or not.
- HashMap + Priority Queue
- Maintained in the ordered by insertion
- Deletion of element in the queue
- Insertion complexity is not constant
- FindFirstUniqueLetterAtAnyPoint Query is O(n)
- Set for counting
- Histogram for every subject
- Queue of unique elements
- First element in the queue is the result
- If the element is new, the element will not be evicted from the queue.
- New Front of the Queue may be dirty — evict it if so.
- Find all the arrangements among vowels
- Use each arrangement as a chunk and find all arrangements
- What if vowels were duplicated?
- Why is it a bad idea to use a set? Generating all useless combinations