Media.net Interview Experience (2020 Summer Internship On-Campus)
Round 1 (Coding Round, 1.5 hours):
N strings of varying lengths are given. Each character used in the strings has some value. The value of a string is the sum of all characters used in that string. Given a length L, we have to use a subset of the given strings so that the total length of the strings used is L and the sum of values of all strings is maximised.
There are N ships, each with some seats S[i] (1≤i≤N). There are M passengers who want to buy the tickets for ships standing in a queue. The price of the ticket for a particular ship is always equal to the vacant seats in the ship. We have to find the maximum and minimum costs possible if all M passengers buy tickets.
There are N nodes in a graph. They are connected using directed edges. For each vertex i (1≤i≤N), we have to determine whether there exists a path such that starting from vertex i, we reach vertex i again.
Hint: Topological Sort, O(N)
Round 2 (Coding Round, 1.5 hours):
Given a 2D array of size N*M, we have to return the maximum area from the array such that the elements in that area increase as we go right in the row and down the column.
Hint: DP, Stacks, O(max(M,N)²)
There is a dictionary which contains some words. We are given a start word A and an end word B, both belonging to the dictionary. We are to determine the minimum number of moves so that we reach B starting from A, provided the intermediate words are all in the dictionary. Allowed operations are insertion of a character, deletion of a character, modification of a character.
A vehicle has to reach x = D starting from x = 0. The vehicle can store infinite amount of petrol. The vehicle has P_initial units of petrol initially. 1 unit distance can be travelled using 1 unit of petrol in 1 min, or by dragging the vehicle in 5 min. There are N petrol pumps in between the source and destination. The amount of petrol at station i is P[i] (1≤i≤N). Filling the vehicle’s petrol tank takes K mins. Find the minimum time in which we can reach B.
Hint: 2D DP
Round 3 (Technical Interview, 1.25 hours):
The interviewer took a look at my resume and asked some questions from it. Then he gave me a DSA question.
Given an array with N elements, with some values, we’ve to select exactly X elements such that the sum of values is maximised. The constraint was that each subarray of size K should have atleast one element which is there in our selection of X items.
Solution Approach 1:
I started off with the brute force solution — iterate over all X sized subsets of the array and check whether atleast one element is used from each K sized subarray and return the required answer.
Time Complexity: O(2^N*N²)
Solution Approach 2:
Soon I realised that if I had the solution for it’s subproblems, I could formulate the complete solution. So I thought of a 2D DP where dp[i][j] denotes the maximum sum of values if I choose to select the ith index in my subset and have exactly j elements in my subset. Then my final answer would be max(dp[i][X], (1≤i≤N).
Time Complexity: O(N*X*K)
I discussed the solution with the interviewer and then I was given 10 minutes to code up the solution.
Round 4 (HR + Technical Interview, 1.25 hours):
The interviewer started off by asking me about my interests, hobbies, etc. He asked me about my strengths and USPs as well.
Then, he asked some basic questions about OOP and DBMS —
>Basic 4 concepts of OOP and their examples
>Run-time polymorphism and virtual functions
>Use of abstract classes
>Indexing and it’s use
>B-Trees and B+Trees and their implementation
Then, I was given another DSA question:
There are N bananas in city A, and another city B at a distance of D from city A. We’ve to transfer maximum number of bananas from A to B. The only mode of transport is an elephant which has a max capacity C. The elephant eats CR bananas per unit distance. (The elephant can leave the leave the bananas mid-way and pick them up later)
I used a sample test to get the basic idea of how to approach the question and then generalised the result. The idea was to let the elephant carry C bananas for every journey and put them at an intermediate distance x, return back and carry the rest of the bananas to x. Since the elephant needs bananas to move, 2*CR*x ≤ C for all trips where he has to make a round trip and CR*x ≤ C for the last trip. Using this information, we can find x and thus the number of bananas (say N’) the elephant can carry till point x. The problem f(N, D) is then reduced to f(N’, D-x) and we can use recursion to solve the problem.
And that was it! After an hour or so, I was told that I was hired as a summer intern in Media.net.
A huge credit of bagging this internship goes to Team Demux — a group of dedicated and knowledgable mentors who helped me strengthen my concepts throughout the 2019 summer break. My family and friends also played an important role as they supported me throughout the internship process.
Overall, the interview experience was a great one and I learned a lot from it.