[Hard] interview questions #8

[rygh4775]

Circus Tower: 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.

[RoyMoon]

Solution :

1. Sorting by height or weight.
2. iterate loop and make two a two branch. element with in(if valid) or without.
3. find logest subset.

Solution 1 : Recursive

ArrayList<HtWt> longestlncreasingSeq(ArrayList<HtWt> items) 
{ 
     Collections.sort(items);
     return bestSeqAtlndex(items, new ArrayList<HtWt>(), 0);
}

ArrayList<HtWt> bestSeqAtlndex(ArrayList<HtWt> array, ArrayList<HtWt> sequence, int index) 
{
      if (index >= array.size()) return sequence; 
      HtWt value = array.get(index);
      ArrayList<HtWt> bestWith = null;
      if(canAppend(sequence, value)) {
           ArrayList<HtWt> sequenceWith = (ArrayList<HtW>) sequence.clone(); 
           sequenceWith.add(value);
           bestWith = bestSeqAtlndex(array, sequenceWith, index + 1);
      } 
        ArrayList<HtWt> bestWithout = bestSeqAtlndex(array, sequence, index + 1);
       if (bestWith == null || bestwithout.size() > bestWith.size()) 
        { 
            return bestWithout;
         }
        else 
       {
           return bestWith;
       }
}

boolean canAppend(ArrayList<HtWt> solution, HtWt value) { 
    if (solution == null) return false;
    if (solution.size() == 0) return true;
    HtWt last = solution.get(solution.size() -1)
    return last.isBefore(value); 
}

TimeComplexity

O(2^n) = 바이너리 트리 순회 시간 (2^n -1)

Solution 2 : Iteratorative

ArrayList<HtWt> longestlncreasingSeq(ArrayList<HtWt> array) {
 Collections.sort(array);
 ArrayList<ArrayList<HtWt>> solutions new ArrayList<ArrayList<HtWt>>();
  ArrayList<HtWt> bestSequence = null;

  for (int i = 0; i < array.size(); i++) {
      ArrayList<HtWt> longestAtlndex = bestSeqAtlndex(array, solutions, i); 
      solutions.add(i,longestAtlndex);
      bestSequence = max(bestSequence, longestAtlndex);
  }
return bestSequence;
 }
ArrayList<HtWt> bestSeqAtlndex(ArrayList<HtWt> array,
    ArrayList<ArrayList<Htwt>> solutions, int index) {
    HtWt value =array.get(index);

    ArrayList<HtWt > bestSequence = new ArrayList <Htwt>();
    for (int i =0; i <index; i++) {
      ArrayList<HtWt> solution =solutions.get(i);
       if (canAppend(solution, value)) {
        bestSequence = max(solution, bestSequence); 
       }
     }
     ArrayList<HtWt> best = (ArrayList<HtWt>)bestSequence.clone();
     best.add(value); 
    return best;
}

TimeComplexity

O(n^2)