MagicalThinking.

So, creation of a secret santa program. A simple task you might think. Well, it might well be! Indeed I believe there is an entire application in timetable management and scheduling, which if I was truly aware of, would make this task trivial, or at least tractable!

As it stands, I entered it blindly, produced a naive solution, got burnt, thought about it some more, and got to grips with some really interesting problems. I’ve ended up with a BETTER solution but it still has some problems. Let us share my investigation.

First, the problem, in it’s entirety. A set of X friends (s.t. X E AllFriends) get together every year and have a lovely meal at christmas. If that wasn’t enough loveliness, they also get each other gifts every year! Wonderful! However, things are not as lovely as they might seem. Within X = [x1,x2,x3,...,xn] there lies certain people who shouldn’t really get each other presents. For example x13 and x72 have been dating for years and x20 through x77 live together in some sort of crazy commune! They are getting each other gifts anyway so what the hell is the point of them getting gifts again! Then we come to the actual exchange, we postulate that it is “boring” if xi gets xi a gift, and equally “boring” if xi gets xj a gift and xj gets xi a gift. Fuck that shit.

So, the contraints: * certain people can’t get presents from others * 2 people must not directly give each other a gift * a person can’t give themselves a gift.

The first method that came to mind was the “picking names out of a bag” method. We’ll call that baseline. In that scenario you’d pick a name, if it was invalid for you, you replaced it in the bag, try again. Intuition states that the first person to have a dip would be the person with the most constraints, i.e. with the most names in the bag they can’t have, if you did it any other way it would be far too likely that the last person would end up with no valid names in the bag. We’ll see why intuition is a little fucked up in a moment.

So a solution: create a set of available people, for each person a set of invalid people and finally, hold a set of people already assigned a santa. Pick a person (a santa) with the MOST constraints (i.e. the person who has issue with getting gifts from the most people) and assign them a person to give a gift to (a santee) at random. Now, make the santa an invalid gift giving choice for that selected santee. Do this repeatedly and you’ll either fuck up and end up with 1 person who can’t be assigned, or you’ll have a good selection. Simple, brute force and it WILL break. But so will the baseline solution, and this is easier to run many many times. But if you run this enough you’ll get a matching of people which fits your construct. Good enough right?

FALSE

I’ll explain why when I’ve prettied the data.

About 6 weeks ago, I applied for a Research Scientist role at Google Boston. Eventually I was interviewing for a Software Engineer role, given the way google work internally, I found this sort of role was definitely what I wanted, titles aside. I had 1 non-technical interview, 3 technical interviews and eventually was rejected for the role. The interview process made me revisit some basics of computer science and the preparation has helped me make some key decisions like: “the fuck do I actually want to do”.

Overall I’d say the experience was incredibly useful, the preparation for the non technical questions provoked some real soul searching and both preparation for and answering the technical questions was fun and engaging. Unfortunately the conclusion to the experience has left me confused as very little information is given as to what actually went wrong. Indeed nothing may have gone wrong… But I get ahead of myself, let us start at the beginning

I had already gone through the act of applying to a job at google through their online form once before. It isn’t a very good system. Firstly there are separate job search engines per country with no method of saying “yes anywhere really, just show me the cool jobs”. The google UK jobs site was in a completely different location to the US jobs site and there was no way to combine the results. Also their job search results “felt bad”. This isn’t as wishy washy as it sounds, there are reasonable metrics available as to why search results sometimes feel bad, but I’ll save you the over-analysis, just go try it yourself: think of a job you want to do at google, search for it, and see what happens. Also the act of applying to a given job is pretty awful. There is no way to save your details against your google account or anything like that. Every time you apply you are filling out the whole application again. The whole process is very manual, very old web, frankly very not google. It was by far the worst part of an otherwise well managed and thoughtful interview process.

My previous application fell on deaf ears, this one got through! Not entirely sure why, but I was contacted by a nice lady (we’ll call her H) and I started the first step of the process, proving to google I “has one of them there educations”. This seemed to be an issue as H was asking me things like “give me the list of courses you did on your PhD.” Now this doesn’t really make sense as during a PhD, (in an English PhD anyway) one does not do courses, well, not enforced and certainly not graded, I got the impression that they do in the states. Anyway, after some dancing around I got her my Masters grades and a photocopy (read: webcam) of my PhD certificate. Woo. She threw me to the main HR person I was talking to, let’s call her C. C organised a non-technical interview with me 5 days after her first contact. Right. Preparation.

At this point I started to read and prepare. Thanks to Paul I had a heads about about this book called “Programming Interviews Exposed : secrets to landing your next job”. I acquired a copy of this book and went about reading chapter 15, Non-technical questions. I had seen such questions before, I have had interviews before after all and they all use the same ones. But this time around, I actually gave them real thought. I felt like I’ve reached a point in my life where some real decisions need to be made, I’ve finished my PhD, I’m as qualified as I can be (academically) and apparently I’m an “expert in my field”, whatever one of those is. So usually bullshit questions like “What do you want to do?” sounded a lot more like “What do you think is important?”. How DO I like to work?

Why change careers? Now that was a big one. Is academia that important to me? Does it matter as much as it used to. It is still a current question, even now after the interviews I’m still thinking about it. Though I have to say my current decision is “yes, academia is very important to me”. I want to be an academic, I believe I would be willing to leave academia, but I am not going to leave it for arbitrary company or random startup. But google… seeing the work they do, seeing the things they create, reading the papers they write… yes, I’d be willing to leave for google.

So anyway, after all this soul searching… the non-technical interview didn’t really need any of it! Mainly C was trying to figure out what I wanted to do at google, but not in philosophical way, but more in a “no seriously what do you want here because then I can throw you to the right people for the next interview.” We talked about the boston office, we talked about what they do, I realised they do a lot of work on google images there and that confirmed I’d made the right choice in terms of office. So yeah, that went by pretty quickly and a technical interview was booked for 2 weeks after the non-technical interview

...shit…

What the fuck is a data structure?

I kid, my day job though research is actually quite programming heavy. I have to think about data structures and efficient algorithms for “shit tones” of data all the time. But I decided to just hardcore it. I treated the technical interview as an exam, I treated the programming interview book + google interview blogs as the answers. I went through the book 3 or 4 times programming each question in Java, C and python. Though no question was impossibly hard, I’d be lying if I said I found them all trivial. I had to think about some of the recursion stuff, The concurrency stuff though something I deal with daily was quite difficult to do from scratch. In short I’d recommend the procedure, I feel like I’m really on top of my basics now and it has made me much more confident in some of the programming I’ve been doing recently.

I also googled around for google style “puzzle” questions, four light bulbs in a prison on a rickety bridge that needs a candle to cross while looking at a clock with 10 numbers instead of 12. That sort of shit. While revising those I felt a little resentful. I couldn’t help but think that: if a tricksy bullshit weird thinking puzzle question is going to be the thing that decides whether I get a job or not, frankly, I don’t want the job. I appreciate the link between “thinking strangely” and engineering problems. But let us please be honest for one second, solving a puzzle and solving an engineering problem are NOTHING alike. The interview book’s strategy was a good indicator of how different the two kinds of thinking are. “The obvious solution is almost never the right one”. What? Well I’m sorry but a well implemented obvious solution often is EXACTLY the right one, so please fuck off with your puzzles. Revised them anyway of course, lots of good websites for this so just look around. It turned out google’s technical interviews don’t involve any of this horse shit… but I get ahead of myself.

Finally during this two weeks I tried to get a feeling for other people’s experiences. What had other’s been asked was a hard question to answer? Finding this out laid one of my main exam revision techniques dead on arrival, google don’t like you telling other people EXACTLY what you were asked, so yeah, it isn’t really out there. But regardless, how people felt about their application process really made me feel better. Also I gathered together some key correlations of people who failed/succeeded, and why they failed/succeeded (rather, why they THOUGHT they failed/succeeded.) and from this I tried to get a little strategy together. Some points on the strategy included: “windows only” programmers seem to fail royally; asking questions of your own and starting a conversation is good; think out loud while answering questions (well I could try THIS but that might break so I’d give this a go, but if that happened then this then that then RARARAA) is good. So yeah,

Two weeks passed, every evening and weekend was spent doing the above. I have to say that since my PhD started nothing has been as prescribed, as obvious, as formulaic as this. It was hard work, it was perhaps a little tedious at times, but there was a goal, there were clear tasks and I was bashing through them, notably improving at the tasks as I did so. I’m not sure I can explain exactly to what degree a PhD is NOTHING like this, so in a sick way this felt really good.

Anyways, the technical interviews happened next. I had been booked with 2 technical interviews in a row by C’s receptionist (she was called R). On paper this would take 2 hours chatting over google talk, 45 minutes + a gap * 2. Fine. It all kicked off at 19:00 (mid afternoon boston time). My first technical interview went very smoothly. His name was P, and he worked on youtube. We had a really interesting discussion about streaming content and he asked me about my PhD. Then the technical questions themselves. I’m not supposed to give specific details, but I’ll just say one thing: The questions were fair. All of them, not just P’s. They were things I feel that someone who calls themselves a programmer should know, and know to a high enough degree that they can have a little chat about solutions, alternatives, possibilities for extension etc. P’s questions were about arrays… how best to do a thing to them when the arrays were small, large etc. The complexity, the run time costs, the constant time costs. All this sort of stuff. Then he threw one at me about trees, same sort of deal. I should make it clear that this wasn’t just verbal. There was talking over google talk while writing the code to solve the questions in a google docs document. Google. Docs. Writing code in Word. Can you fucking imagine? Slowest coding EVER. Practise this, practise the balls off it. You will be about 1/2 your speed as compared to your favourite editor and it will stress you out. This I promise. So the general flow of this and all the programming questions were that I was asked something, I explained my tactic, I started coding all the while telling them exactly what I was thinking as I went.

Anyway, that went well… the second interview was less smooth on all counts. His name was D. Firstly D’s mic was broken. To address this I ran around the lab trying to find the land line number for the phone in the room I was in. Eventually he found a webcam with a built in mic. This whole faff meant the 20:00 interview started at 20:30. His question was also much more involved than P’s. A problem which felt similar to some computer vision algorithms I have addressed in the past, but also his style was very different from P. He didn’t ask me to code right away, instead we sat down and dissected the problem, literally as though he didn’t have an answer and we were just bashing through a problem on a white board. I was trying to keep the conversation going the whole time but solution took me a while to come up with. I was getting a little bit flustered but all in all I think it went well because of how I explained myself. My final solution was correct and NEAR optimal (I checked after the interview) but was not optimal (the optimal solution was actually very tidy, it was quite pleasing to figure it out later). D asked me to stop coding after I had most of the structure for my solution there and asked me some questions about what I liked and what I could do. I asked him bits and bobs about google boston, about google images specifically and what the guys in boston did towards that. Though not as good as it could have gone, I still felt good about the outcome. Basically: though my solution wasn’t the best it could have been, I felt I held my own in terms of how I worked with him to solve it and how I explained the solutions I was trying at each stage. I got the feeling D thought it went well also. The interview ended at 22:00. So after 3 hours of telephone interviewing and programming I was done, and in all honesty feeling a little spaced out.

Now, according to my research, google telephone interviews (of which there are usually 2) are often proceeded by an on site interview at which point many, many people fail. Like we’re talking 90% get 2 technical phone interviews and get an on site interview, then 90% of those are told nicely to go away. For me it was different, C contacted me 2 days after the interview and said she needed another technical interview. Now my only thoughts were over how I tackled the D’s question… did I bullshit too much? don’t think so but I think I… (insert 40 minutes of introspective jibber jabber, analysing every WORD I said to him that eventually gets to the conclusion that)... so I don’t think it went ALL that badly

But anyway, tech interview 3. It was 5 days later. I gave myself another weekend of preparation, but finding any more time was quite difficult as the interview turned out to be the last week before I went on holiday which was ALSO the week of a 3 day group activity where we worked on an awesome project, which ALSO involved me giving a hadoop workshop which… left me rather busy. I mean I was working like 12 hour days followed by 3 hours of prep. As you can imagine it was an interestingly stressed time.

But the interview happened. It was at 19:00 on a wednesday. My interviewer was Q. This one started very very strangely. Firstly my interview insisted we talk briefly on the phone instead of google talk. The phone in the room I was in was very crackley and quiet. I heard his questions well enough though, turned out he worked on the search engine algorithm itself and we had a really interesting conversation about search result freshness. I thought some good points were stated and he seemed satisfied. On with the tech interview.

What? You want me to put the phone down? I should communicate with you while I write the document? So I’m coding in the same place that I’m telling you what im thinking?

Fuck. Had not prepared for this, but ok lets go. This was fucking hard. Not his question, his question boiled down to understanding how a particular sort algorithm works, I thought I tackled it correctly. But the format. He asked the question and I wrote a paragraph explaining what I would do to solve this. No feed back… tick tick tick… “yes this is correct, implement this.” I mean wow, I had no idea how much I was relying on the conversation format of the other two interviews. It was so hard to gauge whether he even thought I understood the problem, let alone whether I was approaching it correctly. But I persevered. I started to code, and realised I should be telling him what I’m doing as I go. I tried to do this in the format of comments, but this was SO HARD. Try it yourself: Sit down and start coding, then every second line before writing the code write a comment. But not a normal coding comment “This does this, this does that”. But a “ok now I’m going to try this, but I understand this and this might be a limitation, but let us see where it goes”. The process was breaking my flow CONSTANTLY. What I was totally happy saying out loud, I found near impossible to stitch into the very code I was writing. About half way through my implementation I had had enough, I pleaded with Q to let me talk to him on google talk, I couldn’t give him the best answer under these conditions. He said ok and we got on google talk. We had the rest of the interview and I finished my implementation, allowing for some fringe cases to boot. It was easy once I could talk!

Those were the interviews! Done! This time C did not reply for a week or so. I then got a very polite and positive email which basically said, thanks, but no. Try again later. At this point I was in the middle of my holiday in Germany and on the road our driver and myself had picked up a little stomach bug. No big deal, felt better after 1 night, but still… stomach bug + bad news made for an interesting bout of nightmare filled sleep. I emailed C back thanking her for the opportunity and asking whether there were any specific things she thought I needed to address to be successful in my next application. She said she couldn’t, but said that many candidates have better chances with a second shot as they get more coding experience, more industrial experience. She also said a reasonable grace period for the next try was like… 6 months… 12 months.

This final paragraph was the reason it has taken me so long to write up this experience. I realise the competition is hard, and that rejection could be as much luck of the draw (as compared to other candidates) as anything else. But I still don’t have a good conclusion, I’m not sure how to end this write up. I have reasonable programming experience, and to augment it I have a reasonable portfolio as a junior academic. I worked hard for the interviews, the technical interviews went well, and the parts that went worse I felt I handled effectively. So yeah, basically… I’m not sure what actually went wrong, and I know that is going to bite at me for a while. Friends who are now interviewers for tech companies themselves tell me not to read too much into it, and that getting new people especially in a place like google is pretty competitive. It is a shame though.

On a brighter note, I count this interview process as a really valuable use of my time. I feel my basic technical knowledge has gotten a proper refresh. Also, I feel like I’ve seen a glimpse the hardest a tech interview can get, and I found it quite fun actually! But perhaps most importantly I feel the time spent thinking about what I want has given me enough confidence to make some key decisions about the direction I want to go in the future.

Firstly, yes, I still want to work at google. They do the most exciting applications of what I feel is the most genuinely important technology research in the world. But I feel this experience has lead me to draw the line here in terms of academia vs industry. So secondly, I will not be leaving academia for any other reason but joining Google (or MAYBE Yahoo or Microsoft research, those guys are doing pretty hot stuff too). I’ve applied to some other industry guys, a startup here, a company there… and I might even follow through with the interviews just for completeness. But I will not leave academia for them… I just don’t think it is worth it.

More industrial experience? Why? My research is very application driven, I am a lead developer on an open source computer vision library which I really care about, that will have to do. I code like 60% of time, the other time is spent reading or writing; researchy things that I’d want the company I was with to care about anyway!

I refuse to spend my time doing anything but what I am passionate about. I know I can bring myself to care deeply about a lot of kinds of research, both in my field as well as in related fields. I know, however, that I cannot become passionate about coding for revenue’s own sake. Indeed, this application driven approach to tasks I feel are important was an attitude I made abundantly clear in the interviews, so perhaps that was an issue it itself?

Meh… enough of that. The bottom line: Important research lead work first, money will follow in its wake. I feel Google has this attitude, I don’t feel many other companies do. So post docs and other academic roles for now, and I’ll roll the google dice again in a year or so.

Anyway, back to the research mines :-)

I accidently went to youtube today. I accidently watched a video about religion by an idiot and was driven to much rage. But. Linked off this idiot i found another video and it was not by an idiot. Reasonable questions were framed and an argument was stated and acceptable. So. I felt I had to reply. Someone was being right on the internet. So I sent him a message. The message was long but I feel quite to the point. I am posting the message here, word.

Right let's go. You are the first person to frame the right questions, so here is my attempt at a structured response

Firstly a summary. Your discussions circulates around the notion of an objective truth or an absolute and objective measurement system, and lack there of. The argument goes that if there is no belief in a structured and absolute truth, who is to say one belief system is higher than another, and indeed if that were to be said it has to be also explicitly stated upon which measurement system the statement being made, assuming no absolute truth (i.e. god).

I suppose the reflected notion for the religious individual is that: with a belief in an absolute power (residing in any given holy power of your choosing), it is possible to make decisions on the worth of various belief structures, using the assumed wishes of the absolute power as the measurement system

I hope I got that right.

Now, stepping back for a moment let us discuss survival. Specifically the survival of an idea. An idea survives if it portrays tenants which can survive. More specifically in humans an idea survives if its existence (in some way or another) benefits its carrier, in the idea's case the human brain and the body there in contained. 

So fine, on that level we have ourselves a handy measurement system. This system though not necessarily de jure is provably de facto. If an idea portrays the tenants of survival and ascribes benefits to its participants then it is a "good" idea in the sense that it is propagated and survives. On this level it is obvious that rational and non-rational viewpoints can both have potential benefits. A completely rational agent attains survival benefits in one way, a non-rational agent attains different but similar benefits to survival in another way. Great.

Stepping back from the completely abstract for one moment, let us examine this concept of "worth" more closely. I agree completely that in the general sense it is impossible to call religious belief inferior to non-religious. But, let us consider specific scenarios: Let us pretend that all we cared about as a society was the discussion of the objective measurement, modelling and explanation of the universe. If this were the case then one can make statements such as "belief of an all knowing all seeing creator is an inferior model to the belief in the scientific method of measurement, model construction and model refutation". Now in its isolated form the statement just made is incredibly controversial. But ascribed to the very specific purpose of "modelling and explaining the universe" it is more accurate. By this I mean if you were a gambling man you would be better off (most of the time) going with the scientist rather than the priest when given the task of measuring the state of the universe and from these measurements concocting an explanation.

The reason I am an atheist is that upon further examination of most of the issues i face in life (professional, social, cultural, political, economical etc.) scientific examination and structured thought has payed higher dividends than social and moral dogma extrapolated from ancient tomes.  

So, in the general case, from theists, I don't request an explanation. It would be ludicrous to do so, unless for whatever reason their beliefs were insistent on affecting a specific situation. That is to say, in discussions where I believe rational debate to be more fruitful than dogmatic defaults, I require my opponent to show evidence for their conjecture as I am perfectly willing to do so for mine. In those situations i patiently question faith.

So TLDR: I made a tool using node.js/jsdom/jquery and it is on github, enjoy.

Last week we finished porting a really cool face detector developed by some guys over at oxford’s robots research group back in 2007. To test the face detector I thought it would be cool to be able to detect members of the deparment. As a training set I thought their public profiles from ecs people would be nice to grab. A light amount of investigation seemed to show that the SPARQL endpoint didn’t give easy access to the images. This meant some HTML grep goodness. But this didn’t feel nice, my immediate desire was to do a jQuery dom selection of all the appropriate image tags, then printing all their src tags then… passing the output to curl or something?

It occured to me that it would be much easier to do this via the command line rather than using firebug and some copypasta. But To My Knowledge™ no such tool exists. In the end i decided it would be nice if there was a tool that let me do something like this:

jsgrep -s <jqueryLikeDomSelector> [-a <someAttribute>] [-r] [-nt]

You’d use -r to make the elements get printed recursively (i.e. all their children) and you’d use -nt to not print the actual tags (i.e. just their content). You could then pipe the output to a large chain of lovely unix tools and get what you wanted done much more efficiently than having to grep your way around html tags.

An excuse to use node.js

So jQuery is a js library right? I’d recently heard about v8 and node.js and I thought, “finally, an excuse!”. So i went about implementing my first nodejs program that read off the standard input and spat stuff to the standard out. Here is what i came up with:

var stdin = process.openStdin();
stdin.setEncoding('utf8');

input = ""
stdin.on('data', function (chunk) {
	input += chunk;
});
stdin.on('end', function (chunk) {
	process.stdout.write(input);
});

So everything in nodejs is events right? What this does is take data from the stdin when there is some, i.e. when the data event happens. It concatinates all this output and when the stdin is done (end event) it spits it all out. Lovely! Weird, and probably the wrong way to do this relatively simple thing, but it served to help me understand “what the fuck was going on”™.

Next! let’s load jquery. Right so i just need to do is include jquery right?

require("./jquery.js")

No sorry. jQuery needs the dom. It has the dom attached to its soul. Luckily the nodejs community have been busy little bees. They’ve built this awesome package manager called npm which is a lovely package manager. Now I can install a lovely thing called jsdom. JSdom was purpose built for the task of including jquery into the shit you do, specifically it lets you load html as a DOM and… do DOM things. Sweet! You make all that go as follows:

var jsdom = require('jsdom').jsdom

jsdom.env(input, ['jquery.js'], {
	features:{
		FetchExternalResources   : false, 
		ProcessExternalResources : false,
		MutationEvents           : false,
		QuerySelector            : false
	}
},
function(errors, window) {
	// do shit to your window
})

Well isn’t this nice? You provide that callback function and (once the html is loaded as a dom object) away it goes! You can even tell it to inject jquery into your html for you. Sweet! Right so finally, i want to read command line arguments. Now you can do by including sys and dealing with sys.argv manually. But fuck that noise, someone somewhere must have done a nice args manager. yes, yes they have! It is also on npm. js-opts it is called. Once that’s installed you can do lovely things like:

var options = [
	{ short : 'i'
	, long : 'input'
	, description : 'HTML URL or Filename'
	, value : true
	}
];

// Grab the options
opts.parse(options, true);
var input  = opts.get('input') || false

Awesome! That’s it really, the tool i’ve built should even be installable via npm though not online, and I havn’t tested that. But by doing a node src/jsgrep.js you can feed it html on the pipe, or on the -i, and get some lovely things going on, so here are all the images I use on my blog:

curl -s sinjax.net | node src/jsgrep.js -s img -a src -nt | sort | uniq

outputs:

/graphics/cats.png
/graphics/comments.png
/graphics/date.png
/graphics/globe.png
/graphics/link.png
/style/face

Nice. Clearly using nodejs is a little overkill. Hell using jQuery is a little overkill. But yeah think i learnt something from that voyage so that’s nice :-)

Update: If you have installed nodejs and npm already you can now do a npm install jsgrep to have a play