Cisco 2+ years SDE Hackerrank OA

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

Q2.Coin Change(but we need to find maximum no 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, was able to write the below code for this :

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 wierd thing was that, if I remove the dp array 9/12 cases were passing, and if I use it, only 3 were passing.This leds to believe, negative values might be allowed. So how would we tackle this question if negative array values or negative target was allowed.

Q3.
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 eachi: [1,4]
3.  Sum(Si) = Sum(Fi)

Input:

Total number of entries = 13

1. First line specifies the number of entries in the array, which is 12 in our case

2. Next 4 lines contain the capacities of the 4 jugs

3. Next 4 lines contain the initial content of the 4 jugs

4. 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

How to approach Q2 and Q3 ? Thanks