## Microsoft Interview Question for Software Engineer Interns

Team: Lync
Country: United States

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

This is array rotation question.
wwwDOTgeeksforgeeks.org/array-rotation/

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

Here are the possible solutions:

Solution #1 (brute force)
1. temp = first element of array
2. Shift all the remaining array elements left by 1
3. last element of array = temp
4. Continue for n steps
Time complexity: O(n * k)

Solution #2 (with a temp array)
1. Copy the first n bits to a temp array.
2. Move the remaining arrayLength - n bits to front
3. Copy the temp array to the end
Space complexity: O(k), Time complexity: O(n)

Solution #3 (with reverse):
FrickinHamster solution - reverse the strings. But reversing a string takes O(n) and this will need 3 reverse. Good but not the best.

Solution #4 (most efficient solution and I think the interviewer is looking for this one)
Circular left shift the entire array with each element moved to right position at first iteration itself. This will utilize mod operation to compute next position. I could explain more, but the following link does a far better job. Time Complexity: O(k) Best case, O(n) average case

stackoverflow.com/questions/11893053/circular-left-shift-of-an-array-by-n-positions-in-java

PS: k = number of elements, n = array length

Comment hidden because of low score. Click to expand.
0

``````(shift_by_x + index_of_digit)%size_of_array will do right shifting by x

100 200 300 400
shift by 2
so output should be         300  400 100 200
so let's see how this formula works for 300
index_of_300 is 2
shift_by_x = 2
so     (2+2)%4 = 0 and which is right.``````

Comment hidden because of low score. Click to expand.
0

Solution 4 is clever, but if you count all assignments and arithmetic operations (+, - %), it does not perform better than double-swapping solution. Besides, the logic behind solution 4 makes implementing it is more difficult than implementing double-swapping solution.

Comment hidden because of low score. Click to expand.
0

@Anonymous - Swapping is far more costlier since it involves actual data movement compared to just integer arithmetic operations. Here for example, we considered data to be int, but in real scenarios, it could be documents, videos, anything. So, each swap matter. 4th solution has a best case of O(k), which is more efficient than reversing the elements which is O(3*n).
(k = number of elements to be shifted, n = array length)

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

Here is my algorithm :
Consider you have an array which can be split into A( first N elements), B( remaining array)
1. Reverse the first n elements in the array.
2. Reverse the elements n+1 to end of the of the array.
3. Reverse the whole array once.

Eg : say you have an Array [1, 2, 3, 4, 5 ,6, 7,8,9,10]

say n = 3 meaning 3 elements have to copied to end of the array. expected output is [4,5,6,7,8,9,10,1,2,3]

1) we will have [3,2,1,4,5,6,7,8,9,10]
2) we will have [3,2,1,10,9,8,7,6,5,4]
3) we will have [4,5,6,7,8,9,10,1,2,3] => expected output

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

``````public class ReversefirstNuNUmbers {
public static void main(String[] args) {
int a[] = { 2, 12, 8, 6, 5, 1, 2, 10, 3, 2 };
reverseArray(a,3);
display(a);

}

public static void display(int a[]) {
for (int a1 : a) {
System.out.print(a1 + ",");
}
}

public static void reverseArray(int a[],int count)
{
for (int i=0;i<count;i++) {

int temp=a[i];
a[i]=a[a.length-i-1];
a[a.length-i-1]=temp;;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Hi Ravi, your solution is incorrect, your code directly swaps the first n numbers with the last n numbers, the result is "2, 3, 10, 6, 5, 1, 2, 8, 12, 2," while the expected result should be 6, 5, 1, 2, 10, 3, 2, 2, 12, 8

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

``````#include <stdio.h>
#include <stdlib.h>

main()
{
int a = {1,2,3,4,5,6,7,8,9,0},*ptr,i,j,n;

ptr = malloc(10*sizeof(int));

printf("enter how many no's wish to push\n");
scanf("%d",&n);

//copying last 10-n into ptr//

for(i=n,j=0;i<10;i++,j++)
{
*(ptr+j) = a[i];
}

//copying first n into ptr //

for(i=0,j=10-n;i<n;i++,j++)
{
*(ptr+j) = a[i];
}

for(i=0,j=0;i<10,j<10;i++,j++)
{
a[i] = *(ptr+j);
}

for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}

printf("\n");
free(ptr);
}``````

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

``````public static void moveToEnd(int[] a, int n){
int[] temp = new int[a.length];
for(int i = 0; i < a.length; i++){
temp[i] = a[i];
}
for(int i = 0; i < a.length - n; i++){
a[i] = temp[i + n];
}

int j = 0;
for(int i = a.length - n; i < a.length; i++){
a[i] = temp[j];
j++;
}
}``````

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

if n element has does not have to maintain the same order, this might work.

``````void move(int arr[], int n)
{
// if n is less than or equal to 5 we swap first n elem with last n elements
// if n is greater than 5, we swap first 10 - n elements with the last (10-n) elements

if (n >= 10 || n < 0) return;

int j = 10 - 1;
int numSwaps = n <= 5 ? n : 10 - n;

for (int i = 0; i < numSwaps; i++, j--)
{
swap(&arr[i], &arr[j]);
}
}``````

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

public static void ReverseArray()
{
int[] arr= new int[] {1,2,3,4,5,6,7,8,9,10};
int[] Temparr= new int;
int n;
Console.WriteLine("Enter no of element to be reverse <10");

for (int i = 0; i < arr.Length; i++)
{
if ((i + 1) <= n)
{
Temparr[i] = arr[i];
}
else
{
break;
}
}
Console.WriteLine("element is going to reverse");
foreach (var item in Temparr)
{
Console.Write(item +",");
}
//shifting the reamning array1
for (int i = n; i < arr.Length; i++)
{
arr[i - n] = arr[i];

}
Console.WriteLine("After shifting");
foreach (var item in arr)
{
Console.Write(item + ",");
}

//shifting the reamning array2
int loc= arr.Length -n;

for (int i = 0; i < n; i++)
{
arr[loc]=Temparr[i];
loc++;
}

Console.WriteLine("After All");
foreach (var item in arr)
{
Console.Write(item + ",");
}

}

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

I am not going to swift the array element but I have solution to get the expected output

New_index=Index+(10-num_of_swift) % 10

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

``````#include <stdio.h>

int main(void) {
int array [] = { 1, 2, 3, 4, 5, 6, 7, 8, 9};

int prev, next;

int k = sizeof (array)/sizeof (array);
int n = 4;

int i = 0;
int j = 0;

prev = array ;

for (;;)
{
j = (i + n) % k;

next = array [j];
array [j] = prev;

prev = next;
i = j;

if (j == 0)
break;
}

for (i = 0; i < k; i++)
printf ("%d, ", array [i]);

return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Forgot to mention, this has O(n) complexity and O(1) space usage.

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

private static void moveToRight(int [] array, int n){

for( int i =0 ; i< array.length - n; i++){
int tmp = array[i];
array[i] = array[i + n ];
array[i+n] = tmp;
}

}

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

``````// Left shift the array in O(n) with O(1) space.

public static void leftShift(int[] array, int n) {
int temp;
int len = array.length;
for (int i = 0; i < n; i++) {
temp = array[len - n + i];
array[len - n + i] = array[i];
array[i] = array[n + i];
array[n + i] = temp;
}
}``````

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

``````static int[] moveNelements(int[] array, int n) {

for (int i = 0; i < n; i++) {

int temp = array[n];
array[n++] = array[i];
array[i] = temp;
if (n == array.length) break;
}
return array;``````

}

Simple swappings

Comment hidden because of low score. Click to expand.
-1
of 1 vote

The suggested method takes O(n) time for reversing the elements..

In java, we can use subList method of ArrayList class. I guess it takes constant time...

``````List<Integer> list1 = list.subList(0, 4);
list = list.subList(4, 9);

Can anyone confirm ?

Comment hidden because of low score. Click to expand.
0

The interviewer is definitely not looking for this answer! This is an algorithm question, not C# /Java language skill-set :)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

p://msdn.microsoft.com/ru-ru/library/he2s3bh7(v=vs.110).aspx

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Array rotation is inefficient as its complexity is O(n*n). I suggest you hould try place swaping with n and 10-n. In that case complexity is only O(n)

Comment hidden because of low score. Click to expand.
0

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.

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