Last active
April 29, 2016 07:21
-
-
Save satorusasozaki/d781105accdeb902980298a4e495f3fa to your computer and use it in GitHub Desktop.
Found some cases that the solution does not return the right answer in app academy practice problem 2-1 and tried to fix it. http://prepwork.appacademy.io/coding-test-2/practice-problems/
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
// The Original Problem Description | |
// # Write a function, `nearest_larger(arr, i)` which takes an array and an | |
// # index. The function should return another index, `j`: this should | |
// # satisfy: | |
// # | |
// # (a) `arr[i] < arr[j]`, AND | |
// # (b) there is no `j2` closer to `i` than `j` where `arr[i] < arr[j2]`. | |
// # | |
// # In case of ties (see example below), choose the earliest (left-most) | |
// # of the two indices. If no number in `arr` is larger than `arr[i]`, | |
// # return `nil`. | |
// # | |
// # Difficulty: 2/5 | |
// | |
// def nearest_larger(arr, idx) | |
// diff = 1 | |
// while true | |
// left = idx - diff | |
// right = idx + diff | |
// if (left >= 0) && (arr[left] > arr[idx]) | |
// return left | |
// elsif (right < arr.length) && (arr[right] > arr[idx]) | |
// return right | |
// elsif (left < 0) && (right >= arr.length) | |
// return nil | |
// end | |
// diff += 1 | |
// end | |
// end | |
// What I have found is that | |
// when a number which is greater than the number at the given index is found, | |
// the function immediately returns it without considering numbers left in the array | |
// though there might be numbers which are less than the number found earlier and | |
// greater than the number at the given value | |
// For example | |
// nearest_larger([2,4,3,8], 0) should return 2 because the nearest larger number of | |
// 2 at the index of 0 is 3 at the index of 2. However the solution function returns 1 where | |
// 4 is at because the function returns when it finds a number | |
// which is greater than the number at the given index for the first time | |
// So I have tried to fix the issue below. | |
// I made it to keep iterating through the whole array even after a number which is greater than | |
// the number at the given index is found. | |
#include <iostream> | |
#include <vector> | |
using namespace std; | |
int nearest_larger(vector<int> &array, int index) { | |
int result_index = 0; | |
int temp_index = 0; | |
bool found_one = false; | |
for (int i=0; i<array.size(); i++) { | |
if (i != index) { | |
if (array.at(index) < array.at(i)) { | |
temp_index = i; | |
if (!found_one) { | |
// if a number which is greater than the number at the given index | |
// for the first time | |
result_index = temp_index; | |
found_one = true; | |
} else { | |
// if at least a number which is greater than the number at the given index | |
// is already found, then need to compare it with upcoming numbers | |
// to determine the number at result_index is really a nearest larger number | |
if (array.at(temp_index) < array.at(result_index)) { | |
result_index = temp_index; | |
} | |
} | |
} | |
} | |
} | |
return result_index; | |
} | |
int main () { | |
vector<int> array = {2,4,3,8}; | |
cout << nearest_larger(array, 0) << endl; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment