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.

  • Kevin

    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.

    • stfu

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

    • damienlepage

      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.

    • Matt

      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.

  • http://jasonrundell.com/ Jason Rundell

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

    • http://jasonrundell.com/ Jason Rundell

      I’d drop a fun visual overlay on it with Google maps and CSS.

    • damienlepage

      This choice was made in order for us to easily provide a test case and automate some verifications of the submissions. It’s not restricted to Java though, we accept any JVM language and both Javascript and PHP have been ported to the JVM:
      https://developer.mozilla.org/en-US/docs/Rhino (already embedded in the JDK)
      http://quercus.caucho.com/

  • King Chung Huang

    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?

  • Kevin Hanna

    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)?

    • Kevin Hanna

      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.

  • Mike Chung

    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.

    • Darren

      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.

  • Kevin Hanna

    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

    • Brendan

      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.

      • Kevin Hanna

        :) 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?)

        • Brendan

          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!

    • damienlepage

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

      • Kevin Hanna

        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. ;)

        • Kevin Hanna

          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.

          • SomeGuyYouHelped

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

          • Kevin Hanna

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

        • Kevin Hanna

          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

          • Jordan

            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.

        • Mike Chung

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

          • Kevin Hanna

            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 ;)

          • Mike Chung

            Mine runs takes 10 minutes to run ? =P

  • Matt

    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”?

    • damienlepage

      Yes, you need to drop all the suffixes.

      • Mike Chung

        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 ?

        • damienlepage

          No sorry, you need to deal with the existing method signature. Thanks

          • Mike Chung

            can I write that stream to the file system ? and reacess, it I know that sounds crazy, but I wrote the whole solution without at that signature.

          • damienlepage

            Yes you can, as long as your code is portable.

      • Wynford

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

        • damienlepage

          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.

          • Wynford

            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.

          • damienlepage

            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

          • Wynford

            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 !!

          • damienlepage

            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.

  • chamberlain2007

    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.

  • hidy

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

    • damienlepage

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

  • Guest

    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

    • Mike Chung

      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.

    • Jordan

      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

      • Jim

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

        • Jordan

          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

    • King Chung Huang

      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

      • Anna-Chiara Bellini

        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 :-)

        • King Chung Huang

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

      • Anna-Chiara Bellini

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

        • King Chung Huang

          Yeah, plain Java in the project as provided by Kijiji.

    • Guest

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

    • Eugene Loykov

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

    • Guest

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

    • karmakaze

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

  • Vinayak

    Can I submit updated code again ?

    • damienlepage

      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.

  • shadowku

    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?

    • damienlepage

      We will simply run “mvn test” from command line, if that works for you then it should work in our test environment too.

      • Ron

        Are you only testing it with the provided unit test?

        • damienlepage

          No, we will use a few secret test cases to automate some of the scoring.

          • Guest

            Ha, secret test cases…:) Can you submit these tests to github after the deadline?

          • damienlepage

            Yes we will.

          • Guest

            Thanks! Perhaps some participants can add their own tests..

  • karmakaze

    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?

    • damienlepage

      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.

  • DL

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

    • damienlepage

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

      • King Chung Huang

        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.

      • King Chung Huang

        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.

  • King Chung Huang

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

    • damienlepage

      Good question. Our mistake for missing the precision so we’ll go with the worst case scenario and accept submissions unti 11:59 PM HAST, which gives you another 6 hours.

      • Anna-Chiara Bellini

        And so it’s over now!!! :-) I can stop obsessing about it :P

  • Anna-Chiara Bellini

    Itching…

  • damienlepage

    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!

    • Jordan Milne

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

  • http://damienlepage.com/ Damien Lepage
  • java development company

    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!

Pinterest