CareerCup

#include <assert.h>
#include <algorithm>
#include <vector>

using std::vector;
using std::pair;

using std::sort;
using std::swap;

unsigned int RearrangeToNext(unsigned int x) {
    if (x == 0) return 0;
    vector<int> vec;
    unsigned int xx = x;
    while (xx > 0) {
        vec.push_back(xx % 10);
        xx = xx / 10;
    }
    int prev = 0;
    auto it = vec.begin();
    decltype(it) it_swap;
    auto it_end = vec.end();
    while (it != it_end) {
        if (prev > *it) {
            auto it2 = vec.begin();
            it_swap = vec.end();
            while (it2 != it) {
                if (*it2 > *it) {
                    if (it_swap == vec.end() || *it_swap > *it2) {
                        it_swap = it2;
                    }
                }
                ++it2;
            }
            if (it_swap != vec.end()) break;
        }
        prev = *it;
        ++it;
    }
    if (it == it_end) return x;
    swap(*it, *it_swap);
    sort(vec.begin(), it, [](int lhs, int rhs) { return (lhs > rhs); });

    unsigned int rval = 0;
    auto rit = vec.crbegin();
    auto rit_end = vec.crend();
    while (rit != rit_end) {
        rval = rval * 10 + *rit;
        ++rit;
    }
    assert(rval > x);
    return rval;
}

DFS/BFS is getting slower in the case of n ary tree.
if there is the pointer to the parent node available,
1) calculate the paths from the nodes to the root
2) there is the common path for all the paths, and the last node of the common path is the answer.

// 11 -> 0.36, 00 -> 0.16, 10 -> 0.24, 01 -> 0.24
// and discard the case of 11 and 00.
int f1() {
  while (1) {
    int a = f();
    int b = f();
    if (a != b) return a;
  }
}

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>

template<class Iterator, class CONT2, typename FUNC>
Iterator SearchBound(Iterator beg, Iterator end, const CONT2& sorted, FUNC func) {
    if (beg == end) return beg;
    auto it = beg + std::distance(beg, end) / 2;
    if (it == beg) return beg;

    auto sv_beg = cbegin(sorted);
    auto sv_end = cend(sorted);
    while (sv_beg != sv_end) {
        if (func(cbegin(*sv_beg), cend(*sv_beg), *it) == cend(*sv_beg)) {
            return SearchBound(beg, it, sorted, func);
        }
        ++sv_beg;
    }
    return SearchBound(it, end, sorted, func);
}

void MinimumRange(const std::vector<std::vector<int> >& sorted_vec) {
    std::vector<int> vec;
    std::for_each(begin(sorted_vec), end(sorted_vec),
        [&vec](const std::vector<int>& c) {
        vec.insert(cend(vec), cbegin(c), cend(c));
    });
    std::sort(begin(vec), end(vec));
    vec.erase(std::unique(begin(vec), end(vec)), end(vec));

    auto beg = vec.cbegin();
    auto end = vec.cend();
    auto lower = SearchBound(beg, end, sorted_vec,
        [](decltype(beg) a, decltype(end) b, int c) { return std::lower_bound(a, b, c); });
    auto upper = SearchBound(beg, end, sorted_vec,
        [](decltype(beg) a, decltype(end) b, int c) { return std::upper_bound(a, b, c); });
    std::cout << "[" << *upper << ", " << *lower << "]" << std::endl;
}

#include <iostream>
#include <sstream>
#include <string.h>

std::string ConsecutiveChars(const std::string& str) {
    if (str.empty()) return std::string();

    std::ostringstream ostr;
    size_t len = str.length();
    size_t count = 1;
    char prev = toupper(str[0]);

    for (size_t i = 1; i < len; ++i) {
        char c = toupper(str[i]);
        if (prev == c) {
            ++count;
        } else {
            ostr << prev << count;
            count = 1;
            prev = c;
        }
    }
    ostr << prev << count;
    return ostr.str();
}

There seems no need for list structure, bit vector is sufficient.
I think it is better to use two different bit vectors for A and B,
for better localization of data.
e.g A for Thread 1 and B for Thread2