CareerCup

Create an array of size 256 to record frequency of each letter, ex. for a,a,b,c,k ... the array will be [...,2,1,1,...,1,...] Than go through the each word and see it can be made by given letters.

To check a word, do following for each letter in the word:
1. if the value of the corresponding element in the array is zero than that word can not be made from given letters
2. otherwise decrease the value of that element by one.

Repeat this for each word and record the longest word matched.

This solution is O(m+n)

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;

public class WordMaker {
	
	public static void main(String[] args) {
		
		// Defining local variables
		String fileName = "wordList.txt";
		char[] letterList = {'a','l','l','i','e','s','m'};
		
        // Create a dictionary of the list of letters and their count
		HashMap<Character, Integer> letterCount = new HashMap<Character, Integer>();
		for(char l : letterList)
			letterCount.put(l, letterCount.containsKey(l) ? letterCount.get(l) + 1	:  1);
		
		// Read the file line by line to find the longest word
		String line;
		char[] lineChars;
		Integer currlineLength;
		Integer tempLongestWordLength=0;
		ArrayList<String> currLongestWords = new ArrayList<String>();
		HashMap<Character, Integer> tempLCount = new HashMap<Character, Integer>();
		BufferedReader br;
		
		try {
			br = new BufferedReader(new FileReader(new File(fileName)));	
			while((line = br.readLine()) != null) {
				
				//Storing the dictionary temporarily in tempLCount
				tempLCount.putAll(letterCount);
				
				//Reset currlineLength
				currlineLength=0;
				
				//don't go further if the current line length is shorter than the current longest word length
				if(line.length() < tempLongestWordLength) continue;
				
				//convert string to character array, so that we can loop through each letter
				lineChars = line.toCharArray();
				for(Character lc : lineChars){
					
					//if the letterCount contains the key we move forward or we break this for loop and continue with the next line 
					if(!letterCount.containsKey(lc)) break;
					
					//subtract from the available count of letters
					tempLCount.put(lc,tempLCount.get(lc) - 1);
					
					//if the count of the letter exceeds the count in the letter list then break this for loop
					if(tempLCount.get(lc) < 0) break;
					
					//increase the count of the letters that wen through
					currlineLength++;
				}
				
				//If the count of the letters that went through is same as the length of the line string then there was a match
				if(currlineLength == line.length()){
					
					//If the current line length is greater than the longest word length then we clear the currLongestWord list 
					//and put this new one and change the longest length to the current line length 
					if(line.length() > tempLongestWordLength){
						tempLongestWordLength = line.length();
						currLongestWords.clear();
					}
					
					//Finally add the line to the currLongestWords list
					currLongestWords.add(line);					
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
		//Print out the list of longest words
		System.out.println(currLongestWords);
	}
}

This is a typical trie problem (for details, you can read about Trie in WIkipedia).
Let the number of words be n and the number of characters be m.
The solution is the following:
1. You build a trie from the dictionary words of length <=m (other words are not of interest since they definitely cannot be built from m characters). This will require O(n*m) time and O(n*m) space;
2. You use character set to explore all possible words. You assume that first letter can be any in the set (m possibilities) then you explore m-1 possibilities for each of them and so on. Even though it might look like O(n!) but in reality, each of the node of the trie will be touched only ones, that is the overall complexity will be O(n*m);

As a rule, trie is difficult to beat in problems like this, so I believe it to be optimal.

Trie is a well-defined thing, so please check it out to understand the details of the solution... (you anyway need to do so if you really wish to succeed in Google job interviews%))

Group the words according to their lengths in a HashMap<Integer, ArrayList<String>>. Traverse the hashmap starting with the largest key value (indicates group of words of similar length) and determine if there is at least one word which can be formed from the parameters. If there is one or more words print it out and stop execution once the list is completely traversed. If not continue on to the next smallest group of words.

In order to determine if a word can be formed from the given list of acceptable letters, create a hashset of the acceptable letters and use set_object.contains(s.charAt(index)) to do so, where s represents the string from the ArrayList.

My solution is O(n) (where n is the length of the letters in the wordlist).

You can run this by putting the code in a .js file on your Apple computer (since Apples have a built in word library). Also, you need node.

var fs = require('fs'), words = '';
fs.readFile('/usr/share/dict/web2', function (err, data) {
  words += data;
  longestWord(words, 'a', 'e', 'j', 's', 'f', 'u', 'r', 'v', 'm', 'l', 'd', 'g');
});



function longestWord (wordsList, letters) {
  var wordsList = wordsList.split('\n');
  var letters = [].slice.call(arguments, 1);
  var lettersHash = {};
  letters.forEach(function(val, i) {
    lettersHash[val] = (lettersHash[val] === undefined) ? 1 : lettersHash[val] + 1;
  });
  var solution = [];

  for (var i=0;i<wordsList.length;i++) {
    var word = wordsList[i];
    if ( (solution.length === 0 && checkWord(word, lettersHash)) || (solution.length && word.length === solution[0].length && checkWord(word, lettersHash)) ){
      solution.push(solution.push(word));
    } else if (solution.length && word.length > solution[0].length && checkWord(word, lettersHash)){
      solution = [word];
    }
  }

  console.log(solution);
}

function checkWord(testWord, lettersHash) {
  var testWordHash = {};
  for (var i=0;i<testWord.length;i++){
    var letter = testWord[i];
    testWordHash[letter] = (testWordHash[letter] === undefined) ? 1 : testWordHash[letter] + 1;
    if (lettersHash[letter] === undefined || testWordHash[letter] > lettersHash[letter]) return false;
  }
  return true;
}

then type "node [whatever you named the file]" in console

public class WordMatcher {
    public static void main(String[] args) {

        String[] wordList = {"azotised", "zzdystocia", "iceboats", "thisisatest"}; // to read from the file

        char[] chars = {'w', 'g', 'd', 'a', 's', 'x', 'z', 'c', 'y', 't', 'e', 'i', 'o', 'b'};// to read from cmd

        // 1 create binary string for each word
        // 2 create binary string for supplied char set
        // 3 compare binary strings, if there is a add the word to a list
        // 4 return the longest ( longest 10 letters ?) from the list

        //2
        byte[] key = new byte[256];
        for (byte b : key) { b = 0; }
        for (char c : chars) {
            key[c]++;
        }

        List<String> matchingList = new ArrayList<>();
        // 1
        for (String word : wordList) {
            // each  word can be mapped to an byte array of length 256
            byte[] temp = convertToByteArray(word);
            // 3
            if (contains(key, temp)) {
                matchingList.add(word);
            }
        }

        // 4
        System.out.println(matchingList);


    }

    static byte[] convertToByteArray(String word) {
        byte[] temp = new byte[256];
        for (byte b : temp) {
            b = 0;
        }
        for (char c : word.toCharArray()) {
            temp[c]++;
        }
        return temp;
    }

    /**
     * true if all characters in key is in the array
     *
     * @param key
     * @param array
     * @return
     */
    static boolean contains(byte[] key, byte[] array) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] > key[i]) {
                return false;
            }
        }
        return true;
    }

}

Group the words by their length and sort in descending order. (O(nlog(n)), n be the number of groups). Create a frequency map of the given letters(linear). Work from the longest words and break when any word in a group meets the condition. Check each word in a group by iterating each letter. When a letter is not found in the map, or the count in the map becomes 0, skip the word otherwise decrement the count of that letter.

Implementation in scala

object LongWord extends App {
	import scala.collection.mutable.Map
	
	def longestWord(words: Seq[String], letters: Seq[Char]):Seq[String] = {
		val ws = words.groupBy(_.length()).toSeq.sortBy(0-_._1)
		
		var ls = letters.groupBy(identity).map(t=>t._1->t._2.size) //frequency map
		
		def canBuild(word:String):Boolean = {
			var l2 = Map.empty++ls //make a mutable copy
			for(c<-word) {
				if (l2.contains(c) && l2(c)>0) l2(c)-=1
				else return false
			}
			return true
		}
		
		for (i<-0 until ws.length) {
			val w = ws(i)._2.filter(canBuild _)
			if (w.size>0) return w.toSeq
		}
		return Seq.empty[String]
	}
	
	val words = Seq("azotised", "bawdiest", "dystocia", "geotaxis", "iceboats", "oxidates", "oxyacids", "sweatbox", "tideways", "wgda", "wgdaasxzcyteiob") 
	val letters = "wgdasxzcyteiob"
		
	println(longestWord(words, letters))
}

The code checks two extra words, one can be built from the letters but is shorter, the other can not be built from the letters because it needs more occurences of a letter than provided.

O(nm) solution, where:
n: number of words,
m: length of each word.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

bool isValid(string &s, vector<int> count){
    for(int i = 0; i < s.size(); i++){
        count[s[i] - 'a']--;
        if (count[s[i] - 'a'] < 0) return false;
    }

    return true;
}

int main(int argc, char *argv[]){
    vector<int> count(26, 0);

    for (int i = 2; i < argc; i++){
        char c = argv[i][0];
        count[c - 'a']++;
    }

    vector<string> words;
    string w;
    ifstream in(argv[1]);
    int maxLength = 0;

    while(getline(in, w)){
        words.push_back(w);

        if (isValid(w, count)){
            maxLength = max(maxLength, (int)w.size());
        }
    }

    for (int i = 0; i < words.size(); i++){
        if (isValid(words[i], count) && words[i].size() == maxLength){
            cout << words[i] << endl;
        }
    }

    return 0;
}

bool isValidWord(const std::string& str, std::vector<int> letters) {
  for (int i = 0; i < str.size(); i++) {
    if (--letters[str[i] - 'a'] < 0){
      return false;
    }
  }
  return true;
}

int main(int argc, char* argv[]) {
  std::vector<int> letters(26);
  for (int i = 2; i < argc; i++) {
    letters[argv[i][0] - 'a']++;
  }
  
  std::ifstream file(argv[1]);
  std::string str;
  int max_size = 0;
  std::list<std::string> longest_words;
  while (file >> str) {
    if (str.size() < max_size || !isValidWord(str, letters))
      continue;
    if (str.size() > max_size) {
      longest_words.clear();
      max_size = str.size();
    }
    longest_words.push_back(str);
  }
 
  for (auto w : longest_words)
    std::cout << w << std::endl;

  return 0;
}

def longest_word(a_list,word_list):
    max_len = 0
    max_len_word = None
    for i in word_list:
        if word_check(a_list,i) & len(i)> max_len == 0:
            max_len = len(i)
            max_len_word = i
    return i

def word_check(a_list,word):
    for i in word:
        if i in a_list:
            a_list.remove(i)
        else:
            return False
    return True

def longest_words(wordstxt, str_legal_letters):
	"""takes in a text file with list of possible words
	separated by newline,
	and a string of legal letters and return the longest
	word in the text file that can be made with only the 
	legal characters in the amt supplied in the str_legal_letters
	"""
	##reading in list of words from text file
	with open(wordstxt, 'r') as f:
		wordsn = f.readlines()
	list_of_words = [wordn.replace("\n","") for wordn in wordsn]
	
	longest_matches = [""]
	legal_unique = set(str_legal_letters)
	legal_count = [str_legal_letters.count(letter) for letter	in legal_unique]
	same_set = False
	all_same_count = False
	for word in list_of_words:
		##test if word matches set of legal letters only
		if set(word).issubset(legal_unique):
			same_set = True
			# only if word matches set of legal letters only, test if they use the same number of each
			word_count = [word.count(letter) for letter in legal_unique] #counting number of each of letters in legal_unique in the word in same order as legal_unique
			lessorsame_count = []
			#checking that count for each letter in the word is less than or equal the count for each letter in the string of legal letters
			for i in range(len(word_count)):
				if word_count[i] <= legal_count[i]:
					lessorsame_count.append(True)
				else:
					lessorsame_count.append(False)
			#checks counts for letters in the word are ALL less than or equal to the count allowed by the rstring of legal letters
			if False not in set(lessorsame_count):
				all_same_count = True		 
		else:
			continue
		# if same letters used and all in the allowed amounts and the length of the word is the same or longer than the longest match
		# then append it to the list of longest matches (if same length as current longest match) OR replace the list of longest matches
		# with just that word (if that word is longer than longest match)
		if same_set and all_same_count and len(word) >=  len(longest_matches[0]):
			if len(word) > len(longest_matches[0]):
				longest_matches = [word] 
			else:
				longest_matches.append(word)
	return longest_matches

it is Knuth-Morris-Pratt string matching algorithm

Easy Linear Solution using Python Dictionary Concept:

class LetterList:

    def __init__(self, aList):
       self.letterDict = self.buildLetterDict(aList)


    def buildLetterDict(self, aList):
        
        bDict = dict()
        for a in aList:

            if a in bDict.keys():
                bDict[a] += 1
            else:
                bDict[a] = 1

        return bDict        
          

   
    def isPossible(self, b):
       
        bList = list(b)
        bTempDict =  self.buildLetterDict(bList)  
        #print(b)
        #print(bTempDict) 
        for b in bTempDict.keys():
            if b not in self.letterDict.keys():
                 return False
            elif bTempDict[b] > self.letterDict[b]:
                 return False 
        return True


    def findAllPossible(self, bList):
        largestW  = 0
        pList = set()
        for b in bList:
            if self.isPossible(b):
               pList.add(b)  
               if len(b) > largestW:
                  largestW = len(b)

        print('Largest Possible Word-Length ::', largestW )
        return pList





letters = ['a', 'b','o','o','g','k', 'x','l', 't']
wordList = ['axe', 'gooltk','bag', 'book', 'goat', 'book', 'list', 'box', 'boat']

cl = LetterList(letters)
#print(cl.letterDict)
p = cl.findAllPossible(wordList)
#print(p)