## Amazon Interview Question

SDE1s**Country:**United States

```
int k = 2;
void sort(int[] arr) {
int n = arr.length;
int[] idx = new int[n];
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
int delta = j - i;
int leftShift = idx[j] - delta;
int rightShift = idx[i] + delta;
if(arr[i] > arr[j] && ( Math.abs(leftShift) <= k ) ) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
idx[i] = leftShift;
idx[j] = rightShift;
}
}
}
```

}

```
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class App8 {
public static void main(String... arg) {
int[] ints = {7, 8, 11, 10, 13, 1, 3, 4, 6};
run(ints, 2);
System.out.println(Arrays.toString(ints));
}
public static void run(int[] arr, int k) {
Map<Integer, Integer> moveMap = new HashMap<>();
for (int i = 0, arrLength = arr.length; i < arrLength - 1; i++) {
int i1 = 0;
while (i1 <= k && arr[i - i1] > arr[i + 1 - i1]) {
int i2 = moveMap.getOrDefault(arr[i + 1 - i1], 0) + 1;
moveMap.put(arr[i + 1 - i1], i1);
int t = arr[i - i1];
arr[i - i1] = arr[i + 1 - i1];
arr[i + 1 - i1] = t;
i1 = i2;
}
}
}
}
```

Question not clear - a = [5, 2, 4, 3, 1], k = 2

- getPDat April 12, 2018Return [2, 3, 1, 4, 5]

Can you please provide some more example?