CODEWITHSUNDEEP
pythonpython-3.xlis
Blake French
Blake French

Reputation: 53

Cracking The Coding Interview - Circus Tower Problem (17.8)

Question:

I'm working through Cracking the Coding Interview 6th ed, and I'm having trouble with the Circus Tower problem (number 17.8). I have a solution that I think runs in O(N logN) time, but the book's solution (which is different) says that the O(N logN) solution is very complex, but my code is not. I'd like some help figuring out if my solution is correct, and if it actually runs in O(N logN) time. I want to understand why I am wrong (or right), so any details would be helpful.

Here's the problem text:

A circus is designing a tower routine consisting of people standing atop one another's shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.

My solution:

def circus_tower(people):
    
    # People is a list of tuples of length 2, where item[0] is their height, and item[1] is their weight.
    
    if len(people) == 0:
        return 0
    
    people = sorted(people, key=lambda x: x[0])  # Sort people by heights. O(P*logP).
    start = 0
    end = 0
    longest_sequence = 0
    
    for i in range(1, len(people)):  # O(P).
        if people[i][1] > people[i-1][1]:  # Weight check.
            end = i
        else:
            longest_sequence = end - start + 1
            start = i
            end = i
    
    return max(longest_sequence, end - start + 1)

Here are some sample inputs and what my code returns:

circus_tower([(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110)])
6

circus_tower([(65, 100), (70, 150), (56, 90), (75, 190), (65, 95), (68, 110)])
4

circus_tower([(56, 90), (65, 95), (72, 100), (68, 90), (70, 150), (75, 190)])
2

circus_tower([])
0

Upvotes: 3

Views: 2821

Answers (5)

Pro_Cas
Pro_Cas

Reputation: 1

I went through this thread and decided I can attempt to clarify this. Consider this as an example of those cases where a greedy approach does not work because we are not able to decide for sure if taking a particular element is invariably the better solution that not taking it. We have seen a similar problem with Knapsack 0/1 problem. If you are given the weights: [1,2,3,4] and profits [80, 100, 20, 60] and your capacity is 5, then greedily you can choose 120 (100+20), but then you will realise that leaving out 100 was the better choice, since you could have got 140 (60+80).

To solve this problem, we need to assume a somewhat similar approach: first let's sort the array of people, because unlike in case of Knapsack, here the order of taking elements matters. But both of these approaches boils down to a similar idea: to optimize the output, should you take the nth element or leave it?

Here is my Java recursive solution which runs in O(2^n) complexity:

Approach-1: Recusrive/Backtracking solution

public static void makeTower(List<Person> list, List<Person> tower, int index)
{
    //Base case
    if(index==-1)
    {
        printTower(tower);
        return;
    }
    if(tower.get(tower.size()-1).height > list.get(index).height && tower.get(tower.size()-1).weight > list.get(index).weight) {
        tower.add(list.get(index));
        //if it is possible to add this person to the tower, add him
        makeTower(list, new ArrayList<>(tower), index - 1);
    }
        //OR, choose to exclude the person
        tower.remove(list.get(index));
        makeTower(list, new ArrayList<>(tower), index-1);

}

Where "Person" class is just the encapsulation of his height and weight

public class Person {
int height;
int weight;
public Person(int _h, int _w)
{
    this.height = _h;
    this.weight = _w;
}
}

And "printTower" method does nothing but just print the possible tower to you after every combination

public static void printTower(List<Person> t)
{
    for(Person p : t)
        System.out.println(p.height+" , "+p.weight);
    System.out.println("-----END-----");
}

Test input and output:

So if we consider this example:

The people (height, weight) : [20, 80] [10, 40] [80, 40] First step, sort by heights -> [10, 40] [20, 80] [80, 40] Then, we can possibly construct these towers:

[10, 40] on top of [20, 80]

This is the only tower possible from all the combinations.

So finally, the main (driver) method:

public static void main(String args[])
{
    List<Person> people = new ArrayList();
    people.add(new Person(20,80));
    people.add(new Person(10, 40));
    people.add(new Person(80, 40));
    Collections.sort(people, new Comparator<Person>()
    {
        @Override
        public int compare(Person one, Person two)
        {
            return (one.height-two.height);
        }
    });
  
    List<Person> t = new ArrayList<>();
    t.add(new Person(1000,1000));
    makeTower(people, t, people.size()-1);
}

As mentioned, the runtime complexity of this algorithm is exponential, but it turns out that there is a better method for this which suits only this problem. This solution is explained in Cracking the coding interview.

Approach 2 - Dynamic Programming

The second approach runs in O(n^2) complexity, not pretty but definitely a lot of improvement over exponential. The approach is that we will take turns to consider each person as the last person in the tower. How long will the tower run if person-0 is the last person? And so on till person-n. In our case,

length of tower(given person-0 is at base) : 2 (highest) length of tower(given person-1 is at base) : 1 length of tower(given person-2 is at base) : 1

So 2 is our answer (maximum tower size). Bam! That's our answer. Much less fuss, but as with most DP approaches, the problem with this approach is that its a much more specific type of solution that may/may not suit other similar types of problems, and hence a tad bit more difficult to come up with.

Since this post has already run so long, let me know if anyone would need the code for approach-2 with explanation, would be glad to help! :)

Upvotes: 0

Vimit Dhawan
Vimit Dhawan

Reputation: 677

I have divided the problem into three parts.

  1. Insert the data HeightWeight object and then sort with height or width. I have sorted with height

  2. After that insert the values into the map to get unique heights with minimum weight.

  3. After that I have found the Longest Increasing subsequence for weight.

    import java.util.*;
public class CircusTower {
private class HeightWeight implements Comparable<HeightWeight>{
    int height;
    int weight;
    HeightWeight(int height, int weight) {
        this.height = height;
        this.weight = weight;
    }
    @Override
    public int compareTo(HeightWeight other) {
        if(this.height == other.height){
            return this.weight - other.weight;
        }else{
            return this.height - other.height;
        }
    }
}
public static void main(String[] args) {
    int[][] arr = {{1,1},{1,7},{1,9},{2,2},{2,6},{3,3},{3,5},{4,4}};
    CircusTower ct = new CircusTower();
   System.out.println(ct.getMaxHeightTower(arr));
}

public int getMaxHeightTower(int[][] arr){
    List<HeightWeight> list = new ArrayList<>();
    int i =0;
    for(i =0; i<arr.length; i++){
        list.add(new HeightWeight(arr[i][0], arr[i][1]));
    }
    Collections.sort(list);
    Map<Integer, Integer> map = new HashMap<>();
    for(i =0; i<list.size(); i++){
        HeightWeight current = list.get(i);
        if(!map.containsKey(current.height)){
            map.put(current.height, current.weight);
        }
    }
    int[] nums = map.values().stream().mapToInt(Integer::intValue).toArray();
    return getLIS(nums);
}

public int getLIS(int[] nums){

    int _l = nums.length;
    int[] out = new int[_l];
    int mx = Integer.MIN_VALUE;

    /*
    we initialize the array with ones because
    a single character has a subsequence of length one
    */
    Arrays.fill(out, 1);

    for(int i = 0; i < _l; i++)

        for(int j = i + 1; j < _l; j++){
            /*
            every iteration, all we're doing is checking what is the longest
            increasing subsequence so far, till this point
            */
            if(nums[j] > nums[i])
                out[j] = Math.max(out[j], out[i] + 1);

            /*
            we keep checking for a max value because the longest
            subsequence could exist before the end of the string
            */
            mx = Math.max(out[j], mx);
        }

    return mx == Integer.MIN_VALUE ? 1 : mx;
}

    }

Upvotes: 0

Alexander
Alexander

Reputation: 485

There is a correct solution

module CircusTowerSo
  class Person
    include Comparable

    attr_reader :height, :weight

    def initialize(height, weight)
      @height = height
      @weight = weight
    end

    def <=>(other)
      res = height <=> other.height

      if res == 0
        weight <=> other.weight
      else
        res
      end
    end

    def smaller?(other)
      height < other.height && weight < other.weight
    end

    def to_s
      "(#{height}, #{weight})"
    end

    def inspect
      to_s
    end
  end

  # Time=O(n * n) Mem=O(n * n)
  def solve_b(people)
    sorted = people.sort

    find_lis_by_weight(sorted).size
  end

  def find_lis_by_weight(people)
    longest_by_index_cache = people.each_with_index.map { |person, i| [i, [person]] }.to_h
    longest = []

    people.each_with_index do |person, index|
      res = longest_for_index(longest_by_index_cache, index, person)

      if res.size > longest.size
        longest = res
      end

      longest_by_index_cache[index] = res
    end

    longest
  end

  def longest_for_index(longest_by_index_cache, index, person)
    longest_prev_seq = []

    index.times do |i|
      prev_seq = longest_by_index_cache[i]

      if prev_seq.last.smaller?(person) && prev_seq.size > longest_prev_seq.size
        longest_prev_seq = prev_seq
      end
    end

    longest_prev_seq + [person]
  end


  RSpec.describe 'CircusTower' do
    include CircusTower

    subject { solve_b(people) }

    context 'book example' do
      let(:people) do
        [
          Person.new(65, 100),
          Person.new(70, 150),
          Person.new(56, 90),
          Person.new(75, 190),
          Person.new(60, 95),
          Person.new(68, 110),
        ]
      end

      it { is_expected.to eq 6 }
    end

    context 'tricky example' do
      let(:people) do
        [
          Person.new(1, 1),
          Person.new(1, 7),
          Person.new(1, 9),
          Person.new(2, 2),
          Person.new(2, 6),
          Person.new(3, 3),
          Person.new(3, 5),
          Person.new(4, 4),
        ]
      end

      it { is_expected.to eq 4 }
    end

    context 'more tricky example' do
      let(:people) do
        [
          Person.new(1, 1),
          Person.new(2, 2),
          Person.new(3, 3),
          Person.new(4, 1),
        ]
      end

      it { is_expected.to eq 3 }
    end
  end
end

see more solutions for CTCI on https://github.com/holyketzer/ctci_v6

Upvotes: 0

Alexander
Alexander

Reputation: 485

I also "found" a simple solution and can't understand where I'm wrong:

module CircusTower
  class Person
    include Comparable

    attr_reader :height, :weight

    def initialize(height, weight)
      @height = height
      @weight = weight
    end

    def <=>(other)
      res = height <=> other.height

      if res == 0
        weight <=> other.weight
      else
        res
      end
    end
  end

  # Time=O(n * log n) Mem=O(n)
  def solve_b(people)
    sorted = people.sort.reverse

    res = []

    sorted.each do |person|
      if res.size == 0
        res << person
      else
        if res.last.height > person.height && res.last.weight > person.weight
          res << person
        end
      end
    end

    res.size
  end

  RSpec.describe 'CircusTower' do
    include CircusTower

    subject { solve_b(people) }

    context 'book example' do
      let(:people) do
        [
          Person.new(65, 100),
          Person.new(70, 150),
          Person.new(56, 90),
          Person.new(75, 190),
          Person.new(60, 95),
          Person.new(68, 110),
        ]
      end

      it { is_expected.to eq 6 }
    end

    context 'tricky example' do
      let(:people) do
        [
          Person.new(1,1),
          Person.new(1,7),
          Person.new(1,9),
          Person.new(2,2),
          Person.new(2,6),
          Person.new(3,3),
          Person.new(3,5),
          Person.new(4,4),
        ]
      end

      it { is_expected.to eq 4 }
    end
  end
end

Upvotes: 0

antonio
antonio

Reputation: 154

Your solution is wrong. If you run

circus_tower([[1,1],[1,7],[1,9],[2,2],[2,6],[3,3],[3,5],[4,4]])

it returns 2 while the longest subsequence ([1,1]<[2,2]<[3,3]<[4,4]) has length 4.

The problem with your code is that you only find contiguous subsequences.

Upvotes: 2

Related Questions