Microsoft Interview Question for Senior Software Development Engineers

Country: India
Interview Type: Phone Interview

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

Say length of string=n
rotate by=k

for all indexes i from 0 -> (n-1)
if (i<k) newIndex = n - 1 - i;
else newIndex = i -k;

This will be very simple if saving first substring (k-length) into a temp string.
Also simple, if we can copy to a new string.

If needs to happen in place w/o extra space, do the 3 string reverse operations..
one for String[0..k-1], second String[k..n-1] and third on the resulting string of 1,2 operations.

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

The solution to this problem is outlined by Jon Bentley in Programming Pearls, Column 2. The idea is that the amount of characters to rotate acts as if your string was divided into two blocks, A and B, such that the original string is AB and you wish to turn it into BA.

The elegant way to do it is with reverse(reverse(A) + reverse(B)). This is time- and space-efficient.

Out of curiosity, here's a small interesting excerpt of that Column: Brian Kernighan and P. J. Plauger used precisely this code in their 1981 Software Tools in Pascal to move lines within a text editor. Kernighan reports that it ran coorectly the first time it was executed, while their previous code for a similar task based on linked lists contained several bugs.

In place, O(n) solution, ready with a main() to run your own tests:

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

void reverse(char *str, size_t begin, size_t end) {
while (begin < end) {
end--;
char tmp = str[begin];
str[begin] = str[end];
str[end] = tmp;
begin++;
}
}

void left_rotate(char *str, size_t amt) {
size_t str_sz = strlen(str);
amt %= str_sz;
reverse(str, 0, amt);
reverse(str, amt, str_sz);
reverse(str, 0, str_sz);
}

static char input_buf[512];
int main(void) {
printf("Enter a string and a value to rotate it left.\n");
printf("> ");

while (scanf("%s", input_buf) == 1) {
size_t amt;
scanf("%zu", &amt);
left_rotate(input_buf, amt);
printf("%s\n", input_buf);
printf("> ");
}

return 0;
}``````

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

In JAVA:
If we are allowed to use substring() method of string class, then following can be useful: -

int n=3;
String str= "helloworld";
String l = str.substring(0,n);
String r = str.substring(n);
System.out.println(r+l);

=== Output
loworldhel

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

``````static public String rotateString(String input, int times) {
StringBuilder sb = new StringBuilder();
int len = input.length();

for (int i = 0; i < len; i++) {
if (i < times)
sb.append(input.charAt(i));
else
sb.insert(i-times, input.charAt(i));
}

return sb.toString();
}``````

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

``````class Rev
{
public static char[] Reverse(char[] arr, int left, int right)
{

char temp;

while(left != right && left <= right)
{
temp = arr[left] ;
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
return arr;
}
public static void main(String args[])
{
String str = "George";
int n = 3;
char[] s = str.toCharArray();
char[] s1 = Reverse(s,0,n-1);
char[] s2 = Reverse(s1,n,s1.length-1);

System.out.println(Reverse(s1,0,s1.length-1));
//Output is rgeGeo
}
}``````

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

Outer For Loop: O(n)
Inner For Loop: O(k) where k is constant
Total: O(nk) == O(n)

``````int main()
{
char str[8] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g' };
int i, j, k, temp, n;
k = 3; //rotation factor
n = 7; //String Length

printf("Before Rotation: %s\n", str);

for (i = 0; i < n - k; i++)
{
for (j = i + k; j > i; j--)
{
temp = str[j];
str[j] = str[j - 1];
str[j - 1] = temp;
}
}
printf("After Rotation: %s\n", str);
}``````

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

Running time: O(nk). O(1) space overhead. Ruby implementation:

``````def rotate(array, n)
return [] if array.nil?
return array if n <= 0 || array.length==0 || n % array.length == 0

store_index=array.length-1

(0...n).to_a.reverse.each do |element_index|
for iter in (element_index...store_index)
swap(array, iter,iter+1)
end

store_index -= 1
end

array
end

def swap(array, first_index, second_index)
array[first_index]=array[first_index]^array[second_index]
array[second_index]=array[first_index]^array[second_index]
array[first_index]=array[second_index]^array[first_index]
array
end``````

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

//Left rotation of a string by N number of times;

#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<stdio.h>
void main()
{
clrscr();
int n;
char str [40];
cout<<"\n Enter the string: \n";
gets(str);
cout<<"\n How many times do yhou want to left rotate the string? \n";
cin>>n;

if(n%4 == 0)
puts(str);
if(n%4 == 1)
{
for(int i = 0; i< strlen(str); i++)
{
putchar(str[i]);
cout<<"\n";
}

}
if(n%4 == 2)
{
for(int i = strlen(str); i>=0; i--)
{
putchar(str[i]);
}
}
if(n%4 == 3)
{
for(int i = strlen(str); i>=0; i--)
{
putchar(str[i]);
cout<<"\n";
}

}
getch();
}

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

var rotate=function(str , n)
{
var res="";
var length=str.length;
if(n>length)
n=Math.floor( (n%length));
var from=length-n;
for(var i=from;i<length;i++)
{
res=res+str[i];
}
for(var i=0;i<from;i++)
{
res=res+str[i];
}
return res;

}

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

var rotate=function(str , n)
{
var res="";
var length=str.length;
if(n>length)
n=Math.floor( (n%length));
var from=length-n;
for(var i=from;i<length;i++)
{
res=res+str[i];
}
for(var i=0;i<from;i++)
{
res=res+str[i];
}
return res;

}

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

``````var rotate=function(str , n)
{
var res="";
var length=str.length;
if(n>length)
n=Math.floor( (n%length));
var from=length-n;
for(var i=from;i<length;i++)
{
res=res+str[i];
}
for(var i=0;i<from;i++)
{
res=res+str[i];
}
return res;``````

}

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

``````var rotate=function(str , n)
{
var res="";
var length=str.length;
if(n>length)
n=Math.floor( (n%length));
var from=length-n;
for(var i=from;i<length;i++)
{
res=res+str[i];
}
for(var i=0;i<from;i++)
{
res=res+str[i];
}
return res;

}``````

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

For (i>=k)
{
move to i-k
}

for (i<k)
{
move to (n-k+i)
}

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

``````bool is_rotation ( string a , string b ) {

if (a.length() != b.length() ) {

return false;

}

else {

char first_letter = a[0];
int index;

for (int i=0; i<a.length(); i++) {

if (b[i] == first_letter) {

index=i;
}
}

int j=0;

for ( j=0;j<a.length() - index; j++) {

if ( a[j]  == b[j+index] ) {

}

else {

return false;

}
}

for (int k=0; k<index; k++ ) {

if (b[k] == a[k+j]) {

}

else {

return false;
}
}

return true;

}
}``````

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

public static void RotateString(string myString,int times)
{
char[] myChar = myString.ToArray();
List<char> lst = new List<char>();

int firstStringCount= myChar.Count() - times;

for (int i = firstStringCount; i < myChar.Count(); i++)
{
}
for (int i = 0; i < firstStringCount; i++)
{
}
lst.ForEach(s=>Console.Write(s));
}

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

``````#!/usr/bash
# Psudo:
#-- 1. Print (with no \n) the inputString.substring(offset, (len-offset))
#-- 2. Calculate remaining chars 'Wrapped_Len' starting from index 0
#-- 3. Print append inputString.substring(0, Wrapped_Len)

STR=\$1
OFFSET=\$2
if [[ \${#STR} = 0 ]]; then echo "Invalid input" exit 1; fi
else
if [[ \$OFFSET = 0 ]]; then echo "Rotating right for \`\$STR\` starting pos \$OFFSET is \$STR"
else
LEN=\${#STR}
TRAILING=\$(( \$LEN - \$OFFSET ))
LEFTWRAP=\$(( \$LEN - \$TRAILING ))
echo -n "Rotating right for \`\$STR`\ starting pos \$OFFSET:   "
echo -n "\${STR:\$OFFSET}"
echo "\${STR:0:\$\$LEFTWRAP}"
fi
fi``````

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

``````// C#
string rotateLeft(string s, int n) =>
s.SubString(n % s.Length) + s.SubString(0, n % s.Length);``````

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

I think, we don't have to actually retate the string, we can just use index update to treat the string rotated for users, Here is one of the example

``````A <- Input String
Current Start index = 0, EndIndex = A.length``````

If user ask us to rotate the string left by 2, we can update the

``start_index to 2``

, and

``end_Index to 1``

, the next index calculation can be done with modulo operation. this code assume string as array of char, but will work fine with normal string variable as well.
Here is the complete set of the code in c#

``````private static void PrintWithRotation(string inputStr, int rotationCount, string rotationSide)
{
int length = inputStr.Length;
Console.WriteLine("Printing the input string with {0} {1} rotation", rotationCount, rotationSide);
rotationCount = rotationCount % length;
int startPoint = rotationSide == "left" ? rotationCount : length - rotationCount;
for(int i = startPoint;i<length;i++)
{
Console.Write(inputStr[i]);
}
for (int i = 0;i < startPoint;i++)
{
Console.Write(inputStr[i]);
}
Console.WriteLine();
}``````

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

``````public static void sort(int a[], int k) {
for (int i = 1; i < a.length-1; i++) {
if (a[i] > a[i + 1]) {
swap(a, i, i+k);
} else if (a[i - 1] > a[i]) {
swap(a, i, i-k);
}
}
}

private static void swap(int a[], int i, int k) {
int tmp = a[i];
a[i] = a[k];
a[k] = tmp;``````

}

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.