Microsoft Interview Question for Software Engineer in Tests


Country: Ireland
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
5
of 7 vote

1) Reverse the whole string from start to end and you get the this output.

"remmargorp erawtfos a ma I"

2) Reverse the individual words at odd locations, we get the below string.

"programmer erawtfos a ma I"

- jayram singh June 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 6 votes

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 June 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

@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 June 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@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.

- arun_lisieux June 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@aka,
I think i agree with the above comment. We will need a counter or a single flag atleast.

- nutty June 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Time Pass June 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For :
push and pop, use variable 's'
enqueue and dequeue, use variable 'q'

- Time Pass June 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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);
	}
}

- veldisimo June 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

	}

}

- Nits June 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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());
        }
    }
}

- chisingh June 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 :)

- Badam Santhosh June 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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]);
}

- Anonymous June 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we have to use extra space, right? Can we do without it, by not introducing much complications?

- Anonymous June 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous June 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void reverseString(char str[]) {
int len =strlen(str);
int i = 0, j = len -1;
while (i<j) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}

- James June 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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();
}

- Anonymous June 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

voide Reverse(char sen[]);
int main()
{
Char sen[20];
gets(sen);
Reverse(sen);
printf(“the recersed sentence is:”);
puts(sen);
return 0;
}

- Anonymous June 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous June 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
        }
    }
}

- SRRK June 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Gab June 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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(" ");
}
}

}
}
}

- karthi G June 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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(" ");
}
}

}
}
}

- karthi G June 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Mz July 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- himanshu September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse a sentence using stack and queue without changing the place of punctuation marks in c/c++
example : hello ! how are you ?
you ! are how hello ?

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse a sentence using stack and queue without changing the place of punctuation marks in c/c++
example : hello ! how are you ?
you ! are how hello ?

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse a sentence using stack and queue without changing the place of punctuation marks in c/c++
example : hello ! how are you ?
you ! are how hello ?

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse a sentence using stack and queue without changing the place of punctuation marks in c/c++
example : hello ! how are you ?
you ! are how hello ?

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse a sentence using stack and queue without changing the place of punctuation marks in c/c++
example : hello ! how are you ?
you ! are how hello ?

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse a sentence using stack and queue without changing the place of punctuation marks in c/c++
example : hello ! how are you ?
you ! are how hello ?

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse a sentence using stack and queue without changing the place of punctuation marks in c/c++
example : hello ! how are you ?
you ! are how hello ?

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse a sentence using stack and queue without changing the place of punctuation marks in c/c++
example : hello ! how are you ?
you ! are how hello ?

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse a sentence using stack and queue without changing the place of punctuation marks in c/c++
example : hello ! how are you ?
you ! are how hello ?

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse a sentence using stack and queue without changing the place of punctuation marks in c/c++
example : hello ! how are you ?
you ! are how hello ?

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

reverse a sentence using stack and queue without changing the place of punctuation marks in c/c++
example : hello ! how are you ?
you ! are how hello ?

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# 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')

- Galileo December 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

What if the input is:

I am a software programmer too

Should the output be:

oot programmer erawtfos a ma I

Or should it be:

too remmargorp software a am I

aka's solution produces the latter.

- liu425 June 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Can you give one more example ? not able to understand what is zig zag here?

- Gaurav Khurana June 09, 2013 | 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