So You Think You Can Code, Eh?

We’re launching a contest, open to all Programming enthusiasts! If you love to code and solve problems, try solving this one from the Kijiji Canada Development Team:

Armed with the JVM language of your choice, your mission is to figure out which Toronto street gives the city the most revenue from parking tickets.
This challenge is based on data published by the City of Toronto on its open data portal. Detailed instructions can be found at https://github.com/kijiji-ca/2013-coding-contest. This contest is open until July 31st, 2013 at 11:59pm

The winners will receive not only bragging rights, but some pretty sweet prizes:

  • 1st Prize – 15–inch MacBook Pro with Retina display
  • 2nd Prize – 32GB iPad with Retina display
  • 3rd Prize – 16GB iPad mini

Submissions will be reviewed by our team and scored based on the following criteria:

  • Readability
  • Efficiency (bonus points for parallel processing)
  • Creativity

Kijiji is constantly recruiting talented developers in Toronto. If you think that a fast paced, fun, quirky company with a startup culture would be a good fit for you, seize the opportunity when you have the attention of the developers, and attach your resume to your email submission. This is not mandatory, and will have no effect on the contest results – but could have a very dramatic one on your career. Kijiji is a top 10 website in Canada, and a property of eBay, Inc., so the sky is the limit on advancement opportunities for those with talent and drive.

79 comments on “So You Think You Can Code, Eh?

  1. I’m curious as to why you would want to use a jvm language for this? The fastest way to get the solution to this would be to leverage a database. Import the data into a table with indexes and then run a query to get the results. It would require the least amount of machine resources aswell.

    • These kijiji people are morons. I wouldnt waste a second of my time coding for this bullshit, let alone for a MAC, fuck mac.

    • Hi Kevin,
      For a real life situation you’re totally right that this particular problem can be solved without much programming. One may also argue that the easiest way would be a shell script. The constraints exist because this contest is designed to stimulate pure programming skills.

    • Even when using a database, there are still considerations which do not absolutely guarantee acceptable speed or space characteristics. I’m sure people can think of reasons why. The constraint also makes the contest easier to administer since a database installation (I am sure everyone will want their own custom db choice and settings) is unnecessary.

  2. Java solutions only? Why not open it to creative solutions with JavaScript/PHP? I’d totally be into that.

  3. This JVM requirement is a humongous fail. You’re forcing talented developers to ignore rich environments like node.js or python and cloud resources like Heroku and Amazon AWS, to instead waste their time on Maven and Java? How am I supposed to develop something that fits in this decade using Java?

  4. Are you looking for the top X streets in revenue, or are you actually looking for *all* streets (in the dataset) sorted high to low which will also give which streets provide the least revenue (>0)?

    • I guess if the returned dataset includes:

      assertThat(streets.get(“KING”), closeTo(2570710));
      assertThat(streets.get(“ST CLAIR”), closeTo(1871510));
      assertThat(streets.get(streets.firstKey()), closeTo(3781095));

      it satisfies the criteria.

  5. I think alot of people are missing a point its about writting an efficient algorithm derp and who cares about the language, developers at this level are language agnostic by now.

    • Hey Mike, looks like we got a friendly competition going on now haha!

      And yeah I fully agree, all languages are useful in their own way, and what better way to learn an unfamiliar one than a contest? Sure Java isn’t as hip as node or go, but it still has it’s utility in many modern systems.

  6. Something seems fishy… I just want to verify:

    This JUnit test is going to find the first street alphabetically, not the street with the most revenue (though that is a very high number so I don’t think this is your intention)
    assertThat(streets.get(streets.firstKey()), closeTo(3781095));

    You want a SortedMap where the street name is the key, and the fines are the value.

    Fromt he API: “The map is ordered according to the natural ordering of its keys”. Even with a custom Comparator, you can only sort on the key, there’s no way to sort on the value.

    The way you’ve set up the test and the SortedMap, your results will be sorted alphabetically, not by aggregate fine amount.

    Cheers,
    Kevin

    • I noticed this as well. But with a tweak you can have it ordered by the values and still manage to lookup by street name.

      • :) It’s an interface, one can make it work any way they wish. There’s a reason though, why the pedal second from the right stops every car. You change the expected behaviour and PEOLE DIE! (a little over dramatic?)

        • Heh, maybe just a little. I like to think that I’m giving a car wheels, and not messing with the pedals. ;) In this form the data structure is doing what it is meant to be doing. (Finding the most lucrative street)

          To heck with the lives lost!

    • Just one comment at this point: this is no accident. More to come after the contest is closed ;o)

      • Fair enough… But it will need to break the spec for SortedMap. It can’t pass all 3 assertions and conform to:

        “A Map that further provides a total ordering on its keys. The map is ordered according to the natural ordering of its keys, or by a Comparator…” (yes I see the Comparator there, but…)

        “firstKey()

        Returns the first (lowest) key currently in this map.” (note: “lowest”).

        The streets.get(“KING”) means the street name needs to be the key, the key needs to be sorted and “firstKey” needs to return the value for the “lowest” key (which will not be the street you are looking for).

        I may be missing something there. But methinks one will need to break one or more parts of the spec.

        Thanks for the response,
        Kevin

        P.S. can I get the MacBook now? It’s hard to test how well concurrency for 4 cores performs on my 2 core processor. ;)

        • P.P.S.: I fully reserve the right to be partially or entirely not correct in my statements above. And all mocking will be deserved, but handled poorly.

          • FYI Kevin, I don’t know if you intended to globally tip off everyone doing this contest… but if so. Thanks for the help!

          • Glad to help. :) Though, whoever wins will have to do the other 99% on their own ;)

        • Not all objects have a natural sorting order, thus “lowest” as it is written in the api/spec is subjective. It must be referring to as it relates to the compare(o1, o2) function, thus can be defined and/or altered. I understand how this can be done free of sin (not breaking an interface contract).

          Thanks again for your response..
          Kevin

          • I think you’re right. I took a look at the spec, I think “lowest” means “lowest according to the implementation-defined sorting order.”

            “The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time” taking the “or” into consideration, the spec wouldn’t preclude a descending natural sort, or a non-natural sort even for types that *do* have a natural sorting order. I think even using a comparator that returns completely random results would be technically compliant.

        • I wondering how long it takes you to do the processing to get the keyvalue pair list with one core ?

          • That’s 2 cores thank you very much ;) I don’t expect I’ll get it much faster than it is now. Sharing that info can only motivate others, or give them cause to laugh at me behind my back ;)

          • Mine runs takes 10 minutes to run ? =P

  7. So to match with the test cases, if there’s hypothetically a “KING ST” “KING AVE” and “KING COURT” then they all count as “KING”?

    • Yes, you need to drop all the suffixes.

      • Hey is it possible for you guys to change the interface and allow a string to a file path and or a input stream to come through? or is this really strict ?

      • What about double suffix for example ‘WYNFORD DR’ vs ‘WYNFORD HEIGHTS CRES.’? Do we merge them into single ‘WYNFORD’?

        • No, in that case you should get 2 streets WYNFORD and WYNFORD HEIGHTS. The suffix is only for the type of street as explained in the test case and there can be only one per address.

          • It’d be better if all of us could agree on the list of possible street types. Because, according to wikipedia HEIGHTS, GARDENS, VIEW, HILL, etc.; they are all street types.

          • Ok, that’s a good point. We assumed there couldn’t be more than one suffix per street. Also, to be honest we may have overlooked the type of suffix you mention. But anyway don’t worry, we will not perform any verification on ambiguous street names. So feel free to parse them however you find is easier. Thanks

          • Thanks for the reply. Just to be clear; using different sets for street suffixes would result in different number of streets in the final SortedMap and the difference may not be very small !!

          • This is fine. We will not verify the number of entries in the map either. Differences in parsing, other than suffix parsing, could result in very different map sizes, in particular depending on the way malformed addresses are treated or ignored. As a general rule, don’t worry about map entries with a very low amount of money.

  8. To echo the other sentiments, the bit with the SortedMap and its ordering was a fun little thing to throw in. Not too hard to solve, but cool.

  9. can we form a team atleast of 2 members and submit? if we win, can we get respective prizes or just 1

    • The contest is designed for individual participation. If you get help from someone you will still need to submit under one name. Thank you.

  10. I wonder would anyone be confident enough to brag about their runtimes? I’m itching to know if I’ve got a good time or if everyone else is miles ahead of me

    • 16 seconds non optimized with optimizations I can get it down to like probably 4 seconds, but I have bigger problems like I am not using the input stream. and I have to find a way around that and that could kill my time and make it take 1 minute. I am not sure where I rank in this but if I don’t find away around the input stream then ill just forfeit.

    • Duration of computation = 1516 ms

      It’s almost entirely I/O bound now, Just reading the file takes around 1300ms. I’ve taken to writing optimized versions of I/O classes for my use-case to get extra performance, even though it’s probably a bad idea :P

      • hey, Jordan, how many CPU cores do you use to get 1516 ms result?

        • I used four cores on a Phenom II X4 955 BE, using the JRE settings specified in the rules.

          However I just realized that even though what I had satisfied the test case, it was unacceptably inaccurate in other cases. My current best is around 3750ms.

          That said, we all have different hardware and I/O bottlenecks can really kill your speed, so I don’t know if we can really compare times without running each other’s algorithms on our own computers. :P

    • Now that it’s over, here’s my times on a 2011 iMac and 2012 MacBook Air.

      iMac (Core i7 @ 2.93 GHz)

      Duration of computation = 1424 ms
      Duration of computation = 1313 ms
      Duration of computation = 1485 ms
      Duration of computation = 1364 ms

      MacBook AIr (Core i5 @ 1.7 GHz)

      Duration of computation = 2453 ms
      Duration of computation = 2509 ms
      Duration of computation = 2438 ms
      Duration of computation = 2152 ms

      • It’s really hard to compare times… I have a Windows 7 64bit, with Core i7 @ 3.2 GHz (2011 processor) and fast RAM and I get around 760 ms, on my notebook (Win 7 64 bit, Core i5, slower RAM and disk) I have to drastically reduce the level of concurrency and can get around 3500 ms… it’s really impossible to compare execution times on different operating systems and hardware, especially on such CPU-intensive tasks… let’s just wait and see :-)

        Also, I’m pretty sure that – despite how hard I’ve worked to take the execution time down – that’s just one part of the story, and not quite the most important :-)

        • Wow, 760ms! You’re right, it’s hard to compare numbers and there is more to it than just straight runtime numbers. :)

      • I’m more curious about another thing, rather than execution times… which language did you use? Plain Java or what?

    • On my notebook with Win7 64, Core i5 @ 2.27GHz = ~4 seconds.

    • Win7 64, Core i7 3.4Ghz
      Duration of computation = 343 ms

    • ~500-550ms on i7 3rd gen mobile@2.6GHz, 2 cores with HT.

    • These are all great times. ~405-550ms on Linux Core i7 3.4GHz.

  11. Can I submit updated code again ?

    • Yes you can. Note that to keep things fair for all participants, we will only consider your latest submission before the deadline, any previous submissions will not be included in the runnings.

  12. I’m new to using Mavin and I’m not sure how I can ensure that my solution will work when you guys are testing it (learning about the pom.xml now).

    How will you be testing our code?

  13. Can you give any more details on the execution platform? Those co-incidentally developing in a similar environment get better benchmarking.
    (a) JVM implementation (64-bit or 32-bit, vendor, os)
    (b) HyperThreading CPU?
    (c) L1, L2, L3 cache sizes?

    Btw, was the question about multiple entries answered?

    • Great to see your attention to details. We didn’t include any environment details in the instructions because we don’t want people to focus on environment-specific optimizations. Most people would be penalized for not having access to a similar environment to test their code.

      Also, keep in mind that the contest is open to any JVM language and we will not penalize someone for using a slower language (or for the bootstrapping time required for the chosen language).

      Of course, for a given language, an implementation which is 10 times slower than another is unlikely to be scored better, but a difference of 10 or 20% will not have a significant impact on the scoring. In other words, fine tuning is out of scope for this contest.

      If you find in your code a big potential performance impact depending on the target environment, feel free to mention your assumptions with your submission. You can also provide a way for us to test different configurations of your solution. But again, if the expected difference is less than 20% that’s probably not worth the effort.

  14. Will I get a confirmation after submission? Also, could you post some stats/ranking at the end? like time, loc,test cases etc.

    • Yes, we confirm reception after we receive an e-mail. We will also certainly provide some general feedback and stats after the contest.

      • I emailed an entry an hour ago and just sent a small update. Hopefully they made it. I haven’t received any emails confirming receipt, yet.

      • I emailed an entry an hour ago and just sent a small update. Hopefully they made it. I haven’t received any emails confirming receipt, yet.

  15. Is the deadline 11:59 PM EDT (ie: the time in Toronto)? Or, is it a different time zone?

  16. Itching…

  17. Hi Everyone. Thanks for your participation. We received more than 100 submissions, half of them on the last day. We’re working hard on reviewing them. We’ll provide a quick update tomorrow on this blog and we should be able to publish the results by Wednesday next week. Stay tuned!

    • Looking forward to seeing everyone’s entries now that submissions are closed! Make sure you push your solution to your github fork!

  18. You are in actuality a wonderful site owner. The web page launching tempo is astounding. It seems that you might be carrying out almost any unique secret. Also, The articles are work of genius. you’ve done a wonderful job with this matter!

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Pinterest