Pergunta de entrevista da empresa Spire Global
The second question asks you to refactor a function in O(n^2) and make it O(n), basically by eliminating the nested for-loop.
This is the function you're asked to refactor:
int solution(int *A, int N) {
int result = 0;
int i, j;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (A[i] == A[j])
if (abs(i - j) > result)
result = abs(i - j);
return result;
}
Respostas da entrevista
Tried a few different angles that weren't working and ultimately ran out of time without a working solution.
int better_solution(int *A, int N)
{
int result = 0;
std::map nums;
for (int i = 0; i result)
{
result = distance;
}
}
}
return result;
}
This seems simple. The function is basically trying to find the largest difference between any two members of the array. Well, the largest difference would be the difference between the largest member of the array and the smallest member of the array. Thus, you just find the max and min and return abs(max - min).
i.e.
int solution(int *A, int N) {
int result1 = 0;
int result2 = 0;
int i;
for(i = 0; i result2) {
result2 = A[i];
}
}
return abs(result2 - result1);