Last Updated: 20 Nov, 2021

Special Array

Moderate

Asked in companies

Solve now

Problem statement

Your task is to design a special type of array that will store integers(duplicate values possible). You have to define a class having the following functions:

‘SPECIAL_ARRAY’() is a function that initializes your array.
‘INSERT’( ‘VAL’ ) inserts the ‘VAL’ into the array and returns a boolean value. If ‘VAL’ is not present in the array before insertion, return ‘TRUE’, else return ‘FALSE’.
‘REMOVE’(‘VAL’) removes the ‘VAL ’from the array if present. This function would return a boolean value ‘TRUE’ if ‘VAL’ was present in the array before the deletion, else returns ‘FALSE’. If multiple occurrences of ‘VAL’ are present in the array, delete only one occurrence.
‘GET_RANDOM’( ) returns any random value of the array.

For Example

If the functions calls are as follows:
‘INSERT’(10).
‘INSERT’(20)’.
‘INSERT’(20)
‘REMOVE’(20).
‘GET_RANDOM()’
So, the answers for the calls are [‘TRUE’, ’TRUE’, ’FALSE’, ’TRUE’,10]. Another valid output of the 
‘GET_RANDOM()’ function call is 20.

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N’, denoting the number of function calls.

The second line contains a list of ‘N’ function names.
The third line of each test case contains ‘N’ integers denoting the parameters passed in each function call. (Parameter value corresponding to  any ‘GET_FUNCTION’() function is -1.)

Output Format:

For each test case, output the values returned by function calls as ‘TRUE’, ’FALSE’ or the returned number.

Print the output of each test case in a separate line.

Note:

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

Constraints:

1 <= T <= 10
1 <= N <= 10000.
0 <= ‘VAL’ <= 10^6 .  

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will implement this special array using a simple dynamic array.

In the insert function, we will search if the element is present in the array or not and insert the new element.

In the insert function, we will search if the element is present in the array or not, and if present, we will swap it with the last element of the array and remove the last element from the array.

In getRandom function, we will randomly select an index between 0 to (length of array -1), then return the value corresponding to that index.

Algorithm:

Defining SPECIAL_array():
- Declare a dynamic array ‘ARR’.
Defining INSERT(‘VAL’):
- SET ‘IDX’ as -1.
- For i in range 0 to the length of ‘ARR’-1:
  - If ARR[i] is equal to ‘VAL’:
    - Set ‘IDX’ as i.
    - Break.
- Insert ‘VAL’ into ‘ARR’.
- If ‘IDX’ is equal to -1, it implies ‘VAL’ is not present in the array before insertion. So, return ‘FALSE’.
- Return ‘TRUE’.
Defining REMOVE(‘VAL’):
- SET ‘IDX’ as -1.
- For i in range 0 to the length of ‘ARR’-1:
  - If ARR[i] is equal to ‘VAL’:
    - Set ‘IDX’ as i.
    - Break.
- If ‘IDX’ is equal to -1,it implies that ‘VAL’ is not present in the array. So, return ‘FALSE’.
- Swap ‘ARR[IDX]’ with the last value of the array.
- Remove the last value of the array.
- Return ‘TRUE’.
Defining GET_RANDOM(‘VAL’):
- Set ‘IDX’ as a random number between 0 to length of ‘ARR’-1.
- Return ‘ARR[IDX]’.

Solve now

02 Approach

In this approach, we will use the same ‘ARR’ array to store the values.To avoid the searching process, we will create a HashMap ‘INDICES’ which will store the indices of each value in an set. For examples INDICES[30] will store all the indices of ‘ARR’ which have a value of 30 in an unordered set. So, to check if the number is present or not, we can simply check it in O(1) by checking the size of INDICES[‘VAL’].

Defining SPECIAL_array():
- Declare a dynamic array ‘ARR’.
- Declare a hashmap of ordered set ‘INDICES’
Defining INSERT(‘VAL’):
- Declare ‘ANS’ as the boolean value that has to be returned.
- If the size of INDICES[‘VAL’] is equal to 0:
  - Set ‘ANS’ as ‘TRUE’.
- Else:
  - Set ‘ANS’ as ‘FALSE’.
- Insert ‘VAL’ into ‘ARR’.
- Append the index of the newly added value into the ‘INDICES’ hashmap.
- Append ( length of ‘ARR’ -1) into INDICES[‘VAL’].
- Return ‘ANS’.
Defining REMOVE(‘VAL’):
- Declare ‘ANS’ as the boolean value that has to be returned.
- If size of INDICES[‘VAL’] is equal to 0:
  - Return ‘FALSE’ as no deletion has to perform.
- Else:
  - Set ‘ANS’ as ‘TRUE’.
- ‘LAST’ will store the last value of ‘ARR’.
- Set ‘LAST’ as ARR[lenght of ‘ARR’-1].
- Set ‘REMOVE_IDX’ to store the last index of the ‘VAL’.
- Set ‘REMOVE_IDX’ as the last value of INDICES[‘VAL’].
- Insert ‘REMOVE_IDX’ into INDICES[‘LAST’].
- Remove the last value from INDICES[‘VAL’].
- Remove the last value from INDICES[‘LAST’].
- Set ARR[REMOVE_IDX] as ‘LAST’.
- Remove the last element from ‘ARR’.
- Return ‘ANS’,
Defining GET_RANDOM(‘VAL’):
- Set ‘IDX’ as a random number between 0 to length of ‘ARR’-1.
- Return ‘ARR[IDX]’.

Solve now