Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
What I meant above is that if you flipped your queue back so that
front
stores the head node andback
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.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 andfront
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
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 :)
I wrote this solution during beta to show the significance of random test cases.
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.