Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
in Online Assessments by Expert (34,270 points) | 3,359 views

1 Answer

0 like 0 dislike
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
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.
by Expert (34,270 points)

Get best answers to any doubt/query/question related to programming , jobs, gate, internships and tech-companies. Feel free to ask a question and you will receive the best advice/suggestion related to anything you ask about software-engineering , development and programming problems .