Microsoft Interview Question
Software Engineer / DevelopersTeam: Mobile BI
Country: United States
Interview Type: Phone Interview
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);
}
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.
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
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).
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 :)
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);
}
}
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);
}
}
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();
}
}
#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;
}
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)
#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;
}
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;
}
Nothing fancy, just tail recursion (pass empty string for 2nd argument).
- Sunny April 19, 2013