Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot | Hacker News Reader

Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot

robweir.com

59 pointsFlemlord25 comments

Turning compare into a coin flip is a fun way to illuminate the underlying algorithm.

IE is said to use a heap/tree related sort[1]. The first thing a heapsort does is swap the last entry with the the front (where the front may have been swapped in the heapify step[2]). Thereafter it leaves the last entry alone.

Since the first entry in the unshuffled array is "Internet Explorer" if it survives the initial comparison it will always occupy the last (5th) place.

The other algorithms don't have a case with only one compare which is why they have more complicated distributions.

[1] - http://www.smallapple.net/rnd/art/how_does_your_browser_sort...

[2] - http://en.wikipedia.org/wiki/Heapsort

That is an incredibly long essay to describe a very simple problem. Don't randomize an array the way Microsoft does on browserchoice, because it's not random.

More subtly, don't ignore preconditions of methods. The custom sort method needs to implement several invariants, which the Math.random() approach ignores. This confuses the hell out of the sort algorithm (in turn, leading to non-random order)

It doesn't seem unreasonable there might be a bias to the 5th position, it would be the position you just finished paying attention to before clicking if your scan from left to right.

Is this even what is shipping with Win7 EU? I would assume that the real browser choice screen is not in a browser window, and that this website was created quickly just to give people an idea of what it might look like. Do we even know who actually wrote the code?

sigh That's really quite embarrassing. You can see the source code here: http://www.browserchoice.eu/resources/scripts/page.js

The bug is at the very bottom of the file.

Spot the spelling mistake too:

// Genereate random browser order

At least the programmer got the function name right.

I'm saving this for an example of how not to comment code.

The worst part about the implementation is that the browser icons often appear unsorted initially, and then the sort kicks in 0-5 seconds later, and they all shuffle.

This has caught me out at least twice by clicking on a browser icon to choose it, then the order changes after I clicked and the wrong browser installer is launched.

Its strange that MS got this wrong as the shuffling questions is quite common in the Microsoft interview (as in many other).

Though I do wonder if it makes any difference, may be they are taking this as an opportunity to do some research testing, my personal opinion would be that the browser in the middle position might have a slight upper hand than others.

Perhaps this is Microsoft, or someone who works there, thumbing their nose(s) at the EU - after all, what monopolistic corporation wouldn't be bitter at not having been able to buy out such an influential quasi-government organization [edit: and, worse, be forced to advertise on behalf of one's competitors]?

Don't get me wrong: I'm no fan of MS or IE. But I can see why they might deliberately fail to implement this correctly. [edit: ...]

Again, I see no benefit to MS or harm to EU for using the broken algorithm... It sounds childish that the broken algo is a win against EU of some sort

I don't think it's intentional, unless Microsoft intended to give Google Chrome prime placement (more likely to be in the first 3). More likely this is just sloppy coding that wasn't QA'd properly.

I doubt they put a dev on something like this...probably a 3rd party vendor or intern.

So in essence, Microsoft just handed this off to one of their junior programmers and he wasn't aware of how to do random correctly.

I don't see this being a result of Microsoft's malevolence, merely a programmer's ignorance. I doubt that Microsoft would do something that would be caught while fighting anti-trust charges.

It might be an "oops" from a single programmer, but I thought a high-profile site like this would at least go through some basic code review. The bug isn't that subtle, either.

For the ui JavaScript? Certainly none of the places I've worked subject that to real code review.

I love the (distressingly common) attitude that the only code exempt from review is the layer that interacts with the user, which can completely obscure or invalidate the correct functioning of all the other layers.

Why doesn't your javascript code go through code review?

I'm not debating that it should (certainly if it's javascript that I'm writing), I've just literally never seen that happen.

this was explained in the techcrunch comments at the time, wasn't it? also here - http://news.ycombinator.com/item?id=1145073

Considering IE mostly shows up in the 5th position according to this article, who cares? Does it really matter? Mountain out of a mole hill.

Doesn't that depend on which positions are likely to be chosen by people? On what basis should we assume the 5th position is not favored?

Yeah, I figured someone would bring that up. First, I could ask the reverse question asking why you assume the 5th position is favored. Next, the requirements didn't dictate a study on the positions. Finally, it avoids the real question: Does it really matter? The placement is random (you can't predict the order reliably before you launch the page), and the options are present.

Does it really matter? No, even with understanding your point, and even thinking that it's an interesting thought that I'm sure we'll see answered.

First, I could ask the reverse question asking why you assume the 5th position is favored.

Does questioning someone's assumption necessarily imply that one is making the converse assumption?

Does it really matter?

I think that's an open question. Note that your definition of randomness is a bit off. The linked article shows that one can predict the occupant of the 5th position greater than 1/5th of the time.

Reply on news.ycombinator.com