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$
13
  • 4
    $\begingroup$ The answer is probably something exceedingly silly such as "a 500 page book has constant size so it's $O(1)$". $\endgroup$ Dec 16, 2014 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, 2014 at 12:25
  • $\begingroup$ This is a problem that has been solved very efficiently in China. It is $O(1)$. $\endgroup$
    – babou
    Dec 16, 2014 at 21:39
  • $\begingroup$ @babou Could you please explain it? $\endgroup$
    – hengxin
    Dec 17, 2014 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, 2014 at 7:42

2 Answers 2

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.