Microsoft Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
2
of 4 vote

Below is the solution in Java

private static void printCombinationsforlength(String str, int n) {
		printCombinationsforlength("",str,n);
		
	}

	public static void printCombinationsforlength(String prefix, String str, int n){
		if(n == 1){
			for(int i =0;i<str.length();i++)
				System.out.print(prefix+str.charAt(i) + " ");
		}
		for(int i = 0;i<str.length();i++)
			printCombinationsforlength(prefix+str.charAt(i),str.substring(i+1),n-1);
	}

- loveCoding January 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For n = 2
Output :
cd bd bc cd ad ac bd ad ab bc ac ab :(

- Srikant Aggarwal January 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your algo is correct BUT instead of printing the *suffix* of length n of the permuted string you should print the *prefix* of it. Then for n = 2 you get precisely:
ab ac ad ba bc bd ca cb cd da db dc

- Anonymous January 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is expected output for n=2..
I think in this case bd and db is same why do we need to print both...
so for abcd and n=2, number of combinations would be 6.
Please correct me if i am wrong..
Thanks..

- loveCoding January 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a very simple recursive function. Below is the explanation of the recurrence, followed by the code:

1. Say your string is "abcd"
2. At each step of the recursion, you can either pick a character and move to the next character. So in the first step of the recursion, you can pick "a" and call the recursive function again.
3. OR you can skip "a" and call the recursive function again

Code in C#:

// Call recursive function
       PrintCombinations("abcd", 3, "", 0);

        public static void PrintCombinations(string targetString, int targetLength, string comboSoFar, int pos)
        {
            if (comboSoFar.Length == targetLength)
            {
                Console.WriteLine(comboSoFar);
                return;
            }
            if(pos>=targetString.Length) return;

            char c=targetString[pos];
            PrintCombinations(targetString, targetLength, comboSoFar + c, pos + 1);
            PrintCombinations(targetString, targetLength, comboSoFar, pos + 1);
        }

- Anonymous January 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if (comboSoFar.Length == targetLength)
            {
                Console.WriteLine(comboSoFar);
                return;
            }

The return is extra. Need to remove that.

- Anonymous January 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Adding some comment to make the recursion easier to follow with the explanation:

public static void PrintCombinations(string targetString, int targetLength, string comboSoFar, int pos)
        {
            if (comboSoFar.Length == targetLength)  // This is the desired length of the combination
            {
                Console.WriteLine(comboSoFar);
                return;
            }
            if(pos>=targetString.Length) return;

            char c=targetString[pos];
            PrintCombinations(targetString, targetLength, comboSoFar + c, pos + 1);     // Case: Pick current character and move to next
            PrintCombinations(targetString, targetLength, comboSoFar, pos + 1);         // Case: Skip current character and move to next
        }

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

Below is the C# code both with and without Recursion:
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Enter the input string: ");
string input = Console.ReadLine();
Console.WriteLine("Enter length for combinations: ");
int length;
if (!Int32.TryParse(Console.ReadLine(), out length))
{
Console.WriteLine("Enter valid Integer input. Try Again!!");
}
else
{
if (length > input.Length)
{
Console.WriteLine("The length for combinations should be lesser than the length of the input string.");
}
else
{
//PrintCombinations(input, length);
PrintCombinationsRecursive(input+input.Substring(0, length-1), length, 0);
Console.ReadKey();
}
}
}

/// <summary>
///
/// </summary>
/// <param name="input"></param>
/// <param name="length"></param>
private static void PrintCombinations(string input, int length)
{
for (int i = 0; i < input.Length; ++i)
{
int k = 0;
for (int j = 0; j < length; ++j)
{
if (i + j < input.Length)
{
Console.Write(input[i + j]);
}
else
{
Console.Write(input[k]);
++k;
}
}
Console.WriteLine();
}
}




/// <summary>
///
/// </summary>
/// <param name="input"></param>
/// <param name="length"></param>
private static void PrintCombinationsRecursive(string input, int length, int i)
{
if (input.Length-i < length)
{
return;
}
string combin = input.Substring(i, length);
Console.WriteLine(combin);
PrintCombinationsRecursive(input,length,++i);
}


}

- Pinto Singh January 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Any correct answers for this ?

- Srikant Aggarwal January 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi

I have lot of difficulty understanding this recursion. Can someone pl spare sometime to explain how to formulate the recursion behind this problem ?
That is, pls do ot explain some approach that works. I want to understand the mechanics behind this so that I can apply this to any combinatorial problem that is similar.

Thanks

- Supraja January 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

python:

#!/usr/bin/python
def recurse(a,b):
  if (len(b) == 3):
    print ''.join(b)
  else:
    for i in range(len(a)):
      c = b[:]
      d = a[:]
      c.append(d.pop(i))
      recurse(d,c)


if __name__ == "__main__":
  a="abcd"
  b=[]
  recurse(list(a),b)

abc
abd
acb
acd
adb
adc
bac
bad
bca
bcd
bda
bdc
cab
cad
cba
cbd
cda
cdb
dab
dac
dba
dbc
dca
dcb

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

public class Permute1 
{
	StringBuilder out = new StringBuilder();
	
	
	public void permute (String input, int start, int length)
	{
		
		if (out.length() == length)
		{
			System.out.println(out);
			return;
		}
		
		for (int i = start ; i < input.length() ; i++)
		{
			out.append(input.charAt(i));
			permute (input, i + 1 , length);
			out.setLength(out.length() - 1);
		}
	}
	
	public static void main(String[] args) {
		Permute1 p = new Permute1();
		p.permute("abcd", 0, 2);
	}

}

Java solution

- prabodh.prakash March 13, 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