Fun Developer Interview Question

When conducting interviews, I’ve developed the following criteria for a good interview problem:

• Avoid brain teasers – they tend to be hit/miss and some people don’t really do well under this type of problem
• Challenging – the answer should not be immediately obvious and the should require some creativity
• Rare – similar to above, the problem should not be a common question in order to get
• Flexible – the problem has multiple solutions and can be modified on the fly for different skill levels

I’ve found that the following problem satisfies the criteria and gives a pretty good sense of a developer’s skill level.

The problem starts of as a simple scenario:

You need to write a program that will accept a list of words. After the words are entered, the user will enter words and your program will need to indicate whether the entered word was in the original list. How would you design this program and what data structures would you use?

The typical answer to this question is to either store the initial word list in an array, a tree, or a hash. If it’s an array or a tree, we talk about the Big O of the solutions and compare that to just using a hash. At this point you can get a sense of whether the person you’re interviewing understands basic data structures and knows the use cases of each one.

To dig deeper, I add a twist:

Now imagine you were transported back in time and it turns out your program uses too much memory and you can’t keep track of every word. Do you have any alternative solutions?

The creative solutions start appearing here and you can get a pretty good sense of the problem solving skills. For example, a proposed solution at this point is to use word roots or repetitive letter combinations in a tree like structure to reduce the memory usage. We then talk about the algorithm that would need to be written and try to point out possible problems and see how they would be addressed.

And a final twist:

Let’s say you still do not have enough memory and but you find out that you don’t need to be correct all the time. Can you think of any solutions that can achieve this?

At this point, many people will try to come up with a heuristic or machine learning technique to try to identify words that resemble the words previously entered. We can then talk about both how to construct the algorithm as well as talk about the accuracy of the approach. It turns out that for these solutions it’s difficult to quantify the trade off between error rate and space requirements.

At this point the concept of a Bloom Filter is brought up, either by me or by the person I’m talking to. If it’s by me I go through the basic concepts (bit array, hash functions, probabilistic data structures) and can get a good sense of whether this is understood or I need to dig deeper. It’s great when you can see the moment that someone “gets” the value of this data structure and knows immediately how to use it. At this point we discuss the trade off between the size of the bit array and the number of hash functions. If there’s time, we’ll work on deriving the relationship between the two as well as talk about where they can be used in the real world.

I wish I could remember how I came up with this problem – I think it stemmed from me encountering Bloom Filters for the first time as well as reading a few articles about spell checking and dictionaries.

Related articles

• Wikipedia: Bloom Filter (wikipedia.org)
• Python Implementation (www.coolsnap.net)

Posted in Uncategorized | 9 Comments »

Google Giving Employees Free Adwords?

According to this blog post Google gives their employees $1 a day to advertise on Google. The intent is to give employees the perspective of an Adwords user in order to improve the product. In addition to giving employees exposure to Adwords, this also has potential to increase the competition in Adword auctions by causing bids to increase and leading to more revenue  for Google. Given that Google has more than 10,000 employees worldwide this can have an effect on smaller advertisers.

Other people have written about Google advertising for their own products and giving employees free money can have a similar, although smaller, effect.

Related articles by Zemanta

• The Problems With Google House Ads (webguild.org)

Posted in Business, Musings | No Comments »

More Posts Coming Soon!

I will try a new policy – at least one post a week. Harass me if I’m not doing it.

Posted in Uncategorized | 2 Comments »

Improving Your Luck

People often blame bad luck for their failures. This absolves them of responsibility and allows them to stop trying. What they should have done is admitted their failure, learned from the experience, and prepared themselves for the next opportunity. Exposing yourself to opportunities is the best way to overcome bad luck. Authors are a great example of this: J K Rowling and John Grisham had their novels rejected numerous times before they succeeded. Yet soon after publishing they became blockbusters. How many authors gave up when trying to have their work published? Imagine if they had the determination that J K Rowling and John Grisham had.

As Seneca the Younger, a Roman philosopher, said, “Luck is what happens when preparation meets opportunity.” In order to increase your luck you need to increase your exposure to different opportunities. In addition, you need to realize an opportunity when it presents itself. A way to view this is through the simple roll of a die. Although a die only has a 1 in 6 chance of rolling a 1 when rolled once, it has a greater chance of landing on a 1 when rolled multiple times. Most people give up after a few rolls but in order to succeed you need to keep on playing the game until you get a successful roll.

The fact that you are reading this shows that you are luckier than the majority of the world’s population. You have access to the internet and the desire to improve your luck. You can leverage that to contact leaders in your field or people who can help you succeed. You may get no responses from some but you will get encouraging responses from others. You just need to be open and increase your opportunities.

Posted in General, Musings | 2 Comments »

Power of Twitter

I may be a bit late to the party but I was finally able to see the power of Twitter this afternoon.

I kept on getting an “Authentication failed” message when trying to log in to AIM. A few years ago I would not know what to do except ask my friends if they were having any trouble. Right now, I went to searched for “AIM” on Twitter and discovered that other people were having the same problem. Turns out it was a systematic problem and I wasn’t the only one affected. Being able to know more about this problem is a great benefit. There has been a lot of talk of the power of real time search and real time news but this was my first real glimpse into the power of Twitter.

My first action wasn’t to search for “AIM log in problem” on Google but to search for “AIM” on Twitter. It’s amazing to me that Twitter was able to replace a certain type of search. The majority of my searches will still be done on Google but it seems that for anything with a pulse – Twitter search is the way to go.

Twitter’s character limit is a great way to take advantage of the network effect. Having a low character limit encourages a lot more users to tweet thereby making Twitter feel alive and giving everyone else more information.

There have been numerous ideas of Twitter being used for market research and to get an early customer response – I can imagine that happening now and it’s mind blowing.

Posted in General, Technology | 2 Comments »

Enabling Modules in Apache 2 under Ubuntu

The Apache enabled modules are found in “/etc/apache2/mods-enabled” as a set of .load and .conf files. If the modules you want are in the /etc/apache2/mods-available folder but not in “/etc/apache2/mods-enabled” folder, just copy the .load and .conf files over (note that the .conf file may not exist).

If there is no file in the mods-availble folder, you will need to create a new .load file in the mods-available folder to point to a module in “/usr/lib/apache2/modules”. To do this, create a .load file containing the line “LoadModule xxx /usr/lib/apache2/modules/yyy.so” where xxx is the name of the module and yyy is the file name. After creating this file, you can just copy it over to the mods-enabled folder and restart apache using “sudo /etc/init.d/apache2 restart”

Posted in Apache, Programming | 4 Comments »

What’s the easiest way to be elected President?

Answer: Be elected for a first term, the second term will follow.

It turns out it’s pretty likely that a president will be elected to a second term. If we examine all previous Presidential Elections, we will see 8 presidents who failed to get reelected:

On the other hand, if we look at all presidents with 2 or more terms, we only see a few Presidents who have failed to get elected. Some of these, like Andrew Jackson, failed to get elected initially but were then able to get 2 terms in office. Grover Cleveland had non consecutive terms in office. In total, there were 16 presidents who had a second term.

Franklin Delano Roosevelt ran for, and won, a 3rd term in 1940 using the idea that one should “not change horses in midstream.” He did not need to do that since it seems people stick with what they are comfortable with.

Note: If I made a mistake anywhere let me know so I can correct it. The data was retrieved from Wikipedia.

Posted in Musings, Politics | 4 Comments »

More posts coming up

I’ve been busy recently but have a bunch of topics that I want to write about so keep on checking.

Thanks for reading!

Posted in Uncategorized | 4 Comments »

Weekend Voting

I found an op-ed in the NY Times that claimed that the best way to increase voter turnout was by having election day fall on a weekend. They provide a few examples but nothing too detailed. I tried pulling in some data and seeing if I could come to the same conclusion. I used two data sets: voter turn out by country and election dates by country.

Combining this data into one table, and ignoring the missing data:

It does seem as if they are on to something – the average turnout for weekday election days was 76% while the average turnout for weekend election days was 84%. This wasn’t a very rigorous examination and I am sure there are many more issues that factor in to the voting process but it does make intuitive sense.

Posted in Musings, Politics | No Comments »

Some Thoughts on Innovation

I stumbled unto an article written in 1968 that tries to predict what the world of 2008 will be like. Usually, these types of predictions are completely off and tend to predict a future far more advanced than what it actually becomes.

Image via Wikipedia

As expected, the article had it’s exaggerations (automatic cars driving at 250 miles per hour, inter-continental rockets, average work day of 4 hours ) but what struck me the most is how accurate the predictions about computers are:

The single most important item in 2008 households is the computer. These electronic brains govern everything from meal preparation and waking up the household to assembling shopping lists and keeping track of the bank balance. Sensors in kitchen appliances, climatizing units, communicators, power supply and other household utilities warn the computer when the item is likely to fail. A repairman will show up even before any obvious breakdown occurs.

Computers also handle travel reservations, relay telephone messages, keep track of birthdays and anniversaries, compute taxes and even figure the monthly bills for electricity, water, telephone and other utilities. Not every family has its private computer. Many families reserve time on a city or regional computer to serve their needs. The machine tallies up its own services and submits a bill, just as it does with other utilities.

Money has all but disappeared. Employers deposit salary checks directly into their employees’ accounts. Credit cards are used for paying all bills. Each time you buy something, the card’s number is fed into the store’s computer station. A master computer then deducts the charge from your bank balance.

Computers not only keep track of money, they make spending it easier. TV-telephone shopping is common. To shop, you simply press the numbered code of a giant shopping center. You press another combination to zero in on the department and the merchandise in which you are interested. When you see what you want, you press a number that signifies “buy,” and the household computer takes over, places the order, notifies the store of the home address and subtracts the purchase price from your bank balance. Much of the family shopping is done this way. Instead of being jostled by crowds, shoppers electronically browse through the merchandise of any number of stores.

Compared to the rest of the predictions, this is amazingly close to what we currently have. There is still some emphasis on the server and treating computers as a utility that is not currently present but with the rise of Google Docs and other online tools, that is not such a distant notion.

This begs the question, why are the predictions so close when it comes to computers but so off when it comes to other technologies? More importantly, why does Moore’s Law apply to transistors but not to larger technologies? I have a few ideas:

• Infrastructure costs – it’s cheaper to replace modern day computers than modern day cars. Thus, innovation can happen at a faster pace as people replace their computers. Also, computers tend to work in a much more solitary environment than cars do; being able to drive a car 300 miles per hour is useless when the roads can’t take it and the laws prevent it.
• Experimentation – it’s easier for the average person to hack around on a computer than it is to hack around on a car. Thus, a lot more people are working on ideas and due to sheer numbers, more ideas are bound to stick.
• Brand new technologies breed creativity -
  

  Image via Wikipedia

  When computers were invented, no one knew what they were capable of and everyone had ideas as to how they could be used. Many people pursued their ideas and were able to create and improve on various technologies. Also, many teenagers and students were involved in embracing this new technology – and they didn’t know what was impossible so they reached for the stars.Now, everyone is so used to what cars are that people don’t even imagine what cars could be capable of. We may be approaching this same plateau with computers.

I’ll try to update these when I think of any more.

Posted in General, Musings, Technology | 3 Comments »