Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
#include "stdafx.h"
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
int count_crossings_after_sort(vector<int> in) // no depes aloud !
{
unordered_map<int, int> value_to_old_index;
for (int i = 0; i < in.size(); i++)
{
value_to_old_index[in[i]] = i;
}
sort(in.begin(), in.end());
int c = 0;
for (int i = 0; i < in.size() - 1; i++)
{
for (int j = i + 1; j < in.size(); j++)
{
if (value_to_old_index[in[i]] > value_to_old_index[in[j]])
{
c++;
}
}
}
return c;
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> in = { 3, 5, 2, 1 };
int r = count_crossings_after_sort(in);
return 0;
}
- Makarand September 12, 2017