Problem of autocorrect - A quick solution using Approximate String Matching

I was always curious about the auto correct feature of Google.  I mean, lets face it - it looks ultra cool especially when we type in some vague disjointed letters and Google suggests us exactly what we had in our mind.  It feels like Google kind of reads our mind !

With some time in my hand, I decided to venture out on finding how to do it.  Of course, I don't have the monstrous server farms that Google has its disposal, to make an equivalent web solution.  Also, considering the fact that I'm mostly a C/C++ guy, I decided to analyze and implement a solution more suited to the C++/desktop configuration.

A quick Google search for this problem domain yields many results.  Apparently string matching / searching is a popular research topic.  But, I wanted a more simpler solution than suggested by the results.  And what do you know, the age old classic book on algorithms - 'The Algorithm Design Manual' by Skiena, just had something that meets my needs.  Combining the solution given in the book with some extra code, I could arrive at a decent auto correct solution.  Of course, it has many flaws.  But its a good first step effort IMO.

So, without further ado, here's what it looks like :

1. Design:

Approximate String matching is achieved by finding the minimum distance between two strings.  Here distance between two strings is calculated by the no. of operations (substitutions/insertions/deletions) it takes to convert one string to another.

For ex: lets assume our input string is abiliti and we have to convert it to either ability or capability.
We would need to substitute i with y, to convert abiliti to ability.  But it would take much more effort to convert from abiliti to capability.  So the distance between abiliti and ability is much lesser than abiliti and capability.

Now if we have a dictionary(text file) of grammatically correct words, all we need to do is to compare our input string (the one which needs a correction) against each of the word in the dictionary , calculating the distance in each case.  The word with the minimum distance is the one that should be the correct one.

Easy isn't it ? Not so fast.  Its easier said than done.  And moreover, this method does have its flaws, which I will cover in another topic.  But for now, lets see how to go about implementing this.

2. Implementation

Lets say"dictionary" is a string of vectors containing the list of grammatically correct words.

lets initialize lowestCost to a high value say 65535,

Suggest would be the auto corrected string.  This does work fine in many cases.  But not all.  Anyway, the correctness of the above solution will be analyzed in another post.  But for now, even if its successful in giving the correct output, I would say it still has some basic flaws.

Can you spot the problem with the above approach ?

For one, we are unnecessarily comparing the input string with every word in the dictionary.  To take the above ex:  abiliti, my search should have compared only the alphabets starting from a.  But in the above, I continue until Z.

So to improve it further, I would construct my dictionary in a more intelligent manner.  Instead of a single vector, I would have an array of 26 vectors, each corresponding to an alphabet.  I will have a Map that maps from the letter to the exact vector.  Now, if I've to search for the word straight, I would go from my Map, to the corresponding vector list that has words starting only from S.

Our dictionary is now a map of alphabet -> vector list of grammatically correct words starting with  that alphabet.  So, instead of running through all the words, we just take the first character of our inputStr and use it as an index to directly jump to the corresponding vector list.

So, the above algorithm changes to :

Now , that the main function is in place , what about the utility function - string_compare, which is the one doing the actual grunt work of calculating the minimum distance.  How do you go about comparing two strings to calculate the minimum distance ?  Do keep in mind that we have to perform this operation for hundreds (maybe even thousands depending on the size of your dictionary).  I'll leave it as an exercise to the reader.  Skiena's book, proposes an elegant as well, using dynamic programming .  It could also be easily googled.

What matters the most ?

Sorry for the lame, obvious catchy line intended to attract readers :)

I don't mean to ask this question in the grand scheme of life.  But more specific in one's career's growth.  Especially in a company with thousands of employees.  What do you think matters the most ? What makes a person standout in the crowd ?  While most folks burn out at middle management, and others just give up and move to other business, there are quite a few who stick it out in their chosen field, and grow up in a company , often reaching to the peak before they retire. I was pondering over this issue, talking to one of my friends the other day, and he said, there was some special "factor" required for a person to get noticed, to move into premium roles like, a VP or SVP.  So what's this "factor" that differentiates one person from the herd ?

Here are some obvious answers to this:

1. Skill: While this may sound to be the most obvious, IMO, this can take you only so far.  At some stage in your career, you reach a place where everybody around you are equally skilled in a particular line of work as you are, if not more than you.  While it really helps move your career in leaps in the initial stages, this cannot propel you all the way to the top, unless you are in a very small company, or you happen to be one of the initial founders.

2. Hard Work: This is might tie with no.1 as the most obvious answer.  A really worthy quality to have .  You might have all the skill set in the world, but none of them are useful, if you don't work hard and keep it honed.  But again, I've seen hundreds of employees who are damn hard workers, but they just wait and stagnate.  Most senior management see them as necessary folks with no life of their own.  This is the worst category to be in, if this is one's sole strength, for he is in the danger of depression/burnout much sooner than others.

3. Focus: Now, this is a particularly interesting talent to have.  Many people can be hardworking or skilled, but not everyone is focused on the task at hand.  I've seen many skilled engineers while away their time browsing random web pages or really hard working men, staying up until 11 in the night, with no productivity to show.  So, focus is indeed important.  But it cannot be a unique talent on its own.  Its often best complimented with the above two points.

So, now, coming back to the topic title, IMO, the one talent that differentiates a person from the crowd is.... 

4. Consistency:  Yes.  You heard it right.  IMO, this is the most important factor is differentiating a leader from the herd.  "How consistent you are in executing the task given to you !"

Its not enough to be skilled.  "Are you consistently able to hone your skillet over a period of time, and remain in business ? "

Its not enough to work hard for one stretch. "Can you do it consistently until the goal is accomplished?" 

Its not enough to be focused at one given task for a while and finish it.  "Can you consistently focus on the tasks given to you day after day without getting distracted ?"

IMO, this is what differentiates leaders form the herd.  They give consistent results, time after time.  They hone their skill-sets regularly, they are hard working and focused over a longer period of time than most.

So, if there are any of you who think you have been mistreated in-spite of being skilled, hardworking or focused at your job, ask  this to yourself - 'are you consistent enough' ?

(link to the image: http://profilestopartners.com/2011/09/10/who-is-ready-to-lead-your-company/leader-standing-out-from-crowd/)

Pomodoro Technique

People assume that, being an Engineer in the software development field, I spend all my time working on some of the most complex and interesting problems out there.  While its true to some extent, the reality is that, its not always. Some days are filled creative tasks like finding obscure bugs, brainstorming design decisions etc., which really makes you glad you choose this field.  But, time to time, on some days, even us engineers are subjected to the "non-grey cell consuming", soul crushing , boring , mundane tasks.  And the irony is, you can't have one without the other.

Now, based on my work experience so far, I found that I have a tendency to procrastinate all these mundane not-so interesting work until the last minute.  And one fine day I walk into my office, open my office email, and BOOM ! my manager needs the report in the next hour.  You start cursing yourself for neglecting it so long, and start working on it asap ignoring even that cup of coffee you brought in to drink.  Needless to say, it causes lot of stress, and also takes valuable time away from more important things that has to be attended to on that day.  I tried many ways to get around this problem, and one of the most effective way, that really works for me, is the pomodoro technique.

In a nutshell, quoting straight from wikipedia:

The technique uses a timer to break down periods of work into 25-minute intervals called 'Pomodori' (from the Italian word for 'tomatoes') separated by breaks. 

So, this is how I tackle these mundane/routine tasks at my office these days:

1. First thing in the morning, make a TODO list of the tasks to be completed.

2. Pick the least interesting / mundane tasks and fit all of them into one of the day slots (usually post lunch, unless its required to be completed before that) 

3. Before beginning the task, start a timer of 25 mins and start working on it.

4. Take a break for 10 mins, and then start another timer of 25 mins and continue to work, so on until the task is completed.

The reason this has been working, in my opinion, is that, it brings in a psychological relief to me.  When I start a timer for 25 mins, I'm telling my mind that - "hey its ok, even if the work is boring, I've to survive it only for the next 25 mins".  It has so happened that sometimes, at the end of the 25 mins, the work no longer seems boring , and instead of the 10 min break, I just go ahead and finish it. 

If you have any other techniques to battle the routine/mundane tasks, put them in the comments below.   Cheers !

(link to the original image:  http://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Il_pomodoro.jpg/220px-Il_pomodoro.jpg)

2013 - With new year comes new Resolutions !!

First, let me wish you all a very happy and prosperous new year !!

Given below are some of the resolutions I plan to abide by in this new year.  I'm not sure how long will I take to achieve any or all of them , goal is to get it perfected around 2 months from now !

1. Wake up early by 6 AM - Well, I've been practicing waking up early (than usual) for the past few days (usually i wake around 7 - 8AM most days , including holidays), and I've found  that the quiet time you get alone in the morning is totally worth the hassle.  And moreover, if this article is any indication, then, most successful people are early risers.  It also gives me sometime to read up on any interesting tech, or explore more on the ideas I might have.

2. Exercise daily for at-least 15 mins - I've been practicing this as well since the past few days.  I've to admit, this adds a huge amount of difference to how positive you are when you start your day.  I have not been lifting weights, but just simple push ups and ab exercises.  Even the small 15 mins duration, helps me boost my self confidence and makes me cheerful at the beginning of the day.  In my opinion, starting a day on a cheerful note does increase your productivity in that day.

3. Join a Gym and work out for at-least 4 days in a week - Now, this is something I've been putting off since a long time.  I'm not sure what the problem is, but seems that I'm too afraid that I'm gonna fail at this. And whenever I make up my mind to enroll, something at the back of my mind tells me not to, and pulls me back. But, with winter around, and chances of going for running/walking are at an all time low, hitting the gym is a must to stay fit.

4. Blog twice a week - This is basically to improve my writing skills as well as bring some thoughts out of me in a creative way.  Not that my English is bad, but I feel I've lot of room for improvisation, especially when it comes to articulating my thoughts/ideas in a creative and simple manner. Also, being a techie, one of the most important aspects of my job is to explain to the non-techies in a way they understand.

5. Avoid unhealthy food - Note that I've written 'Avoid', not 'Stop'.  My goal is to avoid eating junk whenever / where ever I can.  For ex: If I've a bowl of fruits / veggies vs a fried snack, guess what would I pick ? Hope you get the idea.  Indulging once in a while is no issue, but I don't want to gorge only on unhealthy food all the time, especially when I have an alternative.

Anyway, that's about it.  Would love to revisit next year and see how many of the above I got to meet !

Taxonomy of the manager species !

Here's a brief list of the kind of managers I've got the opportunity to work for in my career so far:

1. Control Freak - Thinks he owns you.  Controls every minute detail of your work.  Would throw a tantrum if you don't include him in emails.  Will cause a ruckus if you spring a surprise at him, always wants to be the one in control and hates anyone who challenges his authority.  You can grow as long as you don't threaten his position.

2. The Dude - He still thinks he's in his twenties.  Makes lewd jokes and remarks about fellow colleagues.  Discusses the latest pop videos , movies, rock concerts to show he's one in the gang.  Tries too hard to impress everyone and takes everything as a joke.  Believes in team work.  If you are under one of these "Dude's" find the nearest exit and bail out.  Unless you like splitting tab for the beer at TGIF !

3. The "Delegator" -  Believes everyone knows their job. Gives little guidance or support to the team.  His way of conflict management is to make everyone shake hands with each other. Does little team management.  Acknowledges your existence once in a while (mostly when you put down your papers).  Believes that his job ends at delegation and collecting status reports.  You learn the art of ownership under such people, but he'll do little to take your career forward.

4. The "Wannabe" -  This is by far the worst kind.  Runs his team on the principles laid down by "Philip Kotler" , and quotes frequently from popular "self help" books.  Always on a high of meeting deadlines and always on one toe trying to get things to perfection.  Believes in the company values, would sell his liver if the bosses ask and expects to get the corner office by hook or crook.  Will try everything in his capacity to achieve his goals.  Easy to spot - they come in formals , keep using words like 'in the loop', 'synergize' etc, usually the first to come to office and the last to leave.  Can be seen hanging around on weekends as well, if you dare to step in.  These are another bunch to avoid !

PS: Just my opinion, not intended to offend anybody !!

Melancholy ....

Some days are just off, you just wonder how to pass the time and indulge yourself in random activities.  The activities themselves don't have to bear any meaning for you, you just do something as if your mind is stuck in a cycle of indecision and laziness.  And, before you know - BAM ! Its 2 AM in the morning and you are still staring at your computer monitor ! Where the time flew ? 'Ah life sucks !', you declare and continue staring, randomly browsing, munching away that unhealthy snack that kills you a little every single day, and again make another resolution (in vain). to change yourself and upgrade your life first thing the next morning.

The cycle of melancholy that seeps into your life every once in a while, is a cruel master.  It makes you its slave. It eats away any form of energy you would have.  It engulfs your mind, clouds your judgement, pulls you back into boring and lifeless routine activities. It prevents you from accomplishing anything, and makes you surrender yourself involuntarily to it.  But from time to time, it does ensure that you remind yourself how of miserable you are as a person and while you do it laughs and jeers at you.

Yet, it happens to all of us, happens to the best of us, happens to the worst of us, and almost anybody who fits the description of a mortal human being.  Melancholy is perhaps one of the constants of life, like change.  It cannot be avoided, it cannot be planned for.  Its always lurking in the corner, sneering, waiting for the right opportunity to pounce on you at a time when you least expect it.  And when it does arrive, it saps at your motivation and slowly gnaws its teeth at your character.  

The only escape from its dark, cold and foreboding touch, that I know of , is to wait.  Simply wait until it settles away, don't try too hard to push it.  It begs you to do it, it derives pleasure as you try to shake it off from you.  It laughs at your efforts on curing yourself.  It loves a fight as it knows its gonna win at the end.  So, instead, make it your friend.  You don't need to necessarily like it.  Treat it as one of those friends / relatives who you have to shake hands with once a year at the family gathering.  You hate it, but you have to deal with it and move on.  Just wait for the unpleasantness to get over, and then slowly, collect back what's left of yourself and surge past it.  Melancholy hurts, just minimize the damage you allow it to do on you.

(link for the image : http://www.phocabulary.com/melancholy)

Self Leadership and Imagination

I recently attended a two week workshop on general soft skills / cross culture and related subjects' training.  Two topics really made me look up and take notice.  The others were good too, but the below topics really caught my attention.

1. Self leadership

2. Fostering creativity

I will not describe or discuss here as to what was taught to us in the workshop.  But I will just put down my own independent thoughts on the above topics from my perspective.

1. Self Leadership: 
I think this is perhaps one of the most interesting topics that has caught my attention recently.  We often complain of how much change we would like to bring in a "system" given the chance.  We often complain about the lack of leadership skills shown by others who hold such positions.  But when you do some introspection you realize that, leadership is in fact, not so easy.  And you realize it the hard way , when you try to "lead" yourself into "change".  The "change" could be anything , it could be as simple as "waking up early in the morning".  You can make a plan and start the process of "self leadership" into accepting yourself into this simple change, and you'll realize how hard it is ! It takes great amount of force to pull yourself out of routine and adjust yourself to a new reality. Most of us give up somewhere along the way, and say "it just isn't possible" or simple, procrastinate it so you wont feel guilty of totally giving up.  Whatever the case maybe, you need to ask yourself this - "If its so hard leading yourself, how do you think you'll be able to lead others ?"  Note that, I'm talking about "leading" and not "managing", they are totally different from each other.  Managing people is rather easy, but leading them, is hard.  And to those, who think they're already better leaders, or they think they can be better leaders, I would say your litmus test is when you start "self leadership" !  Try leading yourself into accepting a simple change from yourself towards improvement and you can gauge how good your leadership skills are !

2. Fostering creativity: 
Now this is another interesting misconception that I see most people have.  I see how often people believe that they are not "creative", and it takes some genius to be really creative.  After attending the workshop, I feel that this notion of "lone genius" is really misguided.  Creativity exists in all of us, its just that we let it go into hibernation, simply because we find it easier to adjust to routine and stay in our comfort zone.  For ex: We were asked to paint a dragon with water colors.  Now, even though I was fairly good at drawing long long time ago, I did not know I still had it in me.  But when I took those brushes and started painting, I felt I did a fairly decent job.  Now what sparked this ? In my opinion, its just that I was not afraid of the results / or in other words "failure", there was no one to judge me, and I had no critic to tell me whether it was good or bad.  I was like a child, exploring what I could  do with those brushes.  That's creativity.  Creativity exists in all of us  , but it only sparks when we set our minds free, get out of the "routine" box , stop thinking of risks and feasibility and worry about acceptance .  When we do that, we can see that we explore so many avenues which we initially thought did not exist.