Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
void reverse(vector<int> &v, int start, int end) {
if(v.size() < (end - start)) return;
for(;start < end; start++, end--) {
std::swap(v[start], v[end]);
}
}
void rotate(vector<int> &v, int k) {
reverse(v, 0, k-1);
reverse(v, k, v.size() - 1);
reverse(v, 0, v.size() - 1);
}
#include<iostream>
#include<vector>
using namespace std;
void Rotate( char * , int );
int main()
{
char Arr[] = {'A' , 'B' , 'C' , 'D' , 'E' };
vector<char> v(Arr , Arr+5);
//Can do it for 3 or any rotations
for( int k = 2 ; k < v.size() ; k++ )
{
cout << v[k];
}
for( int j=0 ; j<2 ; j++ )
{
cout << v[j];
}
}
public int[] rotate(int[] given, int index) {
int l = given.length;
int[] res = new int[l];
for (int i = 0; i < l; i++) {
if (i >= index) {
res[i - index] = given[i];
} else {
res[l - index + i ] = given[i];
}
}
return res;
}
<pre lang="" line="1" title="CodeMonkey79477" class="run-this">//Working java code to solve this problem
package com.arrayRotation;
class RotationOfArray {
public RotationOfArray(){
//Do nothing
}
private static void initialize(char arr[]){
char start= 'A';
for(int i=0;i<arr.length;i++){
arr[i] = start;
++start;
}
}
public static void main(String[] args){
char[] initArray = new char[5];
int rotationIndex=2;
initialize(initArray);
rotate(initArray,rotationIndex);
for(int i=0;i<initArray.length;i++){
System.out.print(initArray[i]+ " ");
}
}
public static void rotate(char arr[],int rotationIndex){
//First reverse the array completely
reverse(0,arr.length-1,arr);
//reverse the last rotation index length of the array
reverse(arr.length-rotationIndex,arr.length-1,arr);
//finally reverse first array length - rotation index
reverse(0,arr.length-rotationIndex-1,arr);
}
private static void reverse(int start, int end,char arr[]){
char temp;
while(start<end)
{
temp = arr[start];
arr[start]= arr[end];
arr[end]=temp;
++start;
--end;
}
}
}
</pre><pre title="CodeMonkey79477" input="yes">
</pre>
Good solution nish:
Just to add more thought to your code. The reverse can be implemented in a recursive way also i guess.
Note; These are just random hacks to improve the efficiency of the code.
void reverse(int start, int end, char *arr)
{
if(start < (start+end)/2) return;
{
char temp = arr[end - start];
arr[end-start] = arr[start];
arr[start] = temp;
// maybe use XORing between arr[end-start] and arr[start] to avoid temp as well
reverse(start+1, end, arr);
}
}
<pre lang="" line="1" title="CodeMonkey72464" class="run-this">import java.util.Arrays;
public class Rotation
{
public static void main(String[] args)
{
String[] array = {"A", "B", "C", "D", "E"};
int rotateBy = 30;
rotate(array, rotateBy);
System.out.println(Arrays.toString(array));
}
private static void rotate(String[] array, int rotateBy)
{
rotateBy = (array.length + rotateBy) % array.length;
String num = array[0];
for (int i = 1; i <= array.length; i++)
{
int j = (rotateBy * i) % array.length;
String oldNum = num;
num = array[j];
array[j] = oldNum;
}
}
}</pre><pre title="CodeMonkey72464" input="yes">
</pre>
#include<stdio.h>
#include<stdlib.h>
void main()
{
int i, j, n, index, next;
int a[10], b[10];
printf("\nEnter n\n");
scanf("%d" ,&n);
printf("\nEnter the items\n");
for(i = 0; i < n; i++)
scanf("%d" ,&a[i]);
printf("\nEnter the index\n");
scanf("%d" ,&index);
for(i = index, j = 0; i < n; i++, j++)
b[j] = a[i];
next = j;
for(i = 0, j = next; i < index; i++, j++)
b[j] = a[i];
printf("\nRotated items are as follows\n");
for(i = 0; i < n; i++)
printf("%d\t", b[i]);
//system("pause");
}
void Rotate(int[] arr, uint offset)
{
if (offset == 0 || arr == null || arr.Length == 0)
return;
int len = arr.Length;
for (int i = 0; i <= (len - 1) % offset; ++i)
{
int prevVal = arr[i]; // temporary value to store current value
int curIndex = i;
do
{
curIndex = (curIndex + offset) % len;
int curVal = a[curIndex];
a[curIndex] = prevVal;
prevVal = curVal;
} while (curIndex != i);
}
}
#include<stdio.h>
void reverse(char *t,int start,int end)
{
while(start<end)
{
*(t+start)^=*(t+end);
*(t+end)^=*(t+start);
*(t+start)^=*(t+end);
start++;
end--;
}
}
int main()
{
char src[6]="ABCDE";
int rind;
printf("Enter an rotate index for %s: ",src);
scanf("%d",&rind);
reverse(src,0,strlen(src)-1);
reverse(src,0,rind-1);
reverse(src,rind,strlen(src)-1);
printf("%s",src);
getch();
return 0;
}
1.for j=index;j<array_length;j++
2. i = j-1;
3. while(i>=0)
4. exchange a[i]<--->a[i+1]
5. i = i -1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class CircularArrayTest {
public static void main(String[] args) {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String input = null;
int index = 0;
System.out.print("Enter Inputs: ");
try {
input = bf.readLine();
System.out.println("Enter index : ");
bf = new BufferedReader(new InputStreamReader(System.in));
index = Integer.parseInt(bf.readLine());
} catch (IOException e) {
e.printStackTrace();
}
char[] array = input.toCharArray();
if (index > 0) {
if ((array.length % 2 == 0) && (array.length / 2 == index - 1)) {
for (int i = 0; i < index - 1; i++) {
char temp = array[i];
array[i] = array[index + i - 1];
array[index + i - 1] = temp;
}
} else {
int n = array.length;
int x = 0;
char temp1 = 0;
char temp2;
int count = 0;
int y = 0;
int i = 0;
do {
if (x >= (index - 1)) {
y = (x + 1 - index);
} else {
y = (n + x + 1 - index);
}
temp2 = (x == i) ? array[x] : temp1;
temp1 = array[y];
array[y] = temp2;
x = y;
count++;
if (x == i) {
x++;
i = x;
}
} while (count != n);
}
}
for (char string : array) {
System.out.print(string + " ");
}
}
}
static void Main(string[] args)
{
int p = 9;
Console.Write("My Name ");
char[] Arr = { 'A', 'B', 'C', 'D', 'E' };
Display(Arr);
const int RotateByVal = 2;
for (int i = 0; i < RotateByVal; i++)
{
shiftLeft(Arr);
}
Console.WriteLine("------------------------");
Display(Arr);
}
private static void shiftLeft(char[] Arr)
{
if (Arr.Length > 1)
{
char Temp = Arr[0];
int i = 0;
for (i = 1; i < Arr.Length; i++)
{
Arr[i - 1] = Arr[i];
}
Arr[i - 1] = Temp;
}
}
private static void Display(char[] Arr)
{
foreach (char c in Arr)
{
Console.Write(c);
}
}
#include<iostream>
#include<vector>
using namespace std;
void Rotate( char * , int );
int main()
{
char Arr[] = {'A' , 'B' , 'C' , 'D' , 'E' };
vector<char> v(Arr , Arr+5);
//Can do it for 3 or any rotations
for( int k = 2 ; k < v.size() ; k++ )
{
cout << v[k];
}
for( int j=0 ; j<2 ; j++ )
{
cout << v[j];
}
}
#include<iostream>
#include<vector>
using namespace std;
void Rotate( char * , int );
int main()
{
char Arr[] = {'A' , 'B' , 'C' , 'D' , 'E' };
vector<char> v(Arr , Arr+5);
//Can do it for 3 or any rotations
for( int k = 2 ; k < v.size() ; k++ )
{
cout << v[k];
}
for( int j=0 ; j<2 ; j++ )
{
cout << v[j];
}
}
#include<iostream>
#include<vector>
using namespace std;
void Rotate( char * , int );
int main()
{
char Arr[] = {'A' , 'B' , 'C' , 'D' , 'E' };
vector<char> v(Arr , Arr+5);
//Can do it for 3 or any rotations
for( int k = 2 ; k < v.size() ; k++ )
{
cout << v[k];
}
for( int j=0 ; j<2 ; j++ )
{
cout << v[j];
}
}
#include<iostream>
#include<vector>
using namespace std;
void Rotate( char * , int );
int main()
{
char Arr[] = {'A' , 'B' , 'C' , 'D' , 'E' };
vector<char> v(Arr , Arr+5);
//Can do it for 3 or any rotations
for( int k = 2 ; k < v.size() ; k++ )
{
cout << v[k];
}
for( int j=0 ; j<2 ; j++ )
{
cout << v[j];
}
}
#include<iostream>
#include<vector>
using namespace std;
void Rotate( char * , int );
int main()
{
char Arr[] = {'A' , 'B' , 'C' , 'D' , 'E' };
vector<char> v(Arr , Arr+5);
//Can do it for 3 or any rotations
for( int k = 2 ; k < v.size() ; k++ )
{
cout << v[k];
}
for( int j=0 ; j<2 ; j++ )
{
cout << v[j];
}
}
#include<iostream>
#include<vector>
using namespace std;
void Rotate( char * , int );
int main()
{
char Arr[] = {'A' , 'B' , 'C' , 'D' , 'E' };
vector<char> v(Arr , Arr+5);
//Can do it for 3 or any rotations
for( int k = 2 ; k < v.size() ; k++ )
{
cout << v[k];
}
for( int j=0 ; j<2 ; j++ )
{
cout << v[j];
}
}
#include<iostream>
using namespace std;
void Rot( int *A ,int size , int k)
{//1 ,2,3,4,5
for (int i=0 ; i<k ; i++ )
{
int t = A[0];
for( int j=0 ; j<(size-1) ; j++ )
{
A[j] = A[j+1];
}
A[size-1] = t;
}
for (int l=0 ; l<size;l++ )
cout << A[l];
}
int main()
{
int A[] = {1,2,3,4,5};
Rot(A , 5 , 2 );
return 0;
}
~
public class ReverseArrayFromIndex {
public static void main(String[] args) {
char a[] = { 'a', 'b', 'c', 'd', 'e' };
int rotateIndex = 5;
int beg = 0;
int end = a.length - 1;
if(rotateIndex >= a.length){
System.out.println("enter index within range");
System.exit(0);
}
a = swap(a, beg, end);
a = swap(a, beg, rotateIndex);
a = swap(a, rotateIndex+1, end);
for (int i = 0; i <= end; i++) {
System.out.print(a[i]);
}
}
public static char[] swap(char a[], int beg, int end) {
while (beg < end) {
char temp = a[beg];
a[beg] = a[end];
a[end] = temp;
beg++;
end--;
}
return a;
}
}
static void Main(string[] args)
{
char[] a = { 'a', 'b', 'c', 'd', 'e' };
int n = a.Length;
Array.Resize<char>(ref a, a.Length + 2);
int len = 0;
for (int i = 1; i >= 0; i--)
{
a[a.Length - 1 - len] = a[i];
len++;
}
for (int k = 0; k < a.Length - 2; k++)
{
a[k] = a[k+2];
}
Array.Resize<char>(ref a, a.Length - 2);
}
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
namespace ConsoleApplication3
{
class Program
{
static void Main(string[] args)
{
char[] a = { 'a', 'b', 'c', 'd', 'e' };
int n = a.Length;
int val = 2;
Array.Resize<char>(ref a , n + val);
int j = 0;
for (int i = n; i < a.Length; i++)
{
a[i] = a[j];
j++;
}
for (int i = 0; i < a.Length - val; i++)
{
a[i] = a[i + val];
}
Array.Resize<char>(ref a, n);
}
}
}
Good solution nish:
Just to add more thought to your code. The reverse can be implemented in a recursive way also i guess.
Note; These are just random hacks to improve the efficiency of the code.
void reverse(int start, int end, char *arr)
{
if(start < (start+end)/2) return;
{
char temp = arr[end - start];
arr[end-start] = arr[start];
arr[start] = temp;
// maybe use XORing between arr[end-start] and arr[start] to avoid temp as well
reverse(start+1, end, char * arr);
}
}
Group 1: A B
- Anonymous November 11, 2011Group 2: C D E
{A B C D E} = { Group 1, Group 2}
Reverse Group 1 = {B, A}
Reverse Group 2 = {E, D, C}
Reverse {Group 1', Group 2'} = {C, D, E, A, B}