Boolean Queries

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in company
Google inc

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].
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
3
1 2 1
3 0
2 4 
3
3 1
2 6
2 5

Sample Output 1:

False
True
True
Explanation:
For first test case,  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 in a single line [False]

For the second test case, Q = [[3, 1], [2, 6], [2, 5]], Here
Q[0] is the query that sets all the indices to True.
Q[1] is the query that gets the value at index 6, this is True.
Q[2] is the query that gets the value at index 5 that is True.
Hence the answer is [True, True].
Sample Input 2:
2
5
2 4
1 4 1
2 4
3 0
2 4
2
3 1
2 9
Sample Output 2:
False
True
False
True
Hint

Try to think of an approach by maintaining an array.

Approaches (2)
Array

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]
Time Complexity

O(max(index)*Q), Where Q is the number of queries and the index is the given value of indices.

 

We are iterating over all the queries. The setAllFalse and setAllTrue query will take O(max(index)) time and the rest of the queries will take O(1) time. Hence the overall time complexity will be O(max(index)*Q).

Space Complexity

O(max(index)), Where the index is the given value of indices.
 

We maintain an array to store the boolean value of indices that takes O(max(index)) in the worst case. Hence the overall space complexity is O(max(index)).

Code Solution
(100% EXP penalty)
Boolean Queries
Full screen
Console