Interview question, part 4

I dug up another one from years ago 🙂 This one asked to write a program that:

Prints all binary numbers that do not contain consecutive bits set.

My approach was to brute force over all possible numbers and test each one with a sliding 0b11 bit mask for 2 consecutive bits set.

The answer:

#include <iostream>
#include <limits>
#include <bitset>
#include <cstdint>

using namespace std;

int main(int argc, char** argv)
{
    using type = uint8_t;

    for(type number = 0; number < numeric_limits<type>::max(); ++number)
    {
        bool print = true;

        for(type shift = 0; shift <= numeric_limits<type>::digits - 2; ++shift)
        {
            static type mask = 0b11;
            if((number & (mask << shift)) == (mask << shift))
            {
                print = false;
                break;
            }
        }

        if(print)
            cout << bitset<numeric_limits<type>::digits>(number) << endl;
    }

    return 1;
}

#include <iostream>

#include <limits>

#include <bitset>

#include <cstdint>

using namespace std;

int main(int argc, char** argv)

{

using type = uint8_t;

for(type number = 0; number < numeric_limits<type>::max(); ++number)

{

bool print = true;

for(type shift = 0; shift <= numeric_limits<type>::digits - 2; ++shift)

{

static type mask = 0b11;

if((number & (mask << shift)) == (mask << shift))

{

print = false;

break;

}

if(print)

cout << bitset<numeric_limits<type>::digits>(number) << endl;

}

return 1;

}

7 Replies to “Interview question, part 4”

Alf P. Steinbach says:

February 11, 2019 at 2:06 pm

Your approach is reasonable, because the type can be chosen with so many bits that the listing would never finish in one’s lifetime, even if the computer could be expected to keep running that long.

It’s also sufficiently efficient, because the main time consumer here is the i/o.

However, it’s a bit more complex than strictly needed, because the check (for a value of unsigned type) can be reduced to

(x & (x >>1)) == 0

.

Loading...

Reply

#include 
#include 

 
void print_binary_implementation(int size, std::string& str)
{
    if (size == str.size())
    {
        std::cout << str << std::endl;
        return;
    }
   
    if (str.size() == 0 || str.back() == '0')
    {
        print_binary_implementation(size, str.append("0"));
        str.pop_back();
        print_binary_implementation(size, str.append("1"));
        str.pop_back();
    }
 
    else
    {
        print_binary_implementation(size, str.append("0"));
        str.pop_back();
    }
}

void print_binary(size_t size)
{
    std::string s = "";
    print_binary_implementation(size, s);
}


int main()
{
    print_binary(8);
}

#include

void print_binary_implementation(int size, std::string& str)

{

if (size == str.size())

{

std::cout << str << std::endl;

return;

}

if (str.size() == 0 || str.back() == '0')

{

print_binary_implementation(size, str.append("0"));

str.pop_back();

print_binary_implementation(size, str.append("1"));

str.pop_back();

}

else

{

print_binary_implementation(size, str.append("0"));

str.pop_back();

}

void print_binary(size_t size)

{

std::string s = "";

print_binary_implementation(size, s);

}

int main()

{

print_binary(8);

}

Jason says:

February 11, 2019 at 3:17 pm

This is a recursive solution to the problem.

Loading...

Reply
1. Martin Vorbrodt says:
  
  February 11, 2019 at 5:38 pm
  
  Use code tag for inline and pre tag for blocks of code
  
  Loading...
  
  Reply

[3ʳᵈ try, code formatting, + the right code; please delete posting attempts 1 and 2.]

I think Vorbrodt’s approach of filtering is the most reasonable one since it’s so simple. Except as noted, the checking is really as simple as

(x & (x >>1))

. But for what it’s worth, here’s an iterative generative solution:

#include <cppx-core/_all_.hpp>

namespace my
{
    $use_cppx( n_items_in );
    $use_std( vector );

    void advance( vector<int>& digits )
    {
        for( int i_start = 0; ; )
        {
            for( int i = i_start; ; ++i )
            {
                if( i == n_items_in( digits ) )
                {
                    digits.push_back( 1 );
                }
                else
                {
                    digits[i] = 1 - digits[i];
                }

                if( digits[i] == 1 )
                {
                    const int i_next = i + 1;
                    if( i_next < digits.size() and digits[i_next] == 1 )
                    {
                        i_start = i;
                        break;
                    }
                    return;
                }
            }
        }
    }
}  // namespace my

auto main() -> int
{
    $use_std( begin, cout, endl, vector );
    vector<int> digits;
    cout << "0" << endl;
    for( int count = 0; ; ++count )
    {
        my::advance( digits );
        for( int i = digits.size() - 1; i >= 0; --i ) { cout << digits[i]; }
        cout << endl;
    }
}

#include <cppx-core/_all_.hpp>

namespace my

{

$use_cppx( n_items_in );

$use_std( vector );

void advance( vector<int>& digits )

{

for( int i_start = 0; ; )

{

for( int i = i_start; ; ++i )

{

if( i == n_items_in( digits ) )

{

digits.push_back( 1 );

}

else

{

digits[i] = 1 - digits[i];

}

if( digits[i] == 1 )

{

const int i_next = i + 1;

if( i_next < digits.size() and digits[i_next] == 1 )

{

i_start = i;

break;

}

return;

}

} // namespace my

auto main() -> int

{

$use_std( begin, cout, endl, vector );

vector<int> digits;

cout << "0" << endl;

for( int count = 0; ; ++count )

{

my::advance( digits );

for( int i = digits.size() - 1; i >= 0; --i ) { cout << digits[i]; }

cout << endl;

}

Hopefully the code’s now presented correctly.

Wish one could edit comments!

John Kurlak says:

February 13, 2019 at 10:06 pm

We can solve it faster than that: https://pastebin.com/DWeq7LHR

Loading...

Reply

Here’s a really fast solution:

<pre class="decode:1 inline:true " >class Solution {
    public static void main(String[] args) {
        printBitwiseNonconsecutiveNumbers(0, 50);
    }

    public static void printBitwiseNonconsecutiveNumbers(int min, int max) {
        for (int num = getNext(min - 1); num <= max; num = getNext(num)) {
            System.out.println(num);
        }
    }

    private static int getNext(int num) {
        int a = ~(num | (num >> 1));
        int b = a & -a;
        return (num | b) & ~(b - 1);
    }
}

<pre class="decode:1 inline:true " >class Solution {

public static void main(String[] args) {

printBitwiseNonconsecutiveNumbers(0, 50);

}

public static void printBitwiseNonconsecutiveNumbers(int min, int max) {

for (int num = getNext(min - 1); num <= max; num = getNext(num)) {

System.out.println(num);

}

private static int getNext(int num) {

int a = ~(num | (num >> 1));

int b = a & -a;

return (num | b) & ~(b - 1);

}

Practical Modern C++

Interview question, part 4

Like this:

Related

7 Replies to “Interview question, part 4”

Leave a ReplyCancel reply

Practical Modern C++

Interview question, part 4

Share this:

Like this:

Related

7 Replies to “Interview question, part 4”

Leave a ReplyCancel reply