Google Interview Question Software Engineer / Developers
Can we do it as recursion, i believe recursion is subset of DP.
After sorting, while iteration, when there is a conflict, there are two possibilities, and we can diverge from there. That is O(nlonn) i suppose.
This only works if all the heights are different. if the same heights are allowed for more people then it complicates things (Based on the problem text, the one on the top must be strictly less in height than the one below him/her). Could be actually solved by sorting by height and if height is the same sort by weight. After that the ones which have the same height needs to be compacted, having only one element and using various values. when doing the longest increasing subsequence algorithm, another binary search needs to be done to get the most appropriate weight value for a given height. Although, I doubt that this can be implemented as an interview problem as it involves quite a bit of coding.
I think its a variation of Box stacking DP problem.
It can be done as follows:
1. Sort the input in decreasing order of weight and find the longest decreasing sequence of hight.
2. Sort the input in decreasing order of hight and find the longest decreasing sequence of weight.
Take max of 1 and 2.
Time: O(N^2), Space: O(1)
wont the finding longest decreasing sequence of hight/weight has O(N) space complexity?
The overall space complexity of your algorithm should be O(N).
what are you talking about ,it's O(n^2)
LIS[n]=if(arr[n] not in order with arr[n-1]) , LIS[n-1]
else max(max(LIS[i] :i=0 to n-1) , LIS[n-1]+1)
Wrong, the person should be BOTH lighter and shorter than the person under him or her, yours only satisfy one criteria
1. sort people by their weights in decreasing order, without loss generality, assume the order is p_1, p_2, ... p_n
2. assume H(p_k) is the maximal height that can be achieved with the top people being p_k
3. It is obvious that H(p_k) = h_k + max(H(p_i), where i < k && h_i > h_k)
4. Let H(p_0) = 0 and h_0 = infinity and w_k = infinity
5. After calculate H(p_1) to H(p_k), find the maximal height in that array and return it
Space complexity: O(N)
Time complexity: (N^2)
Firstly, sort on the basis of either height or weight and then on the other field, do the same processing as we have done with Longest Decreasing subsequence.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Circus {
class Dimension implements Comparable<Dimension> {
int height;
int weight;
Dimension(int height, int weight) {
this.height = height;
this.weight = weight;
}
@Override
public int compareTo(Dimension d) {
return(this.height < d.height) ? 1 : this.height == d.height ? 0 : -1;
}
}
private void getMaxPeople(Dimension [] dimension, int n) {
int[] h = new int[n];
Arrays.fill(h, 1);
for(int i=0;i<n;i++) {
for(int j=i;j<n;j++){
if(dimension[j].weight < dimension[i].weight && h[j] < (h[i] + 1)) {
h[j] = h[i] + 1;
}
}
}
for(int i=0;i<n;i++) {
System.out.print(h[i] + " ");
}
System.out.println();
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the number of inputs");
int n = Integer.parseInt(br.readLine());
Dimension [] dimension = new Dimension[n];
System.out.println("Enter the coordinates");
Circus circus = new Circus();
for(int i=0;i<n;i++) {
dimension[i] = circus.new Dimension(Integer.parseInt(br.readLine()), Integer.parseInt(br.readLine()));
}
Arrays.sort(dimension);
circus.getMaxPeople(dimension, n);
}
}
Please let me know if I'm wrong, but here's my interpretation of this question.
I think we can't assume that weight and height go together - so, we might have:
(56, 90) , (60, 85) , (65, 100), (75, 190)
(in the above - 60,85 has higher weight but lower height than 56,90).
In any case - if we order it by height-then-weight we'd get the above (I would the actual sort by representing each person as Weight*1000 + Height).
Then we just need to pick our people - it doesn't have to be a sequence of people - so we can pick from the list above person A, person C, person D.
Can it be that simple?
<pre lang="" line="1" title="CodeMonkey45653" class="run-this">typedef struct PeopleData
{
int height;
int weight;
}PeopleData;
int peopleDataCompare(const void* data1, const void* data2)
{
PeopleData *d1 = (PeopleData*)data1;
PeopleData *d2 = (PeopleData*)data2;
if (d1->height < d2->height)
return -1;
else if (d1->height == d2->height)
return 0;
else
return 1;
}
int getMaxSortData(PeopleData *arr, int nLength)
{
if (NULL == arr)
return -1;
qsort(arr,nLength,sizeof(PeopleData),peopleDataCompare);
int max = 1;
int curMax = max;
int cur,next;
for (int i = 0;i < nLength;i++)
{
curMax = 1;
cur = i;
next = i+1;
while (next < nLength)
{
if (arr[cur].height != arr[next].height)
{
if (arr[cur].weight < arr[next].weight)
{
cur = next;
curMax++;
}
}
next++;
}
if (curMax > max)
max = curMax;
}
return max;
}
</pre><pre title="CodeMonkey45653" input="yes">
</pre>
First, form a directed graph using the height-weight pairs as nodes and putting an edge from one pair to another if the first has *both* height and weight greater than the second. This will take O(n^2) time and space.
Second, starting with each of the source nodes, i.e., those with no incoming edges, do a recursive procedure to compute the descendant node to use in order to form the maximum path to a sink node, i.e., those with no outgoing edges, recording also, for each node, the length of the maximum path. Note that this is a dynamic programming formulation: when you encounter a node that was previously encountered, you can just use its cached maximum path info. Now take a source node with a maximum path and follow the previously computed links to get the maximum path. This should take O(n) time and space.
1. Arrange the n persons in decreasing order of weight
2. Have an array of size n, which stores {humanChainSize if person is included, index of previous person}
3. For heaviest person, let Array[0] = {1, 0}. Here 1 corresponds to humanChainSize because the heaviest person is included and since he is the lowest person in human chain, there is no previous person to him and hence the index is set to 0.
4. For second heaviest person if it can stand on top of previous person(height should be lower that previous element), then Array[1] = {2, 0} and if the previous person cannot be included then let Array[1] = {1,1}
5. For the ith person, go through all elements Array[0] to Array[i-1] and find the index 'temp' (corresponding to person) where it can standup on. Update Array[i] = {Array[temp].humanChainSize+1,temp}. As we iterate, we need to update Array[i] if the new humanChainSize is greater.
6. When the iteration finishes, go through the Array from n to 0, find the element which has highest humanChainSize value, print the currentIndex. Find the index stored in the current element and go to Array[index] and print the element. Do it till currentIndex = index.
Complexity O(nlog(n)).
It can be done also via data structure - ternary tree with the following properties:
1. left node must have both properties less
2. right node must have both properties greater
3. mid node doesn't meet first two criterias
4. the node height is maximum of (left.height + 1, mid.height, right.height + 1)
In case we'll build this ternary tree with weight and height properties - the root node height will be the maximum human tower height. Here's the code:
#include <iostream>
#include <vector>
/**
* Calculate maximum human tower height, where next person
* to be shorter and ligther than a person below
*/
struct TernaryNode {
size_t height{0};
size_t weight{0};
size_t maxHeight{0};
TernaryNode *left{nullptr};
TernaryNode *mid{nullptr};
TernaryNode *right{nullptr};
bool operator<(const TernaryNode &other) {
return this->height < other.height &&
this->weight < other.weight;
}
bool operator>(const TernaryNode &other) {
return this->height > other.height &&
this->weight > other.weight;
}
};
TernaryNode* buildTTree(std::vector<std::pair<size_t, size_t> > &staff,
size_t index = 0) {
TernaryNode *node = new TernaryNode();
node->height = staff[index].first;
node->weight = staff[index].second;
if(index == staff.size() - 1) {
return node;
}
TernaryNode *subNode = buildTTree(staff, index + 1);
if(*subNode < *node) {
node->left = subNode;
node->maxHeight = std::max(node->maxHeight, subNode->maxHeight + 1);
} else if(*subNode > *node) {
node->right = subNode;
node->maxHeight = std::max(node->maxHeight, subNode->maxHeight + 1);
} else {
node->mid = subNode;
node->maxHeight = std::max(node->maxHeight, subNode->maxHeight);
}
}
size_t calcMaxTowerHt(std::vector<std::pair<size_t, size_t> > &staff) {
TernaryNode *node = buildTTree(staff);
return node->maxHeight;
}
int main()
{
std::vector<std::pair<size_t, size_t> > circusStaff{{60, 230}, {50, 130}, {56, 240},
{52, 220}, {57, 200}, {53, 160},
{58, 210}, {51, 140}, {55, 180},
{59, 220}};
std::cout << calcMaxTowerHt(circusStaff);
return 0;
}
I tried to solve it by using the approach described in Question 9.10 of Cracking the Coding Interview, but it doesn't work. Can someone tell me what's wrong?
public static ArrayList<HtWt> getIncreasingSequence(ArrayList<HtWt> people) {
if (people == null) {
return null;
} else if (people.size() == 0) {
return people;
} else {
return getIncreasingSequence(people, null);
}
}
public static ArrayList<HtWt> getIncreasingSequence(ArrayList<HtWt> people,
HtWt bottom) {
ArrayList<HtWt> max_list = new ArrayList<HtWt>();
for (int i = 0; i < people.size(); i++) {
if (canBeAbove(people.get(i), bottom)) {
ArrayList<HtWt> new_list = getIncreasingSequence(people,
people.get(i));
if (max_list == null || new_list.size() > max_list.size()) {
max_list = new_list;
}
if (bottom != null)
max_list.add(people.get(i));
}
}
return max_list;
}
public static boolean canBeAbove(HtWt compare, HtWt bottom) {
if (bottom == null) {
return true;
}
return compare.Ht < bottom.Ht && compare.Wt < bottom.Wt;
}
I've tried applying the tallest tower finding algorithm (9.10), but it doesn't work. Any ideas?
public static ArrayList<HtWt> getIncreasingSequence(ArrayList<HtWt> people) {
if (people == null) {
return null;
} else if (people.size() == 0) {
return people;
} else {
return getIncreasingSequence(people, null);
}
}
public static ArrayList<HtWt> getIncreasingSequence(ArrayList<HtWt> people,
HtWt bottom) {
ArrayList<HtWt> max_list = new ArrayList<HtWt>();
for (int i = 0; i < people.size(); i++) {
if (canBeAbove(people.get(i), bottom)) {
ArrayList<HtWt> new_list = getIncreasingSequence(people,
people.get(i));
if (max_list == null || new_list.size() > max_list.size()) {
max_list = new_list;
}
if (bottom != null)
max_list.add(people.get(i));
}
}
return max_list;
}
public static boolean canBeAbove(HtWt compare, HtWt bottom) {
if (bottom == null) {
return true;
}
return compare.Ht < bottom.Ht && compare.Wt < bottom.Wt;
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package Circlus;
import java.util.ArrayList;
import java.util.Collections;
/**
*
* @author Gangeshwari Rajavelu
*/
public class HtWt implements Comparable<HtWt>{
int ht;
int wt;
HtWt(int h,int w)
{
ht = h;
wt = w;
}
@Override
public int compareTo(HtWt o) {
if(this.ht == o.ht)
{
if(this.wt == o.wt)
{
return 0;
}
else
return this.wt>o.wt?1:-1;
}
else
{
return this.ht>o.ht?1:-1;
}
}
@Override
public String toString() {
return "("+ht+","+wt+")";
}
static int findMaxSeqLength(int[] wts)
{
int fitlength = 0;
int maxseqlength = 0;
for(int i =1;i<wts.length;i++)
{
if(wts[i]>wts[i-1])
{
if((i-1)==0 || i==wts.length-1)
fitlength+=1;
fitlength++;
}
else
{
fitlength = 0;
}
if(fitlength>maxseqlength)
maxseqlength = fitlength;
}
return maxseqlength;
}
public static void main(String args[])
{
ArrayList<Integer> maxSeqLengths = new ArrayList<Integer>();
HtWt obj1 = new HtWt(1,12);
HtWt obj2 = new HtWt(2,14);
HtWt obj3 = new HtWt(3,16);
HtWt obj4 = new HtWt(4,50);
HtWt obj5 = new HtWt(5,40);
HtWt obj6 = new HtWt(6,70);
ArrayList<HtWt> mylist = new ArrayList<>();
mylist.add(obj1);
mylist.add(obj2);
mylist.add(obj3);
mylist.add(obj4);
mylist.add(obj5);
mylist.add(obj6);
Collections.sort(mylist);
int[] wts = new int[mylist.size()];
int j = 0;
for(HtWt i:mylist)
{
System.out.println(i);
wts[j++] = i.wt;
}
int maxseqlength = findMaxSeqLength(wts);
System.out.println("length="+maxseqlength);
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package Circlus;
import java.util.ArrayList;
import java.util.Collections;
/**
*
* @author Gangeshwari Rajavelu
*/
public class HtWt implements Comparable<HtWt>{
int ht;
int wt;
HtWt(int h,int w)
{
ht = h;
wt = w;
}
@Override
public int compareTo(HtWt o) {
if(this.ht == o.ht)
{
if(this.wt == o.wt)
{
return 0;
}
else
return this.wt>o.wt?1:-1;
}
else
{
return this.ht>o.ht?1:-1;
}
}
@Override
public String toString() {
return "("+ht+","+wt+")";
}
static int findMaxSeqLength(int[] wts)
{
int fitlength = 0;
int maxseqlength = 0;
for(int i =1;i<wts.length;i++)
{
if(wts[i]>wts[i-1])
{
if((i-1)==0 || i==wts.length-1)
fitlength+=1;
fitlength++;
}
else
{
fitlength = 0;
}
if(fitlength>maxseqlength)
maxseqlength = fitlength;
}
return maxseqlength;
}
public static void main(String args[])
{
ArrayList<Integer> maxSeqLengths = new ArrayList<Integer>();
HtWt obj1 = new HtWt(1,12);
HtWt obj2 = new HtWt(2,14);
HtWt obj3 = new HtWt(3,16);
HtWt obj4 = new HtWt(4,50);
HtWt obj5 = new HtWt(5,40);
HtWt obj6 = new HtWt(6,70);
ArrayList<HtWt> mylist = new ArrayList<>();
mylist.add(obj1);
mylist.add(obj2);
mylist.add(obj3);
mylist.add(obj4);
mylist.add(obj5);
mylist.add(obj6);
Collections.sort(mylist);
int[] wts = new int[mylist.size()];
int j = 0;
for(HtWt i:mylist)
{
System.out.println(i);
wts[j++] = i.wt;
}
int maxseqlength = findMaxSeqLength(wts);
System.out.println("length="+maxseqlength);
}
}
package Circlus;
import java.util.ArrayList;
import java.util.Collections;
/**
*
* @author Gangeshwari Rajavelu
*/
public class HtWt implements Comparable<HtWt>{
int ht;
int wt;
HtWt(int h,int w)
{
ht = h;
wt = w;
}
@Override
public int compareTo(HtWt o) {
if(this.ht == o.ht)
{
if(this.wt == o.wt)
{
return 0;
}
else
return this.wt>o.wt?1:-1;
}
else
{
return this.ht>o.ht?1:-1;
}
}
@Override
public String toString() {
return "("+ht+","+wt+")";
}
static int findMaxSeqLength(int[] wts)
{
int fitlength = 0;
int maxseqlength = 0;
for(int i =1;i<wts.length;i++)
{
if(wts[i]>wts[i-1])
{
if((i-1)==0 || i==wts.length-1)
fitlength+=1;
fitlength++;
}
else
{
fitlength = 0;
}
if(fitlength>maxseqlength)
maxseqlength = fitlength;
}
return maxseqlength;
}
public static void main(String args[])
{
ArrayList<Integer> maxSeqLengths = new ArrayList<Integer>();
HtWt obj1 = new HtWt(1,12);
HtWt obj2 = new HtWt(2,14);
HtWt obj3 = new HtWt(3,16);
HtWt obj4 = new HtWt(4,50);
HtWt obj5 = new HtWt(5,40);
HtWt obj6 = new HtWt(6,70);
ArrayList<HtWt> mylist = new ArrayList<>();
mylist.add(obj1);
mylist.add(obj2);
mylist.add(obj3);
mylist.add(obj4);
mylist.add(obj5);
mylist.add(obj6);
Collections.sort(mylist);
int[] wts = new int[mylist.size()];
int j = 0;
for(HtWt i:mylist)
{
System.out.println(i);
wts[j++] = i.wt;
}
int maxseqlength = findMaxSeqLength(wts);
System.out.println("length="+maxseqlength);
}
}
1. sort the input persons by height. O(nlogn)
- wenlei.zhouwl May 20, 20122. find the longest increasing weight sequence in the sorted list. This can be done in O(nlogn) with DP.