## Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.home.careercup;

public class InsertionSortForInversionCounting {

public static void main(String[] args) {
final int a [] = {3,3,3,3};
System.out.println(inversionCount(a));
}

/*
find number of positions any element moves forward during
sorting using selection sort.
This is not the most optimal.
Other faster  ( O(n log (n)) methods are possible ( hint: divide and conquer)
*/
static int inversionCount(int arr[]) {
int n = arr.length;
int forwardMoves = 0;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;

while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
forwardMoves++;
}
arr[j + 1] = key;
}
return forwardMoves;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

x ==> value at index
i ==> index
abs(i-x) ==> each index off by this much value when the numbers are sorted

(Sum of all abs(i-x) )/2 ==> number of intersections (divide by 2 bcos each intersection is counted twice)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.