Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

1.Sort by "NumberOfTall" and "height":
(1)those who have fewer people taller in front of them have smaller index;
(2)for those having same number of tallers in front, the taller his own height is, the smaller index he has.

struct Person{
    string name;
    int height;
    int frontTaller;
};
struct Compare{
    bool operator()(const Person& a, const Person& b){
        if(a.frontTaller != b.frontTaller) return a.frontTaller < b.frontTaller;
        else return a.height > b.height;
    }
};

2.Insert each person into the queue after counting his "NumberOfTaller":

list<Person> retrieveQueue(vector<Person>& v)
{
    sort(v.begin(), v.end(), Compare());
    list<Person> q;
    list<Person>::iterator iter;
    for(int i = 0; i < v.size(); ++i){
        iter = q.begin();
        for(int n = v[i].frontTaller; n > 0; ++iter){
            if(iter->height > v[i].height) --n;
        }
        q.insert(iter, v[i]);
    }
    return q;
}

- uuuouou February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I had the same idea but I could not write a clean code for it. The running time of the code is O(n^2) right? because for each element we inverse the whole queue.

- pari February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 votes

good solution :)
we can do it in another way, it's more simple:
1. first sort the array by height from taller ones to shorter ones;
2. use the frontTaller as the index, insert it to the result list.

bool Compare(const Person& a, const Person& b)
{
    if (a.height != b.height) return a.height > b.height;
    return a.frontTaller < b.frontTaller;
}

list<Person> retrieveQueue(vector<Person>& v)
{
    sort(v.begin(), v.end(), Compare());
    list<Person> q;
    for (int i = 0; i < v.size(); ++ i)
    {
        q.insert(q.begin() + v.frontTaller, q);
    }
    return q;
}

- zdzapple February 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

for example:
after sort:
height: 11 10 6 5 4 1
frontTaller: 0 0 2 1 0 4

insert 11 to list[0]; -> 11
insert 10 to list[0]; -> 10 11
insert 6 to list[2] ; -> 10 11 6
...
result:
4 10 5 11 1 6

- zdzapple February 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

but the solution above is O(n^2).

we can use BST to reduce to O(nlogn)

- zdzapple February 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

zdzapple, can you elaborate how to use the BST to reduce to O(nlogn)?

- qxixp February 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 votes

Could anyone please explain what the question really asks for? input: <"Height","NumberOfTall","Name">,
<6,2,"A">,<1,4,"B">,<11,0,"C">,<5,1,"D">,<10,0,"E">,<4,0,"F">
output: "F","E","D","C","B","A" --> end of queue?
Looks like the queue is simply the reverse order of the input list.

- Guy February 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's pure coincidence ;)
You have to sort the given elements in a way, that for every element e, there are "NumberOfTall" elements in front of e, that have a greater "height" value.
For example there has to be one element in front of D that is taller and that element would be F. In fact there's always only one possible solution, if all heights differ. In the given example coincidentally the reverse order ;)

- Markus March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I will tell how it is possible to partly add BST to make it slightly faster, but still worst-case is O(n^2). It is not purely my idea, I saw it in some other thread with similar question.

You may sort it by height and take the heighest first, slowly building the BST, where each node has an information about the number of people that are in his left branch. So imagine we have already some BST built. Now we have a human X with T taller people that we want to put into this BST. In case T is lower than root.T, we go into the left branch adding +1 to the root.T. In case it is bigger, we add root.T into our variable that sums the parent.T and go into right branch.

- mbriskar May 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

We will use recursion to solve this.

dequeue(set of people)
	filter all people who have 0 no of people in front of them 
		//as 0 means either they are in the front of the queue or all people ahead of them are smaller than them
	find the person with smallest height
		//this will be the guy standing at the front of the queue
	As this person will be removed so all people having height less than him and behind him (no of tall > 0) will no longer be able to see him. So we need to reduce the count of no of tall people by 1 for each
	print the person and call the function with the remaining set of people.

- kr.neerav February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I was just about to write this exact explanation. This is the simplest and most efficient solution!

- andonov92 February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looking for smaller heights makes it n^2. My solution nlogn

- CT February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

A Java implementation for the idea of (1) sorting by decreasing height and by decreasing order of taller for equal height and then (2) Inserting items of the sorted list one by one into the new list into the position indicated by the "taller" field. Complexity is O(n^2)

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;


public class OrderTallPeople {

	private static class Person {
		String name;
		int height;
		int tallCount;
		
		Person(int h, int t, String n){
			name = n;
			height = h;
			tallCount = t;
		}
		
		@Override
		public String toString() {
			return "<"+name+","+height+"," +tallCount+">";
		}
	}

	static class HeightComparator implements Comparator<Person> {
		public int compare(Person p1, Person p2){
			int ret  = p2.height - p1.height;
			return (ret == 0)?p2.tallCount - p1.tallCount:ret;
		}
	}


	public static List<Person> orderByHeightAndTaller(Person[] people){
		Arrays.sort(people, new HeightComparator());
		LinkedList<Person> ret = new LinkedList<>();
		for(Person p: people){
			ret.add(p.tallCount,p);
		}
		return ret;
	}

	public static void main(String[] args) {
		Person [] people = {
				new Person(6,2,"A"),
				new Person(1,4,"B"),
				new Person(11,0,"C"),
				new Person(5,1,"D"),
				new Person(5,3,"K"),
				new Person(10,0,"E"),
				new Person(4,0,"F")
				
				
		};
		System.out.println(orderByHeightAndTaller(people));
		
		
	}
	
	
}

- konst May 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Idea: Sort them first base on their height. After that insert each of them
# into the final queue. The insert position is simply how many taller people are
# ahead of them.

input = <<HERE
6,2,"A"
1,4,"B"
11,0,"C"
5,1,"D"
10,0,"E"
4,0,"F"
HERE

Person = Struct.new(:height, :taller, :name)

people = input.split("\n").map do |line|
  height, taller, name = line.split(",")
  Person.new(height.to_i, taller.to_i, name)
end

people_sorted = people.sort_by {|person| person.height}

queue = []
queue << people_sorted.pop

people_sorted.reverse.each do |person|
  queue.insert(person.taller, person)
end

puts queue

- Anonymous February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your algorithm will not produce the correct output.

As per your solution,
i) First sort on heights
The list will be B, F, D, A, E, C

ii) Now putting the elements as per the number of taller people ahead of them will give me
F, D, A, B
E and C has conflicts for the spot '0'

- Akhilesh Pandey February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Akhilesh Pande:

You didn't work out the example correctly. This algorithm works fairly elegantly.

<6,2,"A">,<1,4,"B">,<11,0,"C">,<5,1,"D">,<10,0,"E">,<4,0,"F">

Sorting based on increasing height:

BFDAEC

Start with just the tallest person: [C]
E sees 0 taller people: [CE]
A sees 2 taller people: [ACE]
D sees 1 taller person: [ACDE]
F sees 0 taller people: [ACDEF]
B sees 4 taller people: [ABCDEF]

Done.

(I built the answer in the opposite example from the question, because this makes more sense to me.)

- nilkn March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

# here 2 arrays are used p and final.
# sort the input array in ascending order in p[]. then use the function . final[] will contain the output

int isblank(int i)
{
//printf("%d ,k==%d blank=%d\n",i1,i,(final[i].height==0));
 return final[i].height==0;

}
void finalselection()
{       int i=0,j=0,k=0;
	for(i=0;i<6;i++)
	{          j=-1,k=-1;
		do
		{
		  if(isblank(k+1))
		  j++;
		  k++;

		} while(j<p[i].taller && k<6-1);
		final[k]=p[i];


	}


}
void main()
{

input();
sort();
finalselection();


display();

}

- shubhmmehta February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think your code works. when you sort the p[] you sort relative to the taller or the heights?

- pari February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Array of Linked list, index numOfTals, LinkedList is sorted by heights. head of Linked List at 0 is next element. Unlik part of linked list from index 1 and on and move to linked list at index one less. The unlik part is from the heights equal to removed and on.

Each linked list is also indexed to allow binary search where to unlink or where to link

- CT February 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

hey CT could not understand your solution. Could you elaborate a little more with examples.

- kr.neerav February 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I see the flow, we need array of heaps, num ofTalls index. extract next from 0th, note length and extract less or equal from i to i-1

- CT February 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create 2 sorted arrays.
Array 1 contains all the people with 0 taller people in front of them, sorted by height shortest to tallest
Array 2 contains all the people with 1 or more taller people in front of them also sorted by height tallest to shortest.
Insert people from Array 2 into Array 1 in a position where they have the correct number of taller people in front of them.

- Rincer July 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use rope data structure for this question. It is a tree with an additional information at each node about the total number of nodes in the left subtree.

The steps are :
1. First sort the given input according to the height.
2. Insert each value one by one in the tree.
Insertion algo:
a. If the root is null just make the current value as root.
b. if the height is less than the root's height then try in left subtree of the root and at the same time increase the value of the variable containing information about the number of nodes in the left subtree.
c. else decrease the height by the total number of nodes in the left subtree and try in the right subtree.
3. Finally do an inorder of the tree

Code: (my code just print the queue according to the height and not by the name)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <malloc.h>
#include <algorithm>
using namespace std;

struct  node
{
    int value;
    int data;
    node *left;
    node *right;
};
struct man
{
    int height;
    int number;
};
int cmp(man a,man b)
{
    if(a.height>b.height)return 1;
    else return 0;
}
node *tree_insert(node *root, man a)
{
    if(root==NULL)
    {
        root=(node *)malloc(sizeof(node));
        root->left=root->right=NULL;
        root->data=a.height;
        root->value=1;
    }
    else if(a.number<root->value)
    {
        root->value+=1;
        root->left=tree_insert(root->left,a);
    }
    else
    {
        a.number-=root->value;
        root->right=tree_insert(root->right,a);
    }
    return root;
}
void inorder(node *root)
{
    if(root)
    {
        inorder(root->left);
        printf("%d ",root->data);
        inorder(root->right);
    }
}
int main()
{
    int test,i,j,n;
    scanf("%d",&test);
    node *root=NULL;
    while(test--)
    {
        scanf("%d",&n);
        man a[n];
        root=NULL;
        for(i=0;i<n;i++)
            scanf("%d",&a[i].height);
        for(i=0;i<n;i++)
            scanf("%d",&a[i].number);
        sort(a,a+n,cmp);
       // for(i=0;i<n;i++)cout<<a[i].height;
        for(i=0;i<n;i++)
           root=tree_insert(root,a[i]);
        inorder(root);
        printf("\n");

    }
}

- Ujjwal Prakash October 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Create lists for each "NumberOfTall"
2) Sort each list separately
3) Modified-Merge sort two consecutive list at time keeping in mind the conditions for "Height" and "NumberOfTall"

- aditya.eagle059 February 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Seems suitable for bash...

taller_input:
6 2 "A"
1 4 "B"
11 0 "C"
5 1 "D"
10 0 "E"
4 0 "F"

taller.sh:

#!/bin/bash

while read height numberTaller name
do  
  i=0
  while [[ -n "${output[$i]}" || $numberTaller -gt 0 ]]
  do
    if [[ -z "${output[$i]}" ]]
    then
      numberTaller=$(($numberTaller-1))
    fi
    i=$((i+1))
  done
  output[$i]=$name
  
done < <(cat $1 | sort -n)

echo ${output[@]}

$ ./taller.sh taller_input
"F" "E" "D" "C" "B" "A"

- SBD February 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

To put it simply print the order in which people are standing in the row.

- kr.neerav February 19, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More