## Google Interview Question for SDE1s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Remove duplicates from the array now array has unique integers.
int countTrees(int n){
int T[] = new int[n+1];
T[0] = 1;
T[1] = 1;
for(int i=2; i <= n; i++){
for(int j=0; j <i; j++){
T[i] += T[j]*T[i-j-1];
}
}
return T[n];
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is about "Catalan Number". As 'adr' said, i took a look leetcode#96 but i also found there couple of excellent youtube out there. easy to understand..

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.