Databases
StackOverflow2013
Postsdbo
POAlgorithm for Human Towering
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAlgorithm for Human Towering
    primarykey
    data
    text
    <p>In <a href="http://www.amazon.co.uk/Cracking-Coding-Interview-Fourth-Edition/dp/145157827X/ref=sr_1_2?ie=UTF8&amp;qid=1374531842&amp;sr=8-2&amp;keywords=cracking%20the%20coding%20interview" rel="nofollow">Cracking the Coding Interview, Fourth Edition</a>, there is such a problem:</p> <blockquote> <p>A circus is designing a tower routine consisting of people standing atop one anoth- er’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.</p> <p>EXAMPLE: Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) </p> <p>Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)</p> </blockquote> <hr> <p>Here is its <strong>solution in the book</strong></p> <blockquote> <p>Step 1 Sort all items by height first, and then by weight This means that if all the heights are unique, then the items will be sorted by their height If heights are the same, items will be sorted by their weight</p> <p>Step 2 Find the longest sequence which contains increasing heights and increasing weights To do this, we:</p> <p>a) Start at the beginning of the sequence Currently, max_sequence is empty</p> <p>b) If, for the next item, the height and the weight is not greater than those of the previous item, we mark this item as “unfit”</p> <p>c) If the sequence found has more items than “max sequence”, it becomes “max sequence”</p> <p>d) After that the search is repeated from the “unfit item”, until we reach the end of the original sequence</p> </blockquote> <hr> <p>I have some questions about its solutions.</p> <p><strong>Q1</strong></p> <p>I believe this solution is wrong.</p> <p>For example</p> <p><code>(3,2) (5,9) (6,7) (7,8)</code></p> <p>Obviously, <code>(6,7)</code> is an unfit item, but how about <code>(7,8)</code>? According to the solution, it is NOT unfit as its h and w are bother bigger than <code>(6,7)</code>, however, it cannot be considered into the sequence, because <code>(7,8)</code> does not fit <code>(5,9)</code>.</p> <p>Am I right?</p> <p>If I am right, what is the fix?</p> <p><strong>Q2</strong></p> <p>I believe even if there is a fix for the above solution, the style of the solution will lead to at least <code>O(n^2)</code>, because it need to iterate again and again, according to step 2-d.</p> <p>So is it possible to have a O(nlogn) solution?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USColonel Panic
    1. USJackson Tale
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POAlgorithm for Human Towering
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. POAlgorithm for Human Towering
      1. This table or related slice is empty.
      1. VTDownMod
    3. VO
      singulars
      1. POAlgorithm for Human Towering
      1. This table or related slice is empty.
      1. VTUpMod
    1. COClarify. Step b says "... mark this item..." but is "this" item the "previous" or the "next" item from the first part of the step? Secondly, if you find an "unfit" item, is it skipped? Does it end the sequence? I also don't understand what "the search is repeated" in step D means.
      singulars
      1. POAlgorithm for Human Towering
      1. USLee Meador
    2. COThe algorithm may or may not be correct, but the way it's described seems to leave it impervious to most attempts at understanding it... If that's verbatim from the book, I'd get rid of it.
      singulars
      1. POAlgorithm for Human Towering
      1. USJacob Raihle
    3. COEchoing what JacobRaihle said, that book doesn't seem to have been proofread very well. I remember reading the first few chapters and finding a few errors in the solutions/edge cases that were uncovered. It does a good job of outlining topics you should cover in your prep, but it didn't seem particularly authoritative in any of the information it covered.
      singulars
      1. POAlgorithm for Human Towering
      1. USrliu
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload