I've decided to start posting little programs and code snippets that solve interview questions I've asked in the past. Why would I do this? I recently interviewed someone who disagreed when I stated their solution was expensive, they didn't believe me when I told them there was a more optimal (space and time) way to solve a problem. Now I can point them here so they can learn why they're not invited back for a second round.
This first example is a solution to the following problem -
Write a program that will quickly return a list of all anagrams that match a query string.
#include <cstdio>
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;
string counting_sort(string &word) {
transform(word.begin(),word.end(), word.begin(), ::tolower);
int counts[26] = {0};
int offset = 97;
int len = word.length();
for(int i = 0; i<len; i==++==) {
if(word[i] == ' ' || word[i] == '\n' || word[i] == '-' || word[i] == '\'') {
continue;
}
int idx = ((char)in[i]) - offset;
counts[idx] += 1;
}
ostringstream os;
os << "[" << counts[0];
for (int i = 1; i < 26; ==++==i) {
os << "," << counts[i];
}
os << "]" << "!!\n!!";
string ret = os.str();
return ret;
}
int main(int argc, char *argv[]) {
map<string, vector<string> > all;
cout << "reading dictionary...";
ifstream words("/usr/share/dict/words");
while(!words.eof()) {
string line;
getline(words, line);
string key = counting_sort(line);
all[key].push_back(line);
}
cout << "done." << endl;
while(true) {
cout << endl << "Word: ";
string in;
cin >> in;
string key = counting_sort(in);
vector<string>& vs = all[key];
int count = vs.size();
cout << "there are " << count << " matches." << endl;
if(count > 0) {
for(int i = 0; i < count; i==++==) {
cout << vs[i] << endl;
}
}
}
return 0;
}
eric@nutrino:~/src/anagram>g++ -O3 -o ana anagram.cpp eric@nutrino:~/src/anagram>./ana reading dictionary...done. Word: retinas there are 6 matches. asterin eranist restain stainer starnie stearin Word: restrain there are 3 matches. restrain strainer transire Word: phone there are 2 matches. pheon phone Word: ^C