Design Front Middle Back Queue

MediumDesigndesign

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Design FrontMiddleBackQueue, a queue that supports insertion and removal at the front, the back, and the middle. - pushFront(val), pushBack(val) add val at the front or back. - pushMiddle(val) inserts val so that it lands at index n // 2, where n is the size before insertion. - popFront(), popBack() remove and return the front or back element. - popMiddle() removes and returns the element at index (n - 1) // 2. In other words, when there are two middle positions, the **frontmost** one is used for both push and pop. Every pop on an empty queue returns -1.

Examples

Input: ["FrontMiddleBackQueue","pushFront","pushBack","pushMiddle","pushMiddle","popFront","popMiddle","popMiddle","popBack","popFront"] [[],[10],[20],[30],[40],[],[],[],[],[]]
Output: [null,null,null,null,null,10,30,40,20,-1]
The queue grows [10] -> [10,20] -> [10,30,20] -> [10,40,30,20]. popFront gives 10 leaving [40,30,20]; popMiddle takes index 1 (30); popMiddle on [40,20] takes index 0 (40); popBack gives 20; the queue is now empty, so the final popFront returns -1.
Input: ["FrontMiddleBackQueue","popMiddle","pushMiddle","pushMiddle","pushMiddle","popMiddle","popMiddle","popBack"] [[],[],[5],[6],[7],[],[],[]]
Output: [null,-1,null,null,null,7,6,5]
Pushing into the middle builds [5] -> [6,5] -> [6,7,5]. popMiddle takes index 1 (7), then index 0 of [6,5] (6), and popBack returns 5.

Constraints

  • 1 <= val <= 10^9
  • At most 1000 calls in total

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More design problems