Microsoft Bisect interview question

bisect.cpp

#include <vector> 
#include <iostream> 

#define PASSED  0 
#define FAILED  1 

using namespace std; 

int bisect(const vector<int> &v, int l, int r) {
  
  if (r >= l) {
    int mid = l + (r - 1) / 2; 

    // Check left
    int val = v[mid]; 
    if (val == PASSED) {
      // if the node directly to the right of this node is a failed, then we
      // found our failed commit
      // Current one passed. 
      int right = mid + 1; 
      // Make sure we are in bounds
      if (right < v.size()) {
        int rightVal = v[right]; 
        if (rightVal == FAILED) {
          // We found the swtich! return it. 
          return right; 
        } 
      } 
      // Current one passed, so we need to go on the right side now. 
      return bisect(v, mid + 1, r); 

    } else {
      // Current on didn't pass. 
      // If we look the left of this one, and we found a PASSED, then our
      // current id is the culprit. 
      int left = mid - 1; 
      if (left >= 0) {
        int leftVal = v[left]; 
        if (leftVal == PASSED) {
          // We found it! 
          return mid; 
        } 
      } 
      return bisect(v, l, mid -1); 
    } 
  } 

  return -1; 
} 

int main() {

  // In this case, I am requiring that there be a "bit flip", i,e, a 0 must be
  // changed to a 1 somewhere
  vector<vector<int>> testCases{
      {PASSED},  // invalid case, -1
      {FAILED} , // invalid case, -1 
      {PASSED, FAILED}, 
      {PASSED, FAILED, FAILED}, 
      {PASSED, PASSED, FAILED} , 
      {PASSED, PASSED, FAILED, FAILED, FAILED, FAILED} 
  }; 

  vector<int> answers {
      -1, // if everything passes then we return -1
      -1,
       1, 
       1, 
       2, 
       2
  };

  for (int i = 0; i < testCases.size(); i++) {

    int result = bisect(testCases[i], 0, testCases[i].size() - 1); 
    if (result != answers[i]) {
      cout << "FAILED: Expected " << answers[i] << " but got " << result << " instead! " << endl;
      return -1; 
    } 
  } 

  return 0; 
}