Last Updated: 9 Sep, 2021

Boolean Queries

Moderate

Asked in company

Problem statement

You are given a stream of boolean values. Your task is to maintain a data structure that supports the following functions.

setAllTrue(): Sets all the indicies to true

setAllFalse(): Sets all the indices to false

setIndexTrue(index): Set the value at position index to true

setIndexFalse(index): Set the value at position index to False

getIndex(index): Return the value of position index

Note:

Initially, all the values of the data structure are set to false.

The Queries are in the format below-:
(1, index, value): Set the value at the given index

(2, index): Get the value at the given index 

(3, value): Set all the indices to the boolean value given.

The value 1 represents true and 0 represents false.

For example:

You are given Q = [[1, 2, 1], [3, 0], [2, 4]], Here 
Q[0] is the query that sets the boolean value at index 2 to True.
Q[1] is the query that sets the value of all indices to False.
Q[2] is the query that gets the value at index 4 that is False.
Hence the answer is [False].

Input Format:

The first line of input contains the integer ‘T’ representing the number of test cases.

The second line of input contains a single integer ‘Q’, representing the number of queries.

The next ‘Q’ lines contain space-separated integers denoting the queries.

Output Format:

For each test case, print the list of boolean in separate lines representing the output of the queries.

Print a separate line for each test case.

Constraints:

1 <= T <= 10
2 <= Q <= 10^6
1 <= index <= 10^5

Time Limit: 1 sec

Note:

You do not need to print anything. It has already been taken care of. Just implement the function.

Solve now

Approaches

01 Approach

In this approach, we will maintain an array of max size with all initial values set to false. Then we will change the value of the array in each of the functions

Algorithm:

Create an empty array array of maximum size with all values as False
In the function setAllTrue()
- Set array as an array of maximum size with all values as True
In the function setAllFalse()
- Set array as an array of maximum size with all values as False
In the function setIndexTrue(index)
- Set array[index] as True
In the function setIndexFalse(index)
- Set array[index] as False
In the function getindex(index)
- Return array[index]

Solve now

02 Approach

In this approach, we will maintain a HashMap and add all the indexes to value to the hashmap, but setting all indices true or false will take linear time. So to counter this, we will delete the entire HashMap and change the default value of the hashmap as true or false accordingly.

Algorithm:

Initialse an empty hashmap indexMap
Set defaultValue as False
In the function setAllTrue()
- Set indexMap as an empty hashmap
- Set defaultValue as True
In the function setAllFalse()
- Set indexMap as an empty hashmap
- Set defaultValue as False
In the function setIndexTrue(index)
- Set indexMap[index] as True
In the function setIndexFalse(index)
- Set index[index] as False
In the function getindex(index)
- If index is not in indexMap
  - Return defaultValue
- Otherwise return indexMap[index]

Solve now