Special Array

Moderate
0/80
1 upvote
Asked in companies
LinkedInFacebook

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5
insert insert insert remove getRandom
10 20 20 20 -1
4
insert remove remove getRandom 
10 20 20 -1
Sample Output 1:
true true false true 20
true false false 10
Explanation of sample input 1:
For the first test case,
Initially, the array is empty.[]
insert(10), the array will be become [10], and the function will return ‘TRUE’ as 10 was not initially present in the array.
insert(20), the array will be become [20, 10], and the function will return ‘TRUE’ as 20 was not initially present in the array.
insert(20), the array will be become [20, 20, 10], and the function will return ‘FALSE’ as 20 was initially present in the array.
remove(20), the array will become [20,10], and the function will return ‘TRUE’ as 20 was present in the array before the deletion.
getRandom(), returns a random value among the values present in the array.

So,the answers are [true,true,false,true,20 ].

For the second test case:
Initially, the array is empty.[]
insert(10), the array will be become [10], and the function will return ‘TRUE’ as 10 was not initially present in the array.
remove(20), the array will become [10] and the function will return ‘FALSE’ as 20 was present in the array before the deletion.
remove(20), the array will become [10] and the function will return ‘FALSE’ as 20 was present in the array before the deletion.
getRandom(), returns a random value among the values present in the array.

So,the answers are [true,false,false,10].
Sample Input 2:
2
6
insert getRandom insert remove getRandom insert 
7 -1 4 10 -1 8
5
remove remove insert insert getRandom 
9 1 4 9 -1
Sample Output 2:
true 7 true false 4 true 
false false true true 9
Hint

Try to implement the special array using a simple array.

Approaches (2)
Brute Force.

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

O(N *M), where ‘N’ is the maximum length of ‘array’ and ‘M’ is the number of functions calls.

 

In this approach, all functions use O(N) time to search for the ‘VAL’. Hence the overall time complexity is O(N*M).

Space Complexity

O(N), where ‘N’ is the maximum length of ‘array’.

 

An array of size N is used to store all the values. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Special Array
Full screen
Console