9.1 You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order

Posted on August 14, 2013 by builderfei


#include &lt;iostream&gt;
#include &lt;vector&gt;

using namespace std;

/*
Missed some basic knowledge!
1.[] operator (and at(), front(), back()) ACCESS and MODIFY an element, BUT they cannot spawn an element for you, this is not perl!!!
2. resize() can shrink and expand a container. When shrinking, every iterator in the new scope are valid, BUT expand invalidates all iterators!!!

Solution is better organized.
*/
void merge(vector&lt;int&gt;&amp; A, vector&lt;int&gt;&amp; B)
{
    if (B.size() == 0) return;
    
    if (A.size() == 0 &amp;&amp; (A = B, 1)) return;
    
    int sizeA = A.size(), sizeB = B.size();
    int size = sizeA + sizeB;
    
    A.resize(size);
    
    vector&lt;int&gt;::iterator Aptr = A.begin() + sizeA - 1;
    vector&lt;int&gt;::iterator Bptr = B.end() - 1;
    
    while (size &gt; 0)
    {
        if (*Aptr &gt; *Bptr)
        {
            A[size - 1] = *Aptr;
            
            //from the solution, these segment of data is already in place, no movement is needed
            if (Aptr == A.begin())
            {
                --size;
                while (size &gt; 0)
                {
                    A[size - 1] = *Bptr;
                    --Bptr;
                    --size;
                }
                return;
            }
            --Aptr;
        }
        else
        {
            A[size - 1] = *Bptr;
            if (Bptr == B.begin())
            {
                --size;
                while (size &gt; 0)
                {
                    A[size - 1] = *Aptr;
                    --Aptr;
                    --size;
                }
                return;
            }
            --Bptr;
        }
        --size;
    }
}

int main()
{   
    vector&lt;int&gt; A;
    for (int i = 0; i &lt; 10; i+=2)
    {
        A.push_back(i);
    }
    
    vector&lt;int&gt; B;
    for (int i = 1; i &lt; 10; i+=2)
    {
        B.push_back(i);
    }
    
    merge(A, B);
    
    for (vector&lt;int&gt;::const_iterator cit = A.begin(); cit != A.end(); ++cit)
    {
        cout &lt;&lt; *cit &lt;&lt; endl;
    }
    return 0;
}

8.6 Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2 dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.

Posted on August 14, 2013 by builderfei

#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
#include <deque>
#include <utility>

using namespace std;

const int SIZE = 5;
const string COLORS[] = {"RED  ", "WHITE", "BLACK"};

namespace COLOR
{
    enum Enum
    {
        RED,
        WHITE,
        BLACK
    };
};

void print(vector<vector<COLOR::Enum> >& Screen)
{
    for (vector<vector<COLOR::Enum> >::iterator it = Screen.begin()
    ; it != Screen.end(); ++it)
    {
        for (vector<COLOR::Enum>::iterator it2 = (*it).begin()
        ; it2 != (*it).end(); ++it2)
        {
            cout << COLORS[static_cast<int>(*it2)] << ' ';
        }
        cout << endl;
    }
    cout << endl;
};

void helper(vector<vector<COLOR::Enum> >& Screen, COLOR::Enum color, int x, int y)
{
    
    /*
    BIG BUG:
    I forgot the lower bound
    */
    if (x < 0 || y < 0) return;
    
    if (x >= SIZE || y >= SIZE) return;

    if (Screen[x][y] == color) return; //have been visited, or boundary
    
        Screen[x][y] = color;
        
        //I only check 4 ways.
        helper(Screen, color, x + 1, y);
        helper(Screen, color, x - 1, y);
        helper(Screen, color, x, y + 1);
        helper(Screen, color, x, y - 1);
}

void paintFill(vector<vector<COLOR::Enum> >& Screen, COLOR::Enum color, int x, int y)
{
    if (x >= SIZE || y >= SIZE) return; //out of bound
    /*
    Think about the layout like this
    --------------->y
    | S[0][0] S[0][1] S[0][2]
    | S[1][0] S[1][1] S[1][2]
    x S[2][0] S[2][1] S[2][2]
    */
    
    /*
    LOGIC BUG: DO NEED TO FILL
    */
    //if (Screen[x][y] == color) return; //no need to fill
    
    helper(Screen, color, x, y);
};

void paintFill_iterative(vector<vector<COLOR::Enum> >& Screen, COLOR::Enum color, int x, int y)
{
    deque<pair<int, int> > stack;
    stack.push_back(make_pair(x, y));
    
    while (! stack.empty())
    {
        pair<int, int> xy = stack.back();
        stack.pop_back();
        
        if (xy.first >= SIZE || xy.second >= SIZE || xy.first < 0 || xy.second < 0)
        {
            ;
        }
        else if (Screen[xy.first][xy.second] != color)
        {
            Screen[xy.first][xy.second] = color;
            stack.push_back(make_pair(xy.first + 1, xy.second));
            stack.push_back(make_pair(xy.first - 1, xy.second));
            stack.push_back(make_pair(xy.first, xy.second + 1));
            stack.push_back(make_pair(xy.first, xy.second - 1));
        }
    }
}

int main()
{
    srand(time(NULL));
    vector<vector<COLOR::Enum> > Screen(SIZE);
    for (vector<vector<COLOR::Enum> >::iterator it = Screen.begin()
    ; it != Screen.end(); ++it)
    {
        for (int i = 0; i < SIZE; ++i)
        {
            int acolor = rand() % 3;
            /*
            Syntax error
            (*it).push_back(static_cast<COLOR::Enum>acolor);
            */
            (*it).push_back(static_cast<COLOR::Enum>(acolor));
        }
    }
    
    print(Screen);
    
    int x = SIZE - 3, y = SIZE - 2;
    COLOR::Enum fillcolor = COLOR::BLACK;
    
    //paintFill(Screen, fillcolor, x, y);
    paintFill_iterative(Screen, fillcolor, x, y);
    
    cout << "Paint from " << x << ',' << y << " to " 
    << COLORS[static_cast<int>(fillcolor)] << endl << endl;
    
    print(Screen);
    
    return 0;
}

8.5 Implement an algorithm to print all valid (e g , properly opened and closed) combi-nations of n-pairs of parentheses EXAMPLE: input: 3 (e g , 3 pairs of parentheses) output: ()()(), ()(()), (())(), ((()))

Posted on August 14, 2013 by builderfei


#include <iostream>
#include <set>
#include <string>

using namespace std;

const int N = 3;

void print(set<string>& strs)
{
    for (set<string>::iterator it = strs.begin(); it != strs.end(); ++it)
    {
        cout << *it << endl;
    }
}

//this is bottom-up, divide big into small
void combs(int N, set<string>& strs) 
{
    if (N == 1)
    {
        strs.insert("()");
    }
    else if(N == 0)
    {
        ;
    }
    else
    {
        combs(N - 1, strs);
        
        set<string> aset;
        //Never attemp to modify(add or delete) the container inside its iteration loop.
        for (set<string>::iterator it = strs.begin(); it != strs.end(); ++it)
        {
            aset.insert("()" + *it);
            aset.insert("(" + *it + ")");
            aset.insert(*it + "()");
        }
        strs = aset;
    }
}

//this is top-down, buid small into big
void combs_v2(int N, set<string>& strs) 
{
    if (N == 1)
    {
        return; //missed this return, be careful.
    }
    
    if (strs.empty())
    {
        strs.insert("()");
    }

    set<string> aset;
    //Never attemp to modify(add or delete) the container inside its iteration loop.
    for (set<string>::iterator it = strs.begin(); it != strs.end(); ++it)
    {
        aset.insert("()" + *it);
        aset.insert("(" + *it + ")");
        aset.insert(*it + "()");
    }
    strs = aset;
    combs_v2(N - 1, strs);
}

//This is like BFS, "aset" is the queue for the next level
void combs_iterative(int N, set<string>& strs)
{
    while (N > 0)
    {
        if (strs.empty())
        {
            strs.insert("()");
        }
        else
        {
            set<string> aset;
            for (set<string>::iterator it = strs.begin(); it != strs.end(); ++it)
            {
                aset.insert("()" + *it);
                aset.insert("(" + *it + ")");
                aset.insert(*it + "()");
            }
            strs = aset;
        }
        --N;
    }
}

int main()
{
    set<string> strs;
    combs(N, strs);
    print(strs);
    strs.clear();
    
    cout << endl;
    combs_iterative(N, strs);
    print(strs);
    strs.clear();
    
    cout << endl;
    combs_v2(N, strs);
    print(strs);
    strs.clear();
    
    return 0;
}

8.4 Write a method to compute all permutations of a string

Posted on August 13, 2013 by builderfei


#include <string>
#include <map>
#include <deque>
#include <iostream>

using namespace std;

void helper(map<char, int>& charMap, string str, int size)
{
    if (size == 0)
    {
        cout << str << endl;
        return;
    }
    else
    {
        for (map<char, int>::iterator it = charMap.begin(); it != charMap.end(); ++it)
        {
            if (charMap[it->first] != 0)
            {
                -- charMap[it->first];
                str.push_back(it->first);
                --size;
                helper(charMap, str, size);
                ++size;
                str.erase(str.end() - 1);
                ++ charMap[it->first];
            }
        }
    }
}

void printAllPerms(string str)
{
   map<char, int> charMap;
   for (string::iterator it = str.begin(); it != str.end(); ++it)
   {
       charMap[*it] ++;
   }
   helper(charMap, "", str.size());
}

void printAllPerms_iterative(string str)
{
    map<char, int> charMap;
    for (string::iterator it = str.begin(); it != str.end(); ++it)
    {
        charMap[*it] ++;
    }
    
    
    map<char, int> top;
    int size;
    string perm;
    
    deque<map<char, int> > stack;
    deque<char> stack_char;
    deque<int> stack_size;
    
    stack.push_back(charMap);
    stack_char.push_back('^');
    stack_size.push_back(str.size());
    
    while (! stack.empty())
    {
        top = stack.back();
        stack.pop_back();
        
        size = stack_size.back();
        stack_size.pop_back();
        
        perm.push_back(stack_char.back());
        stack_char.pop_back();
        
        if (size > 0)
        {
            for (map<char, int>::iterator it = top.begin(); it != top.end(); ++it)
            {
                if (top[it->first] > 0)
                {
                    -- top[it->first];
                    -- size;
                    stack.push_back(top);
                    stack_char.push_back(it->first);
                    stack_size.push_back(size);
                    ++ size;
                    ++ top[it->first];
                }
            }
        }
        else
        {
            cout << perm << endl;
            int i = 0;
            while ((! stack_size.empty()) && i <= stack_size.back())
            {
                perm.erase(perm.end() - 1);
                i ++;
            }
        }
    }
}

int main()
{
    string str("12242");
    printAllPerms(str);
    printAllPerms_iterative(str);
    return 0;
}

8.3 Write a method that returns all subsets of a set.

Posted on August 12, 2013 by builderfei

#include <iostream>
#include <set>
#include <deque>

/*
The key is how a greater problem relies on its sub-problems.
and
how to avoid duplicate by visit each element in order.
*/
using namespace std;

void print(set<set<int> >& res)
{
    for (set<set<int> >::iterator it = res.begin(); it != res.end(); ++it)
    {
        for (set<int>::iterator it2 = (*it).begin(); it2 != (*it).end(); ++it2)
        {
            cout << *it2 << ' ';
        }
        cout << endl;
    }
    cout << endl;
}

//THIS IS A VERY BAD IMPLEMENT!!!!!
//real problem is how to wipe out duplicate
//seems "res" is not dispensable
void findAllSets(set<int>& input, set<set<int> >& res)
{
    if (input.empty())
    {
        ;
    }
    else
    {
        set<int> tmp = input;
        res.insert(input);
        for (set<int>::iterator it = tmp.begin(); it != tmp.end(); ++it)
        {
            input.erase(*it);
            findAllSets(input, res);
            input.insert(*it);
        }
    }
}

//bottom-up
void findAllSets_recursive(set<int> input, set<set<int> >& res)
{
    if (input.empty())
    {
        return;
    }
    else
    {
        int i = *input.begin();
        res.insert(set<int>(input.begin(), input.begin()));
        input.erase(i);
        findAllSets_recursive(input, res);
        
        for (set<set<int> >::iterator it = res.begin(); it != res.end(); ++it)
        {
            set<int> aset = (*it);
            aset.insert(i);
            res.insert(aset);
        }       
    }
}

//mimic bottom-up process
void findAllSets_iterative(set<int> input, set<set<int> >& res)
{
    deque<int> stack;
    
    while(1)
    {
        if (input.empty())
        {
            while (! stack.empty())
            {
                res.insert(set<int>(stack.begin(), stack.begin()));
                int i = stack.back();
                stack.pop_back();
                
                for (set<set<int> >::iterator it = res.begin(); it != res.end(); ++it)
                {
                    set<int> aset = (*it);
                    aset.insert(i);
                    res.insert(aset);
                }
            }
            break;
        }
        else
        {
            stack.push_back(*input.begin());
            input.erase(input.begin());
        }
    }
}

int main()
{
    set<int> input;
    set<set<int> > res;
    input.insert(1);
    input.insert(2);
    input.insert(3);
    input.insert(4);
    
    findAllSets_recursive(input, res);
    print(res);
    res.clear();
    findAllSets_iterative(input, res);
    print(res);
    
    //findAllSets(input, res);
    
    return 0;
}

8.2 Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot? FOLLOW UP Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

Posted on August 12, 2013 by builderfei

/*
recursive : back_track
iterative
*/

#include <iostream>
#include <set>
#include <deque>
#include <utility>

using namespace std;

const int N = 6; //grid dimension

typedef pair<int, int> xypair;

//set PATH element to pointer type? Logically wrong!!
//deque<xypair*>* PATH = new deque<xypair>();

//set OFF element to pointer type? Cause problem in find()
//set<xypair*>* OFF = new set<xypair>();

deque<xypair>* PATH = new deque<xypair>();
set<xypair>* OFF = new set<xypair>();

void print(deque<xypair>* PATH)
{
    for (deque<xypair>::iterator it = PATH->begin(); it != PATH->end(); ++it)
    {
        //cout << '(' << (*it)->first << ',' << *(it)->second << ') '; 
        //this is not perl!!
        cout << '(' << (*it).first << ',' << (*it).second << ") ";
    }
    cout << endl;
}

void findAllPath(xypair* xy)
{
    if (xy->first == N && xy->second == N)
    {
        print(PATH);
    }
    else
    {
        if (xy->first != N)
        {
            ++xy->first;
            
            //my most common syntax error
            //if (OFF.find(xy) == OFF.end())
            
            if (OFF->find(*xy) == OFF->end())
            {
                /*
                BUG : PATH must contain a copy of xy instead of pointer type!
                */
                //PATH->push_back(xy);
                PATH->push_back(*xy);
                findAllPath(xy);
                PATH->pop_back();
            }
            --xy->first;
        }
        
        if (xy->second != N)
        {
            ++xy->second;
            if (OFF->find(*xy) == OFF->end())
            {
                PATH->push_back(*xy);
                findAllPath(xy);
                PATH->pop_back();
            }
            --xy->second;
        }
    }
}


/*
this backTrack is tricky to me, I've never done this way before.
Be very careful and learn
*/
void backTrack(deque<xypair>* stack)
{
    if (stack->empty()) return;
    
    xypair sxy = stack->back();
    while (! PATH->empty())
    {
        xypair pxy = PATH->back();
        if (sxy.first - pxy.first == 1 && sxy.second == pxy.second)
        {
            break;
        }
        if (sxy.second - pxy.second == 1 && sxy.first == pxy.first)
        {
            break;
        }
        PATH->pop_back();
    }
}

void findAllPath_iterative(xypair* xy)
{
    deque<xypair> stack;
    stack.push_back(*xy);
    
    while (! stack.empty())
    {
        //stupid
        //xypair cur = PATH->pop_back();
        xypair cur = stack.back();
        stack.pop_back();
        PATH->push_back(cur);
        
        if (cur.first == N && cur.second == N)
        {
            print(PATH);
            
        }
        else
        {
            ++cur.first;
            if (OFF->find(cur) == OFF->end() && cur.first <= N)
            {
                stack.push_back(cur);
            }
            --cur.first;
            
            
            ++cur.second;
            if (OFF->find(cur) == OFF->end() && cur.second <= N)
            {
                stack.push_back(cur);
            }
            --cur.second;
        }
        
        //iteratively pop_back PATH 
        //in order to restore the status for the next loop.
        backTrack(&stack);
    }
}

int main()
{
    OFF->insert(make_pair(4,2));
    OFF->insert(make_pair(4,3));
    OFF->insert(make_pair(4,4));
    OFF->insert(make_pair(4,5));
    OFF->insert(make_pair(4,6));
    findAllPath(new xypair(0, 0));
    cout << endl;
    findAllPath_iterative(new xypair(0, 0));
    /*
    memory release part omitted
    */
    return 0;    
}

8.1 Write a method to generate the nth Fibonacci number.

Posted on August 12, 2013 by builderfei

/*
1.Recursive : top-down; bottom-up
2.Iterative : bottom-up
*/

#include <iostream>
#include <cassert>
#include <climits>

using namespace std;

int rfib(int n) //this is top-down.
{
    if (n == 1 || n == 2)
    {
        return 1;
    }
    else
    {
        //this is hell slow, but neat, unable to check overflow
        return rfib(n - 1) + rfib(n - 2); 
    }
};

//this is bottom-up, totally alike the ifib()
int rfib_v2(int n, int& fb0, int& fb1) 
{
    if (n == 1 || n == 2)
    {
        return 1;
    }
    else
    {
       rfib_v2(n - 1, fb0, fb1);
    }
    
    assert(INT_MAX - fb0 > fb1); //critical
    int fb = fb0 + fb1;
    fb0 = fb1;
    fb1 = fb;
    return fb;
    
};

int ifib(int n)
{
    int i = 3, fb0 = 1, fb1 = 1;
    int fb = 0;
    while (i <= n)
    {
        assert(INT_MAX - fb0 > fb1); //critical
        fb = fb0 + fb1;
        fb0 = fb1;
        fb1 = fb;
        ++ i;
    }
    return fb;
};

int main()
{
    cout << rfib(35) << endl;
    cout << ifib(45) << endl;
    
    int fb0 = 1, fb1 = 1;
    cout << rfib_v2(45, fb0, fb1) << endl;
    return 0;
}

7.1 Design the data structures for a generic deck of cards Explain how you would sub-class it to implement particular card games

Posted on August 10, 2013 by builderfei


/*
1. Investigatation on an individual card instead of a collection of cards, focus on a card's state and interface.
2. A card game has its own specific constrain and requirement on cards, such that a generic card cannot satisfy a blackjack card
3. Player manage multiple cards
*/

#include <iostream>
#include <cstdlib>
#include <vector>
#include <set>

using namespace std;

namespace SUIT
{
    enum Enum
    {
        SPADE,
        HEART,
        CLUB,
        DIAMOND
    };
};

class Card
{
private:
    SUIT::Enum s;
    int v;
    
public:
    virtual SUIT::Enum suit() const
    {
        return s;
    };
    
    virtual int val() const
    {
        return v;
    };
    
    Card(int val, SUIT::Enum suit):s(suit), v(val){};
};

/*
Just remember and practise the paradigm of inheritance
*/
class BlackJackCard : public Card
{
public:
    virtual int val()
    {
        int v = Card::val();
        if (v < 10) return v;
        return 10;
    }
    
    BlackJackCard(int val, SUIT::Enum suit):Card(val, suit){};
};

class player
{
private:
    int id;
    int bet;
    set<int> points;
    vector<BlackJackCard *> bjcs;
    bool addPoint(set<int>& points, BlackJackCard* card)
    {
        if (points.empty())
        {
            points.insert(card->val());
            if (card->val() == 1)
                points.insert(11);
        }
        else
        {
            /*
            set elements are ALWAYS CONST, they can't be modified once inserted.
            */
            set<int> tmp;
            for (set<int>::iterator it = points.begin(); it != points.end(); ++ it)
            {
                tmp.insert(*it + card->val());
                if (card->val() == 1)
                    tmp.insert(*it + 11);
            }
            points = tmp;
        }
    }
     
    void getPoints()
    {
        cout << "You All Possible Points : " << endl;
        for (set<int>::iterator it = points.begin(); it != points.end(); ++ it)
        {
            cout << *it << endl;
        }
    };
    
    int getMinPoints()
    {
        /*
        set is implemented by commonly BST, so eles are in order!!!
        learn to use lower_bound() and upper_bound()
        
        "they allow the direct iteration on subsets based on their order."
        which gives us another option to find min. preferable
        */
        
        //return *(points.lower_bound(0));
        return *(points.begin());
    };
    
    void printCards()
    {
        cout << "You Cards : " << endl;
        for (vector<BlackJackCard *>::iterator it = bjcs.begin(); it != bjcs.end(); ++ it)
        {
            cout << (*it)->val() << endl;
        }
        
    }
public:
    player(int i, int j):id(i),bet(j)
    {
        bjcs.push_back(new BlackJackCard(rand() % 13 + 1, SUIT::SPADE));
        bjcs.push_back(new BlackJackCard(rand() % 13 + 1, SUIT::SPADE));
        addPoint(points, bjcs[0]);
        addPoint(points, bjcs[1]);
    };
    
    void getAnotherCard()
    {
        for (set<int>::iterator it = points.begin(); it != points.end(); ++ it)
        {
            /*
            predefined strategy for the player
            */
            if (*it <= 21 && 21 - *it <= 4)
            {
                printCards();
                getPoints();
                cout << "Stand" << endl; 
                exit(1);
            }
        }
        bjcs.push_back(new BlackJackCard(rand() % 13 + 1, SUIT::SPADE));
        addPoint(points, bjcs.back());
        if (getMinPoints() > 21)
        {
            printCards();
            getPoints();
            cout << "Busted" << endl;
            exit(2);
        }
    };
    
    virtual ~player()
    {
        for (vector<BlackJackCard *>::iterator it = bjcs.begin(); it != bjcs.end(); ++it)
        {
            delete *it;
        }
    };
    
};

int main()
{
    srand(time(NULL));
    player p(1, 1000);
    p.getAnotherCard();
    p.getAnotherCard();
    p.getAnotherCard();
    
    return 0;
}

5.3 Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation

Posted on August 9, 2013 by builderfei


/*
Observe and find the pattern
001001 -> 001010, 000110
001010 -> 001100, 001001
one more:
001110 -> 010011, 001101

I can see two patterns
01..10..0 -> 10..01..1, 01..11..0
10..01..1 -> 10..01..10, 01..10..0

Exceptions:
1..10..0 -> No larger or overflow
0..01..1 -> No smaller
0 -> N/A
FFFFFFFF -> N/A
*/

/*
1. set 1 => 'or' with 1 others 0,   0x01 | (1 << 1) = 0x1
2. set 0 => 'and' with 0, others 1, 0x101 & (~(1 << 2)) = 0x101 & 0x011 = 0x001
3. get => 'and' with 1 or 'or' with 0, 1 & 1 = 1; 0 & 1 = 0; 1 | 0 = 1 ; 0 | 0 = 0
*/

#include <iostream>

using namespace std;

int main()
{
    int anumber = 0x2;
    
    if (anumber == 0xFFFFFFFF || anumber == 0x0)
    {
        cout << "N/A" << endl;
    }
    else
    {
        int num = anumber;
        int i = 0, j = 0;
        
        
        if (num & 0x1) //pattern two
        {
            while (num & 0x1)
            {
                num  = num  >> 1;
                ++ i;
            }
            
            //find larger
            cout << "Larger 0x: " << hex << anumber + (1 << i) - 1 << endl;
            
            
            if (num == 0x0) // Exception
            {
                cout << "Smaller : N/A" << endl;
            }
            else
            {
                int smaller = anumber;
                while ((num & 0x1) == 0x0)
                {
                    num = num >> 1;
                    ++ j;
                }
                smaller = smaller - (1 << (i + j));
                smaller = smaller + (1 << (i + j - 1));
                
                //int mask = 1 - (1 << (i - 1));
                int mask = ~(1 << (i - 1)); //this is absolutely a SAFER way
                
                smaller = smaller - mask;
                mask = mask << (j - i);
                cout << "Smaller 0x: " << (smaller | mask) << endl;
            }
        
        }
        else //pattern one
        {
            while ((num & 0x1) == 0x0)
            {
                num  = num  >> 1;
                ++ i;
            }
            
            if (num == (0xFFFFFFFF >> i)) // Exception
            {
                cout << "Larger: N/A" << endl;
            }
            else
            {
                int larger = anumber;
                while (num & 0x1)
                {
                    num = num >> 1;
                    ++ j;
                }
                larger = larger + (1 << (i + j));
                larger = larger - (1 << (i + j - 1));
                
                int mask = 1 - (1 << (j - 1));
                larger = larger - (mask << (i - 1));
                cout << "Larger: 0x" << hex << (larger | mask) << endl;
            }
            cout << "Smaller: 0x" << hex << (anumber - (1 << i) + (1 << (i - 1))) << endl;
        }
    }
    return 0;
}

5.2 Given a (decimal – e.g. 3.72) number that is passed in as a string, print the binary representation If the number can not be represented accurately in binary, print “ERROR”

Posted on August 9, 2013 by builderfei

/*
Background:
0.5 = 0.1
0.25 = 0.01
0.125 = 0.001
0.0625 = 0.0001
So:
0.8125 = 0.5 + 0.25 + 0.0625 = 0.1 + 0.01 + 0.0001 = 0.1101
*/

#include <iostream>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;

int main()
{
    double input = atof("2312313.8125");
    
    int    i = input;
    double d = input - i;
    
    string left;
    while (i != 0)
    {
        left.append(1, i % 2 + '0');
        i = i / 2;
    }
    reverse(left.begin(), left.end());
    
    string right;
    double e = 0.00000001;
    //while (d < 0 - e || d > e - 0)
    while (d - 0 > e - 0) //distance from 0
    {
        if (right.size() > 10)
        {
            cout << "ERROR" << endl;
            return 1;
        }
        d = d * 2;
        
        if (d > 1 || (d > 1 - e && d < 1 + e)) //critical
        {
            right.append(1, '1');
            d = d - 1;
        }
        else
        {
            right.append(1, '0');
        }
    }
    
    
    cout << left << '.' << right << endl;
    return 0;
}

Under Known

What the BUG!?

Category Archives: Cracking Code Interview

9.1 You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order

8.6 Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2 dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.

8.5 Implement an algorithm to print all valid (e g , properly opened and closed) combi-nations of n-pairs of parentheses EXAMPLE: input: 3 (e g , 3 pairs of parentheses) output: ()()(), ()(()), (())(), ((()))

8.4 Write a method to compute all permutations of a string

8.3 Write a method that returns all subsets of a set.

8.1 Write a method to generate the nth Fibonacci number.

7.1 Design the data structures for a generic deck of cards Explain how you would sub-class it to implement particular card games

5.3 Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation

5.2 Given a (decimal – e.g. 3.72) number that is passed in as a string, print the binary representation If the number can not be represented accurately in binary, print “ERROR”