0
$\begingroup$

I was recently in an interview and was asked what would be the smallest memory foot print and fastest system to check if a given phone number is in your data store given that all phone numbers will only be 7 digits.

I was told the answer is a byte but, I'm still not 100% sure how this would work and have not been able to find any information on it as of yet. If anyone knows the name of the structure/algorithm or would be willing to explain it I would be very appreciative.

Example data set:
6041234567
6041234568
6041234569
6041234570
6041234571

Output if checking for 6041234569:
True

Output if checking for 6041234580:
False

Edit: Please ask questions so I can try and make my question more clear.
Edit2: I only need to know if the phone number exists. I don't need to get it out.

$\endgroup$

closed as unclear what you're asking by David Richerby, Evil, fade2black, Yuval Filmus, Rick Decker Sep 4 '17 at 16:24

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What do you mean by "data structure"? Is the string itself a data structure? Does the code if (s[0]=='1' && s[1]=='2' && s[3]=='3' && s[4]=='-' && s[5]>='0' && s[5]<='9' && ...) {...} even use a data structure at all? $\endgroup$ – David Richerby Sep 1 '17 at 20:40
  • 3
    $\begingroup$ Voting to close as unclear, but I'm not even convinced that this is computer science rather than programming. $\endgroup$ – David Richerby Sep 1 '17 at 20:41
  • $\begingroup$ @DavidRicherby Would you be able to elaborate on why this isn't a computer science question? $\endgroup$ – SudoKid Sep 1 '17 at 20:57
  • $\begingroup$ It is clear from the form of the question and the suggested correct answer what the intention behind the interview question was. It might have been poorly worded and I agree that it falls foul of the problem of converting data into code as pointed out. But at the end of the day all that @DavidRicherby does in his comment above is loop unrolling the DFA evaluation. $\endgroup$ – Ukko Sep 1 '17 at 21:07
  • $\begingroup$ @Ukko I'm aware that the question is poorly worded and I'm trying to fix that. Any questions about it would help me reword it. My goal with this question is to learn more about the system the interviewer put forward which is a byte search system of some kind. $\endgroup$ – SudoKid Sep 1 '17 at 21:20
1
$\begingroup$

It's possible, if the "data store" referred to is small enough, that an 8-bit Bloom Filter or some better equivalent would be the answer they're looking for.

God only knows what a good enough set of hash functions would look like though…

$\endgroup$
  • $\begingroup$ I'll look into the bloom filter thing $\endgroup$ – SudoKid Sep 2 '17 at 0:48
  • $\begingroup$ I think this has pointed me in the right direction. It may have been a bit array or a bloom filter. Thanks for this. I'm going to keep reading. $\endgroup$ – SudoKid Sep 2 '17 at 1:00
  • $\begingroup$ You have to recognize 1,000,000 different phone numbers. Here is a handy calculator for the size of the bit array you would need to get a 1% false positive rate hur.st/bloomfilter?n=1000000&p=0.01 This says your filter will need to 1.14MB in size. $\endgroup$ – Ukko Sep 2 '17 at 2:35
  • $\begingroup$ Also the calculation in my other comment was based on the original version of the question where you were recognizing number from the same area code. In the single number case you get hur.st/bloomfilter?n=1&p=0.01 which yields a filter size of 10 bits. That still has a 1% false positive rate. $\endgroup$ – Ukko Sep 2 '17 at 3:22
  • $\begingroup$ Ah, a million different numbers would be hard work with such a small filter :) $\endgroup$ – Will Crawford Sep 2 '17 at 9:10
1
$\begingroup$

Rewritten to match the new edited version of the question

What you want to think about is the size of the state for a DFA corresponding to a regular expression to match the number in question.

(I don't know how to draw DFAs here so work with my hand waving if you can.)

Since the thing you are looking for is a constant string the regular expression is just that string, say for example 6041234567. As a DFA this is a start node connected 10 intermediate nodes and a final accepting node. Then each of these nodes connect to the next node if the next character is the right one in the stream or back to the start if it is an incorrect input. If you ever reach the final accepting node you have found the phone number and can do a happy dance.

That is all a setup for the fact that the only thing that matters state-wise is the current node you are matching on. In my simple example here there are 12 nodes total, so you really only need 4 bits of data.

So you could have one upped the interviewer and said that in reality all you needed is a single nybble, instead of a whole byte.

A note about loop unrolling and state hiding

You can also achieve this by just writing a long list of checks for each individual digit as David commented above with what appears to be zero state. But what that long list of checks is really doing is just moving the state into the program counter. You can do that with any fixed length matching problem, it is technically true but not really interesting.

One can also argue that I am moving state into the DFA, how is that represented? That is a fair cop, if one is being super pedantic, we would have to specify things like "A DFA is a 5-tuple consisting of yada yada yada" when we really need that precision. Unless you were interviewing for a position in CS theory or compiler design no interviewer would be going there.

The reason that I am pretty certain that my answer is the right one in this case is that this question sounds like one that is asked all the time. About half-way through a Theory of Computation course right after you learn about using DFAs to match REGEXPs you will look into the number of states and how to represent them. This gives a nice intuition about the complexity and "size" of the various languages they match. It also nicely segues into the way that removing determinism can greatly shrink the resulting transition graph and going the other way can result in an explosion in the number of states.

$\endgroup$
  • $\begingroup$ The DFA you describe seems to accept any string that ends 123-ddd-dddd, which isn't the correct language. Also, I'm not sure why you say "use a regular expression" and then explain how to use a DFA. Regular expressions and DFAs aren't the same thing, even though they accept the same languages. $\endgroup$ – David Richerby Sep 1 '17 at 20:36
  • $\begingroup$ @DavidRicherby There is an easy conversion between the two and in trying to explain the logic behind the question I am trying to provide as many potential avenues for the OP to see what is going on. Also the original question did not specify it the phone number was in isolation or part of a larger text. The DFA as described will find the first instance since I said it would quit when reaching the accepting state. $\endgroup$ – Ukko Sep 1 '17 at 21:00
  • $\begingroup$ @Ukko The data set can be summed up to a list of phone numbers that all have the same area code. Which means the last 7 digits are the only ones that matter. In this case using a regex would match every item in the data set. $\endgroup$ – SudoKid Sep 1 '17 at 21:07
  • $\begingroup$ @EmettSpeer That edit you made really changed things. Originally you said that the set was all the phone numbers with the same area code. Not an arbitrary specific phone number. That makes most of the comments on this nonsense, but the answer is still the same. $\endgroup$ – Ukko Sep 2 '17 at 2:44
  • $\begingroup$ @Ukko I'm sorry my first try was so poorly worded. I'll be going over all the suggested system to see what one best suites the interviewers suggestion and then mark as correct. If you have any questions please ask I would love to make this question more clear for everyone. $\endgroup$ – SudoKid Sep 2 '17 at 17:47
0
$\begingroup$

This has of course nothing to do with computer science, but if you realistically want to check if a string represents a phone number, then you use something like libphonenumber which knows the rules of 150 or so countries, knows everything mobile phone numbers, service numbers and so on.

If someone says "a phone number always looks like 123-XXX-XXXX", you just laugh.

$\endgroup$
  • $\begingroup$ I agree that if I wanted to check if a string contained a valid phone number using a 3rd party library would be best. Though this was not the question and I'm sorry for my poor wording. I have updated my question to try and clarify it better. $\endgroup$ – SudoKid Sep 1 '17 at 21:22
0
$\begingroup$

Since there is no pattern neither between phone numbers, nor between input numbers. Then there is no optimization.The only solution is to iterate over your array and test. If you can optimize this, then you are welcome to optimize compilers or memory/CPU structure that has been designed for decades.

$\endgroup$

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