Microsoft Interview Question for Software Engineer / Developers


Team: Mobile BI
Country: United States
Interview Type: Phone Interview




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

Nothing fancy, just tail recursion (pass empty string for 2nd argument).

static void printTable(int n, String s) {
    if(n == 0) {
      System.out.println(s);
      return;
    }
    printTable(n-1, s + "T");
    printTable(n-1, s + "F");
  }

- Sunny April 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great Solution, I debugged but still difficult to understand

- Prashanth April 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

C code

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

void print_table(int n, char *s, int index)
{
  if (n == 0) {
    printf("%s\n", s);
    return;  
  }

  print_table(n-1, (strcpy(s+index, "T"), s), index + 1);

  print_table(n-1, (strcpy(s+index, "F"), s), index + 1);

  return;
}

char s[100];

int main(int argc, char *argv[])
{
  print_table(3, s, 0);

  exit(0);
}

- Neel April 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

print_table[1] = {T, F}
print_table[2] = {T+print_table(1), F+print_table(1)} = {T+{T,F}, F+{T,F}} = {TT,TF,FT,FF}
....
....
print_table[n]={T+print_table(n-1), F+print_table(n-1)}

- Neel April 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

We can print using binary equivalent of number from 0 to pow(2,n)
Code:

public void truthTable(int n) {
		int p = (int) Math.pow(2, n);
		for (int i = 0; i < p; i++) {
			for (int k = 0; k < n; k++) {
				int v = i & 1 << n - 1 - k;
				System.out.print(v == 0 ? "T" : "F");
			}
			System.out.println();
		}
	}

- Dhass April 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static void printTruthTable(int n)
	{
		int[] out=new int[n];
		printTruthTableAux(n,0,out);
	}

	private static void printTruthTableAux(int n, int d, int[] out) {
		if(d==n)
		{
			printArray(out);
			return;
		}
		for(int i=0;i<=1;i++)
		{
			out[d]=i;
			printTruthTableAux(n,d+1,out);
		}
		
	}

	private static void printArray(int[] out) {
		char res;
		for(int a:out)
		{
		  res= a==0? 'F' : 'T';
		  System.out.print(res + " ");
		}
		System.out.println();
	}

Time complexity would be O(n^n)
Space complexity of O(n).
Please correct me if I'm wrong.

- teli.vaibhav April 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think this is a good entry-level question for three reasons: (1) its solution doesn't require foreknowledge of any "trick", just a basic understanding of recursion and how to use it to do multi-combinations. (2) the implementation is elementary enough to code in 15-60 minutes, while under the stress of interviewing for a job. (3) it requires just enough attention to detail so that a candidate unable to code this on a whiteboard, and explain the answer, will not likely be successful coding on your team. Note, however, that the converse is not true: success at answering this question will NOT tell you if someone is a good programmer since it can be practiced or memorized. However, there is NO interview-coding question that can really tell you if someone is a good programmer.

I do NOT recommend this question for senior candidates unless you're just pre-screening. It's insulting and shows the candidate that the interviewer doesn't really know what he's doing. Moreover, it's a waste of time that could be used to ask more salient questions (e.g. "how would you architect X" or "tell me about a time when Y" ).

Here's a recursive solution in D, which I think may be a little easier to understand than some of the other fine solutions presented earlier. The time complexity is O(m^n) where m is the length of the alphabet; the space complexity is O(n). For a truth table, the alphabet is simply "TF"

void printCombinations(string alphabet, int n)
{    
    // note: alphabet is UTF-8 encoded, 
    // but we assume it's all single byte char.
    // use dstring and dchar if this bothers the interviewer
    char[] s = new char[n]; 
    int count = 0;

    // recursive, positional combinations
    void combine(int k)
    {
        if (k==0)
        {
            writefln("\t%3d : %s", ++count, s);
        }
        else
        {
            foreach(c; alphabet)
            {
                s[n-k] = c;
                combine(k-1);
            }
        }
    }

    writeln("Multicombinations for [", alphabet, "], n = ", n);
    combine(n);
    writeln();
}


int main(string[] argv)
{
    // use alphabet "TF" to print the truth table
    printCombinations("TF", 1);
    printCombinations("TF", 2);
    printCombinations("TF", 3);

    // use a different alphabet "abc" to show how the combinations work
    printCombinations("abc", 2);
    printCombinations("abc", 3);

    return 0;
}

Outputs:

Multicombinations for [TF], n = 1
	  1 : T
	  2 : F

Multicombinations for [TF], n = 2
	  1 : TT
	  2 : TF
	  3 : FT
	  4 : FF

Multicombinations for [TF], n = 3
	  1 : TTT
	  2 : TTF
	  3 : TFT
	  4 : TFF
	  5 : FTT
	  6 : FTF
	  7 : FFT
	  8 : FFF

Multicombinations for [abc], n = 2
	  1 : aa
	  2 : ab
	  3 : ac
	  4 : ba
	  5 : bb
	  6 : bc
	  7 : ca
	  8 : cb
	  9 : cc

Multicombinations for [abc], n = 3
	  1 : aaa
	  2 : aab
	  3 : aac
	  4 : aba
	  5 : abb
	  6 : abc
	  7 : aca
	  8 : acb
	  9 : acc
	 10 : baa
	 11 : bab
	 12 : bac
	 13 : bba
	 14 : bbb
	 15 : bbc
	 16 : bca
	 17 : bcb
	 18 : bcc
	 19 : caa
	 20 : cab
	 21 : cac
	 22 : cba
	 23 : cbb
	 24 : cbc
	 25 : cca
	 26 : ccb
	 27 : ccc

- Eric Fleegal July 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dhass's method also can work, but if the input number is larger than 32 or 64, it won't work.
Use a array (integer or bool), which length is n,
as {x(n), x(n-1), ..., x(1)} and x(i) = 1 or 0 (true or false),
imitating the process, add 1 (or do bit operation from x(1) to x(n).
Repeat the process until the array become all 0 (or all false).

- Gabriel April 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Output for 32 will be 4,294,967,296(4.2Billion) values and for 64 it will be 18,446,744,073,709,551,616(18.4 quintillion) values :)

- Dhass April 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

So, if the input number is 65 or more, what will you do with your method?

- Gabriel April 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be achieved in C# in one for loop as shown in the code below:
for (int i = 0; i < Math.Pow(2, n); i++)
Console.WriteLine(Convert.ToString(i, 2).PadLeft(n, '0').Replace("0", "F").Replace("1", "T"));

- Noor Mahdi April 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be achieved in C# in one for loop as shown in the code below:

for (int i = 0; i < Math.Pow(2, n); i++)
Console.WriteLine(Convert.ToString(i, 2).PadLeft(n, '0').Replace("0", "F").Replace("1", "T"));

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

class SpecialPermIterator implements Iterator<String> {

		private static final int MAX_SEQ_LENGTH = 30;
		
		private int curValue = 0;
		
		private final int seqLength;
		private final int maxValue;
		

		private final char[] arr;
		
		
		public SpecialPermIterator(int seqLength){
			
			if( seqLength < 1 ){
				throw new IllegalArgumentException( "Can't create iterator  for value '" + seqLength + "', value should be greater then 1" );
			}
			
			if( seqLength > MAX_SEQ_LENGTH ){
				throw new IllegalArgumentException( "Sequence length too big, current '" + seqLength + "', max value '" + MAX_SEQ_LENGTH + "'");
			}
			
			this.seqLength = seqLength;
			this.maxValue = 1 << seqLength;			
			this.arr = new char[seqLength];
		}
		
		@Override
		public boolean hasNext() {
			return curValue < maxValue;
		}

		@Override
		public String next() {
			
			if( !hasNext() ){
				throw new NoSuchElementException();
			}
			
			String res = toBinaryString(curValue, seqLength);
			++curValue;
			
			return res;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();			
		}
		

		
		private String toBinaryString(int value, int length ) {
						
			int mask = 1;
			
			for( int i = 0; i < length; i++ ){			
				arr[length-i-1] = (( value & mask ) == 0 ? 'F' : 'T' );
				mask <<= 1;
			}
			
			return new String(arr);
		}
		
	}

- m@}{ April 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import sys

def print_bits(n, num_bits):
    for i in xrange(num_bits-1, -1, -1):
        if (n >> i) & 0x1:
            sys.stdout.write('T ')
        else:
            sys.stdout.write('F ')
    sys.stdout.write("\n")

def print_truth_table(n):
    for i in xrange(0, 2**n):
        print_bits(i, n)

if __name__ == "__main__":
    truth_table(5)

- Arup April 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry. I missed two more rows in my question , if n = 2. Here is complete list for n = 2.
Output :
T F
F T
T T
F F

- Surya April 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution is iterative and has complexity O(n*2^n). But uses constant memory. The logic is to flip entries every time based on the position of the entry and the iteration number.

package array;

import java.util.Arrays;

public class TruthTable {

	public static void printTruthTable(int n) {
		if (n == 0) {
			return;
		}

		char[] output = new char[n];
		double[] coeff = new double[n];
		int i, j;
		double numResults = Math.pow(2, n);

		for (i = 0; i < n; i++) {
			output[i] = 'T';
			coeff[i] = Math.pow(2, n - i - 1);
		}

		for (i = 1; i <= numResults; i++) {
			System.out.println(Arrays.toString(output));

			for (j = 0; j < n; j++) {
				if (i % coeff[j] == 0) {
					flip(output, j);
				}
			}

		}

	}

	private static void flip(char[] output, int j) {

		if(output[j] == 'T') {
			output[j] = 'F';
		} else {
			output[j] = 'T';
		}
	}
	
	public static void main(String[] args) {
		
		System.out.println("n=0");
		TruthTable.printTruthTable(0);
		
		System.out.println("n=1");
		TruthTable.printTruthTable(1);
		
		System.out.println("n=2");
		TruthTable.printTruthTable(2);
		
		System.out.println("n=3");
		TruthTable.printTruthTable(3);	

	}

}

- CodeNameEagle April 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Program
    {
        static void Main(string[] args)
        {
            int n = 0,Q=0,R=0;
            String line =" ";
           
            Console.WriteLine("Enter no of combinations");
            n = int.Parse(Console.ReadLine().ToString());
            int possibilities = (int)Math.Pow(2,n) ;
            for(int i=0;i<possibilities;i++)
            {
                Q=i;
                line = " ";
            for(int j=0;j<n;j++)
            {
           R = Q % 2;
            Q=Q/2;
           
                if(R==0)
                    line = String.Format("{0}{1}",'F',line);
                else
                    line = String.Format("{0}{1}",'T',line);
         }
              System.Console.WriteLine(line);
            }
            Console.ReadKey();
        }
    }

- rao.gyaneshwar April 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main()
{
int number1, i, j ;
long number;
printf("Enter the Number:");
scanf("%d",&number1);
number = pow(2, number1);
printf("Printing the square of the number %ld\n", number);
for(j=0; j<number; j++)
{
for(i=0;i<number1;i++)
{
printf("%s", (j << i & 1 << (number1 -1)) ? "T ":"F ");
}
printf("\n");
}
printf("\n");


return 0;
}

- Striker--->>> April 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It's just a binary representation of numbers in [0, n].

- btv April 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, the range is [0, 2^n]

def get_bin(i, n):
    bin_str = bin(i)[2:]
    bin_str_lead_zero = '0' * (n - len(bin_str)) + bin_str
    return bin_str_lead_zero.replace('0', 'F').replace('1', 'T')

def get_tf_table(n):
    if n > 0:
        return [get_bin(i, n) for i in xrange(0, 2**n)]

def main():
    print get_tf_table(3)

- btv April 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It may overflow when using power2
To avoid this problem, please see
sites.google.com/site/spaceofjameschen/home/stl/truth-table-implementation-microsoft

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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
	int n;
	int total;
	int i, j;
	printf ("Enter n\n");
	scanf ("%d", &n);
	total = pow (2, n);
	for (i = 0; i < total; i++)
	{
		for (j = ( n - 1 ); j >= 0; j--)
			(! ( i & ( 1 << j ))) ? printf ("F") : printf ("T");
		printf ("\n");
	}
	return 0;
}

- rohith August 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void truthTable(int n, String str, int ind) {
	    if(ind == n) {
	        System.out.println(str);
	        return;
	    }
	    truthTable(n, str + 'T', ind + 1);
	    truthTable(n, str + 'F', ind + 1);
	}

- Anand November 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Both iterative and recursive solutions (C++):

// Recursive solution

void BuildTableRecursivelyHelper(char *output, int n, int level)
{
    static const char helperArray[] = { 'T', 'F' };

    if (output && n)
    {
        if (level == n)
        {
            output[level] = '\0';
            printf("%s\n", output);
        }
        else
        {
            for (int i = 0; i < 2; i++)
            {
                output[level] = helperArray[i];
                BuildTableRecursivelyHelper(output, n, level + 1);
            }
        }
    }
}

void BuildTableRecursively(int n)
{
    char *output = NULL;

    if (n)
    {
        output = new char[n + 1];
        if (output)
        {
            BuildTableRecursivelyHelper(output, n, 0);
        }
    }

    delete[] output;
}

// Iterative solution

void InitTable(char *output, int n)
{
    // fill all with 'T'
    if (output && n)
    {
        for (int i = 0; i < n; i++)
        {
            output[i] = 'T';
        }
    }
}

bool IsLastSequence(char *output, int n)
{
    bool fLastSequence = true;

    if (output && n)
    {
        // all should be 'F'
        for (int i = 0; i < n; i++)
        {
            if (output[i] == 'T')
            {
                fLastSequence = false;
                break;
            }
        }
    }

    return fLastSequence;
}

void GenerateNewSequence(char *output, int n)
{
    if (output && n)
    {
        if (output[n - 1] != 'F')
        {
            output[n - 1] = 'F';
        }
        else
        {
            int i = n - 1;
            while (i >= 0)
            {
                if (output[i] == 'T')
                {
                    output[i] = 'F';
                    break;
                }
                else
                {
                    output[i] = 'T';
                }
                i--;
            }
        }
    }
}

void BuildTableIteratively(int n)
{

    char *output = NULL;

    if (n)
    {
        output = new char[n + 1];
        if (output)
        {
            output[n] = '\0';
            InitTable(output, n);
            do
            {
                printf("%s\n", output);
                GenerateNewSequence(output, n);
            } 
            while (!IsLastSequence(output, n));

            printf("%s\n", output);
        }
    }

    delete[] output;
}

- AK November 04, 2014 | 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