Skip to main content
gamedev.net
🔒 Locked

Question about programming tests...

Started by CDProp 17 replies 1.9k views
Original Post
CDProp
CDProp
That is, the sort that you are asked to take by a prospective employer so that they can evaluate you. I've taken all sorts of these. Some of them have several questions, some of them have just one challenge. Some of them are timed, some aren't (but they want to know how long it took you to complete it). I just took one, and I'm not going to lie to you, it took me 8.5 hours to complete it. It was a single challenge: given a set of Scrabble tiles, and a Scrabble board that has some words laid down already, find the optimal move, i.e. the move you can make that will score the highest points. It's especially challenging because, as Scrabble players know, you can score extra points if the tiles you lay down help form more than one new word on the game board. I don't know, is that normal? The problem was exacerbated by the fact that the dictionary they provided (a global array of char*) wasn't perfectly alphabetized -- it was close, but there were a few mistakes. In any case, I wrote a binary search function for quick lookups into the dictionary, since I would have to do those often, but since there were some mistakes in the dictionary alphabetization, and I wasn't clear on whether I was allowed to modify the dictionary in-code, I had to create an in-place quicksort that I would run at the very beginning. In any case, it was really difficult to track down this bug in the first place, because at first sight, the dictionary looked sorted perfectly and I didn't think to double-check it. Edit: I also wanted to mention that the algorithm that I settled on takes maybe 1/8th of a second to complete, i.e. fast enough that it can do several per second, but slow enough to cause a noticeable frame rate hitch if not done asynchronously. I can probably get a more accurate time, as I'm just basing this off the fact that it took about 0.5 seconds to complete 4 puzzles. I'm just curious what they're going to think about me taking 8.5 hours to write an algorithm that solves the above puzzle in 0.125 seconds >_< Probably not good, eh? [Edited by - CDProp on February 25, 2009 1:19:57 AM]
PouyaCat
PouyaCat
Well, they'll probably think that you'll spend a lot of time to fix something properly and efficiently. When they give you a task, they can expect perfection. {That would be my analysis}

As a different example: I would probably have written code to solve your problem in half an hour tops. On the other hand, I wouldn't be surprised if it would take my algorithm well over an hour to complete; I like brute-force and recursion. *laughs* Think about what they'd think about /that/ ;)
d000hg
d000hg
It depends if it's a "do you know C++" test or a "do you know how to solve problems" test. You could write a very quick brute force solution first... in fact this is normally needed to test correctness of your clever algorithm. And then try something better, or write why brute-force is bad and the kind of things you might try with more time.

Asking them what they're looking for is always wise though. Maybe they only want to hire people with lots of algorithm skills... dynamic programming, graph theory, etc.
AndreTheGiant
AndreTheGiant
I dont think its uncommon for them to give you a task that is extremely difficult, and they dont necessarily expect you to solve it. They just want to get a glimpse of you thinking process. So I hope you showed all the steps you took.

I remember doing one interview where the company gave me a 'problem' to solve, and it turned out that the 'problem' was the company's entire reason for existance. It was a problem that 6 to 8 people had been working on for 3 years, so they obviously didnt expect me to solve it in an hour.
BeanDog
BeanDog
I don't like those kinds of tests that are far removed from the actual work you're actually going to do (I'm assuming you're not writing TopCoder solutions at this job).

I had to hire a programmer several months back, and the most difficult part of the job technically was going to be writing very complex SQL queries. So I made up a schema that was dumbed down from our actual production schema, then wrote up a test of ten queries to write against it, in increasing order of complexity.

It was obvious when someone was BSing a claim of "8 years" of SQL experience on their resume, when it took them four hours to (poorly/incorrectly) complete eight of the ten problems. Instead, I ended up hiring a fresh graduate who finished most of them in a couple minutes, then asked if he could use Google/Wikipedia.

That gave me a much better idea of the person I'm going to hire than a Scrabble puzzle or a "you're a frog in a blender that's going to turn on in 30 seconds" mind game.
ToohrVyk
ToohrVyk
My three favorite questions I ask at interviews are,

  1. Two-second question: implement the factorial function recursively. If you spend more than a minute thinking about this, bye-bye.

  2. Practical question: implement heap sort.

  3. Design question: you have a model-view-controller design for a website. You want all users to have different e-mail addresses to prevent people from mistakenly registering twice. Where (model, view, controller) do you write that check?
Blog — Facebook
AndreTheGiant
AndreTheGiant
Quote:
Original post by ToohrVyk
My three favorite questions I ask at interviews are,

  1. Two-second question: implement the factorial function recursively. If you spend more than a minute thinking about this, bye-bye.

  2. Practical question: implement heap sort.

  3. Design question: you have a model-view-controller design for a website. You want all users to have different e-mail addresses to prevent people from mistakenly registering twice. Where (model, view, controller) do you write that check?


Whats the answer to number 3? I would say all 3...
BeanDog
BeanDog
Model.

ToohrVyk: I very rarely implement sorting routines myself. Would you allow Wikipedia access so I can remind myself of the algorithm?

[edit] Read your linked blog entry, nevermind.
AndreTheGiant
AndreTheGiant
I was taught that the proper way to enforce a rule involves all 3 parts of the MVC.

You need to do it in the model, eg in the database you would have a UNIQUE property on the email address field, or whatever the detailed requirements are.

You need to enforce it in the controller, meaning making a call to the database to see if the email address already exists, before attempting to insert it. If its already there, you can do some custom error handling such as generating a message asking if they forgot their password.

You need to do it in the view as well, providing instructions that email addresses should be unique, and support for message boxes to pop up (or whatever) informing users when an email address is already in use.

Where possible, its smart to enforce rules in the view (interface), for eg using &#106avascript. For things like entering dates, you can use &#106avascript to check that its a valid date, for speed and convienience. However you still need to enforce the same rule in the controller, because &#106avascript can be circumvented. And you enforce it in the database as well, because databases are happiest when they know everything about the data they're supposed to hold.
BeanDog
BeanDog
Your view (web page) makes a call to the controller (business logic code on the server) saying the user has directed it to insert a new user. The controller performs any manipulation of the data that may be required, and then sends that data to the model (code which makes queries against the database) asking it to insert it into the database. The model then checks that all the data is valid, including checking whether the email address is duplicated. It responds to the controller that it can't insert, and why. The controller then informs the view layer that it was unable to insert the user, and why.

You're right about validating simple user input stuff in the view if possible, but the question was particularly formulated so that it had to be checked at the server.
curtmax_0
curtmax_0
None of the MVC designs I've seen check in all three places.

I've mostly worked with rails though, and the entire system has a DRY philosophy. Maintaining a check in all three places seems to defeat the purpose of the MVC system.

Question 2 would be the hardest for me. I don't ever write sorts manually. I mostly use STL or boost algorithm functions to do sorting.

I know I covered all kinds of sorts (including heap) in classes, and even did alot of analysis in Algorithms but I couldn't remember how it works for the life of me. About a minute on Wikipedia (not including sample source of course) and I could cook up some quick code though.

The MVC questions seems a bit unfair too (unless it's something to be expected in your business). None of my classes have ever covered it to that extent (I think it may have been briefly mentioned in my UML class).
ToohrVyk
ToohrVyk
The MVC question is somewhat similar to the heap sort question: I don't care what answer you give. I want to know why you chose that answer. If you manage to convince me with sound arguments that you don't need to perform a check anywhere at all, that's good.

My personal take on the subject is that you need a model-level check (both in terms of a database constraint and an integrity check that's able to give a clean diagnosis that you can use to notify the user), and can then choose whether you build a system that outputs model integrity failures back to the user upon submitting the registration form (this can be more or less easy, so sometimes the fastest thing to do is simply to special-case the 'mail is unique' feature instead of going for a complex generic solution: DRY versus KISS), or to actually provide feedback to the user before the form is submitted by checking the mail individually from your view/controler as AJAX while the user is editing.

I would be wary of candidates that equate models with databases, though. [smile]
Blog — Facebook
d000hg
d000hg
You would only hire people who know MVC? Seems kind of narrow, unless it's clear on the job ad.
ToohrVyk
ToohrVyk
Quote:
Original post by d000hg
You would only hire people who know MVC? Seems kind of narrow, unless it's clear on the job ad.
Given the choice between someone who knows MVC and someone who doesn't for a given job, I would prefer the one who knows MVC. Mostly because all of our web-side work uses MVC frameworks (such as the Zend Framework) and I'd rather work with someone who knows what that means.

Now, if the candidate does not know MVC, but does show an ability for learning quickly and has some experience in design patterns, I'll be happy to provide a few hours of teaching on the subject. But given the amount of things one has to learn when coming in on an existing project, I'd rather not spend too much time teaching things that could have been learned before joining.

On a job that doesn't involve MVC, I wouldn't really bother (although knowledge of MVC would be a bonus point anyway).
Blog — Facebook
MrCoolsman
MrCoolsman
Quote:
Original post by BeanDog
I don't like those kinds of tests that are far removed from the actual work you're actually going to do (I'm assuming you're not writing TopCoder solutions at this job).

I had to hire a programmer several months back, and the most difficult part of the job technically was going to be writing very complex SQL queries. So I made up a schema that was dumbed down from our actual production schema, then wrote up a test of ten queries to write against it, in increasing order of complexity.

It was obvious when someone was BSing a claim of "8 years" of SQL experience on their resume, when it took them four hours to (poorly/incorrectly) complete eight of the ten problems. Instead, I ended up hiring a fresh graduate who finished most of them in a couple minutes, then asked if he could use Google/Wikipedia.

That gave me a much better idea of the person I'm going to hire than a Scrabble puzzle or a "you're a frog in a blender that's going to turn on in 30 seconds" mind game.


Just for curiosity's sake, what kinds of questions did you ask?
BeanDog
BeanDog
Quote:
Original post by MrCoolsman
Just for curiosity's sake, what kinds of questions did you ask?

Here's a simple schema. Tell me why it's not in the third normal form (Wikipedia allowed). Now tell me why I might decide to structure my database that way anyway.

Here's a person table and a company table, where person has a CompanyId. Get me a list of all the companies with the number of people they have. (Check to make sure they used an outer join so they get all the empty companies). What indexes should the database have to perform your query quickly?

Here's a ledger table, where each row has a positive or negative Amount and a PersonId. Get me the balances (total Amounts) for all the people in Company #3. (Again, check to make sure they get $0 balances for people with no ledger entries). What indexes should the database have to perform your query quickly?

Now get me a list of all the companies with the grand total of all their peoples' balances. Give me one using only joins, and one that uses subqueries. What indexes should the database have to perform your queries quickly? What are the differences in performance characteristics between the subquery version vs. the join version? (Check to make sure they mention that when paging the results, subqueries may be faster since they're only calculated for the rows actually returned rather than for all rows as in the case of the pure join query; the pure join query will generally be faster in MySQL, though).

And so on, making sure they can use UNION, LEFT JOIN and RIGHT JOIN, subqueries, GROUP BY, etc.

I saw all kinds of evil on the results from this test. People GROUPing by the company table's friggin name column instead of its ID, and then not even saying they should have an index on that field. I mean, stuff that keeps me up at night.
Dmytry
Dmytry
Quote:
Original post by ToohrVyk

  • Practical question: implement heap sort.

    • I'd also ask what exactly is heap sort. I'm sure I did learn the algorithm but I cannot quite remember how heap works (always used std::priority_queue for it).
    I'm going to see how long it takes for me to implement heap.

    I implemented a thing conceptually very similar to quicksort as recently as a month ago, for building kd-tree for my game. Knowledge of sorting algorithms really does pay off, even if you never need to implement sorting itself.
    Extrarius
    Extrarius
    After I submitted my resume to my soon-to-be-employer, they sent me back a skill assessment test that included 1 question that had to be answered and another 7 questions from which I must select and answer 2. I spent 2 days writing and refining my answers, and my final response consisted of 8 pages total, which included the questions (approx 1 page total), my responses in english to each (about 1.5 pages each, total 4.5 pages), and C++ code for one of the questiosn that mentioned code might help explain the response (2 pages). The english text was spaced at 110% with a blank line between paragraphs, and the code was spaced at 110% with a blank line between logical lines of code (to make word-wrapped lines easier to read).
    I could have had a much shorter, less detailed response, but the questions were interesting and answering them allowed me to explore my own knowledge. I took 2 days partly because that is approximately how long it took them to respond to me after receiving my resume. I suppose I should clarify that by 2 days, I mean around ~12 hours of my spare time was spent intentionally thinking about and working on my answers, but I also had it in the back of my mind while working, which I think also improves the result.

    In the instructions to the questions, they specifically mentioned that the point was to figure out your thought process and that explaining your thoughts was just as valid as providing an actual answer. I answered all the questions I selected, but did so in a way that revealed my though process to some degree. I didn't just write a stream of consciousness as it would be very difficult to read, but I did include a few tangents and explained the weaknesses of my solution (and in one case, why those weaknesses where inherent in the assumptions made by the question).

    [Edited by - Extrarius on March 4, 2009 12:03:38 PM]
    "Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

    Topic Locked

    This topic has been locked by a moderator. New replies are not allowed.

    Sign in to reply to this topic.