<p>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})$.</p>

<p>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)$).</p>

<p>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.</p>

CC BY-SA 3.0
2014-12-16T14:02:30.130Z
2014-12-16T14:19:42.220Z
2014-12-16T14:19:42.220Z
Aryeh
<p>"For simplicity, assume that you are given the book content as a string"</p>

<p>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.</p>

<p>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.</p>

<p>Modify the pointer to string to be a UINT64 array pointer</p>

<p>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.</p>

<p>let $M$ be the number of steps required by such function and $N$ the number of characters</p>

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

<p>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.</p>

CC BY-SA 3.0
2014-12-16T21:33:47.047Z
2014-12-17T00:59:54.620Z
2014-12-17T00:59:54.620Z
Jesus Salas
<p>I was asked the following question in an interview:</p>

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

<p>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)</p>

CC BY-SA 3.0
2014-12-16T12:12:49.403Z
The answer is probably something exceedingly silly such as "a 500 page book has constant size so it's $O(1)$".
Tom van der Zanden
CC BY-SA 3.0
2014-12-16T12:25:50.730Z
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).
usul
CC BY-SA 3.0
2014-12-16T21:39:09.790Z
This is a problem that has been solved very efficiently in China. It is $O(1)$.
babou
CC BY-SA 3.0
2014-12-17T03:41:22.323Z
@babou Could you please explain it?
hengxin
CC BY-SA 3.0
2014-12-17T07:42:59.200Z
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.
mdxn
CC BY-SA 3.0
2014-12-17T12:25:40.573Z
@hengxin Only a joke. Chinese writing does not use that letter.
babou
CC BY-SA 3.0
2014-12-17T14:49:44.550Z
Huh, why is an algorithms question "off topic" on Theoretical Computer Science site?
Masked Man
CC BY-SA 3.0
2014-12-17T14:50:54.227Z
If the question is suitable for another site, just move it there, duh!
Masked Man
CC BY-SA 3.0
2014-12-17T15:12:40.210Z
@Happy cstheory.se is specifically meant for research level questions while cs.se is appropriate for any. Don't worry, I'm sure it will get migrated.
mdxn
CC BY-SA 3.0
2014-12-17T16:31:12.157Z
Well, then maybe you should rename the site to "Research Computer Science" or something like that.
Masked Man
CC BY-SA 3.0
2014-12-17T16:34:48.987Z
Oh, and don't bother with the migration. I will delete this question. No point in trying to enter your house through another door after you smashed the front door in my face.
Masked Man
CC BY-SA 3.0
2014-12-17T16:35:53.620Z
Wow, now I can't even delete this question. What a fantastic example of theoretical computer science.
Masked Man
CC BY-SA 3.0
2014-12-17T18:03:23.380Z
@Happy I share your frustration with the lack of clarity that this exchange has. You shouldn't be unhappy though. You got your question answered 2-3 different ways and it happened to be well received. I can do nothing with the name of the site. In all honesty, I barely even participate on it.
mdxn
<ds.algorithms>
Counting occurences of 'a' in a book faster than O(n)?
Masked Man
# Counting occurences of 'a' in a book faster than O(n)?

(Asked by: username_0 on 2014-12-16)

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)

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: The answer is probably something exceedingly silly such as "a 500 page book has constant size so it's $O(1)$".  
> **username_2**: 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).  
> **username_3**: This is a problem that has been solved very efficiently in China. It is $O(1)$.  
> **username_4**: @babou Could you please explain it?  
> **username_5**: 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.  
> **username_3**: @hengxin Only a joke. Chinese writing does not use that letter.  
> **username_0**: Huh, why is an algorithms question "off topic" on Theoretical Computer Science site?  
> **username_0**: If the question is suitable for another site, just move it there, duh!  
> **username_5**: @Happy cstheory.se is specifically meant for research level questions while cs.se is appropriate for any. Don't worry, I'm sure it will get migrated.  
> **username_0**: Well, then maybe you should rename the site to "Research Computer Science" or something like that.  
> **username_0**: Oh, and don't bother with the migration. I will delete this question. No point in trying to enter your house through another door after you smashed the front door in my face.  
> **username_0**: Wow, now I can't even delete this question. What a fantastic example of theoretical computer science.  
> **username_5**: @Happy I share your frustration with the lack of clarity that this exchange has. You shouldn't be unhappy though. You got your question answered 2-3 different ways and it happened to be well received. I can do nothing with the name of the site. In all honesty, I barely even participate on it.  

---

## 2 answers

### Answer by username_6 on 2014-12-16. Score: 8

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.


---

### Answer by username_7 on 2014-12-16. Score: 2

"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.


---

