The FizzBuzz Paradox

I always thought that there is a paradox around the FizzBuzz test.

On one hand companies claim that X% of their candidates could not solve FizzBuzz, where X can be as high as 95%. This somehow suggests that it is rare that people who call themselves programmers can program even a little bit.

Let’s look at the other side of the coin: There is evidence that there are millions of living  programmers who can create working software. Software that actually achives something, that is used, that can be selled. Where do I know it? Even the lowest-paid tier of our industry can create working software. Let’s see some stats: There are more than 900.000 apps alone in Apple’s appstore, created by at least 250.000 devepers, most earning very low amount of money. Similarly for Google Play. We all know that the number of websites, the number of web programmers is way bigger than this, maybe an order of magnitude bigger. On sites like ‘rentacoder’, ‘elance’ etc… people are offered very low amount of money for actual working code.

How is it that on one hand it seems that a programmer who can even program some lines of code is someone special, on the other hand it seems that there are millions of programmers who maybe write mediocre code, write maybe unmaintanable code, but it is beyond doubt that they can write some lines of working code?

This is a huge paradox. I don’t know the exact resolution of it. I think it is a combination of lots of things, which are all (half)true:

– Most programmers can solve FizzBuzz. It is the programmers who do not have jobs and try to get into hundreds of companies that cannot solve FizzBuzz. They are the minority but they apply to lots of jobs.

– Programmers got better, FizzBuzz results from 2007 are no-longer relevant in 2013.

– People are incredibly stressed on an interview

– Geographical differences. At some parts of the world there is probably really shortage of even mediocre programmers, because the demand is so high. At other parts of the world it is not true, but we hear the FizzBuzz stories from the high-demand places.

– It is possible to create relatively simple but working software without algorithmical and/or mathematical thinking. The tasks at a real job are THIS MUCH different than an algorithmization task.

What do you think? How can this paradox be resolved?

(If you liked this post consider downloading and trying my iOS puzzle game called ‘Find the Mafia!‘, which I just made free for some days to reach more people. It is especially interesting for geeks because it is based on a graph-theory problem, called ‘maximum clique problem’.)

Posted in Uncategorized | 1 Comment

Top Tech Companies: You mostly filter on raw IQ, and here is how to do it more effectively

Here is what I think of current tech company recruitment trends: While less prominent companies measure experience and basic coding skills (for example FizzBuzz), the most prominent companies (Google, Facebook, Microsoft, etc..) mostly measure raw IQ. Raw processing power of the brain. They are not interested in whether you know a concept or not, if you want, they explain an unknown concept when showing you a problem. They are interested in how smart you are.

There are different ways to be smart of course.

1. There are people who think very differently than others, have unusual thoughts which are sometimes right (sometimes not): these are creative people.

2. There are people who are the long-distance runners of thinking, maybe they are not very fast, but forming an important theory (or solving an important theorem) through years.

3. And there are the sprinters, who win competitions, and excel at top tech comany interviews. They have a huge, real-time raw processing power, which is effective in  time-constrained environments.

Of course these three things correlate with each other. But they are not completely the same things.

Top tech companies measure the third kind of smartness, and I think they do it the wrong way, because their system can be gamed.

They give you computer science puzzles not because they are interested in how much years you spent to solve these kind of problems (you will not solve these kind of problems in your job), but to measure how smart you are generally, and they expect to apply this general smartness in your job. The system can be gamed this way: someone just moderately smart studies and excercises comp-sci problems fo years. It seems absurd that I say that learning comp-sci is gaming the system, but if you think about it, practicing these problems too much is really some kind of ‘overfitting’. What we see on the internet: tips on how to study for a Google/Facebook interview, database of Google/Facebook interview questions: these show that people are willing to game the system. If you already know an interview question you successfully gamed the system. You even gamed the system if you have solved lots of similar problems.

If these companies really want to test the 3rd kind of smartness I mentioned, then what these companies need is a standardized test for the 3rd kind of smartness, which cannot be gamed so easily. And while this territory will have to be heavily reasearched, I think I know a possible direction:

Make the candidates solve lots of random cases of NP-Complete problems in a short time-frame.

I think this may be the kind of standardized IQ test, which cannot be gamed. At least that is what I think after playing hard with my iOS game ‘Find the Mafia!‘ for a week. ‘Find the Mafia!‘ is a game which gives you random cases of the ‘maximum clique problem‘ with preset graph size, and clique size, and measure how fast you solve these problems on average.

Image

– It really seems you cannot significantly become better in it unless you really become smarter in the 3rd meaning I mentioned.

– You cannot memorize cases. Every case is different.

– No cultural bias. After 2 minutes everybody knows what the game is about, even relatively small children.

You just need the 3rd kind of smartness, the raw processing power, the ability to find solutions fast in a chaotic/problematic scene.

I would be really really interested in how efficiency in ‘Find the Mafia!’ would correlate with the efficiency in Tech Company interviews. If my theory is right, the correlation becomes bigger and bigger if we somehow normalize Top Tech Company interview efficiency with the amount of time the individual practiced comp-sci problems.

Posted in Uncategorized | 7 Comments

My iOS game based on the maximum clique problem: Find the Mafia!

Months ago I have read an article about how mathematicians constructed pure mathematical models of some classic video-games, and proved them to be NP-complete. Turns out that most of the most successful classic video games are NP-complete (for example Tetris).

Suddenly an idea came to my mind: What about the other direction? Constructing a video game based on a classic NP-complete problem? As those days I was thinking about learning iOS development, I thought something along the lines of this idea could be my first iOS app.

The obvious candidate was my favourite problem: the maximum clique problem: find the biggest complete subgraph of a graph.

ipad_ftm

Screenshot from the game

This problem is my favourite because I find it so extremely simple on so many levels.

It is very simple mathematically. The concept of graphs require very few concepts, and the mathematical logical description of the maximum clique is a small expression.

It is also very simple to understand by humans. My five year old daughter could understand the rules of the game I have created based on it!

ftm_classic

The rules are so simple that the game feels like a classic. Who knows? Maybe the ancient Greeks already played it in the sand.:)

I knew that because the maximum clique problem is much more simple than the mathematical model of classic games, the game created based on it will be probably the puzzle game with the most simple rules ever created.

But I did not know how challenging and how much fun it will be.

I have created a prototype fast, tested it with some of my friends and family members, and it turned out the game is fun, on the appropriate level it can be just as challenging which is still fun, and can be very addicting. My first personal impression was that I was surprised that the game can be so challenging on what I thought to be relatively low levels. I thought finding a 4 node complete graph in a 10 node graph will be always trivial, while it is not!

It also turned out that the game is most fun when playing it on a level where solving cases one after the other can be done relatively quickly, and the challenge is to shorten your average time. (So a core concept of the game design became measuring time. For me personally the game is most fun somewhere at ‘finding 4 nodes in 10 nodes’ (4/10), or as I become better maybe 4/12. My five-year-old daughter plays on 6/3.

It is interesting how different the difficulty of the randomly generated graphs is. For half of the cases I see the solution immediately. For a quarter of them I need to think for a minute or more. (on 4/10).

It is an interesting question that what kind of ability this game measures? I don’t know what it is (some kind of pattern matching), but it feels something quite fundamental. I can imagine that because of its stripped-down rules this game can be a good tool for cognitive psychologists.

If you became interested click on the website of the game with a gameplay video and appstore link on it.

Posted in Uncategorized | 1 Comment

Javascript Genesis

Everyone knows that God created the world in 7 days, but only few people are aware of the fact that first God had to create the different forms of nothing on day zero.

On day zero in the first hour God created the divine form of what we usually call unknown. He called it:

undefined

In the second hour God created the divine concept of nothing. Here it is:

null

In the third hour – they say this was the hour when mystery was born – God created the thing (unimaginable by us humans) which is something, so it is not nothing, but about which we can’t say anything, as it has no attributes at all, and anything we want to ask about it, the answer is unknown:

{}

In the fourth hour God created emptiness by creating the divine empty box:

[]

In the fifth hour God created silence:

In the sixth hour God created the divine thing which we experience when trying to count things, but we cannot find anything to count:

0

And in the seventh hour God created the concept of doing nothing, the concept of letting things as they are:

function(x){return x;}

And God saw that it was good, so on the next day … but I stop here as you all know what happened next.

Posted in Uncategorized | 1 Comment

The good guys and bad guys algorithm

A good introduction to the mistery of the P vs. NP problem is to examine polynomial-time algorithms which ‘almost’ solve an NP-complete problem. Usually such algorithms solve the problem for most inputs, and ‘only’ fail at some quite rare ‘evil’ special inputs. Here I present such an algorithm of mine. I don’t even know for which kind of evil inputs it fails. (It probably fails for some inputs of course, it is just harder to provide counterexamples than to come up with the algorithm itself.) The reason that I present this algorithm is that I want to demonstrate a rarely considered possibility: Maybe P equals NP, maybe we will even find the algorithm which is not that incredibly complicated, we will use the algorithm in practice, but it will be crazily hard to prove that the algorithm is correct because the algorithm is based on pseudorandom behaviour (a.k.a Monte Carlo method) and some kind of ’emergent’ behaviour instead of a simple direct, easily analyzible behaviour.

So here is an algorithm which tries to find an N/2 clique in a graph. (A clique with half of the vertices.)

Please note that it is enough to find one vertex which is surely not in the clique. Then we can recursively use the algorithm for the remaining vertices, and it is easy to see that we will still be in polynomial time.

At the beginning let’s erase those vertices which has less then N/2-1 neighbours.

Let’s call the vertices ‘guys’. The ones in the N/2 sized clique are the good guys, the other N/2 guys are the bad guys. The good guys form a clique. The bad guys decide how they connect with the good guys and with each-other. They intentionally try to ‘game’ the system, they intentionally connect in tricky ways to make our algorithm fail.

Now we randomly distribute the vertices into two N/2 sized distinct sets:

– The good set.

– The bad set.

We repeat the following for a reasonable time: (let’s say N^5 times)

We randomly select two guys in the good set which are not connected. We replace them with two randomly selected guys from the bad set.

Please note that when we do such a replacement, then we do one of the following 2 things (without knowing which case we are dealing with):

– We throw out two bad guys from the good set.

– We throw out one bad guy and one good guy from the good set.

So we never throw out two good guys!

During this  N^5 steps, we note for each vertex for how many time it stayed in the good set. Let’s call it T(n). It is easy to see from the above that the good guys together have a better summa T(n) than the bad guys.

But of course the bad guys can do evil trics. They can create some ‘bad superstars’. These are connected with almost every good guys and almost every bad guys. These can have very good T(n). This does not hurt us though, because we are only interested in the ‘worst’ guy. But they can do even more evil tricks. They can chose two good guys which they don’t connect with. And they connect with good guys and each other very much, on the borderline of creating another N/2 clique (but not creating, because they are not allowed to.) These bad guys, when get into the good set, they throw out these two good guys (while throwing themselves out, but they are in superior numbers.) The two poor good guys can end up having the worst T(n)-s.

But we don’t give up. The T(n)-s represent something about ‘goodness’. We just have to extract some minimal tiny bit of information from this.

We order all the guys according to their T(n)-s.

We mark the best N/2 the ‘goods’, the others the ‘bads’.

Now we give ‘points’ to vertices according to how many good neighbours they have. (Maybe we should somehow penalize bad neighbours, but I am not sure, because this way bad guys could just make harm to good guys by connecting to them.)

Now we order the guys according to points, we call the best N/2 the goods, the other N/2 the bads…

We repeat this let’s say N^5 times. The idea is that good guys are that guys who know very much good guys. Those two poor good guys in the previous example are coming up…

We assume, that the guy with the least points in the end is a bad guy.

This algorithm probably fails for some inputs. (I don’t know for what kind of inputs yet.) The real question is that: can it be fixed? Is this really fundamentally impossible, or just a bit more tricky than we first thought?

Posted in Uncategorized | 8 Comments