blog.whoop.as

Anagrams

2009-03-05T00:00:00-08:00

Anagrams

3 Mar 2009

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;
}

Here's an example run... you might notice a bug or two.

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

New MacBook Pro

2009-02-28T00:00:00-08:00

New MacBook Pro

28 Feb 2009

A few weeks ago I ordered a new 17" MacBook Pro to replace my current perfectly capable 17" MacBook Pro.

I didn’t expect it to ship until mid-March but it seems that it’s on a pallet in Fed-Ex’s possession right now and it should arrive at my door by 3/4/09. Nice.

Specs of the new MBP are default except for :

7200 rpm disk
non-shiny screen

I’m not exactly sure what I’ll do with my current MBP.

This butt's for you

2009-02-27T00:00:00-08:00

This butt’s for you

27 Feb 2009

I recently quit smoking. Despite the anecdotes and my mothers experience I found it easy and painless.

I’m sure my ease in quitting will piss of the perpetual quitter, but solace yourself with the knowledge that I started smoking in my early 20’s, not my teens.

I found that I smoked more as a situational habit rather than nicotine craving.

Clean Start

2009-02-26T00:00:00-08:00

Clean Start

26 Feb 2009

So long wordpress, you won’t be missed…

No more pseudo CMS for a silly bunch of text and images.
No more spam.
No more ~~comments~~ time wasting arguments.
No more disgustingly slow mysql instances. thanks textdrive!
nearly No more politics.

This new iteration of whoop.as is just static text, written in Emacs using textile, generated with jekyll, synced with rsync.

I’ve squirreled away a copy of the old dribble and may decide to resurect some of the better posts in the future, but for now a clean start is refreshing.