## Microsoft Interview Question

Country: India

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

for(each number i from the given digits)
{
printf(binaryToGray( i));

}
unsigned int binaryToGray(unsigned int num)
{
return (num >> 1) ^ num;
}

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

nth gray code = n ^ floor(n/2)

rest is simple

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

``````public void greyCode(int n)
{
int totalN = (int) Math.pow(2,n);
for (int i = 0; i < totalN; i++)
{
int greyCode = i ^ (i / 2);
System.out.println(greyCode);

intToBinary(greyCode); // Converts the num to binary pattern

}
}``````

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

void grey_code(int n)
{
r=pow(2,n);
int a[n];
for(i=0;i<r;i++)
{
k=i;
for(j=n-1;j>=0;j--,k/=2)
a[j]=k%2;
k=0;
for(j=0;j<n;j++)
{
if(k==0)
{
if(a[j]==1)
k++;
printf("%d",a[j]);
}
else if(a[j]==a[j-1])
printf("0");
else
printf("1");
}
printf("\n");
}
}

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

n represent the bit number.
Code tested in Java.
Output in String. Could use out.print to reduce memory consumption if need.
Run-time O(n*2^n) to output n*2^n char. Memory O(n) extra.

``````public static void run(int n) {
String gc="";//gray code output string
Boolean flip;//determine gray code reflection
int cur;//temp value to store baise
int[] index = new int[n];//reflection length, used to determine if the number of certain index took a reflection or not
for (int i = 0; i < n; i++) {//init index
index[i] = (int) Math.pow(2, i);
}
for(int i=0; i<Math.pow(2,n);i++){//output gray code one by one
flip=false; cur=0;
for (int j=n-1;j>=0;j--){
if(i>=index[j]+cur){
if(flip) gc+="0";else {gc+="1";flip=true;}
cur+=index[j];
}else{
if(flip) {gc+="1";flip=false;}else gc+="0";
}
}
gc+=" ";
}
}``````

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

``````#include<stdio.h>
#include<malloc.h>
#include<math.h>
#include <string.h>     /* strcat */
#include <stdlib.h>     /* strtol */

int *array,counter = 0;

void byte_to_binary(int x,int n)
{
static char b[9];
b[0] = '\0';

int z;
for (z = 128; z > 0; z >>= 1)
{
strcat(b, ((x & z) == z) ? "1" : "0");
}
int i = 8-n;
while(i<8){
printf("%c",b[i]);
i++;
}
}

int greycode(int n )
{
int k,i;
array[counter++]=0;
array[counter++]=1;
for(i=1 ; i < n; i++){
k = counter -1;
while(k>=0){
array[counter++] = array[k--] | 1<<i;
}
}

}
main()
{
int n,i;
printf("\nEnter n\n");
scanf("%d",&n);
array = (int*)malloc(pow(2,n)*sizeof(int));
greycode(n);
printf("\n------------------------greycode------------------------------\n");
for(i=0;i<counter;i++){
byte_to_binary(array[i],n);
printf("\n");
}
}``````

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

``````void CreateGrayCode(string str[], int arrayLen, int currLen, int length)
{
if(currLen == length)
{
for(int i=0;i<arrayLen;i++) cout<<str[i]<<endl;
return;
}
string *newstrArray = new string [arrayLen*2];
for(int i= 0;i<arrayLen;i++)
{
string temp1 = "0";
temp1.append(str[i]);
string temp2 = "1";
temp2.append(str[i]);
newstrArray[i] = temp1;
newstrArray[2*arrayLen-i-1] = temp2;

}
CreateGrayCode(newstrArray, arrayLen*2, currLen+1, length);
return;

}
int main()
{
int m = 4; //Lets  default it to 4 bits.
string strArray[] = {"0", "1"};
CreateGrayCode(strArray,2,1,m);
return 0;
}``````

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

Memory leak is here.
->

``string *newstrArray = new string [arrayLen*2];``

To correct this all the temporary strings should use the same memory as a final string. And memory for the final string should be allocated in th main() function.

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

the total number of grey codes of n is 1 << n
nth codes add 1 << (n - 1) codes to the n-1 th codes
let i loop from 1 to n and update those 1 << (n-1) by adding radix, which is 1 << (n-1), to the corresponding codes,

no recursion needed

``````public int[] geryCodes(int n)
{
int[] a = new int[1 << n];
int k = 1;
int p = 0;
int r = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 1 <<(i - 1); j++) {
a[k] = r + a[p];
p--;
k++;
}
p = k -1;
r <<= 1;
}
return a;
}``````

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

guys u can try below code. Its based on recursion approach...
code is self explanatory...

public void greyCodeGen(String str,int i,int MAX){

if(i==MAX){
System.out.println(str);
}else{
greyCodeGen(str+'0',i+1,MAX);
greyCodeGen(str+'1',i+1,MAX);
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int x;
while((x=scan.nextInt())>0){
greyCodeGen("",0,x);
}
}

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

nth gray code sequence =n-1sequnce+ reverse n-1 sequence and add 2^(n-1)
f(2)= ( 00 ,01,11,10)
f(3) ={reverse= (10,11,01,00)and then add 1 in front
={000,001,011,010,110,111,101,100}

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

There is a direct formula for this nth grey code is n xor floor(n/2)

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

``````import java.util.ArrayList;

public class GrayCode {

public static ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (n == 0) {
return list;
} else {
ArrayList<Integer> prev = grayCode(n - 1);
for (int i = prev.size() - 1; i >= 0; i--) {
list.add(prev.get(i) + (int) Math.pow(2.0, n - 1));

}
return list;
}

}

public static void main(String[] args) {
ArrayList<Integer> result = grayCode(2);
for (int i : result) {
System.out.print(i + " ");
}
// you could generate to binary form
for (int i : result) {
System.out.print(Integer.toBinaryString(i) + " ");
}
}

}``````

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

import java.util.Scanner;
class grayCode
{
static int matr[][]=new int[20][20];
static int number,row,column;

public static void main(String args[]){
Scanner sc = new Scanner(System.in);
System.out.println("Enter no.");
number=sc.nextInt();

row=(int)Math.pow(2,number);
column=number;

for(int i=0;i<number;i++)
{
fillCol(i);
}
for(int ii=0;ii<row;ii++)
{
for(int jj=0;jj<column;jj++)
System.out.print(matr[ii][jj]);
System.out.println();
}
}

static void fillCol(int colno)
{
int j=0;
int i=0,flag=1;
int ncoll=number-colno;
int packet=(int)Math.pow(2,ncoll);
int zero=(int)Math.pow(2,ncoll-1);
//System.out.println("p="+packet+" z="+zero+ "col no="+colno );
for(j=0;j<zero;j++)
{
matr[j][colno]=0;
}
for(j=zero;j<row;j++)
{
if(packet==0)
{ packet=(int)Math.pow(2,ncoll);
if(flag==1)
flag=0;
else if(flag==0)
flag=1;
}
matr[j][colno]=flag;
packet--;
}

}
}

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

please can anyone tell me the code for checking if two strings are grey code or not?

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.

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