Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Really most wonderful one, i guess i need to refresh my math memory now, :(. Just spend some time proving its correctness:
(x>>1)^x=(y>>1)^y <==> (x==y)
(x>>1)^x and ((x+1)>>1)^(x+1) only has one bit change.
binary representation of x and y could easily give out the result.
I think you need one more step. Compute a list of gray-code values and then turn those into numbers (not their equivalent), because the problem asks for the bits of the actual numbers to be at a distance of 1, not their gray-code equivalents (i.e. 00001 and 00010, differ in 2 bits and not by 1 bit, as the problem asks, although their graycode equivalent differs in only 1 bit). So I believe one more step is required, once the gray-codes are generates is to transform them into numbers
program to print numbers in gray code:
def numbers(cur,pos,n,reverse):
if pos==n:
print cur
return
if not reverse:
cur[pos]=0
numbers(cur,pos+1,n,reverse)
cur[pos]=1
numbers(cur,pos+1,n,not reverse)
else: #roles of 0,1 are reversed, so anti image of above!
cur[pos]=1
numbers(cur,pos+1,n,not reverse)
cur[pos]=0
numbers(cur,pos+1,n,reverse)
if __name__=='__main__':
n=4
numbers([0]*n,0,n,False)
Here is a code which can achieve this (I think); some optimizations and cleaning are possible.
public String[] return_hamming1_walk(int n) {
if (n == 1)
return {"0", "1"};
String[] smaller_walk = return_hamming1_walk(int n-1);
String[] walk = new String[2*smaller_walk.length];
for(int i = 0; i < smaller_walk.length; ++i) {
walk[i] = "0" + smaller_walk[i];
}
for(int i = 0; i < smaller_walk.length; ++i) {
walk[smaller_walk.length + i] = "1" + smaller_walk[small_walk.length-i-1];
}
return walk;
}
How about this.
public static void grayCode(int number) {
double total = Math.pow(2, number)-1;
for(int i = 0; i <= total; i++){
System.out.println(Integer.toBinaryString(toGrayCode(i)));
}
}
public static int toGrayCode(int number){
return (number >>> 1) ^ number;
}
Here is an iterative version, (also added recursive version just for comparison)
So, that is as optimal as it gets! in space and time
#!/usr/bin/python
#iterative version(binary->gray) (similar logic can be used for gray->binary)
def gray(n,s):
out=list()
isrev=False
while n>=0 and s>1:
if n<s/2:
if not isrev:
out.append('0')
else:
out.append('1')
isrev = not isrev
s/=2
else: #exact anti-image
if not isrev:
out.append('1')
isrev = not isrev
else:
out.append('0')
s/=2
n-=s
print ''.join(out)
#recursive version
def graycode(cur,pos,n,reverse):
if pos==n:
print ''.join(cur)
return
if not reverse:
cur[pos]='0'
graycode(cur,pos+1,n,reverse)
cur[pos]='1'
graycode(cur,pos+1,n,not reverse)
else: #exact anti-image
cur[pos]='1'
graycode(cur,pos+1,n,not reverse)
cur[pos]='0'
graycode(cur,pos+1,n,reverse)
if __name__=='__main__':
itr=True
n=5
if itr:
t=1<<n
for i in range(t):
gray(i,t)
else:
graycode(['0']*n,0,n,False)
private static int next(int n, int i)
{
int x = (n >> i) & 0b11;
switch (x)
{
case 0b00: x = 0b01; break;
case 0b01: x = 0b11; break;
case 0b11: x = 0b10; break;
case 0b10: x = 0b00; break;
}
n &= ~(0b11 << i);
n |= x << i;
return n;
}
private static int grayCode(int n, int i, int base)
{
if (i >= 2)
{
for (int j=0; j<4; ++j)
{
base = grayCode(n, i - 2, base);
base = next(base, i - 2);
}
}
else if (i == 0)
{
System.out.println(toBinaryString(base, n));
}
else
{
System.out.println(toBinaryString(base, n));
System.out.println(toBinaryString(base ^ 1, n));
}
return base;
}
private static void grayCode(int n)
{
grayCode(n, n, 0);
}
I could have just looked up standard algorithm for Gray codes, but that would have ruined the challenge.
void printAdjacent(int n)
{
if(n <= 0)
{
std::cout << "0" << std::endl;
}
else
{
std::vector<int> nums = {0, 1};
int x = 1;
while(x <= n)
{
std::reverse(nums.begin(), nums.end());
for(int i = nums.size() - 1; i >= 0; i--) nums.push_back(std::pow(10, x) + nums[i]);
x++;
}
for(auto e : nums)
{
std::cout << e << std::endl;
}
}
}
My code:
void singlebitchange(int n, int k, int flag, int *p)
{
int count;
if(NULL==p)
return;
if(k==n)
{
for(count=0;count<n;count++)
printf("%d ", p[count]);
printf("\n");
return;
}
p[k]=flag;
singlebitchange(n, k+1, 0, p);
p[k]=!flag;
singlebitchange(n, k+1, 1, p);
}
Here is the C# implementation of Gray Code
sealed class Program
{
static void Main(string[] args)
{
int n = 1000;
for (uint i = 0; i < n; i++)
{
Console.WriteLine(GrayCode(i));
}
Console.ReadLine();
}
static string GrayCode(uint i)
{
uint a = (i >> 1) ^ i;
return Print(a);
}
static string Print(uint i)
{
StringBuilder builder = new StringBuilder();
for (int j = sizeof(uint) * 8 - 1; j >= 0; j--)
{
if ((i & (1 << j)) > 0)
{
builder.Append("1");
}
else
{
builder.Append("0");
}
}
return builder.ToString();
}
}
static void printAllGrayCodes(int n) {
for (int num = 0; num < 1 << n; num++) {
int val = 0;
for (int i = n; i > 0; i--) {
int x = 0;
if (i == n) {
if (num >= Math.pow(2, n - 1))
x = 1;
} else {
int modn = num % (int) Math.pow(2, i + 1);
if (modn >= Math.pow(2, i - 1)
&& modn + Math.pow(2, i - 1) < Math.pow(2, i + 1))
x = 1;
}
val |= (x << i - 1);
}
System.out.println(val);
}
}
#include <iostream>
#include <iomanip>
#include <vector>
void print(std::vector<bool> const & number)
{
for (int i = number.size(); i > 0; --i) {
std::cout << (int)number[i-1];
}
std::cout << std::endl;
}
void modify(std::vector<bool> & number, std::vector<int> & base, std::vector<int> const & cnt)
{
for (int i = 0; i < number.size(); ++i) {
--base[i];
if (base[i] == 0) {
number[i] = number[i] ^ 1;
base[i] = cnt[i];
}
}
}
void solve(int n)
{
std::vector<bool> number(n, false);
// idx: 3 2 1 0
// cnt: 16 8 4 2
// base: 8 4 2 1
std::vector<int> base(n, 0);
std::vector<int> cnt(n, 0);
for (int i = 0; i < base.size(); ++i) {
base[i] = 1 << i;
cnt[i] = 1 << (i+1);
}
long long total = (long long)1 << n;
// the loop condition can be changed so it breaks out when 0000...0000 appears after 'modify' call, in that case the "n" can be very large
// now it is limited to number of bits in long long - 1
for (long long idx = 0; idx < total; ++idx) {
std::cout << std::setw(3) << idx << ' ';
print(number);
modify(number, base, cnt);
}
}
int main()
{
int n;
std::cin >> n;
solve(n);
return 0;
public class GrayCode {
static char charArray[] = {'0','0','0','0'};
public static void main(String[] args) {
grayCode(4);
}
static void grayCode(int i){
if (i == 1){
System.out.println(charArray);
charArray[0] = (charArray[0] == '0'?'1':'0');
System.out.println(charArray);
return;
}
grayCode(i-1);
charArray[i-1] = (charArray[i-1] == '0'?'1':'0');
grayCode(i-1);
}
}
Just do a loop from 0 to 2^n-1 with the following.
- Rayden February 24, 2013unsigned int binaryToGray(unsigned int num)
{
return (num >> 1) ^ num;
}