SDE - 1

I solved it by using the stack data structure.
1. if the current element of the string will be opening bracket then we will just simply push it into the stack.
2. if control comes to the else part, it means that the current element is a closing bracket, so check two conditions current element matches with the top of the stack, and the stack must not be empty.

The key to the problem is that there is ALWAYS only 1 pair of numbers that satisfy the condition of adding together to be the target value.
We can assume that for all the numbers in the list (x1, x2, ... xn) that there exists a pair such that xa + xb = target
To solve this with a single pass of the list we can change the equation above to xa = target - xb and since we know the target as long as we maintain a record of all previous values in the list we can compare the current value (xa) to it's ONLY pair, if it exists, in record of all previous values (xb)

To keep a record of the previous values and their indices I have used a dictionary. Commonly known as a map in other languages. This allows me to record each previous number in the dictionary alongside the indice as a key value pair (target-number, indice)

1. Create a map to store frequency of each number in the array. (Single traversal is required)
2. In the next traversal, for every element check if it can be combined with any other element (other than itself!) to give the desired sum. Increment the counter accordingly.
3. After completion of second traversal, we’d have twice the required value stored in counter because every pair is counted two times. Hence divide count by 2 and return.

Tip 1 : Get the requirement clarified by asking some questions like how much data will be in the system.
Tip 2 : Don't Jump directly on using Redis cache or NoSQL.
Tip 3 : Start with a basic Data structure that could be used here example hashtables or SortedMap.

Tip 1 : Lot of users will log in daily. Caching can be used.
Tip 2 : What database could be used NoSQL or SQL.
Tip 3 : Database schemas