you have array with n elements. How would you do circular shift of k positions? Time and space complexity?

Question

sarah · Accepted Answer

alright - 
http://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position

shiftArray( theArray, M ):
    size = len( theArray )
    assert( size > M )
    reverseArray( theArray, 0, size - 1 )
    reverseArray( theArray, 0, M - 1 )
    reverseArray( theArray, M, size - 1 )

O(n) with no extra storage. Wish I could have thought of that one myself...

sarah · Answer

oh, sorry, I misunderstood. Not k values, move everything k positions. Praveen Chettypally's answer works but the space complexity would be O(n) since there is a fully copy of the list?

The simplest would probably be to make another array and copy in, starting at the (n-k)th element, going to the end, then starting at the beginning. A second array would probably be a better option than a completely different data structure. 

What if it has to be done in place? is there an O(n) solution?

Praveen Chettypally · Answer

Make a circular linklist, and move headpointer K position to do K shifts. It's O(n) time complexity. Space is contant. (circular link list).

sarah · Answer

Well, space isn't constant because you took an array and then copied it somehow to a linked list. Remember, you were given an array? 

If I understand the question correctly, they're asking to do a circular shift of some range of values, like the first k values in an array of length n? So if you wanted to shift right, 

temp = array[k]
from index=k to 1
   array[index] = array[index-1]
array[0] = temp

this would be O(k)? I mean, it would take k steps, but maybe it's somehow still O(n)

CortexCompiler · Answer

I beieve this does the trick too:

    public static String shiftArray(char[] inputArray, int shiftLen)
    {
        assert(inputArray != null);
        int length = inputArray.length;
        assert(length > shiftLen);
        
        int moves = 0, from= 0, to = 0;
        char next, last;

        to = (from + shiftLen) % length;
        next = inputArray[from];
        
        while(moves < inputArray.length)
        {
            last = inputArray[to];
            inputArray[to] = next;
            
            next = last;
            from = to;
            to = (from + shiftLen) % length;
            
            moves++;
        }
        return String.valueOf(inputArray);
    }

ovymura · Answer

I tried the above function - shiftArray and the looks is not working:

shiftItemsFromList class:

class shiftItemsFromList{

    public static String shiftArray(char[] inputArray, int shiftLen)
    {
        assert(inputArray != null);
        int length = inputArray.length;

        assert(length > shiftLen);

        int moves = 0, from= 0, to = 0;
        char next, last;

        to = (from + shiftLen) % length;
        next = inputArray[from];

        while(moves < inputArray.length)
        {
            last = inputArray[to];
            inputArray[to] = next;

            next = last;
            from = to;
            to = (from + shiftLen) % length;

            moves++;
        }
        return String.valueOf(inputArray);
    }

}


Part of the main function:

        System.out.println("Circle Shift N size array for M possitions:");

        char [] array = {'a', 'b', 'c', 'd', 'e', 'f'};

        shiftItemsFromList sh = new shiftItemsFromList();

        String s = sh.shiftArray(array, 2);
        
        System.out.println("Print the Circle Shift N size array: " + s);

        System.out.println("DONE");

OUTPUT: 

Circle Shift N size array for M possitions:
Print the Circle Shift N size array: cbadaf
DONE

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas