2
$\begingroup$

I was asked the following question in an interview:

How would you count the occurrences of character a in a 500-page book? For simplicity, assume that you are given the book content as a string.

I answered that linear traversal through the book is the best possible solution, since the character can randomly occur in any position, and we cannot figure out until we check every character. However, the interviewer kept insisting on a more efficient algorithm. What algorithm would be more efficient than O(n) for this problem? (if any)

$\endgroup$

closed as off-topic by Tsuyoshi Ito, R B, Kristoffer Arnsfelt Hansen, Marzio De Biasi, Sasho Nikolov Dec 17 '14 at 8:44

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Tsuyoshi Ito, R B, Kristoffer Arnsfelt Hansen, Marzio De Biasi, Sasho Nikolov
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ The answer is probably something exceedingly silly such as "a 500 page book has constant size so it's $O(1)$". $\endgroup$ – Tom van der Zanden Dec 16 '14 at 12:12
  • 4
    $\begingroup$ You must check every character somehow, otherwise your algorithm returns the same answer whether the unchecked character is an 'a' or not (and hence must be wrong for one of these cases). So any alg must be $\Omega(n)$ to get an exact solution. Linear traversal seems the best $O(n)$ algorithm unless you have access to other operations.... One could approximate the answer by sampling $n$ random locations and counting the fraction that are 'a' (a Chernoff bound gives the error of this method, since the number of occurrences is a binomial with probability equal to the true fraction of 'a's). $\endgroup$ – usul Dec 16 '14 at 12:25
  • $\begingroup$ This is a problem that has been solved very efficiently in China. It is $O(1)$. $\endgroup$ – babou Dec 16 '14 at 21:39
  • $\begingroup$ @babou Could you please explain it? $\endgroup$ – hengxin Dec 17 '14 at 3:41
  • $\begingroup$ An algorithm can be more efficient than another while both have the same (worst case) asymptotic complexity. The constants do matter in the real world. Anyways, perhaps you could use the structure of the English language (or properties of the encoding e.g. ASCII) to get some sort of speed up. $\endgroup$ – mdxn Dec 17 '14 at 7:42
8
$\begingroup$

You could try sampling. The assumption that the proportion of a's on any given page is roughly the same as on any other one (and that all pages have roughly the same amount of text) seems reasonable. If $n$ is the total number of pages, you could pick, say $k=n^{4/5}$ random pages, count their average number of characters and the proportion of a's, and scale up to $n$. Your runtime would be $O(n^{4/5})$, and with high probability, your estimate for the number of a's would deviate from the true count by $\tilde O(n^{3/5})$.

You can play with the exponents to get other accuracy-runtime tradeoffs (e.g., in $O(n)$ time you can achieve whp a deviation of $\tilde O(\sqrt n)$).

As pointed out in the comments, an exact count requires $\Omega(n)$ runtime. If the interviewer absolutely insisted on a sublinear runtime, I would suggest sampling.

$\endgroup$
2
$\begingroup$

"For simplicity, assume that you are given the book content as a string"

Then, as we already have the string in memory we don't spend operations reading the contents into memory and we can go directly to count the number of occurrences.

In my opinion its valid to say that an integer operation can be executed in $O(1)$ that includes addition, subtraction, multiply, division and obviously binary comparison operations.

Modify the pointer to string to be a UINT64 array pointer

Iterate the array and for each element (representing 64 bits or 8 characters assuming 1 byte per character) execute a function that by using less than 8 integer binary comparisons accurately tell you how many 'As' are in the element structure.

let $M$ be the number of steps required by such function and $N$ the number of characters

Your supposed upper bound complexity will be then $O((N/8)*M)$

Obviously this is just a fake solution however it could fit real world and interviews are not theoretical exams, the interviewer were just trying to learn how you workout a problem, sometimes is not necessary to have a final valid solution but just show how capable are you to pursue a potential solution.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.