9 weeks ago

John 910

Hyderabad

Avg stipend per month: 40,000 - 50,000rs

Location: Bangalore

Job Role: 2023 Summer Internship

Job Link: Apply here for the internship role

Question 1

Given an array arr of size n, you have to apply the following operation(s): Take a subarray of size k. If this subarray is odd, you have to choose the minimum element in it and if the subarray is even, you have to choose the maximum element (i.e., subarray 0123....k-1 is the first odd subarray and 123...k is the first even subarray and so on). Apply the same operations on this array of selected numbers until a single element is left.

Example

arr = {9,10,19,14,11} and k=3

After first operation, arr = {9,19,11}

Then arr={9}

Constraints:

• n <= 1e5

Question 2

There are n students, each needing arr[i] for a project they are going to make. They are paired into m inclusive-pairs (a student may appear in more than a single pair). You are the VP of a startup and you have to fund these pairs. There are q queries and you have to answer the maximum number of students you can fund with the amount q[j]. If a student has been previously received funds as part of another pair, they won't be funded again.

5 months ago

srijansriv • 20

Islāmpur

Question 1

I tried something for the first question here:

https://appp.me/CeU7kP

I believe the time complexity would be around O((nlogn)logn). Please correct me if I'm wrong. E: i think the time complexity is wrong and should be O(n*nlogn). The solution provided is just an implementation used on the leetcode question:

https://leetcode.com/problems/sliding-window-maximum/description/