Microsoft Interview Question
Senior Software Development EngineersCountry: India
Interview Type: Phone Interview
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;
}
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
}
}
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);
}
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
//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();
}
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;
}
}
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));
}
#!/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
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();
}
Say length of string=n
- X June 02, 2015rotate 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.