## Google Interview Question for Site Reliability Engineers

Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
7
of 7 vote

I found this really hard. It would be fairly straightforward if the words were not concatenated. I came up with some sort of complicated solution involving building a multimap of words of different lengths, so you read n letters, check for a word which matches all letters in the map of words of n length, but I assume there must be a simpler solution.

There's also a major problem if you get a false match. For example, if "hello" is scrambled as "ehllo", the first word you would probably try is "he". At some point you presumably decide "he" is incorrect, so then your next match might be "hell". That is incorrect as well though. There has to be some mechanism for backtracking the process and deciding that the previously tried word (or even words) must be incorrect.

Comment hidden because of low score. Click to expand.
5
of 5 vote

You can take advantage of the byte representations of the characters and make the key of your dictionary to be the tuple of (product,sum) of the integer representations of the bytes. It's invariant to shuffling because of the associative property of addition and multiplication but not to changing the contents (see proof below). Code in Python.

``````scramble = 'ehllotehotwolrd'
wordset = {'hello','to','the','world'}

def wordsetToDict(wordset):
worddict = {}
for word in wordset:
key = 1
key2 = 0
for c in word:
key *= ord(c)
key2 += ord(c)
worddict[(key,key2)] = word
return worddict
worddict = wordsetToDict(wordset)
print(worddict)

def unscramble(scramble,worddict):
outstr = ''
key = (1,0)
counter = 0
begin = 0
while (counter < len(scramble)):
c = scramble[counter]
# make c to be considered in key
key = (key[0]*ord(c),key[1]+ord(c))
# test for existence in wordset
if key in worddict:
# Add word to output string
outstr += worddict[key] + ' '
# update where to begin
begin = begin + len(worddict[key])
# move counter to the beginning
counter = begin
# reset key
key = (1,0)
else:
# increment counter
counter += 1
return outstr[0:(len(outstr)-1)]

unscramble(scramble,worddict)``````

Proof:
Suppose we have two, two character strings (x1,x2,y1,y2 represent any possible character), 'x1y1', 'x2y2'
Question: can we have a collision if x1 != x2,y2 or y1 != x2,y2? collision means product and sum are equal
WLOG assume x1 != x2, y2.
Then ord(x1) != ord(x2), ord(y2)
Suppose ord(x1)*ord(y1) = ord(x2)*ord(y2) and ord(x1)+ord(y1) = ord(x2)+ord(y2)
then ord(y1) = ord(x2)*ord(y2)/ord(x1)
but ord(y1) is an integer. meaning ord(y2)/ord(x1) or ord(x2)/ord(x1) is an integer. Hence there is some k such that ord(x1)*k = ord(x2) or ord(x1)*k = ord(y2). k != 1.
case 1: ord(x1)*k = ord(x2)
So, ord(x1)*ord(y1) = ord(x1)*k*ord(y2) => ord(y1)/k = ord(y2) => ord(x1)+ord(y1) = ord(x1)*k+ord(y1)/k
This means k must equal 1. contradiction!
Similarly for case 2.
So we know that the sum and product of ordinals are invariant with respect to shuffling, but not with respect to changing the contents of the string.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Find anagram, for each anagram look in the dictionary to see the word exists, if it does then we have found the word. You may end up in finding more meaningful words since the characters get re-arranged in anagram

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why can't this just be a case of finding permutations of a string and compare it with the dictionary and see if its present. If the word is present then append to a string builder and return the stringbuilder

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package smapleQuestionsAlgorithms;

import java.util.HashSet;
import java.util.Set;

//swap positions. used for makeSentence() function
public static String swapStringIndexes(String s, int i, int j){
char[] arr=s.toCharArray();
char dummy=arr[i];
arr[i]=arr[j];
arr[j]=dummy;
return new String(arr);
}
//Generates permutations of string and returns a string if it is found in dictionary or return ""
public static String wordExists(String s,Set<String> dictionary,int i,int j){
if(i==j){
if(dictionary.contains(s)){
return s;
}
}else{
for(int k=i;k<j;k++){
String found=wordExists(swapStringIndexes(s, i, k),dictionary,i+1,j);
if(dictionary.contains(found)){
return found;
}
}
}
return "";
}
//return sentence if can be formed with the given string or return ""
public static String makeSentence(String s,Set<String> dictionary,String sentenceBuilder){
if(s.isEmpty()){
return sentenceBuilder; //sentenceBuilder;
}else{
for(int i=1;i<=s.length();i++){
String first=s.substring(0,i);
String second=s.substring(i);
String foundWord=wordExists(first, dictionary, 0, i);
if(!foundWord.isEmpty()){
String sentence=makeSentence(second, dictionary, sentenceBuilder+foundWord+" ");
if(!sentence.isEmpty()){
return sentence;
}
}
}
}
return "";
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Set<String> dictionary=new HashSet<>();
System.out.println(makeSentence("elhloothtedrowl", dictionary,""));
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the solution. Please let me know if there is any mistake.

``````import java.util.HashSet;
import java.util.Set;

//swap positions. used for makeSentence() function
public static String swapStringIndexes(String s, int i, int j){
char[] arr=s.toCharArray();
char dummy=arr[i];
arr[i]=arr[j];
arr[j]=dummy;
return new String(arr);
}
//Generates permutations of string and returns a string if it is found in dictionary or return ""
public static String wordExists(String s,Set<String> dictionary,int i,int j){
if(i==j){
if(dictionary.contains(s)){
return s;
}
}else{
for(int k=i;k<j;k++){
String found=wordExists(swapStringIndexes(s, i, k),dictionary,i+1,j);
if(dictionary.contains(found)){
return found;
}
}
}
return "";
}
//return sentence if can be formed with the given string or return ""
public static String makeSentence(String s,Set<String> dictionary,String sentenceBuilder){
if(s.isEmpty()){
return sentenceBuilder; //sentenceBuilder;
}else{
for(int i=1;i<=s.length();i++){
String first=s.substring(0,i);
String second=s.substring(i);
String foundWord=wordExists(first, dictionary, 0, i);
if(!foundWord.isEmpty()){
String sentence=makeSentence(second, dictionary, sentenceBuilder+foundWord+" ");
if(!sentence.isEmpty()){
return sentence;
}
}
}
}
return "";
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Set<String> dictionary=new HashSet<>();
System.out.println(makeSentence("elhloothtedrowl", dictionary,""));
}

}``````

Comment hidden because of low score. Click to expand.
0

The wordExist() function is too complex, you can just count every character of the word and compare them to know they are scramble or not.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Apologise for duplicate submission.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// ZoomBA : Imperative solution, because people may not like the declarative one
/*
Two phases to do it.
1. Generate all possible splitting - partition of the input string
2. Given a partition, sort the individual words in the split
3. Check if all the words belongs to the dictionary by matching them
4. Against a pre word sorted dictionary
*/
def do_googles_bidding( string , sorted_dict ){
len =  #|string|
for ( n : [ 0 : 2 ** (len - 1)] ){
sn = str(n,2)
sn = '0' ** ( len - #|sn| ) + sn // 0 padded
end = len - 1 ; start = end
partitions = list()
failed = false
while ( start >= 0 ){
if ( sn[start] == _'1' ){
p = string[start:end]
// generate the key by sorting chars, and checking
lc = p.toCharArray() ; sorta(lc) ; lc = str(lc,'')
break ( !(lc @ sorted_dict) ) { failed = true }
end = start - 1
}
start -= 1
}
if ( !failed && end >= 0 ){
p = string[0:end]
lc = p.toCharArray() ; sorta(lc) ; lc = str(lc,'')
if ( lc @ sorted_dict ) {
println( partitions )
return partitions
}
}
}
return []
}
// generate the sorted dict
sorted_dict = mset ( read( '/usr/share/dict/words' ) ) -> {
lc = \$.o.toLowerCase() ; sorta( lc.value ) ; lc }
result = do_googles_bidding( 'elhloothtedrowl' , sorted_dict )
println ( result )``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

backtracking with pruning

Comment hidden because of low score. Click to expand.
0
of 0 vote

As our previous code was grossly complex, this one does crack the algo fine. nJoy, ZoomBA

``````/*
1. Start with the substring from start which is anagram of a word
2. Now match recursively the rest
3. Test if everyone can generate a non empty  word list or not
Doing it recursively, push to stack if need be : string, words_until_now
*/
def do_googles_bidding( string , sorted_dict , words_until_now ){
for ( end : [0:#|string|] ){ // making it non trivial
s = string[0:end] // splice
sorta( s.value ) // sort and gen key
if ( s @ sorted_dict ){
if ( end == #|string| - 1 ){ // in this case, we have found a match
// note : I am not translating back the actual words, that is trivial
println ( words_until_now + ',' + s ) ; return }
// now, do on the suffix string
do_googles_bidding( string[end+1:-1] , sorted_dict ,  words_until_now  + ',' + s )
}
}
}
// generate the sorted dict
sorted_dict = mset ( file( '/usr/share/dict/words' ) ) -> {
lc = \$.o.toLowerCase() ; sorta( lc.value ) ; lc }
do_googles_bidding( 'elhloothtedrowl' , sorted_dict , '')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def google1(input):
d = dict()
d["hello"] = sorted("hello")
d["to"] = sorted("to")
d["the"] = sorted("the")
d["world"] = sorted("world")

start = 0
s = ""
for i in range(1, len(input) + 1):
for k,v in d.items():
if(sorted(input[start:i]) == v):
s = s + k + " "
start = i
print(s)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool isAnagram2(string s1,string s2) {
sort(s1.begin(),s1.end()) ;
sort(s2.begin(),s2.end());

return s1==s2;

}

vector<string> dict ={ "our","us","hello", "the", "world","to"};

string checkAnagraminDict(string s)
{
for( string w : dict) {
if (isAnagram2(w,s))
return w;
}

return "";
}
string unscramble(string s)  {

int len= s.length();
string nstr;

int i=0;
int l=1;
do{
string nw = checkAnagraminDict(s.substr(i,l));

if (nw == "")  {
l++;
}
else {
nstr.append(nw);
nstr.append(" ");
i = i+l;
l = 1;
}

}while ( i < len );

return nstr;

}

void interviewquestion()
{
cout << unscramble("elhloothtedrowl") << endl;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool isAnagram2(string s1,string s2) {
sort(s1.begin(),s1.end()) ;
sort(s2.begin(),s2.end());
return s1==s2;
}

vector<string> dict ={ "our","us","hello", "the", "world","to"};

string checkAnagraminDict(string s){
for( string w : dict) {
if (isAnagram2(w,s))
return w;
}
return "";
}
string unscramble(string s)  {

int len= s.length();
string nstr;

int i=0;
int l=1;
do{
string nw = checkAnagraminDict(s.substr(i,l));
if (nw == ""){
l++;
}
else{
nstr.append(nw);
nstr.append(" ");
i = i+l;
l = 1;
}
}while ( i < len );

return nstr;
}

void interviewquestion(){
cout << unscramble("elhloothtedrowl") << endl;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just a high level idea:
1. For each word in dictionary, generate all permutations. IMO this should take linear time wrt number of words as long as words have a small upper-bound on their length, say 10-12. Plus, we are doing this just once and then use it multiple times for unscrambling.

2. Build a suffix-tree on all the original words and their permutations.

3. For unscrambling, scan the input string and back track over all the matches found to find the exact match of the string. Finding all matches should not be difficult as we can consider all the suffixes in the input string and look for them into the big suffix-tree of words to find matches. Also note that all permutations of a word are assumed to have a pointer back to the original word.

Edit: Last stage actually does not need to perform a back track. Consider the chars of input string as nodes of a DAG starting from left to right. For each match found draw an edge from the beginning vertex to the ending vertex. Then, unscrambling is just finding a path from the left-most node to right-most node.

The complexity of building the suffix-tree is O(L_dic) where L_dic is the sum of the length of all words in dictionary. The complexity of unscrambling the string S is O(|S|) since that is the upper bound on the number of edges we form in the end. Considering that we do unscrambling repetitively, building of suffix-tree should not be an issue.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is one way to do it

1) Preprocess the dictionary (ArrayList<String>):
--- (a) for each word in the dictionary, generate all permutations (considering the fact that characters can repeat in dictionary words).
--- (b) add each of the permutation to a Trie (saves space for repeated permutations across all words in the dictionary).

2) Write a separate method in Trie where in, while searching, if a leaf node is reached before the input word ends, returns the length of the valid word (traversed till now). This mechanism can be used mainly for adding spaces to an input string (Re-Space problem).

3) Finally, for each suffix in the input sentence (substring starting at each index), search in the Trie using the new function defined above (the advantage here is, since we find a matching word in Trie, we can skip our iteration index by that length, thereby skipping all the suffixes in between).

``````class Trie{
private TrieNode root;
class TrieNode{
char c;
HashMap<Character, TrieNode> children;
boolean isLeaf;
}
/*
* Trie method as mentioned above in (2)
*/
public int getLengthOfMatchingWord(String word){
// If a leaf node is reached before word ends, then return the length of the valid word from Trie.
TrieNode node = root;
for(int i =0; i<word.length(); i++){
Character c = word.charAt(i);
node = node.getChildren().get(c);
if(node == null){
return -1;
}
if(node.isLeaf()){
return i;
}
}
// If word finishes before the Trie word/s
return -1;
}
}

public class UnscrambleInput {

private Trie trie;
private HashMap<String, String> permutationToValidWordMap;

public UnscrambleInput(){
trie = new Trie();
permutationToValidWordMap = new HashMap<>();
}

private ArrayList<String> getAllPermutations(String input){
if(input == null || input.length() == 0){
return null;
}

ArrayList<String> result = new ArrayList<>();
HashMap<Character, Integer> freqMap = new HashMap<>();
for(Character c : input.toCharArray()){
if(!freqMap.containsKey(c)){
freqMap.put(c, 0);
}
freqMap.put(c, 1+freqMap.get(c));
}

generatePermutations(result, freqMap, "", input.length(), input);
return result;
}

private void generatePermutations(ArrayList<String> result, HashMap<Character, Integer> freqMap,
String prefix, int remaining, String input){
if(remaining == 0){
permutationToValidWordMap.put(prefix, input);
return;
}

for(Character c : freqMap.keySet()){
int count = freqMap.get(c);
if(count > 0){
freqMap.put(c, count-1);
generatePermutations(result, freqMap, prefix+c, remaining-1, input);
freqMap.put(c, count);
}
}
}

private void preprocess(ArrayList<String> dictionary){
for(String word : dictionary){
ArrayList<String> permutations = getAllPermutations(word);
for(String permutation : permutations){
}
}
}

public String unscrambleSentence(String inputSentence, ArrayList<String> dictionary){
if(inputSentence == null || inputSentence.length() == 0 || dictionary == null || dictionary.size() == 0){
return null;
}

preprocess(dictionary);

StringBuilder sb = new StringBuilder();
// from here, apply the logic that splits words (add spaces) in a sentence
for(int i = 0; i < inputSentence.length(); i++){
String currStr = inputSentence.substring(i);

int endIndex = trie.getLengthOfMatchingWord(currStr);
if(endIndex > 0){
String foundPermutation = inputSentence.substring(i, i + endIndex+1);
String validWord = permutationToValidWordMap.get(foundPermutation);
sb.append(validWord);
sb.append(" ");
i += endIndex-1;
}
}
return sb.toString();
}

public static void main(String[] args) {
ArrayList<String> dictionary = new ArrayList<>();

UnscrambleInput unscrambleInput = new UnscrambleInput();
String unscrambled = unscrambleInput.unscrambleSentence("asyelhloeehtrgottohtedrowl", dictionary);

System.out.println("unscrambled: "+ unscrambled);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Let us denote the input string by S.

1. Preprocess the dictionary - Sort each individual word in the dictionary and keep it in a hash map. Key = sorted version, Value = Original word. Time : O(w log w). w = max length of a word in dictionary.
2. Construct a DP table. dp[i] = There is a meaningful way to partition S[i : N-1]. The actual answer can be reconstructed from the dp table.

How to construct the dp table?
dp[i] = for all j in [i+1 : N - 2] : IsWord(S[i:j]) && dp[j + 1]

How to implement IsWord(str)?
Sort str and check if the sorted version is present in the preprocessed hashset from Step #1. If it is, we will be able to construct the original word from the value in the hash map.

How to recover answer from the dp table?
Basically, how it is usually done. Try to find the first i where S[0:i] is a valid word and dp[i+1] is true, and so on.

Overall complexity = O(N ^ 2) where N is the length of input.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.ArrayList;
import java.util.HashSet;
import java.util.HashMap;

public static void main(String[] args)
{
String input = "elhloothtedrowl";
ArrayList<String> dictionary = new ArrayList<String>();

System.out.println("the input is " + input);
System.out.print("our dictionary is ");
System.out.print(dictionary);
System.out.println("\nthe unscambled sentence is '" + unscrambleTheSentence(input, dictionary)+"'");
}

public static String unscrambleTheSentence(String input, ArrayList<String> dictionary){

HashMap<Character, HashSet<String>> characterToWord = new HashMap<Character, HashSet<String>>();

String finalSentence = "";

for(String word : dictionary){
for(int i = 0; i < word.length();i++){

char key = word.charAt(i);

if(characterToWord.containsKey(key)){

HashSet<String> wordsWithChar = characterToWord.get(key);

}else{

HashSet<String> wordsWithChar = new  HashSet<String>();
characterToWord.put(key, wordsWithChar);
}
}
}

HashSet<String> currentWords = null;
int index = 0;

while(input.length() > 0){

char currentKey = input.charAt(index);

if(currentWords == null){
currentWords = characterToWord.get(currentKey);
}else{
if(currentWords.size() == 1){
String foundWord = currentWords.iterator().next();
input = input.substring(foundWord.length());
finalSentence += foundWord + " ";
index = -1;
currentWords = null;
}else{
currentWords.retainAll(characterToWord.get(currentKey));
}
}
index++;
}
return  finalSentence;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

DICTIONARY does not actually exist.

``````public void findWordsInScrambledString(String scrambled) {

String scrambledToLower = scrambled.toLowerCase();

for(int i = 0; i < scrambledToLower.length(); i++) {
}
String x = "";
while(!charQueue.isEmpty()) {
x = x + charQueue.remove();
String word = getWord(x);
if(word != null) {
System.out.print(word + " ");
x = "";
}
}
}

public String getWord(String possibleWord) {
if(containsVowel(possibleWord)) {
return getWordFromPermutations(possibleWord);
}
return null;
}

public boolean containsVowel(String possibleWord) {
for(int i = 0; i < possibleWord.length(); i++) {
char current = possibleWord.charAt(i);
if(current == 'a' || current == 'e' || current == 'i' || current == 'o' || current == 'u'
|| current == 'y') {
return true;
}
}
return false;
}

public String getWordFromPermutations(String possibleWord) {

char[] characters = new char[possibleWord.length()];
for(int i = 0; i < possibleWord.length(); i++) {
characters[i] = possibleWord.charAt(i);
}
return	getWordFromPermutations(characters, possibleWord.length());
}

public String getWordFromPermutations(char[] characters, int height) {
String word = null;
if(height == 1) {
String possibleWord = new String(characters);
if(DICTIONARY.contains(possibleWord)) {
word = possibleWord;
}
return word;
}
for(int i = 0; i < height; i++) {
swap(characters, i, height - 1);
word = getWordFromPermutations(characters, height - 1);
if(word != null) return word;
swap(characters, i, height - 1);
}
return word;
}

public void swap(char[] a, int i, int j) {
char temp = a[i];
a[i] = a[j];
a[j] = a[i];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

What you can do is take advantage of the byte representation of the characters to create a key in the dictionary, because the product, sum pair of the byte (ord in Python) representations is invariant to shuffling but uniquely identifies the shuffle (see proof below). Here is some code:

``````scramble = 'ehllotehotwolrd'
wordset = {'hello','to','the','world'}

def wordsetToDict(wordset):
worddict = {}
for word in wordset:
key = 1
key2 = 0
for c in word:
key *= ord(c)
key2 += ord(c)
worddict[(key,key2)] = word
return worddict
worddict = wordsetToDict(wordset)
print(worddict)

def unscramble(scramble,worddict):
outstr = ''
key = (1,0)
counter = 0
begin = 0
while (counter < len(scramble)):
c = scramble[counter]
# make c to be considered in key
key = (key[0]*ord(c),key[1]+ord(c))
# test for existence in wordset
if key in worddict:
# Add word to output string
outstr += worddict[key] + ' '
# update where to begin
begin = begin + len(worddict[key])
# move counter to the beginning
counter = begin
# reset key
key = (1,0)
else:
# increment counter
counter += 1
return outstr[0:(len(outstr)-1)]

unscramble(scramble,worddict)``````

Proof:
Suppose we have two, two character strings (x1,x2,y1,y2 represent any possible character), 'x1y1', 'x2y2'
Question: can we have a collision if x1 != x2,y2 or y1 != x2,y2? collision means product and sum are equal
WLOG assume x1 != x2, y2.
Then ord(x1) != ord(x2), ord(y2)
Suppose ord(x1)*ord(y1) = ord(x2)*ord(y2) and ord(x1)+ord(y1) = ord(x2)+ord(y2)
then ord(y1) = ord(x2)*ord(y2)/ord(x1)
but ord(y1) is an integer. meaning ord(y2)/ord(x1) or ord(x2)/ord(x1) is an integer. Hence there is some k such that ord(x1)*k = ord(x2) or ord(x1)*k = ord(y2). k != 1.
case 1: ord(x1)*k = ord(x2)
So, ord(x1)*ord(y1) = ord(x1)*k*ord(y2) => ord(y1)/k = ord(y2) => ord(x1)+ord(y1) = ord(x1)*k+ord(y1)/k
This means k must equal 1. contradiction!
Similarly for case 2.
So we know that the sum and product of ordinals are invariant with respect to shuffling, but not with respect to changing the contents of the string.

Comment hidden because of low score. Click to expand.
0
of 0 vote

python solution running in O(n^2) time

works something like this:
1. create a hash for each string in the dictionary array storing total occurrances of each char
2. loop over string and take similar hash of cumulative string so far
3. compare cumalative hash to each hash of dictionary
4. If cumulative hash equals some dict hash, append that word to output. Reset cumulative string to empty.
5. ???
6. result

``````dictionary = ["hello", "my", "name", "is", "romulus", "remus", "fun"]
def unscramble(string, dictionary):
def getTotals(string):
total = {}
for y in string:
if total.has_key(y):
total[y] += 1
else:
total[y] = 0
all_totals = []
for word in dictionary:
all_totals.append(getTotals(word))
output = []
current = ""
for char in string:
current += char
currentTotals = getTotals(current)
for iTotal in range(len(all_totals)):
if currentTotals == all_totals[iTotal]:
output.append(dictionary[iTotal])
current = ""
break
return output``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The key is to recognize that only the letters within the word are scrambled, not the ordering between words. To recognize a word, then we just have to check if there exists a word in dictionary that is an anagram of current word. That can be easily found by sorting the words, both in the input string, as well as in the input dictionary.

So, for each input word in dictionary, sort by alphabets and create a map from the sorted letter word to actual word. Then traverse each alphabet and see if current substring is in input set, if so, then recursively search for remaining suffix. This can be made more efficient by DP, since there are overlapping calls:

``````import java.util.*;

/**
*
*/
public class Unscrambler {

public static String unscramble(String input, Set<String> dictionary) {
Map<String, String> scMap = getDict(dictionary);
return unscramble(input.toCharArray(), 0, scMap, new HashMap<Integer, String>());
}

private static Map<String, String> getDict(Set<String> dictionary) {
Map<String, String> m = new HashMap<>();
for(String w: dictionary) {
char[] keyArr = w.toCharArray();
Arrays.sort(keyArr);
String key = new String(keyArr);

m.put(key, w);
}

return m;
}

private static String unscramble(char[] input, int si, Map<String, String> dict, Map<Integer, String> memo) {
if(si == input.length) {
return "";
}
if(memo.containsKey(si)) {
return memo.get(si);
}

for(int j = si; j < input.length; j++) {
char[] keyArr = Arrays.copyOfRange(input, si, j + 1);
Arrays.sort(keyArr);
String k = new String(keyArr);

if(dict.containsKey(k)) {
String s = unscramble(input, j + 1, dict, memo);
if(s != null) {
String res = (dict.get(k) + " " + s).trim();
memo.put(si, res);

return res;
}
}
}

memo.put(si, null);
return null;
}

public static void main() {
Set<String> set = new HashSet<String>();
String[] words = new String[] {"hello", "to", "the", "lords", "what", "ello", "not", "war"};
for(String w: words ) {
}
String res = unscramble("ellohothetdlors", set);
if(res == null) {
} else {
System.out.println("Found: " + res);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.TreeMap;

public class Scramble {

public static void main(String[] args) {
String scramble = "ehllotehowtolrd";
String wordset[] = {"hello","to","the","world"};

TreeMap<Character, Integer> map = new TreeMap<>();

for(int i=0; i<scramble.length(); i++){
if(map.containsKey(scramble.charAt(i)))
map.put(scramble.charAt(i), map.get(scramble.charAt(i))+1);
else
map.put(scramble.charAt(i), 1);
}
String output = "";
for(String s: wordset){
int i=0;
for(i=0; i<s.length(); i++){
if(map.containsKey(s.charAt(i)) && map.get(s.charAt(i)) > 0){
map.put(s.charAt(i), map.get(s.charAt(i))-1);
} else
break;
}
if(i == s.length())
output += s+" ";
}
System.out.println(output);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Emm... It is practically and programmatically impossible to arrive at a single solution.

Lets say the word is "facebook" input as "aeoofkcb". How can the program differentiate between face, book and facebook?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class scramblefind {

public static void main(String[] args) {

String[] dictionary = {"hello", "to", "the", "world"};
String input = "elhloothtedrowl";

MultipleValueHashMap<Integer, StringData> hasheddictionary = new MultipleValueHashMap<>();
for (int i = 0; i < dictionary.length; i++) {
StringData sd = new StringData(dictionary[i]);
hasheddictionary.put(sd.stringsum, sd);
}
iterativesearch(input.toCharArray(), 0, "", hasheddictionary);

}

public static void iterativesearch(char[] chars, int loc, String output, MultipleValueHashMap<Integer, StringData> dictionary) {

int sum = 0;
String s = "";
while (loc < chars.length) {
sum += chars[loc];
s += chars[loc];
loc++;

List<StringData> possiblestrings = dictionary.get(sum);
if (possiblestrings != null) {
for (StringData possiblestring : possiblestrings) {
if (possiblestring.equals(s.toCharArray())) {
iterativesearch(chars, loc, output + " " + possiblestring.original, dictionary);
}
}
}

}
if (sum == 0) {
System.out.println(output);
}

}

public static int stringsum(String s) {
char[] chars = s.toCharArray();
int sum = 0;

for (int i = 0; i < chars.length; i++) {
sum += chars[i];
}

return sum;
}
}

class StringData {

String original;
char[] sortedchars;
int stringsum;

StringData(String s) {
original = s;
sortedchars = s.toCharArray();
Arrays.sort(sortedchars);
stringsum = stringsum(s);
}

public boolean equals(char[] chars) {
Arrays.sort(chars);
return Arrays.equals(chars, sortedchars);
}

}

class MultipleValueHashMap<Key, Value> {

HashMap<Key, List<Value>> map = new HashMap<>();

void put(Key key, Value value) {
if (map.get(key) == null) {
}
}

List<Value> get(Key key) {
return map.get(key);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````from collections import defaultdict
dictionary = ["hello", "to", "the", "world"]
def unscramble(s, sorted_dictionary=None):
if not sorted_dictionary:
sorted_dictionary = defaultdict(list)
for word in dictionary:
sorted_dictionary["".join(sorted(word))].append(word)

words = []
for i in xrange(len(s)):
word = "".join(sorted(s[:i+1]))
if len(sorted_dictionary[word]):
word = sorted_dictionary[word][0]
other_words = unscramble(s[i+1:], sorted_dictionary)
if len(other_words) or i+1 == len(s):
words.append(word)
words.extend(other_words)
break
return words

s = "elhloothtedrowl"
words =  unscramble(s)
print " ".join(words)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby, Memoized, I think nlog(n) worst case time....

If anyone can figure out the time complexity would be great.

``````dict = {}
%w(hello to the world).each do |word|
i = 0
res = 0
while i < word.length
res ^= word[i].ord
i += 1
end
dict[res] = dict[res] ? [word] + dict[res] : [word]
end

def is_word str, dict
i = 0
res = 0
while i < str.length
res ^= str[i].ord
i += 1
end
return nil unless dict[res]
dict[res].each do |word|
return word if word.split('').sort == str.split('').sort
end
nil
end

def unscramble str, dict, hash = {}
return '' if str.length == 0
str.length.times do |idx|
value = is_word(str[0..idx], dict)
next unless value
rest = hash[str[idx+1...str.length]] ? hash[str[idx+1...str.length]] : unscramble(str[idx+1...str.length], dict)
next unless rest
return hash[str] = rest == '' ? value : value + " " + rest
end
return nil
end``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String[] args) {
// TODO Auto-generated method stub
Set<String> dic= new HashSet<String>(Arrays.asList("hello","to","the","world"));
String s = "ehllotehotwolrd";

System.out.println(unScramle(dic,s));
}

private static List<String> unScramle(Set<String> dic, String s){
List<String> list = new ArrayList<String>();
if(s.length() == 0) return list;
int max = 0;
for(String str : dic){
max = Math.max(max, str.length());
char[] arr = str.toCharArray();
Arrays.sort(arr);
map.get(String.valueOf(arr)).offer(str);
}

for(int i = 0; i < s.length()-1; i++){
for(int j = i+1; j <= s.length() && j <= i+max; j++){
char[] temp = s.substring(i, j).toCharArray();
Arrays.sort(temp);
if(map.containsKey(String.valueOf(temp))) {
i = j-1;
break;
}
}
}
return list;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String[] args) {
// TODO Auto-generated method stub
Set<String> dic= new HashSet<String>(Arrays.asList("hello","to","the","world"));
String s = "ehllotehotwolrd";

System.out.println(unScramle(dic,s));
}

private static List<String> unScramle(Set<String> dic, String s){
List<String> list = new ArrayList<String>();
if(s.length() == 0) return list;
int max = 0;
for(String str : dic){
max = Math.max(max, str.length());
char[] arr = str.toCharArray();
Arrays.sort(arr);
map.get(String.valueOf(arr)).offer(str);
}

for(int i = 0; i < s.length()-1; i++){
for(int j = i+1; j <= s.length() && j <= i+max; j++){
char[] temp = s.substring(i, j).toCharArray();
Arrays.sort(temp);
if(map.containsKey(String.valueOf(temp))) {
i = j-1;
break;
}
}
}
return list;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static String unscrambleString(String[] dicts,String str){
StringBuilder sb = new StringBuilder();
Boolean[] check = new Boolean[str.length()];

Map<char[],Integer> map = new HashMap<>();
for(int i=0;i<dicts.length;i++){
String ele = dicts[i];
char[] array = ele.toCharArray();
Arrays.sort(array);
map.put(array,i);
}
if(unscrambleHelper(sb,dicts,map,check,str,0)){
return sb.toString().substring(0,sb.length()-1);
}

return "no such string";

}

public static boolean unscrambleHelper(StringBuilder sb,String[] dicts,Map<char[],Integer> map,Boolean[] check,
String str,int index){
if(index==str.length()){
return true;
}

if(check[index]!=null){
return check[index];
}

for(int i=index;i<str.length();i++){
String curStr = str.substring(index,i+1);
char[] curStrArray = curStr.toCharArray();
Arrays.sort(curStrArray);

for(char[] strEle:map.keySet()){
if(strEle.length==curStrArray.length){

if(checkEqual(strEle,curStrArray)){
String ele = dicts[map.get(strEle)];
sb.append(ele+" ");
if(unscrambleHelper(sb,dicts,map,check,str,i+1)){
check[index] = true;
return true;
}
sb.setLength(sb.length()-strEle.length-1);
}

}
}

}
check[index] = false;
return false;
}

public static boolean checkEqual(char[] array1,char[] array2){
if(array1.length!=array2.length){
return false;
}
for(int i=0;i<array1.length;i++){
if(array1[i]!=array2[i]){
return false;
}
}
return true;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

using the default dictionary with words like "t" removed, my program came up with:

"othello the dr low"

The user who said:
"Emm... It is practically and programmatically impossible to arrive at a single solution."

is correct. Too many options to be able to come up with the exact desired output, but you can come up with some output made up of words in the right order.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public String unscrambleString(String str, Set<String> d) {
Map<String, String> dict = new HashMap<>();
for(String s : d) {
char[] t = s.toCharArray();
Arrays.sort(t);
dict.put(new String(t), s);
}

int i = 0;
List<String> result = new ArrayList<>();
while (i < str.length()) {
char[] tc = str.substring(i, str.length()).toCharArray();
Arrays.sort(tc);
String t = new String(tc);
if (dict.containsKey(t)) {
str = str.substring(0, i);
i = 0;
} else {
i++;
}
}
if(i != 0) {
return null;
}
return buildStrFromArray(result);
}

private String buildStrFromArray(List<String> result) {
StringBuilder sb = new StringBuilder();
for (int i = result.size() - 1; i >= 0; i--) {
sb.append(result.get(i) + " ");
}
return sb.toString();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def unscramble(scrambled, words):
result = [letter for letter in scrambled]

# Scan through the words in dict
# For each word, find it's anagram and replace it with the actual word.
for word in words:

# Scan through the scrambled sentence with a
# window of length of the word.
start = 0
end = len(word)
while end < len(result)+len(words): # We'll be adding spaces for each word we find.
# Capture potential corresponding scrambled word in the window
scrambled_word = result[start:end]

# Anagram check
if sorted(scrambled_word) == sorted(word):
# Insert space for the sentence
result.insert(start, " ")

# Replace scrambled word with actual word
result[start+1:end+1] = word
break

# Didn't find it, move the window
start += 1
end += 1
return "".join(result).strip()

def test():
scrambled = "elhloothtedrowl"
words = ["the", "hello", "to", "world"]
result = unscramble(scrambled, words)
assert result == "hello to the world", result

test()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import string
import math
import operator

alph = string.ascii_lowercase
primes = [x for x in range(2, 100) if all(x % y != 0 for y in range(2, int(math.ceil(math.log10(x)))))]
foo = lambda str: reduce(operator.mul, map(lambda x: primes[x], map(lambda x: alph.index(x), str)), 1)

def bar(dict, xdict, str, n):
for p in [str[n:z:] for z in range(n, len(str)+1)]:
x = foo(p)
if (x in xdict):
r = [dict[xdict.index(x)]]
if (n + len(p) != len(str)):
rs = bar(dict, xdict, str, n + len(p))
if (len(rs) != 0):
return r+rs
else:
return r
return []

def unscramble(dict, str):
xdict = map(foo, dict)
return (" ".join(bar(dict, xdict, str, 0)))

d = ['llo', 'hell', 'ocrazyworl', 'ld', 'crazyw', 'ell', 'llocra', 'azyworl', 'll', 'razywo', 'ocr', 'zywo', 'ocrazyw', 'ywor', 'azywo', 'llocrazyworl', 'razywor', 'ellocr', 'yw', 'zyworl', 'lloc', 'ellocrazyw', 'h', 'l', 'cra', 'ywo', 'el', 'llocrazywo', 'ocrazywo', 'crazywo', 'hellocra', 'zy', 'cr', 'ocrazy', 'azyw', 'locraz', 'wor', 'ra', 'rl', 'llocrazy', 'hellocraz', 'razyworl', 'llocr', 'wo', 'ocra', 'ellocrazy', 'orl', 'llocrazywor', 'llocraz', 'razy', 'c', 'ocraz', 'hellocrazy', 'llocrazyw', 'oc', 'o', 'hellocrazyw', 'w', 'lo', 'or', 'hellocrazywo', 'hellocr', 'locrazyworl', 'loc', 'elloc', 'craz', 'hel', 'locrazy', 'hellocrazywor', 'locrazywo', 'locrazyw', 'crazyworl', 'he', 'locr', 'ellocraz', 'worl', 'azy', 'r', 'z', 'crazy', 'helloc', 'azywor', 'ellocrazyworl', 'az', 'raz', 'locrazywor', 'crazywor', 'zywor', 'hellocrazyworl', 'ellocra', 'ellocrazywo', 'ello', 'ocrazywor', 'a', 'locra', 'razyw', 'yworl', 'e', 'ellocrazywor', 'zyw', 'y', 'hello']
str = "hellocrazyworld"

assert(unscramble(d, str) == "h e l l o c r a z y w o r ld")``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

My Solution in Java

{{
private List<String> getWords(String str, List<String> dict) {
Map<Integer, List<String>> dictByCount = new HashMap<>();
int biggestCount = 0;
int smallestCount = 1000;
for (String word : dict) {
List<String> countList;
if (biggestCount < word.length()) {
biggestCount = word.length();
}
if (smallestCount > word.length()) {
smallestCount = word.length();
}
if (dictByCount.containsKey(word.length())) {
countList = dictByCount.get(word.length());
} else {
countList = new ArrayList<>();
dictByCount.put(word.length(), countList);
}
}
return getWordsFromMap(str.toLowerCase(), dictByCount, biggestCount, smallestCount);
}

private List<String> getWordsFromMap(
String str, Map<Integer, List<String>> map, int biggestCount, int smallestCount) {
for (int i = smallestCount; i <= biggestCount; i++) {
String firstWord = str.substring(0, i);
List<String> wordOfCount = map.get(i);
if (wordOfCount != null) {
for (String word : wordOfCount) {
if (isScramble(firstWord, word)) {
List<String> retList = new ArrayList<>();
if (str.substring(i).trim().length() > 0) {
List<String> remainList =
getWordsFromMap(str.substring(i), map, biggestCount, smallestCount);
if (remainList != null) {
}
}
return retList;

}
}
}
}
// System.out.println("Cannot get the remaining:"+ str);
return null;
}

private int[] getDigest(String word){
int[] digest = new int[26];
for(int i = 0; i < word.length(); i ++){
char ch = word.charAt(i);
digest[ch-'a']++;
}
return digest;
}
private boolean isScramble(String word1, String word2){
int[] digest1 = getDigest(word1);
int[] digest2 = getDigest(word2);
for(int i = 0; i < digest1.length; i ++){
if(digest1[i] !=digest2[i]){
return false;
}
}
return true;
}
}}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.