Mar 2017
1 / 9
Mar 2017
Nov 2020
kasiekdec
Mar '17

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.

  • created

    Mar '17

  • last reply

    Nov '20
  • 8

    replies

  • 1.2k

    views

  • 4

    users

  • 3

    links

tjm
Mar '17

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 potentially
problematic is reverse operation. Make sure it runs in constant time.
Implementing reverse by actually reordering all elements in memory takes time
proportional to list size and is too slow.

kasiekdec
Mar '17

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/tRjFtw18

tjm
Mar '17

To remove an element from the end of a single linked list you need to iterate
over the whole list (similarly to add an element to the end). In this situation
a double-linked list tracking both head and tail pointer would be more
appropriate.

Together with idea of reverse flag you already have, all remaining operations
would be completed in constant time.

tjm
Mar '17

With non-empty list, InsertFront does not work correctly. Following test case demonstrates the issue:

4
toFront 51
toFront 10
back
front

If new is used to allocate memory it should be matched with delete, not free.

3 years later
mihir_89
Oct '20

I dont know why I am getting a wrong answer on this. I dont see any mistake in it. Please help.

23 days later