Microsoft Interview Question
Software Engineer in TestsCountry: Ireland
Interview Type: Written Test
This method traverses the string twice. The extra traversal can be avoided. While reversing the whole string, maintain a flag isNormal and flip it at every word. If it is true, push the characters into a stack and pop them. This prints the words in normal order and reduces the time complexity (of course, extra space of largest word is needed).
@arun_lisieux: we don't even need any flag also.
I/P: I am a software programmer
A. Start from end i.e. 'programmer'.Print the last word.
B. Start reversing the alternate words. So you would reverse 'software' & 'am'.For reversing words just use stacks or whatever you want.
So output:
"programmer erawtfos a ma I"
@aka
We would need some kind of variable (flag or boolean or integer) to keep track of alternate elements, right? I'm not aware of a method without this. If you know of a method, kindly post it.
@aka,
I think i agree with the above comment. We will need a counter or a single flag atleast.
Alternate between stack and queue to get it done using 1 iteration
char* zizag(char array[], int length) {
char* new_array = (char *)malloc(sizeof(char*(length + 1)));
int i,j = -1, flag = 1;
Stack s;
Queue q;
for(i = length-1;i>=0;i--) {
if (array[i] != ' ') {
if (flag)
push(q,array[i]);
else
enqueue(q,array[i]);
} else {
if (flag) {
while(isnotempty(q))
new_array[++j] = pop(q);
flag = 0;
} else {
while(isnotempty(q))
new_array[++j] = dequeue(q);
flag = 1;
}
new_array[++j] = ' ';
}
}
mew_array[length] = '\0';
return new_array;
}
Here's some code that works perfectly, and doesn't touch StringBuilder nor StringBuffer:
/*Write a program to reverse a sentence in a zigzag order.
i/p: I am a software programmer
o/p: programmer erawtfos a ma I*/
public class ZigZag {
public String reverse(String str){
String inter = "";
String newstr = "";
for(int i = str.length() - 1; i >= 0;i--){
inter = inter + str.charAt(i);
}
String[] arr = inter.split(" ");
for(int i = 0; i < arr.length;i++){
if(i%2==0){
String word = arr[i];
for(int j = word.length()-1; j>=0;j--){
newstr += word.charAt(j);
}
newstr += " ";
}else{
newstr += arr[i] + " ";
}
}
System.out.println(newstr);
return newstr;
}
public static void main(String[] args){
String in = "I am a software programmer";
ZigZag z = new ZigZag();
z.reverse(in);
}
}
package test;
public class ZigZagReverse {
public static void main(String[] args) {
String input[] = { "zig", "zag", "reverse", "string" };
ZigZagReverse zigZagReverse = new ZigZagReverse();
for (int i = 0; i < input.length; i++) {
String s = input[i];
input[i] = zigZagReverse.reverse(s, i);
}
zigZagReverse.displayOutput(input);
}
/* method to display the output */
private void displayOutput(String[] output) {
for (int i = 0; i < output.length; i++) {
System.out.print(output[i] + " ");
}
}
/* method to reverse a string */
private String reverse(String s, int i) {
int start, end;
char temp;
if (i % 2 == 0) {
char array[] = s.toCharArray();
start = 0;
end = array.length - 1;
while (start < end) {
temp = array[start];
array[start] = array[end];
array[end] = temp;
start++;
end--;
}
s = new String(array);
}
return s;
}
}
How about this?
public class ZigZagReverse {
public static void main(String[] args) {
String input = "I am a software programmer";
String[] parts = input.split("\\s");
for (int i = 0; i < parts.length; i++) {
if (i % 2 == 0)
System.out.println (parts[parts.length-1-i]);
else
System.out.println (new StringBuilder(parts[parts.length-1-i]).reverse());
}
}
}
Here is the simple code in Python which does the purpose:
def ZigZagReverse(input_string):
lst = input_string.split(' ')
start_index = len(lst) - 2
for index in range(start_index, -1, -2):
lst[index] = lst[index][::-1]
print " ".join(lst)
if __name__ == '__main__':
input_string = "I am a software programmer"
ZigZagReverse(input_string
Above code will have minimum amount of traversals :)
#include<stdio.h>
#include<string.h>
void main()
{
char str[100],new[100];
int len,k=0;
printf("enter string\n");
scanf("%[^\n]s",str);
len=strlen(str);
int i,j,prev=len-1,flag=0;
for(i=prev;i>=0;i--)
{
if(str[i]==' '|| i==0)
{
if(flag==0)
{
for(j=prev;j>=i;j--)
{
new[k++]=str[j];
}
flag=1;
}
else
{
if(i==0) i--;
for(j=i+1;j<=prev+1;j++)
{
new[k++]=str[j];
}
flag=0;
}
prev=i-1;
}
}
for(i=0;i<k;i++)
printf("%c",new[i]);
}
C#
string sentence = "I am a software programmer";
string zigZag = string.Empty;
int i = 0;
foreach (var word in sentence.Split(' ').Reverse())
{
if (i % 2 == 0)
{
zigZag += word + " ";
}
else
{
zigZag += string.Join(string.Empty, word.Reverse()) + " ";
}
i++;
}
Probably better to use StringBuilder object instead of appending to strings but you get the gist
#include<stdio.h>
#include<string.h>
#include<conio.h>
int main()
{
int nf,i,j;
char str[]={"I am a software programmer"},temp;
strrev(str);
printf("%s\n",str);
nf=0;///next front
while(str[nf]!='\0')
{
i=nf;
j=i;
while((str[j]!=' ')&&(str[j]!='\0'))
j++;
nf=j+1;
j--;
printf("i=%c j=%c nf=%c\n",str[i],str[j],str[nf]);
getch();
while(i<j)
{
temp=str[i];
str[i]=str[j];
str[j]=temp;
i++;
j--;
}
}
printf("%s",str);
getch();
}
void ReverseZigZag(char str[])
{
int len=strlen(str),i=0,j=-1,temp,k;
bool toggle=1;
i=0,j=len-1;
while(i<j)
{
swap(str[i],str[j]);
++i;
--j;
}
len=strlen(str),i=0,j=-1,temp,k;
while(i<len)
{
if(str[i]==' ' && toggle==0) {toggle=1;j=i;}
else if(str[i]==' ' && toggle)
{
temp=i;
k=i-1;
++j;
while(j<k)
{
swap(str[j],str[k]);
++j;
--k;
}
j=temp;
toggle=0;
}
++i;
}
cout<<str<<endl;
}
namespace ZigZagReverseString
{
class Program
{
public static void ZigZagReverse(string str)
{
char[] charArray = str.ToCharArray();
int j = 0;
for(int i = 0, k=-1; i< charArray.Length; i++)
{
if(charArray[i] != ' ')
{
i++;
}
else if (charArray[i] == ' ' && ++k % 2 == 0)
{
ReverseHelper(charArray, j, i - 1);
j = i + 1;
}
else
{
j = i + 1;
}
}
string strng = new string(charArray);
}
public static void ReverseHelper(char[] chrArray, int start, int end)
{
while (start < end)
{
char tmp = chrArray[end];
chrArray[end] = chrArray[start];
chrArray[start] = tmp;
start++;
end--;
}
}
static void Main(string[] args)
{
ZigZagReverse("this string should be reversed zigzag");
}
}
}
Hi guys!, here another simple solution for this problem
string zigzagorder(string str){
vector<string> words=vector<string>(0);
int idxfirst=0;
int idxspace = str.find(" ");
int zigzag = 1;
string tmpword;
while ( idxspace >= 0){
tmpword = str.substr(idxfirst , idxspace) ;
if ( (zigzag++)%2 == 0 )
reverse( tmpword.begin(), tmpword.end() );
words.push_back( tmpword);
str=str.substr(idxspace+1);
idxspace = str.find(" ");
}
if (str[0]== ' ')
str=str.substr(1);
if ( (zigzag)%2 == 0 )
reverse( str.begin(), str.end() );
words.push_back(str);
int i;
str="";
for (i=words.size()-1; i >= 0 ; i--)
str=str+words[i]+" ";
str=str.substr(0,str.size()-1);
return str;
}
namespace ZigZag
{
class Program
{
static void Main(string[] args)
{
String s = "I Am a Software Programmer";
String[] sp = s.Split(' ');
Console.WriteLine(s);
for (int i = sp.Length -1; i >= 0; i--)
{
if (i % 2 == 0)
{
Console.Write(sp[i].ToString() + " ");
}
else
{
for (int j = sp[i].Length - 1; j >= 0; j--)
{
Console.Write(sp[i].ToString()[j]);
}
Console.Write(" ");
}
}
}
}
}
namespace ZigZag
{
class Program
{
static void Main(string[] args)
{
String s = "I Am a Software Programmer";
String[] sp = s.Split(' ');
Console.WriteLine(s);
for (int i = sp.Length -1; i >= 0; i--)
{
if (i % 2 == 0)
{
Console.Write(sp[i].ToString() + " ");
}
else
{
for (int j = sp[i].Length - 1; j >= 0; j--)
{
Console.Write(sp[i].ToString()[j]);
}
Console.Write(" ");
}
}
}
}
}
Like suggested by many it will be good to keep a boolean value to track alternate reversals.
Here is a working code in java:
public static String Reverse(String words) {
char[] letters = words.toCharArray();
letters = ReverseLetters(letters, 0, letters.length - 1);
String l = new String(letters);
System.out.println(l + "\n");
int start = 0;
int end = 0;
boolean isReversed = true;
while (end < letters.length) {
if ((letters[end] == ' ' || letters[end] == letters.length - 1)) {
if (isReversed) {
letters = ReverseLetters(letters, start, end - 1);
start = end + 1;
isReversed = false;
} else {
start = end + 1;
isReversed = true;
}
}
end++;
}
if (isReversed) {
letters = ReverseLetters(letters, start, end - 1);
}
return new String(letters);
}
private static char[] ReverseLetters(char[] letters, int start, int end) {
while (start < end) {
char temp = letters[end];
letters[end] = letters[start];
letters[start] = temp;
start++;
end--;
}
return letters;
}
#include<stdio.h>
#include<string.h>
char * reverse(char s[],int ,int);
void swap(char *a,char *b)
{
char t=*a;
*a=*b;
*b=t;
}
int main()
{
char str[]="I am a software programmer";
int len=strlen(str);
int prev=0;
int i;
char *s=reverse(str,0,len);
printf("%s",s);
int b=1;
for(i=0;i<=len;i++)
{
if((str[i]==' '||str[i]=='\0')&&(b==1))
{
reverse(s,prev,i);
prev=i+1;
b=!b;
}
}
printf("\n%s",s);
return 0;
}
char * reverse(char str[],int s,int e)
{
int i=s;
int j=e-1;
while(i<j)
{
swap(&str[i],&str[j]);
i++;
j--;
}
return str;
}
# Approach:
# a) Use stack for keeping track of alternate words and reversing them
# b) Uses a boolean to keep track of even and odd words
# Assumptions:
# a) There is only one space char between words
# Boundary conditions tested:
# a) Empty string
# b) Null
# c) proper data type
# d) Strings of length 0,1,2
# e) Unicode handling
def zigzag(string):
"""zigzag reversal of the given string."""
if string is None or len(string) in [0,1,2]:
return string
if not isinstance(string, str):
return 'Invalid data type passed for reversal'
string = string.encode('utf-8')
even = True
stack = []
output = []
i = len(string) - 1
while i >= 0:
while i >= 0 and string[i] != ' ':
if even:
stack.append(string[i])
else:
output.append(string[i])
i -= 1
else:
even = False if even else True
if stack:
while stack:
output.append(stack.pop())
if i >= 0:
output.append(' ')
i -= 1
return ''.join(output)
print zigzag('I am a software programmer')
1) Reverse the whole string from start to end and you get the this output.
- jayram singh June 09, 2013"remmargorp erawtfos a ma I"
2) Reverse the individual words at odd locations, we get the below string.
"programmer erawtfos a ma I"