Programming test for Job interview

D.P. said:
I guess they liked my programming, was offered an interview.:D
Click to expand...

Well done :) Congrats etc.

Had a similar one recently, was given a database with some sample data and a problem to solve. They didn't give me enough time, had 4 hours and that was really just enough time to explore the problem and beta test some approaches.

Have an interview coming up for one of the HFT companies soon, will be interesteing to see what they throw at me.
 
dowie said:
Tis likely easy to attempt to make people feel silly if you're the one controlling the rules of the make believe game.
Click to expand...

That and they've made the assumption that the contestant has made the assumption that they're out at sea. They could be imagining themselves in a non-port town in which case they could still go to a port to get food.
 
Last edited:
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.
 
3 days? Bloody hell, I'd send them the code and a nice fat invoice at the end of it!

Then again, I did interview for an internship at Microsoft. The question from the US interviewer was "Why are manhole covers round". I told him quite politely that manhole covers in the UK are not round and work perfectly well thanks. They didn't call back.

PS. I was secretly thinking that it was because SOME US workers are too dense to get a rectangular manhole cover back into the manhole the right way round.
 
D.P. said:
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.
Click to expand...

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?
 
A 3 day programming test?

I think they're trying to get some free work out of you tbh mate :)
D.P. said:
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.
Click to expand...
Did they provide a dictionary?

Sounds like a fun test. What programming languages could you use?
 
Last edited:
[TW]Fox;19489001 said:
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.
Click to expand...

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.
 
Stretch said:
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?
Click to expand...

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.
 
Tokenbrit said:
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?
Click to expand...

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.
 
You must log in or register to reply here.
Back
Top Bottom