Bloomberg L.P. Interview Question: Given a string of characters ... | Glassdoor

Interview Question

Financial Applications Developer 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
#include
#include

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.