Because the pool is less than the size of the yard, there must be at least one obstacle. The smallest possible obstacle is 1×1, but it has a one-unit pool-free band around it, making it effectively a 3×3 obstacle. If the obstacle is snug against a corner of the yard, it's effectively reduced to a 2×2 obstacle.
If a pool dimension is less than a yard dimension, it must be due to an obstacle. From the previous paragraph, 2 units the smallest possible reduction in size, making a (m - 1)×n pool an impossibility in a m×n yard.
Answers to this question where either completely right (four answers) or completely wrong (two answers).
See pretest question 9 for the answer.
Express your answer as a worst-case asymptotic analysis, clearly indicating the intput and output to your analysis, as well as the analysis itself. Assume a rectangular house.
The input to the analysis is m×n, the dimensions of the house. The output is the amount of money you have to spend. In the worst case, the house gets bigger, meaning you have to spend more money. As the house grows larger, the carpeting required grows by O(mn), while the amount of lighting required grows by O(max(m, n)), assuming a single strip of edge to edge fluorescent lighting along the ceiling.
Assuming the cost of carpeting and lighting are roughly comparable, and assuming there isn't a significant discount to be had by buying larger quantities, it's safer to pay for the lighting, the increase in cost for which is more slowly growing than is the increase in cost for carpeting.
This is an example of the kind of weird questions I like to ask. As a test-taking tip, if the question askes you to express your answer in a certain way, it's a good idea to express your question in this way. Three of the answers given didn't present any sort of asymptotic analysis; these answers didn't do too well. One correct answer cleverly assumed one fluorescent light per room with the number of rooms constant; the result was an even stronger argument in favor of lighting.
str and a single
character ch and returns two indices: one indicating the leftmost
occurrence of ch in str and the other indicating the rightmost
occurrence of ch in str. If ch does not occur in str both
indices should be -1.
For example given str = "hello world" and ch = 'o', your
function should return 4 for the left index and 7 for the right index. Given
str = "hello world" and ch = 'b', both the left and right
indices should be -1.
See pretest question 12 for the answer.
This page last modified on 7 February 2006.