Programming test for Job interview

[D.P.]

I have been firing off job applications for interesting positions in the US for the last 2 weeks without expecting any result. A small company (spin-off of a university research lab) quickly got back to be but I must do a programming test before being invited for an interview.

It should take 3 days supposedly and was described as very hard.

Now, I can program, maybe even quit well, but i am not a guru. Actually, the worst problem wont even be producing code, but I believe I have to develop some complex algorithm first and may need a lot of maths. This, I don't think I am so capable of. The CEO I was chatting to was a professor of maths at Oxford, computer science at Standford for starters. I'm just not on that level

Bricking it waiting for the email.

I know I should just consider it experience but I hate to embarrass myself or loose out on a good opportunity.

Anyone else had to do similar things?

 

[D.P.]

yeah, I have done simple tests before, the biggest took about an hour and I had to implement a vision algorithm after reading the research paper.

Seems to be quite a strict time restriction. 3 Days is a bit awkward to block out, luckily I am not working full time.

 

[D.P.]

If it's out of your league, get some Uzbekistanian from rentacoder.com to do it for a nominal fee for you

The thing is it is not a software engineering challenge, but a challenge in algorithm design, maths and optimization, perhaps machine learning as well.

Managed to delay things until sunday so now I am frantically going back through my undergrad notes and re-learning everything I forgot.

 

[D.P.]

Are you sure he's just not making you do the work that he should be doing for free as an "interview".

A 3 day test seems like full blown overkill to me. I dunno.

The thought crossed my mind but no. It is a small company that exists by using the latest in computer science and artificial intelligence research (many of the management have part time positions within universities). There is no problem I can solve in 3 days that would be useful to them!


Being a small company they have a lot of risk in hiring new people and only want competent people, especially if they have to organize me a US work visa.

 

[D.P.]

So they are essentially asking you to work for free for 3 days? No thanks.

No, they want me to do a difficult test before they spend significant money investing in me.

 

[D.P.]

Its impossible to write a regex for email, the official email address spec allows email addresses to have nested structures such as comments...

This is why you should never attempt to parse html, xml or anything with a recursive structure with regex.

If you want the job that bad, just get a cs phd =P Hell you could become a quant.

I have a PhD in CS, well robotics actually but from the CS department. I thought about training to be a Quant but it isn't really for me.

 

[D.P.]

Are they allowing you research time in that 3 days? Thats probably why its so long. No matter how smart someone is, you can never remember everything. If its something remotely complex, its probably going to require a little bit of research before hand.

Yes I can do research. I will have 3 days to do whatever I can to solve the problem. You are probably right that it is 3 days because they may ask me to implement some obscure algorithm that I will need to read the research paper of first.

 

[D.P.]

For comedic value, if you receive the spec and realise it's just WAAAAYYYY out of your league then just send a drawing of a penis.

Promise me this.

As much as I would want to I need to keep positive relations with any potential contacts. You never know what might happen, e.g. maybe they find out I am actually a poor programmer but they then realize my other attributes are important enough to them that they give me an offer any way -remote but plausible..

 

[D.P.]

I just spent the best part of a week filling in an application form with competency questions.

It's not going to be 72hours of solid work, is it? It's a 3 day project which in the grand scheme of things is not a lot. If you cannot write off 3 days as a speculation on the position then you are likely not right for it in the first place, are you?

Beggars cannot be choosers.

I'm not complaining and I am fully prepared to send 3 days on the problem. Just I am quite busy at the moment and stressed out organizing other things in my life. I was just a bit surprised at a 3 day programming test.

 

[D.P.]

The test will be an example of the type of thing they undertake on a regular basis. It's entirely possible that they're not looking for a solution (although of course that would be great), but rather they want you to demonstrate a systematic approach to the problem.

Several friends and former colleagues have moved onto think tanks, quant jobs, high frequency trading etc. and in each of the interviews they had before the job, they were given hard problems to look at. Only in very few cases did they solve the problem -- they usually got the job because they looked down several intelligent avenues of thought. This is especially important in smaller companies where you're likely to be solving problems with a small group of people. To this end, you should make sure you keep an eye of your failed attempts and let the interviewer know how what you learned from those failures. Also have in mind how you would continue to attack the problem, if you were given more time.

Good luck!

Thank you for the advice, I hadn't directly thought about that. It could well be they merely want to analyse my approach rather than make sure I solve the problem.

 

[D.P.]

Semantics, you're doing 3 days of work for free during which time you could be earning money.

No. This will be a test that they have sent off to dozens of applicants before.

 

[D.P.]

Really?

They are getting 'free work'?

Work they will have to dissect anyway if they wished to use it as it's from an unproven source. In which time they could have coded it themselves to a known standard using existing code snippets.

3 days is nothing. most people spend more time in the pub/clubs in a week. He is looking for a job. He won't find a properly decent position if he has this attitude towards being asked to spend 3 days illustrating what he is made of to a company based in the US.

I don't have a bad attitude to working 3 days on a problem. I have just spent 4 years working on a problem! The fact is in 7 days I am flying off to the US and wont have any computer access for a month and I have a lot of stuff to sort out here.

 

[D.P.]

You seem to be missing the point, that's irrelevant.

Do you expect to get for an interview?

 

[D.P.]

Just completed the programming test. In some sense it was easier than I expected but the test was a little open so i am sure they are more interested in the methods used than the fact that I have a solution.

For those interested, if you know the game boogle, the problem was to find which boogle board (in this case a 5x5 grid of letters) produces the best score (longer words score more points). Being that there are 26^25 different possibilities, exhaustive search was out of the question. One of the key components was a very fast method to check a word is in the dictionary (and a string is a substring of a word int he dictionary)- for this I used a Trie tree structure. I don't want to give details on my search method but it involved combining global and local search behaviors with some heuristics.

I had the base version in a day, spent the next day optimizing/improving, the 3rd day tweaking/cleaning/documenting code, I then ran the search algorithm for a few hours and found a board with ~2500 words and over 10K points.

 

[D.P.]

I guess they liked my programming, was offered an interview.

 

[D.P.]

If they are a US company how to they plan to get you to work for them? They must surely show that there is a shortage of Americans with your skillset for you to get the right Visa?

And one thing there isn't a shortage of in America is people who can code.

Two routes, an H1B visa which doesn't at all matter about other americans and their skills, or a ELB-A greencard which requires a PhD and labour partition claiming they cannot find suitable american candidates. The latter is feasible since I have a PhD and the company does highly specialised development. They are not just a software company.

 

[D.P.]

A 3 day programming test?

I think they're trying to get some free work out of you tbh mate

Did they provide a dictionary?

Sounds like a fun test. What programming languages could you use?

Well, there are solutions to the problem all over the web so a waste of free work

They provided a dictionary but I downloaded a scrabble dictionary that has more words. I used java for quick development but C would have been best for speed reasons.

 

[D.P.]

H1B visa most likely.

So will you be West Coasting if you get this job

It would be west coast but not a major conurbation.

 

[D.P.]

Can you expand a bit on this?

I can think of a couple of fast algorithms to evaluate what score a particular "realization" of the board is.

Trying to find the best possible score however seems quite hard.

The only thing I can really think of doing is starting from an initial realization then keep making "best possible" incremental changes until the board reaches a local optimum.

Calculating new scores from incremental changes should be fairly cheap.

Then take plenty of initial realizations to try and span the "board space" and select the best local optimum you know as a global optimum.

Inside this method though there is a parameter, how many one letter changes to the board to allow in an "incremental step", more letters probably equals better local optimums but at a bigger computational cost.

I guess the best parameter depends on the distribution of length of words in the dictionary.

You could also try and tree the incremental changes, taking the best "n" changes and progressing all of them. Again not sure how to select this parameter, maybe just take all increments which improve the score?

I'm not sure how well this would work but I am struggling to think of anything better?

You are thinking along the right right lines. You can make small changes that you can keep when they make an improvement, but you need to get out of local optimum by allowing changes that are not necessarily optimal. There are various approaches possible for this. there are a few websites with solutions.