Question: Walmart, Recently asked On-Campus Assessments in IITs, November, 2022 | Unique Element Problem | Crayon Box

Entering edit mode

Avg CTC: 18lpa

Location: Bangalore, Chennai

Job Roles: Java Developer, Software Engineers

Job Link: Software Engineering Roles

Question 1

Unique Element Problem

Click here to Practice

1.1 1.2

Question 2

Crayon Box

Click here to Practice

2.1 2.2 2.3

ADD COMMENT • link

Entering edit mode

Crayon Box is a repeated Question. Previously asked for Sprinklr. Checkout the solution below.

Solution Link Here: Crayon Box

ADD COMMENT • link 2.1 years ago Rohit • 610

Entering edit mode

Q1 seems like a dp problem t1 = a[i] + max[i+1][j] + (sum[i+1][j] +dp[i+1][j]) t2 = a[j] + max[i][j-1] + (sum[i][j-1] +dp[i][j-1]) dp[i][j] = max (t1,t2) answer = dp[1][n]

ADD COMMENT • link 2.1 years ago Sahil • 40

Entering edit mode

Question 1: Unique Element Problem

Overview

We are given an array of size N. The array's power represents the sum of the values you obtain after performing the said operations for N times. Our task is to delete the array by performing these operations and print the maximum value of the power that can be obtained after the array is completely deleted.

Approach

Here, first, we have to find out the maximum value for every i and j, i.e., for every subarray, and store that in an array so that we can get the maximum value in O(1) time, and after that, we have to perform Dynamic Programming.
For the DP approach, we have two choices, either to take the first or the last element, so simply, we will recur for both the first and last element and return the maximum of both.

Pseudocode

int x = ((a[i] * turn) + maxarr[i][j]) + func(i + 1, j, a, turn + 1);
int y = ((a[j] * turn) + maxarr[i][j]) + func(i, j - 1, a, turn + 1);
return dp[i][j] = max(x, y);

Complexity

Time Complexity: O(N^2), N is the size of the array.

ADD COMMENT • link 2.0 years ago Akash 240