Cisco | SDE-2 | OA | 2 yr exp

Round 1

Questions:

1. It was a basic sliding window easy question. Able to complete in 10 min.

2. Coin Change (but we need to find maximum number of coins instead of minimum) Problem Statement
   You are given an integer target and an array of integers arr[]. Your task is to find the maximum number of elements from the array that can sum up to exactly match the target. Each element in the array can be used only once.
   If it's not possible to form the target using any combination of elements, return 0.
   Note: No constraints were given, whether the target or elements in the array can be negative, this caused some confusion.

   This looks like a basic coin change problem, with a slight modification.

   Code:

   int solve(const vector<int>& coins, int amount, int index, vector<vector<int>>& memo) {
       if (amount == 0) {
           return 0;
       }
       if (amount < 0 || index >= coins.size()) {
           return -1;
       }
   
       if (memo[index][amount] != -2) {
           return memo[index][amount];
       }
   
       int maxWithSkipping = solve(coins, amount, index + 1, memo);
       int maxWithIncluding = solve(coins, amount - coins[index], index + 1, memo);
       if (maxWithIncluding != -1) {
           maxWithIncluding += 1; 
       }
   
       int result = max(maxWithSkipping, maxWithIncluding);
       memo[index][amount] = result;
       return result;
   }
   
   int maxElements(const vector<int>& coins, int amount) {
       vector<vector<int>> memo(coins.size() + 1, vector<int>(amount + 1, -2));
       int result = solve(coins, amount, 0, memo);
       return result == -1 ? 0 : result;
   }

   This looks pretty ok, but the weird thing was that if I remove the dp array, 9/12 cases were passing, and if I use it, only 3 were passing. This led to believe negative values might be allowed. So how would we tackle this question if negative array values or negative target was allowed?

3. Problem Statement
   Given 4 Jugs namely [J1, J2, J3, J4] with capacities [C1, C2, C3, C4] and initial water content as [S1, S2, S3, S4].
   Determine how many steps are needed to achieve the final state of [F1, F2, F3, F4] by transferring water from one jug to another without losing any water.
   Constraints:

   1.  0 < Ci <= 500 for each i: [1,4]
   2.  0 < Si, Fi <= Ci for each i: [1,4]
   3.  Sum(Si) = Sum(Fi)

   Input:

   • Total number of entries = 13
   • First line specifies the number of entries in the array, which is 12 in our case
   • Next 4 lines contain the capacities of the 4 jugs
   • Next 4 lines contain the initial content of the 4 jugs
   • Next 4 lines contain the final content of the 4 jugs

   Output:
   The minimum number of steps required to reach Final State (F) from Initial State (S).
   Return -1 if not possible.

   Example:
   C = [12, 13, 12, 10]
   Initial = [6, 6, 0, 0]
   Final = [12, 0, 0, 0]
   Output: 1

   Tried doing this using BFS, but unable to complete the solution.