Sumo Logic | Interview experience | YOE: 3y 10m

Round 1

Questions: There is a skating rink, and the skating coach is preparing for a special session with their students. There is a straight line, and there are N distinct points along this line with coordinates x1, x2, ... , xn. The coach wants to place M cones along this line on these points (M <= N) to create a challenging skating course for their students. The coach wants to ensure that the students have enough space to showcase their skills and learn new tricks. To achieve this, the coach needs to place the cones in such a way that the minimum distance between any two cones is maximized. In other words, the coach wants to create a course that maximizes the space available for students to skate freely without risking collisions. Your task is to help the skating coach find the optimal placement for the cones, such that the minimum distance between any two cones is as large as possible.

Test case 1: M = 3
Arr = {1,2,8,4,9}
Output = 3
{1,4,8} & {1,4,9} can be the combinations

Test case 2:
M = 3
Arr: {1,5,8,4,9,12,19}
Output: 8
{1,9,19}

I was able to come up with the right approach, below code is giving me correct output but when I uncomment below lines, the output are 2 and 3 for test case 1 and 2 respectively. Any help would be appreciated.

//   if(prevIndex != -1 && dp[currIndex][prevIndex][m] != -1){
//     return dp[currIndex][prevIndex][m];
//   }

#include <bits/stdc++.h>
using namespace std;

int maxMinDist = INT_MIN;
int findAllSubsequences(vector<int>& nums, int currIndex, int prevIndex, int minDistTillNow, int m, vector<vector<vector<int>>>& dp){
  
  if(currIndex >= nums.size()){
    if(m == 0)
      maxMinDist = max(maxMinDist, minDistTillNow); 
    return minDistTillNow;
  }
  if(m == 0){
      maxMinDist = max(maxMinDist, minDistTillNow);
      return minDistTillNow;
  }
//   if(prevIndex != -1 && dp[currIndex][prevIndex][m] != -1){
//     return dp[currIndex][prevIndex][m];
//   }
  int noTake = findAllSubsequences(nums, currIndex+1, prevIndex, minDistTillNow, m, dp);
  if(prevIndex != -1){
    int dist = nums[currIndex] - nums[prevIndex];
    minDistTillNow = min(minDistTillNow, dist);
  }
  int take = findAllSubsequences(nums, currIndex+1, currIndex, minDistTillNow, m - 1, dp);
  
//   cout<<"prevIndex-> "<<prevIndex<<endl;
  if(prevIndex != -1){
      return dp[currIndex][prevIndex][m] = max(take, noTake);
  }
  return max(take, noTake);
}

// To execute C++, please define "int main()"
int main() {
  auto words = { "Hello, ", "World!", "\\n" };
  for (const char* const& word : words) {
    cout << word;
  }
  vector<int> nums = {1,5,8,4,9,12,19};
  int n = nums.size();
  sort(nums.begin(), nums.end());
  int m = 3;
  vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(n+1, vector<int>(m+1, -1)));
  findAllSubsequences(nums, 0, -1, INT_MAX, m, dp);
  cout<<maxMinDist<<endl;
  return 0;
}

Time Complexity: O(NNM)