Created
March 30, 2020 23:58
-
-
Save AcidLeroy/761799a1bc3e70ad620fb195e289a065 to your computer and use it in GitHub Desktop.
Microsoft Bisect interview question
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment