Design Circular Deque

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

Implement a double-ended queue with a fixed capacity k, backed by a circular buffer. - MyCircularDeque(k) creates an empty deque that can hold at most k values. - insertFront(value) / insertLast(value) add value at the front / back. Return true on success, or false (and change nothing) if the deque is full. - deleteFront() / deleteLast() remove the front / back value. Return true on success, or false if the deque is empty. - getFront() / getRear() return the front / back value, or -1 if the deque is empty. - isEmpty() / isFull() return whether the deque holds 0 / k values. Every operation should run in O(1). Do not use a built-in deque.

Examples

Input: ["MyCircularDeque","insertLast","insertLast","insertFront","insertFront","getRear","isFull","deleteLast","insertFront","getFront"] [[3],[7],[8],[9],[5],[],[],[],[5],[]]
Output: [null,true,true,true,false,8,true,true,true,5]
After three inserts the deque is 9, 7, 8 and full, so inserting 5 fails. Removing 8 makes room, and 5 goes to the front.
Input: ["MyCircularDeque","getFront","isEmpty","deleteFront","insertFront","getRear","insertLast","deleteLast","isEmpty"] [[1],[],[],[],[4],[],[6],[],[]]
Output: [null,-1,true,false,true,4,false,true,true]
With capacity 1, the single value is both front and rear, and a second insert fails.

Constraints

  • `1 <= k <= 1000`
  • `0 <= value <= 1000`
  • At most 2000 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