Hello,I am trying to solve ADAQueue task and I got TLE. First I tried build in queue (from queue library) than I implemented a linked list. Everything seems to be working for example input and for other input generated by me. I also tried a huge input (arount 15k data).Any hints for corner cases?I could attach my code, but I do not know if I would violate any rules here.
Posting code is fine, just remember to remove it after getting answers / suggestions.
Without seeing the code I would guess that one thing that could be potentiallyproblematic is reverse operation. Make sure it runs in constant time.Implementing reverse by actually reordering all elements in memory takes timeproportional to list size and is too slow.
I have changed 'reverse' function as you suggested. I got good answers to all test cases I come up with, but I still got TLE....Here is my code. Maybe someone could show me my mistakes?http://ideone.com/tRjFtw
To remove an element from the end of a single linked list you need to iterateover the whole list (similarly to add an element to the end). In this situationa double-linked list tracking both head and tail pointer would be moreappropriate.
Together with idea of reverse flag you already have, all remaining operationswould be completed in constant time.
Thanks for the answer. I made changes and removed all loops.
Now I got 'wrong answer' .....
Can anybody give me a hint? Judge starts to play on my nerves....http://ideone.com/HGfvWi
With non-empty list, InsertFront does not work correctly. Following test case demonstrates the issue:
If new is used to allocate memory it should be matched with delete, not free.
Your test case surely helped. Thanks! Finally accepted
I dont know why I am getting a wrong answer on this. I dont see any mistake in it. Please help.
Thanks to all for this useful topic!