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.

- X June 02, 2015 | Flag Reply
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;
}

- 010010.bin June 02, 2015 | Flag Reply
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

- Pancuz June 09, 2015 | Flag Reply
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();
    }

- Miroslav June 16, 2015 | Flag Reply
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
 }
}

- liju.leelives June 17, 2015 | Flag Reply
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);
}

- dreamer June 17, 2015 | Flag Reply
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

- Yev June 23, 2015 | Flag Reply
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();
}

- singh.chakresh August 03, 2015 | Flag Reply
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;

}

- Anonymous August 30, 2015 | Flag Reply
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;

}

- YONI August 30, 2015 | Flag Reply
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;

}

- YONI August 30, 2015 | Flag Reply
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;

}

- YONI August 30, 2015 | Flag Reply
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)
}

- pc April 08, 2016 | Flag Reply
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;

}
}

- saurabhinorange October 13, 2016 | Flag Reply
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++)
{
lst.Add(myChar[i]);
}
for (int i = 0; i < firstStringCount; i++)
{
lst.Add(myChar[i]);
}
lst.ForEach(s=>Console.Write(s));
}

- Neelavan April 07, 2017 | Flag Reply
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

- hurricanemark January 07, 2018 | Flag Reply
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);

- lucidio July 26, 2019 | Flag Reply
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();
}

- sonesh June 05, 2015 | Flag Reply
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;

}

- gopaldk June 05, 2015 | Flag Reply


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