Google Interview Question for SDE1s


Country: United States




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

The question says at a position k from its actual positions.
So, assuming that we can take an extra array, we start traversing the array.
For element at 0th index we put, kth element.
Similarly for any index i, we find element at (i-k), (i+k) index. We put at that position the leat of the two nos. provided the element is greater or equal to the element at (i-1) index.

- srikantaggarwal January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Is each element *exactly* k positions from its actual position or *at most* k positions from its actual position? If the former, simple swapping suffices. If the latter, one method is to have a moving window of length k. Find the smallest element of this window and then move the window to the right. (Represent the window as a heap to do this efficiently.)

- nilkn January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Each number is at a distance of k from its original position -- this can only happen when we do only one swap of each position i with position i+k (conversely, i with i-k) . For example,
original numbers = [1, 2, 3, 4, 5, 6, 7, 8]. Then for k=2 we swap 1 and 3, 2 and 4, 5 and 7, 6, and 8. Final array would be [3, 4, 1, 2, 7, 8, 5, 6].

So, in the question we are given [3, 4, 1, 2, 7, 8, 5, 6] and we need to get back to original sorted array. So, we will do the same swap again and we will get back the original array (because swap is reversible).

- zahidbuet106 September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1

- dhs.du.08 September 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

There Can be two approaches both are easy ones.

First.
1. Insert K elements in heap
2. after that delete min and add new element
3.repeat till the end
complexity nlogk

Second
This one also provides nlogk but needs a better implementation of merge sort
1.divide array in n/k parts
2. sort those subparts O(klogk) time
3.Merge them from left

- saumya.tyagi6 January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Shankar:
Can you please give some example for this question?
I have some doubts regarding this question:
1) Output array will be fully sorted? in that case there will be only one possible position for each element in array, how can that be k from its initial position?
2) Is it possible that there is no solution of some given input?
3) Or output should be just each element should be k distance away from its initial position, but not sorted among themselves ?

- SK January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i am doubtful about first solution...are you using heap-sort.
what will be size of heap ..if i am understanding que properly ..then is it like below
0 --- n --> k+0 -->k+n-1
then we can apply simple sorting (k+intial_index,k+end)
?

- amit January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its not clear if this is in place sorting or can use a new Array. In any case, to get new position use (index + k) % N where index is the ith position in the array, k is the number to shift by and N is the size of the Array.

- mo January 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In my understanding, if we want to make sure all elements are shifted k distance, k and N must satisfy: (1) N >= 2k; (2) N % 2k == 0

For example:
input: 1, 2, 3, 4, 5, 6, 7, 8
N = 8, k = 3;

1. consider input[0], it can only be moved to input[3]; and only input[3] can be moved to input[0] to fill it; thus, they are going to be swapped.

2. situation 1 applies when input[i] < k; and after doing that, all first 2k numbers are sorted.
we get 4, 5, 6, 1, 2, 3, 7, 8
3. now we need to get into next segment 7, 8; it is clear that they can not be sorted. This is the reason for the 2 conditions mentioned in the beginning.

- lixiaobai February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

since each number is at a distance k from its actual position, there are an even number of elements and to sort all one has to do is swap.

Let N be the size of the array

The size of the array is at least 2k
for(int i=0; i<k; ++i)
swap(a[i], a[i+k]);

if(4k <= N)
for(int i=0; i<k; ++i)
swap(a[2k+i], a[2k+i+k]);

and so on till the end of the array , i.e., divide the array into blocks of size 2k,
and inside each block swap the elements which are at a distance of k

- tianyang19910112 March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

N has to be multiple of 2^K?
eg: 123456 does not have a solution if k=2
12345678 has a solution for k=2

- aditya.eagle059 February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More