Microsoft Interview Question
Software Engineer InternsTeam: Lync
Country: United States
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
(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.
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.
@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)
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
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;;
}
}
}
#include <stdio.h>
#include <stdlib.h>
main()
{
int a[10] = {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);
}
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]);
}
}
public static void ReverseArray()
{
int[] arr= new int[] {1,2,3,4,5,6,7,8,9,10};
int[] Temparr= new int[10];
int n;
Console.WriteLine("Enter no of element to be reverse <10");
n = Convert.ToInt16(Console.ReadLine());
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 + ",");
}
}
#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[0]);
int n = 4;
int i = 0;
int j = 0;
prev = array [0];
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;
}
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);
list.addAll(list1);
Can anyone confirm ?
This is array rotation question.
- truecool March 04, 2014wwwDOTgeeksforgeeks.org/array-rotation/