CareerCup

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

Can you please provide some more example?

for (i=1; i < a.length; i++)
	c = i;	
	shift_cnt = K;
	while (a[c-1] > a[c] && c > 0 && shift_cnt > 0)
		swap(a[c-1] > a[c])
		c--;
		shift_cnt--;

a = [5, 2, 4, 3, 1]
k = 2
b = list(a)
a.reverse()
b = b + a
res = [b[i] for i in range(k - 1, len(b), k)]

print(res)

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

}

First sort the first K+1 elements.
Every element after the first K+1 elements, consider that and it's previous K elements and perform an insertion sort.

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