Abbreviation Match | tech::interview

Abbreviation Match | tech::interview
Abbreviation: apple can be abbreviated to 5, a4, 4e, a3e, …
If given a string and an abbreviation, return if the string matches abbr.
Assume the original string only contains alphabetic characters.
For example:
"internationalization", "i5a11o1" -> true

bool abbr_match(const string& str, const string& abbr) {

    int strid = 0, abbrid = 0;

    int number = 0;

    for(;; ++abbrid) {

        if(strid >= str.length()) break;

       

        char c = abbr[abbrid];

        if (c >= '0' && c <= '9') {

            number = number * 10 + (c - '0');

        } else {

            if(number != 0) {

                strid += number;

                number = 0;

            }

            if(c == '\0' || str[strid] != c) break;

            strid++;

        }

    }

    return strid == (int)str.length() && abbrid == (int)abbr.length();

}

Read full article from Abbreviation Match | tech::interview

Merge Sorted Stream | tech::interview

Merge Sorted Stream | tech::interview

输入为一个Iterator数组，这些Iterator分别取出来的数都是已排序的，设计并实现一个MergeIterator类，merge这些sorted iterator。
你的MergeIterator类需要包含has_next和get_next方法。
注意，Iterator也只包含has_next和get_next方法。

G家的onsite题，实际上就是多路归并，用一个heap就可以搞定，注意类的细节设计即可。
看过一个面经，面试者跟面试官说Iterator的接口需要有个peek()函数（即只看，不move），实际上是可以不需要的。

    MergeIterator(vector<Iterator> streams) {

        for(auto& pi : streams) {

            if(!pi.has_next()) continue;

            _heap.emplace(pi.get_next(), _streams.size());

            _streams.push_back(pi);

        }

    }

    int get_next() {

        auto ret = _heap.top();

        _heap.pop();

        if(_streams[ret.second].has_next())

            _heap.emplace(_streams[ret.second].get_next(), ret.second);

        return ret.first;

    }

    bool has_next() { return !_heap.empty(); }    

private:

    using _pair = pair<int,int>;

    vector<Iterator> _streams;

    priority_queue<_pair,vector<_pair>,function<bool(_pair&,_pair&)>> _heap {

        [](_pair& a, _pair& b){return a.first >= b.first;}

    };

Read full article from Merge Sorted Stream | tech::interview

Search Missing Numbers | tech::interview

Search Missing Numbers | tech::interview
A sorted array contains integers from 1..n with m of them missing. Find all missing numbers.
Example:
n = 8 , m = 2
arr = [1,2,4,5,6,8]
Result has to be {3, 7}.
http://www.careercup.com/question?id=5692698000359424

def find(a, left, right, result):
    if left == right:
        return

    if left == right - 1:
        if a[left] < a[right] - 1:
            for i in range(a[left] + 1, a[right]):
                result.append(i)
    else:
        mid = (left + right) / 2

        if a[mid] - a[left] > mid - left:
            find(a, left, mid, result)

        if a[right] - a[mid] > right - mid:
            find(a, mid, right, result)

Read full article from Search Missing Numbers | tech::interview

Next Unique-digit Integer | tech::interview

Next Unique-digit Integer | tech::interview
有一种integer序列满足以下条件

1. 非负
2. 不能有重复的digit，比如11是不合法的
3. 递增，既后面产生的比前面产生的要大，比如10的下一个数字是12
   显然，这组数字的范围为[0, 9876543210]

输入一个一定符合该条件的数字，返回下一个（比输入大但是最小的）数。
如果不存在这样的下一个数，则返回0
For example:
Given 789
Next integer should be 790
Given 98
Next integer should be 102
Given 9876543210
Just return 0

int64_t get_next_number(uint64_t n) {

    if(n >= 9876543210) return 0;

    auto check_valid = [](uint64_t num) {

        bool used[10] = {false};

        while(num) {

            if(used[num % 10]) return false;

            used[num % 10] = true;

            num /= 10;

        }

        return true;

    };

    while(!check_valid(++n));

    return n;

}

Read full article from Next Unique-digit Integer | tech::interview