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.

- merlinme October 25, 2016 | Flag Reply
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.

- somedude November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The proof is wrong.

It says: "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"

But this is not true. Example: ord(x1)=6;ord(x2)=2;ord(y2)=3;ord(y1)=1

ord(y1) = ord(x2)*ord(y2)/ord(x1) is true
ord(y1) is an integer
Nonetheless neither ord(y2)/ord(x1) nor ord(x2)/ord(x1) are integers

- Joaquin July 02, 2022 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The proof is wrong.

It says: "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"

But this is not true. Example: ord(x1)=6;ord(x2)=2;ord(y2)=3;ord(y1)=1

ord(y1) = ord(x2)*ord(y2)/ord(x1) is true
ord(y1) is an integer
Nonetheless neither ord(y2)/ord(x1) nor ord(x2)/ord(x1) are integers

- Joaquin July 02, 2022 | Flag
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

- smurugu October 26, 2016 | Flag Reply
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

- Shri October 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package smapleQuestionsAlgorithms;

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

public class GoogleInterviewQuestion {
	//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<>();
		dictionary.add("hello");
		dictionary.add("he");	
		dictionary.add("to");
		dictionary.add("the");
		dictionary.add("world");
		System.out.println(makeSentence("elhloothtedrowl", dictionary,""));
	}

}

- Siva praneeth October 26, 2016 | Flag Reply
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;

public class GoogleInterviewQuestion {
	//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<>();
		dictionary.add("hello");
		dictionary.add("he");	
		dictionary.add("to");
		dictionary.add("the");
		dictionary.add("world");
		System.out.println(makeSentence("elhloothtedrowl", dictionary,""));
	}

}

- sivapraneethalli October 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Justin Gao March 06, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Apologise for duplicate submission.

- sivapraneethalli October 26, 2016 | Flag Reply
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 }
           partitions.add(0, lc ) // add the sorted key 
           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 ) { 
          partitions.add(0, lc )
          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 )

- NoOne October 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

backtracking with pruning

- Anonymous October 26, 2016 | Flag Reply
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 , '')

- NoOne October 26, 2016 | Flag Reply
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)
google1("elhloothtedrowl")

- john October 26, 2016 | Flag Reply
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;
}

- Anonymous October 26, 2016 | Flag Reply
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;
}

- anonymous October 26, 2016 | Flag Reply
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.

- Dant3 October 28, 2016 | Flag Reply
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){
            result.add(prefix);
            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){
                trie.addWord(permutation);
            }
        }
    }

    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<>();
        dictionary.add("these");
        dictionary.add("the");
        dictionary.add("to");
        dictionary.add("together");
        dictionary.add("much");
        dictionary.add("hello");
        dictionary.add("these");
        dictionary.add("world");
        dictionary.add("say");
        dictionary.add("yes");
        dictionary.add("jaffa");

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

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

- jsayyy October 30, 2016 | Flag Reply
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.

- Kushagra November 03, 2016 | Flag Reply
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 class GoogleQuestionUnscambleASentence{
  
  
  public static void main(String[] args)
  {
    String input = "elhloothtedrowl";
    ArrayList<String> dictionary = new ArrayList<String>();
    
    dictionary.add("hello");
    dictionary.add("to");
    dictionary.add("the");
    dictionary.add("world");
    
    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);
          wordsWithChar.add(word);
          
        }else{
        
          HashSet<String> wordsWithChar = new  HashSet<String>();
          wordsWithChar.add(word);
          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;
  }
  
}

- DCIS November 05, 2016 | Flag Reply
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();
        Queue<Character> charQueue = new LinkedList<Character>();

        for(int i = 0; i < scrambledToLower.length(); i++) {
            charQueue.add(scrambledToLower.charAt(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];
    }

- montwell November 06, 2016 | Flag Reply
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.

- Anonymous November 14, 2016 | Flag Reply
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
		return total
	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

- DavidM November 15, 2016 | Flag Reply
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 ) {
            set.add(w);
        }
        String res = unscramble("ellohothetdlors", set);
        if(res == null) {
            System.out.println("Not Found!!!");
        } else {
            System.out.println("Found: " + res);
        }
    }
}

- learner21 November 17, 2016 | Flag Reply
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);
	}

}

- Anonymous November 24, 2016 | Flag Reply
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?

- Yesh November 27, 2016 | Flag Reply
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) {
            map.put(key, new LinkedList<Value>());
        }
        map.get(key).add(value);
    }

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

}

- Paris Stefanou November 27, 2016 | Flag Reply
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)

- Nitish Garg December 26, 2016 | Flag Reply
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

- scoldboy December 30, 2016 | Flag Reply
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;
		Map<String, LinkedList<String>> map = new HashMap<String, LinkedList<String>>();
		int max = 0;
		for(String str : dic){
			max = Math.max(max, str.length());
			char[] arr = str.toCharArray();
			Arrays.sort(arr);
			map.putIfAbsent(String.valueOf(arr), new LinkedList<String>());
			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))) {
					list.add(map.get(String.valueOf(temp)).poll());
					i = j-1;
					break;
				}
			}
		}				
		return list;
	}

- Anonymous May 17, 2017 | Flag Reply
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;
		Map<String, LinkedList<String>> map = new HashMap<String, LinkedList<String>>();
		int max = 0;
		for(String str : dic){
			max = Math.max(max, str.length());
			char[] arr = str.toCharArray();
			Arrays.sort(arr);
			map.putIfAbsent(String.valueOf(arr), new LinkedList<String>());
			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))) {
					list.add(map.get(String.valueOf(temp)).poll());
					i = j-1;
					break;
				}
			}
		}				
		return list;
	}

- Parth May 17, 2017 | Flag Reply
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;
    }

- tiandiao123 October 07, 2017 | Flag Reply
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.

- Mike November 16, 2017 | Flag Reply
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)) {
                result.add(dict.get(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();
    }

- Anonymous November 23, 2017 | Flag Reply
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()

- dsouza.judepk May 27, 2018 | Flag Reply
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")

- adr May 27, 2018 | Flag Reply
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);
}
countList.add(word.toLowerCase());
}
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<>();
retList.add(word);
if (str.substring(i).trim().length() > 0) {
List<String> remainList =
getWordsFromMap(str.substring(i), map, biggestCount, smallestCount);
if (remainList != null) {
retList.addAll(remainList);
}
}
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;
}
}}

- Justin Gao March 06, 2019 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More