Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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.
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;
}
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
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.
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 ;)
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.
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.
I was just about to write this exact explanation. This is the simplest and most efficient solution!
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));
}
}
# 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
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 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.)
# 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();
}
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
hey CT could not understand your solution. Could you elaborate a little more with examples.
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.
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");
}
}
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"
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.
2.Insert each person into the queue after counting his "NumberOfTaller":
- uuuouou February 18, 2014