Monthly Archives: October 2004

Unicode entry

This entry has some unicode characters (devanagari), let's see if they are visible correctly...

मराठीमद्ध्ये लिहिणे आता बरेच सोपे झाले आहे. यासाठी युनीकोडला धन्यवाद दिले पाहिजेत

What your CEO wants You to know…

Came across an article in Fast Company about Dr. Ram Charan and got hold of two books by Dr. Ram:
What the CEO wants you to know and Execution: The Discipline of Getting Things Done

I just finished "What CEO..." and it's filled with countless little gems in very easy to understand terms. Dr. Ram Charan grew up watching the footwear shop of his parents and teaches us the core nucleus of all successful businesses: Cash generation, margin, velocity, return on assets, growth, and customers. The concepts are illustrated by examples from the perspective of street vendor.

Very highly recommended. Now onto "Execution..."

Lateral Thinking…

How will you write a program to find jumbled words ?

The shotgun approach is the first one anyone is bound to follow at first. i.e. For all permutations of the letters, find if there is a match in the dictionary of words. You might do some optimizations to ignore repetitions etc. But this is O(n^2) complexity solution.

I read an elegant way to solve this here. The trick is to notice that the real answer and the jumbled word look the same when they the letters are sorted.
(Let's ignore the time to sort the words for now, which is O(n*log(n)) I believe for decent algorithms.)

Here is a python snippet to solve the jumble:

#!/bin/env python
def find_jumble(jumble, word_file='/usr/dict/words'):
    sorted_jumble = sort_chars(jumble)
    for dictword in open(word_file, 'r').xreadlines():
        if sorted_jumble == sort_chars(dictword):
            yield dictword

def sort_chars(word):
    w = list(word.strip().lower())
    return w

    inp = raw_input("Enter word: ")
    if not inp: break
    for ans in find_jumble(inp):
        print "Answer = ", ans