Design Bitset

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 Bitset(size), a fixed-length sequence of size bits that all start as 0. - fix(idx) sets bit idx to 1 (no change if it already is). - unfix(idx) sets bit idx to 0 (no change if it already is). - flip() inverts every bit. - all() returns true if every bit is 1; one() returns true if at least one bit is 1. - count() returns how many bits are 1. - toString() returns the bits as a string of '0'/'1', with bit 0 first. flip, all, one, and count should each run in O(1).

Examples

Input: ["Bitset","fix","fix","toString","flip","toString","all","fix","count","unfix","one","flip","count"] [[4],[2],[0],[],[],[],[],[0],[],[1],[],[],[]]
Output: [null,null,null,"1010",null,"0101",false,null,3,null,true,null,2]
After fixing bits 2 and 0 the bits are "1010"; flipping gives "0101". Fixing bit 0 makes "1101" with 3 ones. Unfixing bit 1 leaves "1001", and flipping again gives "0110" with 2 ones.
Input: ["Bitset","all","one","fix","fix","all","count","flip","one","toString"] [[1],[],[],[0],[0],[],[],[],[],[]]
Output: [null,false,false,null,null,true,1,null,false,"0"]
A single bit starts at 0. Fixing it twice is the same as once. After a flip it is 0 again.

Constraints

  • 1 <= size <= 10^5
  • 0 <= idx < size
  • At most 10^5 calls in total
  • At most 5 calls to `toString`

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