Ad
  • 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.

  • 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

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

  • Custom User Avatar

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

  • Custom User Avatar

    I had the same issue, but it's supposed to be that the entire string is equal to t * k, not just a substring (which is a substantially harder problem!).

    So, the answer for 'abba' is actually ['abba', 1], not ['b', 2]. I'm going to edit the description to make this clearer.