Ad
  • Custom User Avatar

    Yes. But another question: is it best practice to use such a non-concise code? You must remember the order of operations. In my opinion, it is really hard to read. I would use parentheses instead.

  • Custom User Avatar

    it doesn't matter whether the performance hit is on enqueue or dequeue

    What I meant above is that if you flipped your queue back so that front stores the head node and back the last node while enqueuing at the back and dequeuing at the front as usual, you should find that neither enqueue nor dequeue should suffer a performance hit.

  • Default User Avatar

    Hi,

    Thanks for your response.

    The behavior you describe is intentional. The way I figure it, enqueue will be the more frequent operation and should be faster. At the very least, the cases are equal. If every object that gets enqueued is subsequently dequeued, it doesn't matter whether the performance hit is on enqueue or dequeue. But if there are some enqueued objects that don't get dequeued before the list is destroyed, my implementation saves n - 1 traversals, where n is the number of elements in the queue when it's destroyed (there is still one traversal required to destroy the remaining elements).

    I believe my implementation is defensible and shouldn't be penalized. I can change it around to pass the kata, but I believe this is a bug in the way the kata is graded.

  • Custom User Avatar

    Thanks for posting your solution for review.

    As the description states, all operations should complete in O(1) time (including "dequeue") which means that there should not be any loops involved. Since your "dequeue" method involves iterating through a linked list, its time complexity becomes O(n) which is suboptimal. Upon further inspection, it seems that your implementation of "enqueue" is the culprit - it causes the queue wrapper to maintain two linked lists, one starting from its front member and one from its back with both ending in the same last node, when in reality it was expected for your queue to maintain one linked list throughout where front is the head node and back is the very last node. Hint: If you implement your "enqueue"/"dequeue" operations correctly, the "dequeue" operation should not involve the back of the list at all (except when the queue has one item left) ;)

    EDIT: Apologies for the faulty analysis, I was half asleep last night :p Basically, you've got your queue back to front - its back currently stores the head of the linked list and front its last node when it should be the other way round. Once you fix this, you should find that your dequeue operation no longer requires traversing the entire linked list.

    Hope this helps :D

  • Default User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Custom User Avatar

    Perhaps you could post your code here and mark it as a spoiler so I can review it and hopefully provide a few hints? Cheers :)

  • Default User Avatar

    I keep timing out. My implementation is a pretty standard queue implementation, so I think the tests are too aggressive.

  • Custom User Avatar

    cool thank you!

  • Custom User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Custom User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Custom User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Custom User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Default User Avatar

    I agree. The description is just wrong.

    "If the value passed in is a string containing numbers or other characters other than spaces and alphabet letters, return 'Not letters'"

    but

    Testing for 1jh2o
    It should work for random inputs too - Expected: "1", instead got: "Not letters"

  • Custom User Avatar

    I wrote this solution during beta to show the significance of random test cases.

  • Default User Avatar
  • Loading more items...