Round 1
Questions: A hiker is planning a multi-day trek through the mountains. There are trails, each with a certain length, given as a list, trails, that need to be hiked in the order in the list. The hiker wants to achieve a new world record by completing the trek in record number of days. Each day, the hiker will cover at least one trail and must minimize the sum of the lengths of the longest trail hiked each day. Find this minimum sum.
Example: There are n = 6 trails with lengths trails= [10, 5, 9, 3, 8, 15] and record = 2.
One optimal solution is for the hiker to cover the first trail on the first day, and the remaining trails on the second day. On the first day, the longest trail is 10, and on the second day, it is max(5, 9, 3, 8, 15) = 15. The sum of the lengths of the longest trails is 10 +15 = 25. Return 25.
Function Description
Complete the function efficientTrek in the editor below.
efficientTrek has the following parameters:
- int trails[]: an array of integers denoting the order and length of the trails.
- int record: the number of days to cover all the trails.
Returns
int: the minimum sum of the longest trails on each day
Constraints
- 1 ≤ n ≤ 300
- 1 ≤ record ≤ n ≤ 300
- 1 ≤ trails[i] ≤ 10^5
public static int efficientTrek(int[] trails, int record) { int n = trails.length; long[][] dp = new long[n + 1][record + 1]; long INF = (long) 1e18; for (int i = 0; i <= n; i++) { Arrays.fill(dp[i], INF); } dp[0][0] = 0; long[][] mt = new long[n][n]; for (int i = 0; i < n; ++i) { mt[i][i] = trails[i]; for (int j = i + 1; j < n; ++j) { mt[i][j] = Math.max(mt[i][j - 1], trails[j]); } } for (int j = 1; j <= record; ++j) { for (int i = 1; i <= n; ++i) { for (int k = 0; k < i; ++k) { dp[i][j] = Math.min(dp[i][j], dp[k][j - 1] + mt[k][i - 1]); } } } return (int) dp[n][record]; }
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Round 2
Questions: There is a dual core processor with one process queue for each core. There are n processes, where the time to process the ith process is denoted by time[i] (1 ≤ i ≤ n). There is a latch that helps decide which process is processed by which core. Initially, the first core has the latch. Suppose the latch is currently with the cth core, where c is either 1 or 2, and the ith process needs to be assigned. Then one of the following operations must be performed:
- The ith process assigned to the core c and the latch is given to the other core.
- The ith process is assigned to the other core, and the latch is retained by the core c.
The aim of each core is to have a maximum sum of time of processes with them for better performance. So, while assigning the ith process, the core with the latch decides the operation to be performed such that the total sum of time of processes assigned to it is maximized after all the processes are assigned.
Find the sum of the time of processes assigned to the first and second cores if both the cores work optimally. Return an array of two integers, where the first integer is the sum of the time of processes assigned to the first core, and the second integer is the aim of the time of processes assigned to the second core.
Example
Given n = 5 and time = [10,21,10,21,10].
Hence, the total time of processes for the first core is (21+10+21)=52, and the total time of processes for the second core is (10 +10) = 20. The given assignment is not optimal as for the 4th process, the 2nd core assigned the process with process time = 21 to core 1 and got the 5th process with process time = 10, which is not an move by core 2. The optimal move by the 2nd core would have been to assign the 4th process to itself and the 5th process to core, this would have given the total process time to the 2nd core = 31, which is better than 20.
An optimal assignment is shown.
Hence, the total time of processes for the first core is (10 + 21 + 10) = 41, and the total time of processes for the second core is (10 + 21) = 31.
Return the answer array, [41, 31].
Function Description
Complete the function getProcessTime in editor below.
getProcessTime has the following parameter:
- int time[n]: the processing time required for each process
Return
long[2]: the sums of processing times of the first and second cores
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ time[i] ≤ 10^9
public static List<Long> getProcessTime(List<Integer> time) { int n = time.size(); long[][] dp = new long[n][2]; for (long[] row : dp) { Arrays.fill(row, Long.MIN_VALUE); } return calculateResult(time, dp, n); } private static List<Long> calculateResult(List<Integer> time, long[][] dp, int n) { long sum = time.stream().mapToLong(Integer::longValue).sum(); long ans = f(0, 0, time, dp, n); return Arrays.asList((sum + ans) >> 1, (sum - ans) >> 1); } private static long f(int i, int dff, List<Integer> time, long[][] dp, int n) { if (i == n) return 0L; if (dp[i][dff] != Long.MIN_VALUE) { return dp[i][dff]; } long res; if (dff == 0) { res = Math.max(f(i + 1, 0, time, dp, n) - time.get(i), f(i + 1, 1, time, dp, n) + time.get(i)); } else { res = Math.min(f(i + 1, 1, time, dp, n) + time.get(i), f(i + 1, 0, time, dp, n) - time.get(i)); } dp[i][dff] = res; return res; }
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Round 3
Questions: A company will launch a series of marketing campaigns over several weeks. Each campaign has a certain cost. They want to launch at least one campaign every week, and to plan the campaigns in a way that minimizes the total weekly input. The weekly input is the maximum cost of any campaign planned in that week. Given the cost of the campaigns in a list, costs, and the number of weeks, find the minimum sum of weekly inputs that can be achieved with optimal planning, the campaigns must be organized in the same order in which they appear in the list costs.
For example, say there are n = 5 campaigns, with costs = [1000, 500, 2000, 8000, 1500] and weeks = 3. The company can organize the first campaign in the first week, the second campaign in the second week, and the remaining campaigns in the third week. The sum of weekly inputs in this planning is 1000 + 500 + max(2000, 8000, 1500) = 9500, which is the minimum possible input. Return 9500.
Function Description
Complete the function minimumWeeklyInput in the editor below.
minimumWeeklyInput has the following parameters:
- int costs[n]: the order and cost of the campaigns
- int weeks: the number of weeks to organize all the campaigns
Returns
int: the minimum possible overall weekly input
Constraints
- 1 ≤ n ≤ 300
- 1 ≤ weeks ≤ n ≤ 300
- 1 ≤ costs[i] ≤ 10^5
public int minimumWeeklyInput(List<Integer> costs, int weeks) { int n = costs.size(); long[][] dp = new long[n + 1][weeks + 1]; long INF = (long) 1e18; for (int i = 0; i <= n; i++) { Arrays.fill(dp[i], INF); } dp[0][0] = 0; for (int w = 1; w <= weeks; ++w) { for (int i = 1; i <= n; ++i) { long maxCostInWeek = 0; for (int k = i; k > 0; --k) { maxCostInWeek = Math.max(maxCostInWeek, (long) costs.get(k - 1)); if (dp[k - 1][w - 1] != INF) { dp[i][w] = Math.min(dp[i][w], dp[k - 1][w - 1] + maxCostInWeek); } } } } return (int) dp[n][weeks]; }
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.