Amazon Interview Question: you have array with n element... | Glassdoor.ie

Interview Question

Software Engineer Interview Dublin, Co. Dublin

you have array with n elements. How would you do circular

  shift of k positions? Time and space complexity?
Tags:
algorithm
Answer

Interview Answer

6 Answers

2

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).

Praveen Chettypally on 11 Jan 2011
1

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)

sarah on 23 Jan 2011
2

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?

sarah on 23 Jan 2011
2

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 on 23 Jan 2011
0

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

CortexCompiler on 6 Mar 2011
0

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

ovymura on 8 Aug 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.