Microsoft Interview Question for Software Engineer / Developers






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

public class RevAStringWithGroupOfChar {

	public static void main(String args[]){
		
		String a = "dar|dkik i|s n|ice";
		StringBuilder s = new StringBuilder();
		for (int i = a.length()-1; i >=0 ; ) {
			int j = i;
			boolean isbinchar = false;
			for( ;j >=0; j--) {
				if(isBindingChar(a.charAt(j))){
					j=j-1;
					isbinchar = true;
				}else if(i!=j){
					break;
				}
			}
			if(isbinchar){
				s.append(a.substring(j+1, i+1));
			}else{
				//System.out.print("i"+i);
				s.append(a.charAt(i));
			}
			i=j;
		}
	}
	
	public static boolean isBindingChar(char c){
		return c=='|'?true:false;
	}
		
}

- Anonymous October 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is there any restriction that whether addition memory can be allocated for result string? If we have to do in place reverting, then it can be more complicated because the size of the grouping can be varied.

- Anonymous October 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you please clarify the question, by giving a generic example.

Is it possible to have character groups of different sizes and if so, how do we identify the groups?

- Mahesh October 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Assuming character groups of size 2.
Assuming string will not begin with '|' as character group in that case is undefined.

Idea is to reverse the string normally once and in the second pass, identify the character groups(of size three) and reverse them alone to restore their original order.

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

int getLength(char* input)
{
	int length = 0;
	
	while(*input)
	{
		length++;
		input++;
	}
	return length;
}

//Normal string reversal
void reverseStringRegular(char* input, int begin, int end)
{	
	if(begin >= end) return;
	
	int i = begin, j = end;
	while(i <= j)
	{
		char ch = input[i];
		input[i] = input[j];
		input[j] = ch;
		
		i++; j--;
	}
}

//Find character groups and reverse them again to get original order
void detectGroupsAndReverse(char* input)
{
	int i = 0;
	
	while(input[i] != '\0')
	{
		if(input[i] == '|')
		{
			reverseStringRegular(input, i-1, i+1);
			i = i+2;
			continue;
		}
		i++;
	}
}

void reverseStringByGroup(char* input)
{
	int stringLength = getLength(input);
	if(input[0] == '|' || input[stringLength - 1] == '|')
	{
		printf("Invalid string. Character Grouping failed\n");
		return;
	}
	reverseStringRegular(input,0, stringLength - 1);
	detectGroupsAndReverse(input);
}

int main()
{
	char input[] = "dar|dkik i|s n|ice";
	printf("Input String: %s\n", input);
	
	reverseStringByGroup(input);
	printf("String Reversed: %s\n", input);
}

- Mahesh October 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Execute at www .ideone. com / f5Yfx

- Mahesh October 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice solution!

- Anonymous October 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Almost, but not quite. At the link at ideone you've given:

Input String: dar|dkik i|s n|ice
String Reversed: ecn|i i|s kikr|dad

- Anonymous October 14, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution. Have two pointrs left = 0 and right = length of string. Keep swapping characters till your pointers either meet or cross.

Now traverse from the beginning. If you find "|" at position 'i', interchange 'i-1' and 'i+1'

Possible validations: 1. Your string should not start or end with "|"
2. During second iteration to reorder the special characters, if your re-ordered character at 'i-1' or 'i+1' is also "|", print that the string is not valid and exit

- anon October 22, 2010 | 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