CareerCup

#include <iostream>

using namespace std;

int64_t RandomFib(int64_t start, int64_t end)
{
    int64_t prev_prev = 0;
    int64_t prev = 0;
    int64_t rnd = -1;
    int zero_count = 0;
    int count = 0;
    while (true)
    {
        int n = prev_prev + prev;
        if (n == 0)
        {
            if (++zero_count == 2)
            {
                n = 1;
            }
        }
        if (n >= end)
        {
            break;
        }
        if (n >= start)
        {
            ++count;
            if (rand() % count == 0)
            {
                rnd = n;
            }
        }
        prev_prev = prev;
        prev = n;
    }
    return rnd;
}

int main()
{
    srand(time(NULL));
    cout << RandomFib(5, 9) << "\n";
    return 0;
}

O(k) time. Where k is amount of digits.

#include <vector>
#include <iostream>

using namespace std;

int GetNumber(int k)
{
    if (k <= 0)
    {
        return numeric_limits<int>::min();
    }
    int n = (rand() % 5) * 2;
    int prev = n;
    int denom = 10;
    vector<int> digits;
    for (int i = 1; i < k; ++i)
    {
        digits.clear();
        for (int i = 0; i < 10; ++i)
        {
            if (i != prev)
            {
                digits.push_back(i);
            }
        }
        int digit = digits[rand() % digits.size()];
        n += digit * denom;
        denom *= 10;
        prev = digit;
    }
    return n;
}

int main()
{
    srand(time(NULL));
    for (int i = 0; i < 10; ++i)
    {
        cout << GetNumber(4) << ", ";
    }
    cout << "\n";
    return 0;
}

O(n) time and O(1) space.

#include <iostream>

using namespace std;

class Node
{
    public:
        Node(char val) : val_(val), next_(NULL) {}
        char val_;
        Node* next_;
};

Node* GetWord(Node* head, Node* &h, Node* &t)
{
    h = t = head;
    Node* n = head ? head->next_ : NULL;
    if (h)
    {
        h->next_ = NULL;
    }
    while (n)
    {
        if (n->val_ == ' ')
        {
            t->next_ = n;
            t = n;
            return n->next_;
        }
        Node* next = n->next_;
        n->next_ = h;
        h = n;
        n = next;
    }
    return NULL;
}

Node* ReverseWords(Node* head)
{
    Node* h = NULL;
    Node* t = NULL;
    Node* new_head = NULL;
    Node* new_tail = NULL;
    while (true)
    {
        head = GetWord(head, h, t);
        if (!h)
        {
            break;
        }
        if (!new_head)
        {
            new_head = h;
        }
        if (new_tail)
        {
            new_tail->next_ = h;
        }
        new_tail = t;
    }
    return new_head;
}

void Print(Node* head)
{
    for (Node* n = head; n != NULL; n = n->next_)
    {
        cout << n->val_;
    }
    cout << "\n";
}

int main()
{
    Node n1('g'), n2('o'), n3(' '), n4('o'), n5('n');
    n1.next_ = &n2;
    n2.next_ = &n3;
    n3.next_ = &n4;
    n4.next_ = &n5;

    Print(&n1);
    Print(ReverseWords(&n1));

    return 0;
}

#include <unordered_map>
#include <vector>
#include <iostream>

using namespace std;

class Result
{
    public:
        Result(int max, const vector<int>& boxes) : max_(max), boxes_(boxes) {}
        Result() : max_(numeric_limits<int>::max()) {}
        int max_;
        vector<int> boxes_;
        bool operator<(const Result& other) const
        {
            return max_ < other.max_;
        }
};

void Distribute(const vector<int>& a, int k, vector<int>& boxes, int max, Result& best_res, int idx = 0)
{
    if (idx < 0 || idx > a.size())
    {
        return;
    }
    if (max >= best_res.max_)
    {
        return;
    }
    if (idx == a.size())
    {
        if (boxes.size() == k)
        {
            if (max < best_res.max_)
            {
                best_res = Result(max, boxes);
            }
        }
        return;
    }

    boxes.push_back(a[idx]);
    Distribute(a, k, boxes, std::max(max, a[idx]), best_res, idx + 1);
    boxes.pop_back();

    if (!boxes.empty())
    {
        boxes.back() += a[idx];
        Distribute(a, k, boxes, std::max(max, boxes.back()), best_res, idx + 1);
        boxes.back() -= a[idx];
    }
}

int main()
{
    Result res;
    vector<int> boxes;
    Distribute({1, 21, 41, 61, 81, 159, 160, 169, 170, 179, 180, 189, 190, 199, 200}, 5, boxes, 0, res);
    cout << res.max_ << "\n";
    for (int n : res.boxes_)
    {
        cout << n << ",";
    }
    cout << "\n";

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

class Node
{
    public:
        Node(int val) : val_(val)
        {
            left_ = right_ = NULL;
        }
        int val_;
        Node *left_, *right_;
};

class Entry
{
    public:
        Entry(Node* n, int pos) : n_(n), pos_(pos) {}
        Node *n_;
        int pos_;
};

void Print(Node* n, Node* leaf, vector<Entry>& path, int min_pos = 0, int pos = 0)
{
    if (n)
    {
        min_pos = min(min_pos, pos);
        path.push_back(Entry(n, pos));
        if (n == leaf)
        {
            for (Entry& e : path)
            {
                cout << string(e.pos_ - min_pos, '_') << e.n_->val_ << "\n";
            }
            return;
        }
        Print(n->left_, leaf, path, min_pos, pos - 1);
        Print(n->right_, leaf, path, min_pos, pos + 1);
        path.pop_back();
    }
}

int main()
{
    /*
   (1)
   /
(2)
  \
  (4)
    \
    (3)
     \
     (7)
     / \
   (5) (8)
*/
    Node n1(1);
    Node n2(2);
    Node n3(3);
    Node n4(4);
    Node n5(5);
    Node n6(6);
    Node n7(7);
    Node n8(8);
    n1.left_ = &n2;
    n2.right_ = &n4;
    n4.right_ = &n3;
    n3.right_ = &n7;
    n7.left_ = &n5;
    n7.right_ = &n8;

    vector<Entry> path;
    Print(&n1, &n5, path);

    return 0;
}

#include <unordered_map>
#include <vector>
#include <iostream>

using namespace std;

int MaxProfit(const vector<int>& a, int fee, unordered_map<uint64_t, int>& memo, int bought = -1, int idx = 0)
{
    if (idx < 0 || idx >= a.size())
    {
        return 0;
    }
    if (bought == -1)
    {
        return max(
                MaxProfit(a, fee, memo, a[idx], idx + 1),
                MaxProfit(a, fee, memo, -1, idx + 1)
        );
    }

    uint64_t memo_key = (static_cast<uint64_t>(bought) << 32) | idx;
    auto it = memo.find(memo_key);
    if (it != memo.end())
    {
        return it->second;
    }

    int res = 0;
    int sell_profit = a[idx] - bought - fee;
    if (sell_profit > 0)
    {
        res = sell_profit + MaxProfit(a, fee, memo, -1, idx + 1);
    }
    res = max(res, MaxProfit(a, fee, memo, bought, idx + 1));

    memo[memo_key] = res;
    return res;
}

int main()
{
    unordered_map<uint64_t, int> memo;
    cout << MaxProfit({3, 5, 7, 9, 8, 2, 1, 3}, 1, memo) << "\n";
    return 0;
}

O(log n) time and O(1) space.

#include <vector>
#include <iostream>

using namespace std;

int Find(const vector<int>& a, int val)
{
    if (a.empty())
    {
        return -1;
    }
    int l = 0;
    int r = a.size() - 1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (a[m] == val)
        {
            if (m == a.size() - 1 ||
                a[m + 1] > a[m])
            {
                return m;
            }
            l = m + 1;
        }
        else if (a[m] > val)
        {
            if (m == a.size() - 1 ||
                a[m + 1] < a[m])
            {
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }
        else
        {
            l = m + 1;
        }
    }
    return -1;
}

int main()
{
    cout << Find({5, 3, 1, 3, 6, 5, 7}, 3) << "\n";
    return 0;
}

pair<int, int> MaxProductSubarray(const vector<int>& a)
{
    if (a.empty())
    {
        return pair<int, int>(-1, -1);
    }
    if (a.size() == 1)
    {
        return pair<int, int>(0, a.size());
    }
    int neg_num_count = 0;
    int64_t l_prod = 1;
    int l = 0;
    for (; l < a.size(); ++l)
    {
        if (a[l] < 0)
        {
            ++neg_num_count;
            break;
        }
        l_prod *= a[l];
    }
    if (neg_num_count == 0)
    {
        return pair<int, int>(0, a.size());
    }
    int64_t r_prod = 1;
    int r = a.size() - 1;
    for (; r >= 0; --r)
    {
        if (a[r] < 0)
        {
            ++neg_num_count;
            break;
        }
        r_prod *= a[r];
    }
    if (l == r)
    {
        if (l == 0) {return pair<int, int>(l + 1, a.size());}
        if (l == a.size() - 1) {return pair<int, int>(0, l);}
        return l_prod > r_prod ? pair<int, int>(0, l) : pair<int, int>(l + 1, a.size());
    }
    for (int i = l + 1; i < r; ++i)
    {
        if (a[i] < 0)
        {
            ++neg_num_count;
        }
    }
    if (neg_num_count % 2 == 0)
    {
        return pair<int, int>(0, a.size());
    }
    return l_prod * -a[l] > r_prod * -a[r] ? pair<int, int>(0, r) : pair<int, int>(l + 1, a.size());
};

#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

class Node
{
    public:
        vector<Node*> to_nodes_;
};

bool IsConnectedComponentBipartite(Node* start_node, unordered_set<Node*>& seen)
{
    unordered_map<Node*, bool> part;
    queue<Node*> q;
    q.push(start_node);
    part[start_node] = true;
    while (!q.empty())
    {
        Node* n = q.front();
        q.pop();
        if (seen.find(n) == seen.end())
        {
            seen.insert(n);
            bool p = part[n];
            for (Node* to_node : n->to_nodes_)
            {
                auto it = part.find(to_node);
                if (it != part.end())
                {
                    if (it->second != !p)
                    {
                        return false;
                    }
                }
                else
                {
                    part[to_node] = !p;
                }
                q.push(to_node);
            }
        }
    }
    return true;
}

bool IsBipartite(const vector<Node*>& nodes)
{
    unordered_set<Node*> seen;
    for (Node* n : nodes)
    {
        if (seen.find(n) == seen.end())
        {
            if (!IsConnectedComponentBipartite(n, seen))
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    Node n1, n2, n3, n4;
    vector<Node*> graph = {&n1, &n2, &n3, &n4};

    n1.to_nodes_.push_back(&n2);
    n2.to_nodes_.push_back(&n1);

    n2.to_nodes_.push_back(&n3);
    n3.to_nodes_.push_back(&n2);

    n3.to_nodes_.push_back(&n4);
    n4.to_nodes_.push_back(&n3);

    cout << IsBipartite(graph) << "\n";

    n3.to_nodes_.push_back(&n1);
    n1.to_nodes_.push_back(&n3);

    cout << IsBipartite(graph) << "\n";

    return 0;
}

#include <unordered_map>
#include <vector>
#include <iostream>

using namespace std;

bool CanBeComposed(const vector<int>& a, int target, unordered_map<uint64_t, bool>& memo, int idx = 0)
{
    if (idx < 0 || idx > a.size() || target < 0)
    {
        return false;
    }
    if (target == 0)
    {
        return true;
    }
    if (idx == a.size())
    {
        return false;
    }
    if (a[idx] == 1)
    {
        return true;
    }

    uint64_t memo_key = (static_cast<uint64_t>(idx) << 32) | target;
    auto it = memo.find(memo_key);
    if (it != memo.end())
    {
        return it->second;
    }

    bool res = false;
    if (a[idx] == 0)
    {
        res = CanBeComposed(a, target, memo, idx + 1);
    }
    else
    {
        for (int i = 0; i * a[idx] <= target && !res; ++i)
        {
            res = CanBeComposed(a, target - i * a[idx], memo, idx + 1);
        }
    }
    memo[memo_key] = res;
    return res;
}

bool CanBeComposed2(const vector<int>& a, int target)
{
    vector<bool> dp;
    dp.resize(target + 1, false);
    dp[0] = true;
    for (int i = 0; i < a.size(); ++i)
    {
        if (a[i] == 1)
        {
            return true;
        }
        for (int j = 0; j + a[i] < dp.size(); ++j)
        {
            int k = j + a[i];
            dp[k] = dp[k] | dp[j];
        }
    }
    return dp[target];
}

int main()
{
    vector<int> a = {6, 9, 20};
    int target  = 47;
    unordered_map<uint64_t, bool> memo;
    cout << CanBeComposed(a, target, memo) << "\n";
    cout << CanBeComposed2(a, target) << "\n";
    return 0;
}

O(n) time and space.

#include <vector>
#include <string>
#include <iostream>
#include <unordered_map>

using namespace std;

uint64_t Count(int n, unordered_map<uint64_t, uint64_t>& memo, bool absense = false, int late_in_row = 0)
{
    if (n < 0)
    {
        return 0;
    }
    if (n == 0)
    {
        return 1;
    }

    uint64_t memo_key = (static_cast<uint64_t>(n) << 32) | (late_in_row << 1) | absense;
    auto it = memo.find(memo_key);
    if (it != memo.end())
    {
        return it->second;
    }

    uint64_t count = 0;
    if (!absense && late_in_row < 2)
    {
        count += Count(n - 1, memo, true, late_in_row + 1);
    }
    if (late_in_row < 2)
    {
        count += Count(n - 1, memo, absense, late_in_row + 1);
    }
    count += Count(n - 1, memo, absense, 0);

    memo[memo_key] = count;
    return count;
}


int main()
{
    unordered_map<uint64_t, uint64_t> memo;
    cout << Count(128, memo) << "\n";
    return 0;
}

@tjcbs2. It looks lie the question is not about binary search tree. If it was about BST, the property of BST is something like "for each node in the tree, any value of the left subtree nodes must be < than the node's value, and any value of the right subtree nodes must be >= than the node's value".

What can be wrong with the nodes:
1. Several nodes have no parent.
2. The node is its own parent.
3. The node has left or right child that is not present in nodes.

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

class Node
{
	public:
		Node(int val)
			: val_(val), left_(NULL), right_(NULL) {}
		int val_;
		Node *left_, *right_;
};

bool CanFormBinaryTree(const vector<Node*>& nodes)
{
	unordered_set<Node*> children;
	for (auto& n : nodes)
	{
		if (!n) {
			return false;
		}
		if (n->left_)
		{
			if (n->left_ == n ||
				children.find(n->left_) != children.end())
			{
				return false;
			}
			children.insert(n->left_);
		}
		if (n->right_)
		{
			if (n->right_ == n ||
				children.find(n->right_) != children.end())
			{
				return false;
			}
			children.insert(n->right_);
		}
	}

	// Each node is someone's child, except for the root
	if (children.size() != nodes.size() - 1)
	{
		return false;
	}

	// For cases when a child is a node that doesn't exist in nodes
	for (auto& n : nodes)
	{
		children.erase(n);
	}
	return children.empty();
}

int main() {
/*
       (1)
       / \
    (2)  (3)
    / \
  (4) (5)
*/
	Node n1(1), n2(2), n3(3), n4(4), n5(5);
	n1.left_ = &n2;
	n1.right_ = &n3;
	n2.left_ = &n4;
	n2.right_ = &n5;

	cout << CanFormBinaryTree({&n1, &n2, &n3, &n4, &n5}) << "\n";
	return 0;
}

int RandomOdd(int min, int max)
{
    int delta = max - min;
    if (delta <= 0)
    {
        return -1;
    }
    int odd_numbers_count = delta / 2 + (min % 2 != 0 ? 1 : 0);
    int rnd = rand() % odd_numbers_count;
    return min + rnd * 2 + (min % 2 == 0 ? 1 : 0);
}

I assume, to each word, we can apply any number of ROT_1 or any number of ROT_25.

#include <unordered_map>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

pair<string, string> GetPatterns(const string& s)
{
    string p1, p2;
    for (int i = 0; i + 1 < s.size(); ++i)
    {
        int delta1 = (static_cast<int>(s[i + 1]) - s[i]);
        if (delta1 < 0)
        {
            delta1 += 26;
        }
        int delta2 = (static_cast<int>(s[i]) - s[i + 1]);
        if (delta2 < 0)
        {
            delta2 += 26;
        }
        p1 += to_string( delta1) + ",";
        p2 += to_string(-delta2) + ",";
    }
    return pair<string, string>(p1, p2);
};

vector<string> RotationDups(const vector<string>& words)
{
    vector<string> out;
    unordered_map<string, int> patterns;
    for (auto w : words)
    {
        pair<string, string> p = GetPatterns(w);
        ++patterns[p.first];
        ++patterns[p.second];
    }
    for (auto w : words)
    {
        pair<string, string> p = GetPatterns(w);
        if (patterns[p.first] > 1 ||
            patterns[p.second] > 1)
        {
            out.push_back(w);
        }
    }
    return out;
}


int main()
{
    vector<string> out = RotationDups({"AB", "BC", "FOO", "ZA", "BAZ"});
    for (auto w : out)
    {
        cout << w << ", ";
    }
    cout << "\n";
    return 0;
}

@guilhebl. How a directed acyclic graph will be constructed?

#4, Djkstra.

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Label
{
    public:
        Label(int r, int c, int cost, Label* prev)
        {
            r_ = r;
            c_ = c;
            cost_ = cost;
            prev_ = prev;
        }
        int r_, c_, cost_;
        Label* prev_;
};

class LabelComparator
{
    public:
        bool operator()(const Label* l1, const Label* l2)
        {
            return l1->cost_ > l2->cost_;
        }
};

void PushLabel(priority_queue<Label*, vector<Label*>, LabelComparator>& pq, vector<vector<int>> &m, vector<Label* > &labels, int r, int c, Label* prev)
{
    if (r >= 0 &&
        r < m.size() &&
        c >= 0 &&
        c < m[r].size() &&
        m[r][c] >= 0 &&
        m[r][c] != numeric_limits<int>::max())
    {
        int base_cost = prev ? prev->cost_ : 0;
        Label *l = new Label(r, c, base_cost + m[r][c], prev);
        labels.push_back(l);
        pq.push(l);
    }
}

vector<pair<int, int>> ShortestPath(vector<vector<int>> &m, int source_r, int source_c, int target_r, int target_c)
{
    vector<pair<int, int>> path;
    vector<Label*> labels;
    priority_queue<Label*, vector<Label*>, LabelComparator> pq;
    PushLabel(pq, m, labels, source_r, source_c, NULL);
    while (!pq.empty())
    {
        Label* l = pq.top();
        pq.pop();
        if (m[l->r_][l->c_] != numeric_limits<int>::max())
        {
            m[l->r_][l->c_] = numeric_limits<int>::max();
            if (l->r_ == target_r &&
                l->c_ == target_c)
            {
                while (l)
                {
                    path.push_back(pair<int, int>(l->r_, l->c_));
                    l = l->prev_;
                }
                reverse(path.begin(), path.end());
                break;
            }
            PushLabel(pq, m, labels, l->r_ + 1, l->c_, l);
            PushLabel(pq, m, labels, l->r_ - 1, l->c_, l);
            PushLabel(pq, m, labels, l->r_, l->c_ + 1, l);
            PushLabel(pq, m, labels, l->r_, l->c_ - 1, l);
        }
    }
    for (auto l : labels)
    {
        delete l;
    }
    return path;
}

int main()
{
    vector<vector<int>> m = {
        { 1, -1, 6, 7, 1 },
        { 4, -1, 3, 0, 1 },
        { 4, 7, 3, 10, 1 },
        { 4, 8, 6, -1, 1 }
    };
    vector<pair<int, int>> path = ShortestPath(m, 0, 0, m.size() - 1, m[0].size() - 1);
    for (auto p : path)
    {
        cout << "(" << p.first << "," << p.second << ")=>";
    }
    cout << "\n";
    return 0;
}

O(nm) time and space.

#include <string>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

bool Match(const string& s, const string& p, unordered_map<uint64_t, bool>& memo, int idx_s = 0, int idx_p = 0)
{
    if (idx_s < 0 ||
        idx_s > s.size() ||
        idx_p < 0 ||
        idx_p > p.size())
    {
        return false;
    }
    if (idx_s == s.size() &&
        idx_p == p.size())
    {
        return true;
    }
    if (idx_s == s.size())
    {
        if (p[idx_p] == '*' ||
            p[idx_p] == '+')
        {
            return Match(s, p, memo, idx_s, idx_p + 1);
        }
        else
        {
            return false;
        }
    }
    if (idx_p == p.size())
    {
        return !p.empty() && p.back() == '*';
    }

    uint64_t memo_key = (static_cast<uint64_t>(idx_s) << 32) | idx_p;
    auto it = memo.find(memo_key);
    if (it != memo.end())
    {
        return it->second;
    }

    bool res = false;
    if (p[idx_p] == '*')
    {
        for (int i = idx_s + 1; i <= s.size() && !res; ++i)
        {
            res |= Match(s, p, memo, i, idx_p);
        }
        if(!res)
        {
            res = Match(s, p, memo, idx_s, idx_p + 1);
        }
    }
    else if (p[idx_p] == '+')
    {
        res = Match(s, p, memo, idx_s + 1, idx_p + 1) |
              Match(s, p, memo, idx_s, idx_p + 1);
    }
    else
    {
        res = s[idx_s] == p[idx_p]
          ? Match(s, p, memo, idx_s + 1, idx_p + 1)
          : false;
    }
    memo[memo_key] = res;
    return res;
}

int main()
{
    vector<pair<string, string>> test_cases =
    {
        {"baaabab", "ba*a++"},
        {"baaabab", "ba*a+"},
        {"baaabab", "a*ab"},
        {"", "+"},
        {"baaabab", "ba+"},
        {"baaabab", "ba*"},
        {"ba", "*+**++a+*+**++"}
    };
    unordered_map<uint64_t, bool> memo;
    for (auto t : test_cases)
    {
        memo.clear();
        cout << Match(t.first, t.second, memo) << "\n";
    }
    return 0;
}

O(n^2 * m^2) time and O(n * m) space.

#include <vector>
#include <iostream>

using namespace std;

class Rect
{
    public:
        Rect(int r1, int c1, int r2, int c2)
            : r1_(r1), c1_(c1), r2_(r2), c2_(c2)
        {}
        int r1_, c1_, r2_, c2_;
};

void ComputeRectSums(vector<vector<int>> &m)
{
    for (int r = 0; r < m.size(); ++r)
    {
        for (int c = 0; c < m[r].size(); ++c)
        {
            if (r > 0)
            {
                m[r][c] += m[r - 1][c];
            }
            if (c > 0)
            {
                m[r][c] += m[r][c - 1];
            }
            if (r > 0 &&
                c > 0)
            {
                m[r][c] -= m[r - 1][c - 1];
            }
        }
    }
}

Rect FindPlace(vector<vector<int>> m, int h, int w, int budget)
{
    if (h > 0 &&
        w > 0 &&
        h <= m.size() &&
        w <= m[0].size())
    {
        int delta_h = m.size() - h;
        int delta_w = m[0].size() - w;
        for (int r1 = 0; r1 <= delta_h; ++r1)
        {
            int r2 = r1 + h - 1;
            for (int c1 = 0; c1 <= delta_w; ++c1)
            {
                int c2 = c1 + w -1;
                int price = m[r2][c2];
                if (r1 > 0)
                {
                    price -= m[r1 - 1][c2];
                }
                if (c1 > 0)
                {
                    price -= m[r2][c1 - 1];
                }
                if (r1 > 0 &&
                    c1 > 0)
                {
                    price += m[r1 - 1][c1 -1];
                }
                if (price <= budget)
                {
                    return Rect(r1, c1, r2, c2);
                }
            }
        }
    }
    return Rect(-1, -1, -1, -1);
}

Rect LargestArea(vector<vector<int>> m, int budget)
{
    if (!m.empty()) {
        ComputeRectSums(m);
        int h = m.size();
        int w = m[0].size();
        for (; h > 0 && w > 0; --h, --w)
        {
            Rect rect(-1, -1, -1, -1);
            rect = FindPlace(m, h, w, budget);
            if (rect.r1_ >= 0)
            {
                return rect;
            }
            rect = FindPlace(m, h - 1, w, budget);
            if (rect.r1_ >= 0)
            {
                return rect;
            }
            rect = FindPlace(m, h, w - 1, budget);
            if (rect.r1_ >= 0)
            {
                return rect;
            }
        }
    }
    return Rect(-1, -1, -1, -1);
}

int main()
{
    vector<vector<int>> m = {
        { 4, 6, 7 },
        { 3, 5, 2 },
        { 2, 4, 5 }
    };
    Rect rect  = LargestArea(m, 16);
    cout << rect.r1_ << ", " << rect.c1_ << ", " << rect.r2_ << ", " << rect.c2_ << "\n";

    return 0;
}

#include <unordered_map>
#include <vector>
#include <iostream>

using namespace std;

bool CanBeComposed(const vector<int>& a, int target_sum, unordered_map<uint64_t, bool>& memo, int idx = 0)
{
    if (idx < 0 ||
        idx > a.size())
    {
        return false;
    }
    if (idx == a.size())
    {
        return target_sum == 0;
    }

    uint64_t memo_key = (static_cast<uint64_t>(target_sum) << 32) | idx;
    auto it = memo.find(memo_key);
    if (it != memo.end())
    {
        return it->second;
    }

    bool res = CanBeComposed(a, target_sum - a[idx], memo, idx + 1);
    if (!res &&
        idx != 0)
    {
        res = CanBeComposed(a, target_sum + a[idx], memo, idx + 1);
    }

    memo[memo_key] = res;
    return res;
}

int main()
{
    unordered_map<uint64_t, bool> memo;
    cout << CanBeComposed({1, 2, 3, 4}, 2, memo) << "\n";
    return 0;
}

Assuming the integers are positive, and that we only need unique triplets. Some de-duping is done in the code, but de-duping on the whole triplet should be done to get really unique triplets.

#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <iostream>

using namespace std;

void Triplets(const vector<uint32_t>& a, uint32_t sum_needed)
{
    unordered_set<uint32_t> sums_of_1;
    unordered_map<uint32_t, unordered_set<uint64_t>> sums_of_2;
    for (uint32_t n : a)
    {
        if (n <= sum_needed)
        {
            auto it = sums_of_2.find(sum_needed - n);
            if (it != sums_of_2.end())
            {
                const unordered_set<uint64_t>& s = it->second;
                for (uint64_t key : s)
                {
                    uint32_t n1 = key >> 32;
                    uint32_t n2 = key;
                    cout << n1 << ", " << n2 << ", " << n << "\n";
                }
            }
            for (uint32_t n1 : sums_of_1)
            {
                uint32_t sum_of_2 = n1 + n;
                if (sum_of_2 <= sum_needed)
                {
                    uint64_t key = n1 < n
                       ? (static_cast<uint64_t>(n1) << 32) | n
                       : (static_cast<uint64_t>(n)  << 32) | n1;
                    sums_of_2[sum_of_2].insert(key);
                }
            }
            sums_of_1.insert(n);
        }
    }
}

int main()
{
    Triplets({7, 2, 8, 5, 9, 1, 3}, 15);
    return 0;
}

#include <unordered_map>
#include <string>
#include <iostream>

using namespace std;

bool CanBeMadeEqual(const string& a, const string& b)
{
    if (a.size() != b.size())
    {
        return false;
    }
    unordered_map<char, int> m;
    for (int offset = 0; offset < 2; ++offset)
    {
        for (int i = offset; i < a.size(); i += 2)
        {
            ++m[a[i]];
        }
        for (int i = offset; i < b.size(); i += 2)
        {
            --m[b[i]];
            if (m[b[i]] == 0)
            {
                m.erase(b[i]);
            }
            else if (m[b[i]] < 0)
            {
                break;
            }
        }
        if (!m.empty())
        {
            return false;
        }
    }
    return true;
}

int main()
{
    cout << CanBeMadeEqual("cdab", "abcd") << "\n";
    cout << CanBeMadeEqual("dcba", "abcd") << "\n";
    cout << CanBeMadeEqual("abcd", "abcdcd") << "\n";
    return 0;
}

BFS

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

class Point
{
    public:
        Point(int r, int c)
        {
            r_ = r;
            c_ = c;
        }
        int r_, c_;
};

Point NearestBike(vector<vector<char>> map, const Point& start)
{
    queue<Point> q;
    q.push(start);
    while (!q.empty())
    {
        Point p = q.front();
        q.pop();
        int r = p.r_;
        int c = p.c_;
        if (r >= 0 &&
            r < map.size() &&
            c >= 0 &&
            c < map[r].size() &&
            map[r][c] != '#' &&
            map[r][c] != 0)
        {
            if (map[r][c] == 'B')
            {
                return p;
            }
            map[r][c] = 0;
            q.push(Point(r + 1, c));
            q.push(Point(r - 1, c));
            q.push(Point(r, c + 1));
            q.push(Point(r, c - 1));
        }
    }
    return Point(-1, -1);
}

int main()
{
    Point p = NearestBike(
            {
                    {'.', '.', '.', '.', '.', '#'},
                    {'.', '.', '.', '.', '.', '#'},
                    {'#', '#', '#', '#', '.', '#'},
                    {'.', 'B', '.', '.', '.', '.'},
                    {'.', '.', '.', '.', '.', 'B'},
            },
            Point(1, 2)
    );
    cout << p.r_ << ", " << p.c_ << "\n";
    return 0;
}

O(n^3) time.

#include <unordered_set>
#include <vector>
#include <iostream>

using namespace std;

int64_t Count(const vector<int>& a)
{
    vector<unordered_set<int>> right;
    right.resize(a.size());
    for (int i = 2; i < a.size(); ++i)
    {
        for (int j = i + 1; j < a.size(); ++j)
        {
            right[i].insert(a[j]);
        }
    }

    int64_t count = 0;
    for (int i = 0; i < a.size(); ++i)
    {
        int sum1 = a[i];
        for (int j = i + 1; j < a.size(); ++j)
        {
            int sum2 = sum1 + a[j];
            for (int k = j + 1; k < a.size(); ++k)
            {
                int sum3 = sum2 + a[k];
                const unordered_set<int>& r = right[k];
                if (r.find(sum3) != r.end())
                {
                    ++count;
                }
            }
        }
    }

    return count;
}

int main()
{
    cout << Count({4, 1, 3, 8, 7, 12}) << "\n";
    return 0;
}

#include <unordered_set>
#include <vector>
#include <iostream>

using namespace std;

class Node
{
    public:
        Node(int min_idx, int max_idx)
        {
            min_idx_ = min_idx;
            max_idx_ = max_idx;
        }
        int min_idx_, max_idx_;
};

void Count(const vector<int>& a, unordered_set<int>& seen, vector<Node> &nodes, int nodes_start, int& count)
{
    if (seen.size() == a.size())
    {
        if (!a.empty())
        {
            ++count;
        }
        return;
    }
    for (int j = nodes_start; j < nodes.size(); ++j)
    {
        const Node n = nodes[j];
        for (int i = n.min_idx_; i <= n.max_idx_; ++i) {
            if (seen.find(i) == seen.end()) {
                seen.insert(i);
                nodes.push_back(Node(n.min_idx_, i - 1));
                nodes.push_back(Node(i + 1, n.max_idx_));
                Count(a, seen, nodes, j + 1, count);
                nodes.pop_back();
                nodes.pop_back();
                seen.erase(i);
            }
        }
    }
}

int main()
{
    vector<int> a = {7, 9, 1};
    sort(a.begin(), a.end());
    unordered_set<int> seen;
    vector<Node> nodes = {Node(0, a.size() - 1)};
    int count = 0;
    Count(a, seen, nodes, 0, count);
    cout << count << "\n";
    return 0;
}

The solution differs depending on what we should optimize for. We can do something like this, using a circular buffer, hash maps, and a min heap:

#include <vector>
#include <unordered_map>
#include <queue>
#include <string>
#include <iostream>

using namespace std;

class WordFrequency {
    public:
        WordFrequency(int period) : period_(period)
        {
            slots_.resize(period_);
            words_.push_back("");
            head_ = 0;
            tail_ = 0;
        }

        void AddWord(uint32_t time, const string &word)
        {
            uint64_t &word_id = word_to_word_id_[word];
            if (word_id == 0) {
                word_id = words_.size();
                words_.push_back(word);
            }
            TrimTail(time);
            ++slots_[time % period_][word_id];
            ++period_words_[word_id];
            head_ = time;
        }

        vector<string> GetTopWords(uint32_t time, int n)
        {
            vector<string> out;
            if (time < head_)
            {
                return out;
            }
            TrimTail(time);
            for (auto it = period_words_.begin(); it != period_words_.end(); ++it)
            {
                uint64_t word_id = it->first;
                uint64_t count = it->second;
                if (pq.size() < n)
                {
                    pq.push(PQElement(word_id, count));
                }
                else if (pq.top().count_ < count)
                {
                    pq.pop();
                    pq.push(PQElement(word_id, count));
                }
            }
            while (!pq.empty())
            {
                out.push_back(words_[pq.top().word_id_]);
                pq.pop();
            }
            reverse(out.begin(), out.end());
            return out;
        }

    private:
        class PQElement {
            public:
                PQElement(uint64_t word_id, uint64_t count) : word_id_(word_id), count_(count)
                {}
                bool operator<(const PQElement &other) const
                {
                    if (count_ == other.count_) {
                        return word_id_ > other.word_id_;
                    }
                    return count_ > other.count_;
                }
                uint64_t word_id_;
                uint64_t count_;
        };

        void TrimTail(uint32_t time)
        {
            int new_tail = time - (period_ - 1);
            if (new_tail > tail_)
            {
                int tail_augment = new_tail - tail_;
                if (tail_augment > period_)
                {
                    tail_augment = period_;
                }
                for (int i = 0; i < tail_augment; ++i)
                {
                    DecrementWordCounts(tail_);
                    ++tail_;
                }
            }
        }

        void DecrementWordCounts(uint32_t slot_idx)
        {
            unordered_map<uint64_t, uint64_t> &slot_words = slots_[slot_idx %= period_];
            for (auto it = slot_words.begin(); it != slot_words.end(); ++it)
            {
                uint64_t word_id = it->first;
                uint64_t count = it->second;
                period_words_[word_id] -= count;
                if (period_words_[word_id] == 0)
                {
                    period_words_.erase(word_id);
                }
            }
            slot_words.clear();
        }

        int period_;
        unordered_map<string, uint64_t> word_to_word_id_;
        vector<string> words_;
        vector<unordered_map<uint64_t, uint64_t>> slots_;
        unordered_map<uint64_t, uint64_t> period_words_;
        uint64_t max_word_id_;
        uint32_t head_;
        int tail_;
        priority_queue<PQElement> pq;
};

void Print(const vector<string> &words)
{
    for (auto w : words)
    {
        cout << w << "\n";
    }
    cout << "---\n";
}

int main()
{
    WordFrequency wf(60);

    wf.AddWord(1, "cat");
    wf.AddWord(1, "cat");
    wf.AddWord(10, "rat");
    wf.AddWord(15, "cat");
    wf.AddWord(15, "bat");
    wf.AddWord(20, "rat");
    wf.AddWord(21, "dog");
    wf.AddWord(21, "dog");

    Print(wf.GetTopWords(21, 3));

    wf.AddWord(21, "dog");
    wf.AddWord(41, "rat");
    wf.AddWord(41, "rat");

    Print(wf.GetTopWords(41, 3));

    wf.AddWord(55, "dot");
    wf.AddWord(61, "net");
    wf.AddWord(100, "let");

    Print(wf.GetTopWords(100, 3));

    return 0;
}

We can use interval search tree.
For purposes of an interview, we can sort the ranges by start time and then find overlaps:

class Range {
	public:
		Range(int start, int end, int id)
		{
			s_ = start;
			e_ = end;
			id_ = id;
		}
		
		bool operator<(Range const &other) const
		{
			if (s_ == other.s_) {
				return e_ < other.e_;
			}
			return s_ < other.s_;
		}
		
		bool overlaps(Range const &other) const
		{
			return  (s_ >= other.s_ && s_ < other.e_) ||
					(other.s_ >= s_ && other.s_ < e_);
		}

		int s_, e_, id_;
};

vector<Range> GetOverlapping(vector<Range> a)
{
	sort(a.begin(), a.end());
	vector<Range> out;
	unordered_set<int> out_seen;
	int max_start_seen = numeric_limits<int>::min();
	for (int i = 0; i < a.size(); ++i) {
		Range &r = a[i];
		for (int j = i + 1; j < a.size() && r.e_ > max_start_seen; ++j) {
			Range &r2 = a[j];
			max_start_seen = r2.s_;
			if (r.overlaps(r2)) {
				if (out_seen.find(r.id_) != out_seen.end()) {
					out.push_back(r);
					out_seen.insert(r.id_);
				}
				if (out_seen.find(r2.id_) != out_seen.end()) {
					out.push_back(r2);
					out_seen.insert(r2.id_);
				}
			}
		}
	}
	return out;
}

Works for any number of sock colors. O(N) time, O(K) space, where K is number of colors:

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

enum Sock {
	black = 0,
	white = 1
};

vector<pair<Sock, Sock>> Pair(vector<Sock> const &a)
{
	vector<pair<Sock, Sock>> out;
	unordered_set<Sock, hash<int>> part1;
	for (auto &s : a) {
		if (part1.find(s) != part1.end()) {
			out.push_back(pair<Sock, Sock>(s, s));
			part1.erase(s);
		} else {
			part1.insert(s);
		}
	}
	cout << (part1.empty() ? "all paired\n" : "not all paired\n");
	return out;
}

int main()
{
	vector<pair<Sock, Sock>> pairs = Pair({black, white, white, black, white, black, white, black});
	for (auto &p : pairs) {
		cout << p.first << ", " << p.second << "\n";
	}
}

My code produces a balanced BST, but not necessary a complete one.
O(N) time.

Node *BuildBst(LLNode *head, int size)
{
    if (size <= 0) {
        return NULL;
    }

    LLNode *ll_n = head;
    int left_size = 0;
    for (int i = 0; i < size / 2; ++i) {
        ll_n = ll_n->next_;
        ++left_size;
    }

    Node *n = new Node(ll_n->val_);
    n->left_ = BuildBst(head, left_size);
    n->right_ = BuildBst(ll_n->next_, size - left_size - 1);
    return n;
}

My idea is to keep track of max even sum and max odd sum of the paths going through a particular node. O(N) time, O(log N) space (in case of a balanced tree).

#include <iostream>
#include <vector>

using namespace std;

class Node {
    public:
        Node(int val)
        {
            val_ = val;
            left_ = right_ = NULL;
        }
        int val_;
        Node *left_, *right_;
};

class Sums {
    public:
        Sums(int even, int odd)
        {
            e_ = even;
            o_ = odd;
        }
        int e_;
        int o_;
};

Sums MaxSums(Node *n, int &max_e_sum)
{
    Sums out(0, 0);
    if (n) {
        Sums l_max_sums = MaxSums(n->left_, max_e_sum);
        Sums r_max_sums = MaxSums(n->right_, max_e_sum);

        vector<int> sums = {
            l_max_sums.e_ + n->val_,
            l_max_sums.o_ + n->val_,
            r_max_sums.e_ + n->val_,
            r_max_sums.o_ + n->val_,
            l_max_sums.e_ + r_max_sums.e_ + n->val_,
            l_max_sums.e_ + r_max_sums.o_ + n->val_,
            l_max_sums.o_ + r_max_sums.e_ + n->val_,
            l_max_sums.o_ + r_max_sums.o_ + n->val_
        };

        for (int i = 0; i < 4; ++i) {
            int sum = sums[i];
            if (sum % 2 == 0) {
                out.e_ = max(out.e_, sum);
                max_e_sum = max(max_e_sum, out.e_);
            } else {
                out.o_ = max(out.o_, sum);
            }
        }

        for (int i = 4; i < sums.size(); ++i) {
            int sum = sums[i];
            if (sum % 2 == 0) {
				max_e_sum = max(max_e_sum, sum);
            }
        }
    }

	return out;
}

int main()
{
/*
      10
     /    \
    2      5
   /  \      \
  1   101    13
*/
    Node n10(10), n2(2), n5(5), n1(1), n101(101), n13(13);
    n10.left_ = &n2;
    n10.right_ = &n5;
    n2.left_ = &n1;
    n2.right_ = &n101;
    n5.right_ = &n13;

    int max_e_sum = 0;
    MaxSums(&n10, max_e_sum);
    cout << max_e_sum << "\n";
}

If it's ok to destroy the input, we can do one pass backward, counting backspaces and replacing the chars which will be removed by 0, another pass forward, tracking state of the CapsLock and replacing chars with upper case when needed, and the final pass, comparing non-zeroed non-slashed chars.

If it's not ok to destroy the input, my idea is to find the next characters which will not be removed and compare them. Space is O(1), but time is O(N^2):

#include <iostream>
#include <string>

using namespace std;

int GetNext(string const &s, int idx, bool &caps)
{
    for (int i = idx + 1; i < s.size(); ++i) {
        if (s[i] == '\\') {
            if (s[i + 1] == 'c') {
                caps = !caps;
            }
            ++i;
        } else {
            int chars_count = 0;
            int bs_count = 0;
            bool char_will_be_removed = false;
            for (int j = i; j < s.size() && !char_will_be_removed; ++j) {
                if (s[j] == '\\') {
                    if (s[j + 1] == 'b') {
                        if (++bs_count >= chars_count) {
                            char_will_be_removed = true;
                        }
                    }
                    ++j;
                } else {
                    ++chars_count;
                }
            }
            if (!char_will_be_removed) {
                return i;
            }
        }
    }
    return -1;
}

bool Compare(string const &s1, string const &s2)
{
    bool caps1 = false;
    bool caps2 = false;
    int i = -1;
    int j = -1;
    while (true) {
        i = GetNext(s1, i, caps1);
        j = GetNext(s2, j, caps2);
        if ((i == -1) && (j == -1)) {
            return true;
        }
        if ((i == -1) || (j == -1)) {
            return false;
        }
        char c1 = caps1 ? toupper(s1[i]) : s1[i];
        char c2 = caps2 ? toupper(s2[j]) : s2[j];
        if (c1 != c2) {
            return false;
        }
    }
}

int main()
{
    cout << Compare("Abc\\b\\bt", "\\caef\\b\\c\\bt") << "\n";
}

@vmkaabhirami. I'm also not sure if I understand the question correctly. I assume that out of the set of pipes I should build two pipes (by connecting them) as long as possible. Also, I assume that the lengths of the two long pipes should be equal.

@Shah. Thank you! Fixed the first part.

Regarding the second part. I assume that the pattern doesn't force distance between characters. I.e. I assume that pattern "aza" matches string "121", doesn't taking in account that distance from 'a' to 'z' is not the same as distance from '1' to '2'. If there was an interviewer, it's definitely a good question to ask if the pattern should force distance or not.

@ChrisK.
1. Sorry, I have to read assumptions.
2. Sure. Thank you!

@ChrisK. There is a nuance, which makes the problem a bit more complicated. E.g. the following situation:
0 1 2 3 4 5 6
2 and 6 are occupied.
It would be correct to occupy 4, but most people would probably prefer take 0, because this way we only disturb 1 person (at 2), not two persons (at 2 and 6) :)

@charan. A couple of test cases the code produces a wrong result for:
{3, 8, 8}, k=16 - result is 3, should be 2
{2, 7, 2, -3, 9, -7, -6, -5}, k=12 - result is 9999, should be 4

I assume the taken place numbers are sorted.

#include <iostream>
#include <vector>

using namespace std;

int Place(vector<int> const &a, int bench_start, int bench_end)
{
	int place = -1;
	if (a.empty()) {
		place = bench_start;
	} else {
		int max_free_space = -1;
		for (int i = 0; i + 1 < a.size(); ++i) {
			int free_space = a[i + 1] - a[i] - 2;
			if (free_space > max_free_space) {
				max_free_space = free_space;
				place = a[i] + 1 + free_space / 2;
			}
		}
		int free_space = a[0] - bench_start - 1;
		if (free_space >= max_free_space / 2) {
			max_free_space = free_space * 2;
			place = bench_start;
		}
		free_space = bench_end - a[a.size() - 1] - 1;
		if (free_space >= max_free_space / 2) {
			place = bench_end;
		}
	}
	return place;
}

int main()
{
	cout << Place({1, 3, 4, 5, 9}, 1, 10) << "\n";
}

@dora. Yes, the description looks a bit inconsistent. E.g. in Example 1 the amount of ones is not preserved: 1011000 -> 1111000 only need one flip 0 -> 1.

bool Similar(Node *n1, Node *n2)
{
	if (!n1 ||
		!n2)
	{
		return n1 || n2 ? false : true;
	}

	if (n1->val_ != n2->val_) {
		return false;
	}

	if (Similar(n1->left_, n2->left_) &&
		Similar(n1->right_, n2->right_))
	{
		return true;
	}

	if (Similar(n1->left_, n2->right_) &&
		Similar(n1->right_, n2->left_))
	{
		return true;
	}

	return false;
}

@DyingLizard. [4,4,2,-6,4,10,2],16 produces 6, instead of 3.

@dora. Yes, your solution works great for consecutive elements! Though, they usually call consecutive elements a subarray rather than a subset.

@dora. For list = {3, 1, 2}, k = 2, it returns 4.

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

bool IsEncoded(string const &s, string const &pattern)
{
	if (s.size() != pattern.size()) {
		return false;
	}
	unordered_map<char, char> seen_in_s, seen_in_p;
	for (int i = 0; i < s.size(); ++i) {
		auto it = seen_in_s.find(s[i]);
		if (it != seen_in_s.end()) {
			if (pattern[i] != it->second) {
				return false;
			}
		} else {
			seen_in_s[s[i]] = pattern[i];
		}

		it = seen_in_p.find(pattern[i]);
		if (it != seen_in_p.end()) {
			if (s[i] != it->second) {
				return false;
			}
		} else {
			seen_in_p[pattern[i]] = s[i];
		}
	}
	return true;
}

class EncodingChecker {
	public:
		EncodingChecker(vector<string> const &patterns)
		{
			for (auto &p : patterns) {
				normalized_patterns_.insert(Normalize(p));
			}
		}
		bool IsEncoded(string const &s) const
		{
			return normalized_patterns_.find(Normalize(s)) != normalized_patterns_.end();
		}

	private:
		string Normalize(string const &s) const
		{
			unordered_map<char, char> seen;
			char val = 0;
			string out;
			for (char c : s) {
				auto it = seen.find(c);
				if (it != seen.end()) {
					out += it->second;
				} else {
					out += val;
					seen[c] = val++;
				}
			}
			return out;
		}
		unordered_set<string> normalized_patterns_;
};

int main()
{
	cout << IsEncoded("abcdef", "abcabc") << "\n";
	cout << IsEncoded("cbzabc", "abcabc") << "\n";
	cout << IsEncoded("xyzxyz", "abcabc") << "\n";

	EncodingChecker checker({"abcabc", "yzyzyz", "aaabbbaaa"});
	cout << checker.IsEncoded("123123") << "\n";
	cout << checker.IsEncoded("hahaha") << "\n";
	cout << checker.IsEncoded("777999777") << "\n";
	cout << checker.IsEncoded("121213") << "\n";
}

We can find K largest elements, using a min heap, and find sum of the K largest elements. O(N * log K) time and O(K) space.

For cases like "({[}])" counts will be correct, but the sequence is invalid.

Whenever we see i-th 1 at index idx, we increase the counter by (idx - i).
E.g. for 0, 1, 1, 0, 0, we find the 0-th 1 at index 1, and we find the 1-st 1 at index 2: (1 - 0) + (2 - 1) = 2.
Why? Because an increment in index of 1 increments number of swaps needed, and increment in amount of ones decrements number of swaps needed (because 1s gather at the left side).

We can use a memory-mapped file for the stack.
Also, we can count repeating open brackets instead of adding each into the stack. E.g. for "((({[[" we can have the stack looking like this: "(3{[2". If the file contains a lot of repeating brackets, this should help a lot.

If it's more likely for the file to be wrong, we can do the first pass without a stack. Just counting open and close brackets of each type. If the first pass doesn't fail, we another pass, using a stack.

O(n) time, O(1) space.

int Sum(vector<int> const &a)
{
	int sum = 0;
	if (!a.empty()) {
		sum = a[0];
		int prev = a[0];
		for (int i = 1; i < a.size(); ++i) {
			int n = a[i] <= prev ? prev + 1 : a[i];
			sum += n;
			prev = n;
		}
	}
	return sum;
}

#include <iostream>
#include <vector>
#include <list>

using namespace std;

class Node {
	public:
		Node(int val)
		{
			val_ = val;
		}
		int val_;
};

list<Node *> Merge(list<Node *> &l1, list<Node *> &l2)
{
	list<Node *> out;
	while (!l1.empty() ||
			!l2.empty())
	{
		if (!l1.empty() &&
			(l2.empty() || l1.front()->val_ <= l2.front()->val_))
		{
			out.push_back(l1.front());
			l1.pop_front();
		} else {
			out.push_back(l2.front());
			l2.pop_front();
		}
	}
	return out;
}

int main()
{
	Node n1(1), n2(2), n3(3), n4(4), n5(5), n6(6), n7(7);
	list<Node *> l1 = {&n1, &n3, &n5, &n6};
	list<Node *> l2 = {&n2, &n4, &n7};
	auto l = Merge(l1, l2);
	for (Node *n : l) {
		cout << n->val_ << "->";
	}
	cout << "\n";
}

#include <iostream>
#include <thread>
#include <condition_variable>
#include <mutex>

using namespace std;

int count = 0;
mutex m;
condition_variable cv;

void Run(int start, int end) {
	while (true) {
		unique_lock<mutex> lock(m);
		if (::count >= end) {
			break;
		}
		while (::count < start) {
			cv.wait(lock);
		}
		++::count;
		cout << this_thread::get_id() << " incremented to " << ::count << endl;
		cv.notify_all();
	}
}

int main()
{
	thread t1(Run, 80, 100);
	thread t2(Run, 20, 80);
	thread t3(Run, 0, 20);
	t1.join();
	t2.join();
	t3.join();
}