Interview Question

Interview(Student Candidate)

Given a string of characters (e.g. Scrabble tiles) and a

  dictionary of allowed words, how would you use those tiles (without replacement between words) to construct the 10 longest allowed words?
Answer

Interview Answer

1 Answer

0

#include <iostream> #include <algorithm> #include <string> using namespace std; bool find_remove(string word, string& tiles); struct { bool operator()(string a, string b) { return a.length() > b.length(); } } largerWordFirst; int main() { const int MAX_DICTIONARY_SIZE = 11; const int MAX_ANSWERS = 10; string dictionary[MAX_DICTIONARY_SIZE] = {"apple", "oranges", "fruits", "salad", "coffee", "this", "that", "bloomberg", "rocks", "new", "york"}; string tiles = "appleorangesfruitssaladcoffeethisthatbloombergrocksnewyork"; std::sort(tiles.begin(), tiles.end()); std::sort(std::begin(dictionary), std::end(dictionary), largerWordFirst); for (int i = 0, j = 0 ; i < MAX_DICTIONARY_SIZE && j < MAX_ANSWERS; i++) { if (find_remove(dictionary[i], tiles)) { cout << ++j << ". " << dictionary[i] << endl; } } return 0; } bool find_remove(string word, string& tiles) { string temp = ""; std::sort(word.begin(), word.end()); for (int i = 0 ; i < word.length() ; i++) { int idx = tiles.find((word.at(i))); if ( idx == std::string::npos) { tiles.append(temp); std::sort(tiles.begin(), tiles.end()); return false; } else { temp.push_back(tiles.at(idx)); tiles.erase(idx, 1); } } return true; }

Juan Andrango on Sep 27, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.