Should not the overall TC be: O(N*M*log(k)),

Entering edit mode

Click here to Practice

Submit Problem to OJ

**Given Two time series**

- The time series denote the spike that we have to make in discrete manner at that time.
- The value remains same for all time until the next updated spike.
- let T1 = [ (0,1) , (3,5) , (7,2) ] and T2 = [ (2,2) , (3,3) , (6,1) ]
- For T1 , value = 1 for [0,3) , value = 5 for [3,7) , value = 2 for [7,inf)
- For T2 , value = 0 for [0,2) , value = 2 for [2,3) , value = 3 for [3,6) and value = 1 for [6,inf)
- We have to return a new List which denotes T1 + T2
- T1 + T2 = [ (0,1) , (2,3) , (3,8) , (6,6) , (7,3) ]

**Some good clarifications i asked :**

- is time and value integer? ( No , can be double)
- is List sorted based on time? (Yes)
- Range of time and value? (Assume Infinite)
Can there be 2 spikes for same time? (No , time wont be repeated)

Inititally misunderstood the question , clarified the question again. (wasted 10mins)

- Was able to explain and code up a O(N) solution using two pointers.

**Follow up questions**

- Lets say we have M such time series , how should we approach?
- Came up with divide and conquer strategy to split M->M/2->M/4 ....2 and merge them bottom up using code to merge T1+T2.
- Time Complexity - O(Log(M)*N) , space = O(Log(M)) (recursion stack)

Implement a Cache management class.

```
class Cache{
Cache(int capacity){};
int get(int key);
int put(int key , int value);
}
```

Has fixed capacity and Remove the oldest inserted key if there is size overflow.

Some good clarifications i asked :

- will key be integer ? (Yes)
- do we need to handle cases for invalid requests? (example capacity <= 0) ? (Yes)
- will value be integer? (Yes)

Follow Up questions

- Implement LRU cache.

Pretty much finished this round in 25mins and had good amount of chat regarding the work i did during my summer internship.

Initial Problem : Easy version

Click here to Practice

Submit Problem to OJ

Follow Up : Hard Version

Click here to Practice

Submit Problem to OJ

**Under Progress**

Modifiy the input string with following substitutions.

```
S = "Alice saw a tiger"
subs = [(0,5,"Bob") , (13,18,"cat")] {L,R,string}
result = "Bob saw a cat"
```

Some good clarifications i asked :

- is subs List sorted? (No);
- Are all characters english alphabets? (Yes);
- Are the ranges disjoint? (Yes , for now :) )

Approach for initial problem

- Came up with a binary search solution ,
- sort the subs List based on L
- scan through S from left to right and search for match in subs.
- Replace if there is a match , else append current character and keep scanning.

Follow up

- The ranges are not disjoint now. ( we should replace with the string of an overlapping range that comes first in subs)
- subs = [ (4,6,"hi") , (1,2,"bye") , (2,5,"ohho") , (6,6,"hehe")];
- The range 4,6 overlaps 2,5 which overlaps 1,2 , Hence 1,2 indirectly overlaps 4,6.
- Now when we reach index 1 in S , we will replace it with "hi" and jump to R = 6.
- since range (4,6) is the first range in subs that indirectly overlaps with (1,2).

Approach for follow up

- Came up with a Disjoint set Union solution.
- Merge those ranges that overlap with each other.
- Do Union by Size and store the [min_index , minL , maxR] for each component.
- Make a new merged_subs = [ (minL , maxR , subs[min_index])] for each DSU component.
- Now the question is same as first question , modifying string with disjoint ranges.

G&L (some i remember)

- What would you do if your team lacks innovation
- What if your manager isnt being helpful
- What if one of your team mates arent speaking up
- What if your team is not able to figure out on how to implement something.
- How to bring up innovations ```

Entering edit mode

**Adding 2 Time Series Data**

- First part of the problem is to figure out how to add 2 time series data.
- Looking on few test cases will help you understand how the summation works and will help you come up with a two-pointer method.
- The main idea is to append the value to the result whose time is lesser and the magnitude of this point will depend on the magnitude of previously added point.
- There are few edge cases you might need to handle , but the below code will give you a good idea on the implementation.

**Adding K Time Series Data**

- We know how to add two time series data , and adding the K time series in any order should produce the same result.
- We can use a Divide and Conquer approach to add them.
- Let Merge( i , j ) = result of adding all time series data from T[i ..... j]
- Merge(0 , K) -> Merge(0,K/2) + Merge(K/2+1 , K)
- Base Case = Merge( i , i ) = return T[i]

**Complexity**

- O(N) to add two time series.
- O(NLog(K)) to add K time series of average length N.

**Code**

Loading Similar Posts

Great job solving with good speed, well-asked Clarification questions! Best wishes!

Thanks for sharing the experience honestly with the community, it should be super helpful for all preparing for placements.