## Google Interview Question for Software Engineers

Country: United States

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

``````//Time Complexity : O(N) Space: O(N)
public List<Integer> leaves(int[] arr){
if(arr == null || arr.length == 0){
return Collections.<Integer>emptyList();
}
List<Integer> result = new ArrayList<Integer>();
Stack<Integer> st = new Stack<Integer>();
for(int i = 0; i < arr.length; i++){
Integer l = null;
boolean leafFound = false;
while(!st.isEmpty() && arr[i] > st.peek()){
if(l != null && !leafFound){
leafFound = true;
}
l = st.pop();
}
st.push(arr[i]);

}
return result;
}``````

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

``````// O(N) time, O(depth) space complexity.
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int findLeaf(const vector<int>& pre_order, int start, int break_point, vector<int>* leaves) {
if(pre_order.size() <= start){
return start;
}
int node = pre_order[start];

if(node > break_point){
return start;
}

int end_index_left = findLeaf(pre_order, start+1, node, leaves);
int end_index_right = findLeaf(pre_order, end_index_left, break_point, leaves);

if(end_index_left == end_index_right && end_index_left == start+1){
leaves->push_back(node);
}
return end_index_right;
}

int main(int argc, char* argv[]){
vector<int> pre_order = {6, 3, 1, 5, 4, 8, 7, 9, 10};
vector<int> leaves;
int break_point = INT_MAX; // there is no break point.

int end_index = findLeaf(pre_order,0, break_point, &leaves);

if(end_index != pre_order.size()){
cout << "ERROR: end index: " << end_index << " != " << pre_order.size() << endl;
return -1;
}
for(const int t: leaves){
cout << t << " ";
}
cout << endl;
return 0;
}``````

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

``````char *leafs(char *t, int min, int max)
{
char v = *t++;
char *s = t;
if (min < *t && *t < v)
t = leafs(t, min, v);
if (v < *t && *t < max)
t = leafs(t, v, max);
if (s == t)
printf("<%c>\n", v);
return t;
}

int main()
{
}``````

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

This question seems in-complete. Otherwise wouldn't the last element of the pre-order traversal be a leaf node? Am I missing anything?

If the intent was to find a leaf node in the left sub-tree then we can follow the below steps
1. The root is the first element
2. Find the first value, say max, which is greater than root in the pre-order traversal. We can use binary search for this. Now the value before the max in the pre-order traversal is a leaf node.

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

This is simply not a complete description of the question. The short answer is that there is no way.
Think about two trees:
4
3 nullptr

3
nullptr 4

Both of the trees have exactly the same pre-order traversal, which is 3 4, if nullptr is not taken into account.
The leaf node can be either 3 or 4 depending on the tree, whose information is lost during pre-order traversal.
If we take nullptr into account, this is a simple question. Any time we find two nullptrs after a node, we count it as a leaf. But I guess it is not what the interviewer wanted.

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

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

Comment hidden because of low score. Click to expand.

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.