Interviews

[Google SDE] Word Extensions

user profile image
System made a post.

When people send messages on their phones they sometimes modify word spelling by adding extra letters for emphasis. For example, if you want to emphasize hello you might write it hellloooooooo. Let's call the ls and the os word extensions. Regular text contains 2 or fewer of the same character in a row, while word extensions have 3 or more of the same character in a row. Given an input string representing one word, write a method that returns the start and end indices of all extensions in the word.

Example 1:

Input: "whaaaaatttsup"
Output: [[2, 6], [7, 9]]
Explanation:
"aaaaa" and "ttt" are twitching letters, so output their starting and ending points.
Example 2:

Input: "hellloooooooo"
Output: [[2, 4], [5, 12]]
Follow-up:
Now we want to spell-check extended words. You are given a dictionary of words. Implement method isExtendedDictionaryWord that will return:

true if it is a dictionary word.
true if you collapse the extensions in the word and it is a dictionary word.
false otherwise.

class SpellChecker {
	public SpellChecker(List dict) {
	}

	public boolean isExtendedDictionaryWord(String s) {
	}
}
Example:


SpellChecker checker = new SpellChecker(["hello"]);
checker.isExtendedDictionaryWord("hello"); // true 
checker.isExtendedDictionaryWord("heeello"); // true 
checker.isExtendedDictionaryWord("xyz"); // false

Each extension can only be collapsed to appear once or twice, e.g. heeello can be heello or hello.



One-on-One Algorithm and Coding Training

One-on-One System Design Training

One-on-One Mock Interview

Get one-to-one training from Google Facebook engineers


Top-notch Professionals

Learn from Facebook, Google, Uber senior engineers interviewed 100+ candidates.aonecode.com
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.


Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.


Free Consultation

aonecoding@gmail.com