Google Interview Question
SDE1sCountry: United States
Interview Type: In-Person
#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;
}
Sort the array, remove duplicates, then count recursively picking every i-th element as the root, with 0..i-1 being left subtree, i+1..N right subtree. See solution to leetcode 96.
- adr October 08, 2018