Hey there !
I am *** from NIT Surathkal. Sprinklr conducted online test for both FULL TIME as well as INTERN.
There were three problems, all of them were coding only.
- Given a string S, consisting of only lowercase english letters. Find the number of substrings having all characters distinct.
- Given a list of N intervals, each interval have some weight assigned to it, you are asked to choose two non overlapping intervals of them such that total weight is maximum.
- This one was from Graph, about MinCut standard problem. It was like, Country has n cities connected by m Bidirectional roads. May be multiple roads between pair of cities, country is connected. Importance of road (weight) Separation between 2 cities a,b = min possible sum of roads importance that needs to be removed to make a,b disconnected
Find product of separation value over all unordered pairs of cities % 10^9+7.
This problem is same as https://www.hackerrank.com/challenges/road-network/problem
Solution :
- Just use sliding window with extra space to keep the frequency. And overall complexity will be O(N)
- Sort the given intervals according to start time, and when equal then by finish time. Keep a set of pairs of {curr_start_time, maximum weight with start_time >= curr_start_time}, which will store {u, w}, u as start time and w as maximum weight if we consider [i, n] subarray. Now iterate from back, and if you want to choose current pair{x,y,w} as one of the two, then find the lower_bound of y + 1 in the set , and update the answer accordingly. Just be catious in inserting a pair in set.
- Its a standard algorithm problem, just use Ford Fulkerson algorithm with some modification. May be seeing the Editorial would give you more understanding.
Happy Quarantine :)