We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
After my first approach failed on tests 8-10 due to timeout I spent much time on thinking on a better algorithm and finally arrived at the conclusion that either this problem is be to solved with some additional data structure other than a dequeue or it is an implementation problem. Since the title of the problem is "Java Deque" I rejected the former and concentratated on the latter,
and finally my code passed all the tests in less than 3s.
Some suggestions for those who have problems with timeout:
1. Write your own implementation of a deque based on an array.
2. In you implementation, the "contains" method should written very carefully - linear time is OK, but some optimizations are needed: (a) you can search simultaneously from both sides, (b) do use "for" loop with a loop counter instead of "while" with a condition (such "for" is faster).
The solution given in the editorial use an addition data structure which eats a lot of memory... It solves the problem, but I don't like it.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Java Dequeue
You are viewing a single comment's thread. Return to all comments →
After my first approach failed on tests 8-10 due to timeout I spent much time on thinking on a better algorithm and finally arrived at the conclusion that either this problem is be to solved with some additional data structure other than a dequeue or it is an implementation problem. Since the title of the problem is "Java Deque" I rejected the former and concentratated on the latter, and finally my code passed all the tests in less than 3s.
Some suggestions for those who have problems with timeout: 1. Write your own implementation of a deque based on an array. 2. In you implementation, the "contains" method should written very carefully - linear time is OK, but some optimizations are needed: (a) you can search simultaneously from both sides, (b) do use "for" loop with a loop counter instead of "while" with a condition (such "for" is faster).
The solution given in the editorial use an addition data structure which eats a lot of memory... It solves the problem, but I don't like it.