Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.
insert(val)
: Inserts an item val to the collection.remove(val)
: Removes an item val from the collection if present.getRandom
: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.Example:
// Init an empty collection. RandomizedCollection collection = new RandomizedCollection(); // Inserts 1 to the collection. Returns true as the collection did not contain 1. collection.insert(1); // Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1]. collection.insert(1); // Inserts 2 to the collection, returns true. Collection now contains [1,1,2]. collection.insert(2); // getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3. collection.getRandom(); // Removes 1 from the collection, returns true. Collection now contains [1,2]. collection.remove(1); // getRandom should return 1 and 2 both equally likely. collection.getRandom();
We must support three operations with duplicates:
insert
remove
getRandom
To getRandom
in and have it scale linearly with the number of copies of a value. The simplest solution is to store all values in a list. Once all values are stored, all we have to do is pick a random index.
We don't care about the order of our elements, so insert
can be done in using a dynamic array (ArrayList
in Java or list
in Python).
The issue we run into is how to go about an O(1)
remove. Generally we learn that removing an element from an array takes a place in , unless it is the last element in which case it is .
The key here is that we don't care about order. For the purposes of this problem, if we want to remove the element at the i
th index, we can simply swap the i
th element and the last element, and perform an pop (technically we don't have to swap, we just have to copy the last element into index i
because it's popped anyway).
With this in mind, the most difficult part of the problem becomes finding the index of the element we have to remove. All we have to do is have an accompanying data structure that maps the element values to their index.
Algorithm
We will keep a list
to store all our elements. In order to make finding the index of elements we want to remove , we will use a HashMap
or dictionary to map values to all indices that have those values. To make this work each value will be mapped to a set of indices. The tricky part is properly updating the HashMap
as we modify the list
.
insert
: Append the element to the list
and add the index to HashMap[element]
.remove
: This is the tricky part. We find the index of the element using the HashMap
. We use the trick discussed in the intuition to remove the element from the list
in . Since the last element in the list gets moved around, we have to update its value in the HashMap
. We also have to get rid of the index of the element we removed from the HashMap
.getRandom
: Sample a random element from the list.Implementation
Complexity Analysis
Time complexity : , with being the number of operations. All of our operations are , giving .
Space complexity : , with being the number of operations. The worst case scenario is if we get
add
operations, in which case our ArrayList
and our HashMap
grow to size .
Analysis written by @alwinpeng
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open (
and closing parentheses )
, the plus +
or minus sign -
, non-negative integers and empty spaces
.
Example 1:
Input: "1 + 1" Output: 2
Example 2:
Input: " 2-1 + 2 " Output: 3
Example 3:
Input: "(1+(4+5+2)-3)+(6+8)" Output: 23Note:
eval
built-in library function.This problem is all about understanding the following:
Intuition
This question qualifies really well for a stack question. Since the expression might have parenthesis, we can use a stack to find the value for each sub-expression within a parenthesis. Essentially, we need to delay processing the main expression until we are done evaluating the interim sub-expressions within parenthesis and to introduce this delay, we use a stack.
We push the elements of the expression one by one onto the stack until we get a closing bracket )
. Then we pop the elements from the stack one by one and evaluate the expression on-the-go. This is done till we find the corresponding (
opening bracket. This kind of evaluation is very common when using the stack data structure. However, if you notice the way we calculate the final answer, you will realize that we actually process the values from right to left whereas it should be the other way around.
From the above example we realize that following the simple stack push and pop methodology will not help us here. We need to understand how +
and -
work. +
follows the associative property. For the expression , we have . However, -
does not follow this rule which is the root cause of all the problems in this approach.
If we use a stack and read the elements of the expression from left to right, we end up evaluating the expression from right-to-left. This means we are expecting to be equal to which is not correct. Subtraction is neither associative nor commutative.
This problem could be solved very easily by reversing the string and then using basic drill using a stack. Reversing a string helps since we now put the elements of the expression into the stack from right to left and evaluation for the expression is done correctly from left to right.
Algorithm
123
>> 120 + 3
>> 100 + 20 + 3
. Thus, if the character read is a digit we need to form the operand by multiplying a power of 10
to the current digit and adding it to the overall operand. We do this since we are processing the string in the reverse order.When we encounter an opening parenthesis (
, this means an expression just ended. Recall we have reversed the expression. So an opening bracket would signify the end of the an expression. This calls for evaluation of the expression by popping operands and operators off the stack till we pop corresponding closing parenthesis. The final result of the expression is pushed back onto the stack.
Note: We are evaluating all the sub-expressions within the main expression. The sub-expressions on the right get evaluated first but the main expression itself is evaluated from left to right when all its components are resolved, which is very important for correct results.
For eg. For expression , is evaluated before . While evaluating the order is from left to right. Similarly for the parent expression, all the child components are evaluated and stored on the stack so that final evaluation is left to right.
Push the other non-digits onto to the stack.
Do this until we get the final result. It's possible that we don't have any more characters left to process but the stack is still non-empty. This would happen when the main expression is not enclosed by parenthesis. So, once we are done evaluating the entire expression, we check if the stack is non-empty. If it is, we treat the elements in it as one final expression and evaluate it the same way we would if we had encountered an opening bracket.
We can also cover the original expression with a set of parenthesis to avoid this extra call.
Complexity Analysis
Time Complexity: , where N is the length of the string.
Space Complexity: , where N is the length of the string.
Intuition
A very easy way to solve the problem of associativity for -
we tackled in the previous approach, is to use -
operator as the magnitude for the operand to the right of the operator. Once we start using -
as a magnitude for the operands, we just have one operator left which is addition and +
is associative.
for e.g. could be re-written as .
The re-written expression would follow associativity rule. Thus evaluating the expression from right or left, won't change the result.
What we need to keep in mind is that the expressions given would be complicated, i.e. there would be expressions nested within other expressions. Even if we have something like (A - (B - C))
we need to associate the negative sign
outside of B-C
with the result of B-C
instead of just with B
.
We can solve this problem by following the basic drill before and associating the sign with the expression to the right of it. However, the approach that we will instead take has a small twist to it in that we will be evaluating most of the expression on-the-go. This reduces the number of push and pop operations.
Follow the below steps closely. This algorithm is inspired from discussion post by southpenguin.
Algorithm
123
>> 120 + 3
>> 100 + 20 + 3
. Thus, if the character read is a digit we need to form the operand by multiplying 10
to the previously formed continuing operand and adding the digit to it.+
or -
we first evaluate the expression to the left and then save this sign
for the next evaluation.
(
, we just push the result calculated so far and the sign
on to the stack (the sign and the magnitude) and start a fresh as if we are calculating a new expression.)
, we first calculate the expression to the left. The result from this would be the result of the expression within the set of parenthesis that just concluded. This result is then multiplied with the sign, if there is any on top of the stack.
Remember we saved the sign
on top of the stack when we had encountered an open parenthesis? This sign is associated with the parenthesis that started then, thus when the expression ends or concludes, we pop the sign
and multiply it with result of the expression. It is then just added to the next element on top of the stack.Complexity Analysis
Time Complexity: , where N is the length of the string. The difference in time complexity between this approach and the previous one is that every character in this approach will get processed exactly once. However, in the previous approach, each character can potentially get processed twice, once when it's pushed onto the stack and once when it's popped for processing of the final result (or a subexpression). That's why this approach is faster.
Space Complexity: , where N is the length of the string.
Analysis written by: @godayaldivya.