We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Yes, by "sorted map" I mean sorted keys. An unsorted map (with entries in the order they are provided) wasn't fast enough.
I implemented sorting by inserting each entry at the ordered location and shuffling the remainder down one index. That allowed me to do binary retrieval in O(log n) instead of O(n).
That was better, but still not fast enough. So I added binary insertion as well, which is also an improvement from O(n) to O(log n). IIRC my implementation was simply to perform a binary search to find the insertion point, and then do a memmove style shuffle.
Java's HashMap is O(1) for insertion and retrieval, so it should smash it! This challenge is one of those lovely academic examples of where algorithmic complexity trumps language choice.
As reiterated by ramueller11, already having a map implementation hides much of the challenge. In lower-level languages without a map implementation, the task is rather more involved! Java's "basic HashMap" implemetation is over 600 lines long (>1000 with comments).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Day 8: Dictionaries and Maps
You are viewing a single comment's thread. Return to all comments →
Yes, by "sorted map" I mean sorted keys. An unsorted map (with entries in the order they are provided) wasn't fast enough.
I implemented sorting by inserting each entry at the ordered location and shuffling the remainder down one index. That allowed me to do binary retrieval in O(log n) instead of O(n).
That was better, but still not fast enough. So I added binary insertion as well, which is also an improvement from O(n) to O(log n). IIRC my implementation was simply to perform a binary search to find the insertion point, and then do a memmove style shuffle.
Java's HashMap is O(1) for insertion and retrieval, so it should smash it! This challenge is one of those lovely academic examples of where algorithmic complexity trumps language choice.
As reiterated by ramueller11, already having a map implementation hides much of the challenge. In lower-level languages without a map implementation, the task is rather more involved! Java's "basic HashMap" implemetation is over 600 lines long (>1000 with comments).