Packed Bit Array: Set and Reset Bits
Updated
Problem statement
A sieve of Eratosthenes needs only one yes/no flag per number, so it can store each flag in a single bit instead of a whole integer.
You have n bits, numbered 0 to n - 1, and all of them start at 0. They are stored in an array of 32-bit words that uses the fewest words able to hold n bits. Bit z is bit z % 32 of word z / 32 (integer division). Inside a word, bit 0 is the lowest bit, worth 1, and bit 31 is the highest bit, worth 2^31.
Process the operations in order. operations[i] and values[i] together describe one operation:
"set": make bitvalues[i]equal to 1."reset": make bitvalues[i]equal to 0."word": report the current value of wordvalues[i]as a number from 0 to2^32 - 1.
Return an array whose first element is the number of words used for n bits, followed by the value reported by each "word" operation, in order.
Function
packedBits(n: int, operations: String[], values: int[]) → long[]Examples
Example 1
n = 40operations = ["set","set","set","word","word","reset","word"]values = [3,0,33,0,1,3,0]return = [2,9,2,1]40 bits need 2 words. Bits 3 and 0 are in word 0, so it is 8 + 1 = 9. Bit 33 is bit 1 of word 1, so word 1 is 2. After bit 3 is reset, word 0 is 1.
Example 2
n = 32operations = ["set","set","word","set","reset","word"]values = [31,0,0,31,5,0]return = [1,2147483649,2147483649]32 bits fit in 1 word. Bits 31 and 0 make word 0 equal to 2147483648 + 1 = 2147483649. Setting bit 31 again and resetting bit 5, which is already 0, change nothing.
Example 3
n = 1000000operations = ["set","word"]values = [999999,31249]return = [31250,2147483648]10^6 bits need 10^6 / 32 = 31250 words. Bit 999999 = 31249 * 32 + 31 is bit 31 of word 31249, worth 2147483648.
Constraints
1 <= n <= 10^61 <= operations.length <= 10^4values.length == operations.length- Each
operations[i]is"set","reset"or"word". - For
"set"and"reset",0 <= values[i] <= n - 1. For"word",0 <= values[i] <= ceil(n / 32) - 1.
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Find the Missing Number from 1 to nHyperVerge · ONSITE INTERVIEW
- Missing and Repeated NumberCommvault · ONSITE INTERVIEWCommvault interview questions
- Check Endianness Of A Byte ArrayNVIDIA · ONSITE INTERVIEWNVIDIA interview questions
- Count Set Bits in an Integer ArrayAkuna Capital · ONSITE INTERVIEWAkuna Capital interview questions
- Find the Odd-Occurrence ValueExpedia · ONSITE INTERVIEWExpedia interview questions
- Find the Two Unique NumbersZomato / Eternal · ONSITE INTERVIEWZomato / Eternal interview questions
- Bayesian Scenario ClassifierAmazon · ONSITE INTERVIEW
- Maximum Unique-Character Word SubsetMeta · ONSITE INTERVIEWMeta interview questions
- Hybrid Run-Length and Bit-Packing EncoderDatabricks · ONSITE INTERVIEWDatabricks interview questions
- Largest Combination With Bitwise AND Greater Than ZeroMicrosoft · ONSITE INTERVIEWMicrosoft interview questions