[Hard] interview questions #16

[rygh4775]

[rygh4775]

Description

Pick up maxSum, but no adjacent index.

Sample Inputs

• {30, 15, 60, 75, 45, 15, 15, 45}
• {75, 105, 120, 75, 90, 135}
• {40, 60, 45, 15}

Expected Outputs

• 180 ({30, 60, 45, 45})
• 300 ({75, 120, 135})
• 85 ({40, 45})

Solutions

1: Recursive

int maxMinutes(int[] massages) {
  return maxMinutes(messages, 0);
}

int maxMinutes(int[] masseages, int index) {
  if (index >= messages.length) {
    return 0;
  }

  int bestWith = masseages[index] + maxMinutes(masseages, index + 2);

  int bestWithout = maxMinutes(massages, index + 1);

  return Math.max(bestWith, bestWithout);
}

Call stacks

message length: 5

(0)
  (2)
    (4)
      (6)
      (5)
    (3)
      (5)
      (4)
        (6)
        (5)
  (1)
    (3)
      (5)
      (4)
        (6)
        (5)
    (2)
        (4)
          (6)
          (5)
      (3)
        (5)
        (4)
          (6)
          (5)

• Complexity: N is the length of input array
  • Time: O(N²)
  • Space: O(N)
  • Call stack

2: Recursive + Memoization

int maxMinutes(int[] massages) {
  int[] memo = new int[massages.length];
  return maxMinutes(messages, 0);
}

int maxMinutes(int[] masseages, int index, int[] memo) {
  if (index >= messages.length) {
    return 0;
  }

  if (memo[index] == 0) {
    int bestWith = masseages[index] + maxMinutes(masseages, index + 2);
    int bestWithout = maxMinutes(massages, index + 1);
    memo[index] = Math.max(bestWith, bestWithout);  
  }

  return memo[index];
}

• Complexity: N is the length of input array
  • Time: O(N)
  • Space: O(N)
  • Call stack + memoization table size

3: Iterative: w/o call stack

0	1	2	3	4	5	6	7
30	15	60	75	45	15	15	45

• best(7)
  • best(7) + best(9) = 45
  • best(8) = 0
• best(6)
  • best(6) + best(8) = 15
  • best(7) = 45
• best(5)
  • best(5) + best(7) = 60
  • best(6) = 15
• best(4)
  • best(4) + best(6) = 90
  • best(5) = 60
• ...
• best(0)
  • best(0) + best(2) = 180
  • best(1) = 150

int maxMinutes(int[] massages) {
  int[] memo = new int[messages.length + 2];
  memo[massages.length] = 0;
  memo[massages.length + 1] = 0;

  for(int i = memo.length; i >= 0; i--) {
    int bestWith = messages[i] + memo[i+2];
    int bestWithout = messages[i+1];
    memo[i] = Math.max(bestWith, bestWithout);
  }

  return memo[0];
}

• Complexity: N is the length of input array
  • Time: O(N)
  • Space: O(N)
  • memoization table size

4: Iterative: w/o call stack + memoization

int maxMinutes(int[] massages) {
  int[] memo = new int[messages.length + 2];
  memo[massages.length] = 0;
  memo[massages.length + 1] = 0;
  int oneAway = 0;
  int twoAway = 0;

  for(int i = memo.length; i >= 0; i--) {
    int bestWith = messages[i] + twoAway;
    int bestWithout = oneAway;
    int current = Math.max(bestWith, bestWithout);
    twoAway = oneAway;
    oneAway = current;
  }

  return oneAway;
}

• Complexity: N is the length of input array
  • Time: O(N)
  • Space: O(1)