InternDoor

A list you can add to at both ends

Easydesign · linked listDesign a class

Reported in interviews at (where)

Build FrontBackList, a list of whole numbers kept as a linked list: numbers can be added at the front or at the back, and taken off the front.

FrontBackList() starts empty.

pushFront(x) adds x before every number in the list.

pushBack(x) adds x after every number in the list.

popFront() removes the first number and returns it, or returns -1 if the list is empty.

front() returns the first number without removing it, or -1 if the list is empty.

size() returns how many numbers the list holds.

Every call should take O(1) time: keep a pointer to both ends of the list.

Example 1
Input
["FrontBackList","pushBack","pushFront","pushBack","size","popFront","front","popFront","popFront","popFront","size"]
[[],[5],[8],[1],[],[],[],[],[],[],[]]
Output
[null,null,null,null,3,8,5,5,1,-1,0]

The list goes 5, then 8 5, then 8 5 1. Numbers come off the front in that order, and an empty list gives -1.

Example 2
Input
["FrontBackList","front","pushFront","front","pushFront","front","size"]
[[],[],[0],[],[4],[],[]]
Output
[null,-1,null,0,null,4,2]

Each pushFront puts its number first.

Limits

  • 0 <= x <= 1000000000
  • at most 20000 calls after the constructor

Hints

Hint 1

Each node holds a number and a pointer to the next node. Keep a head pointer for the front and a tail pointer for the back.

Hint 2

Watch the moments the list goes from empty to one number and back: both head and tail change then.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.