« first day (3390 days earlier)      last day (1555 days later) » 

10:01 PM
Maybe. "I feel like there's probably a more interesting mathematical solution to it" sounded like there was no much trust in native PHP function one line solution.
 
The grr base 10 made it sound more likely that he was going to try and work something out by using integer division and modulus.
 
Hmmm
They all seem to be divisible by 11 into a whole number, at least the few random numbers I've thrown into my calculator
 
A palindromic number (also known as a numeral palindrome or a numeric palindrome) is a number that remains the same when its digits are reversed. Like 16461, for example, it is "symmetrical". The term palindromic is derived from palindrome, which refers to a word (such as rotor or racecar) whose spelling is unchanged when its letters are reversed. The first 30 palindromic numbers (in decimal) are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, … (sequence A002113 in the OEIS).Palindromic numbers receive most attention in...
 
Oh, I was doing numbers like 123321
 
You're right though, all divisible by 11 for even numbers of numbers
 
10:15 PM
I need to finish reading The Magic of Math
So many curiosities
 
@MarkR In a technical interview it is the interviewers job to tell you the requirements, not yours. Your job is to figure out how to fulfill them. Because that's what they're hiring you for. The interviewer needs to asses (to some degree of certainty) that this person can fulfill requirements and thus can work there. So when I tell you the requirements are to fit the data into memory, you can't tell me well it depends on the disk space.
 
Sure I can
 
No, you can't, because then what you're saying to me is that you are going to be a nightmare to work with.
You don't want to do that.
Trust me.
 
Work with you? You're probably right I wouldn't want to.
 
Work with the person interviewing you.
You have to work with somebody. Do you really want to present yourself as someone that's more interested in arguing about a problem than solving a problem?
 
10:25 PM
32GB ... 32 billion bytes.... 1 trillion URLs. Do the math.
 
@MarkR I have. I'm not presenting you with an impossible situation. That would be a pointless interview.
As an interviewer, I actually want you to succeed.
 
Is that about drive or RAM? I understood RAM but maybe I'm mislead myself.
 
It does me no good to bring people in, waste their time and mine, just to ensure I've set them up to fail.
 
How exactly are you meant to efficently store a trillion unique pieces of information in memory that can only fit 32 billion?
 
That's a waste of the company's money.
@MarkR This is basically a data structure problem. The solution is to use a bloom filter.
 
10:29 PM
@Sherif You said check if a given URL is in a list, not if it's probably in a list.
 
@MarkR We don't care if it's in the list. We only care that it's definitely not in the list.
Think about it. What does the crawler need to actually know?
 
Goalposts are now moving.
 
Not at all.
Think harder.
Think about the problem as I presented it to you.
What does the crawler need to know?
Keep in mind asking me questions is perfectly acceptable even encouraged.
I'm trying to understand how you deconstruct complex problems. I'm not trying to prove you're stupid or that you know everything.
Quite the contrary.
 
> You're writing a web crawler that needs to check if a given URL is in a list of Known Spam URLs. This list is currently 1 trillion URLs long and must fit in memory on a server that only has 32 GB of RAM.

You stated that it must be in the list.
 
@MarkR Did I?
Think about the question I just asked you. What does the crawler actually need to know?
 
10:33 PM
Yes, you did. I was quoting your message.
 
Try answering my question instead of just arguing with me.
It proves you're interested in the problem and not me.
If you're not interested in the problem I can't help you.
 
My first question would be is list indexed.
 
@Tpojka Indexing is irrelevant here.
Take the hint from your interviewer. When they tell you something isn't important or that you shouldn't worry about it, don't. When they try to draw your attention towards something you're missing, pay close attention. They're giving you a hint.
They're trying to help you solve the problem. Which is what you'd expect from someone you work with on a regular basis.
Your hint is: What information does the crawler actually need to know in order to make the decision "Should I crawl this URL or is it SPAM and I should avoid it?"
Keep in mind we're OK with the crawler NOT crawling some URLs that aren't SPAM.
But we're NOT OK with the crawler crawling URLs that ARE spam.
 
1. check if in list; 2. if it is skip this one; 3. start process for crawling next one
 
@Tpojka But the problem is a bloom filter is a probabilistic data structure. So it can give you false positive, but never false negatives.
Remember the requirements. We don't care if 1 in every 100000 times the crawler doesn't crawl a URL that isn't spam. We do care, however, if the crawler crawls even 1 URL that is spam.
 
10:42 PM
I've quoted the question as you put it, you explicitly said "if a given URL is in a list" and, from my admittedly tiny understanding of bloom filters, they can give false positives, meaning to know if X is in Y, you need all of Y.
 
@MarkR You're correct. But now invert that logic for a second. What do you get?
 
Going to check that subject for sure.
Basically crawling process is far in shadow of checking that link is not in list.
 
Your original statement made no allowance for getting the wrong answer for false positives which were not in the list.
 
@MarkR What happens when instead of asking "is this URL in the list" I ask instead "is this URL definitely NOT in the list"
@MarkR That's not true at all. Just because I stated the problem one way doesn't mean you still can't solve it by looking at in another way.
Without contradicting the requirements.
 
You stated 2 different problems.
 
10:44 PM
Because you see in the real world we often have to view a problem in a different way in order to arrive at a better solution.
@SorinNunca No, I assure you they are the same problem.
However, one view allows you to arrive at a solution. Whereas the other view makes the solution non-obvious.
Notice the problem hasn't changed.
What's confusing you is how you interpreted the requirements.
That's OK.
This is the part where I get to see how you think :)
 
"You're writing a web crawler that needs to check if a given URL is in a list of Known Spam URLs." There's nothing confusing about that statement.
 
@SorinNunca OK, so then how do you solve the problem?
If you aren't confused you wouldn't have trouble finding the solution. Either you are or you aren't. Which is it?
 
With only 32gb of storage, you don't.
 
@MarkR I assure you that you can do it in 32GB
 
Yeah, I'm not arguing the solution. I'm arguing the problems you presented are different. and they are.
 
10:47 PM
Again, stop assuming I'm setting you up for failure. I'm not.
@SorinNunca OK, so let's assume you're right for a second. Explain to me how the problem has changed?
 
If you stated the problem as: "We have a list of known spam urls, and we want to make sure whatever we index is not a spam url", your proposed solution would make sense.
 
@SorinNunca How is "check if a given URL is in a list of known spam urls" different than that?
If we have a list of known spam URLs and we're checking that list, aren't we just trying to make sure we don't crawl spam?
 
Because "is in a list of spam urls" is not the same as "NOT (probably is in a list of spam URLs)"
 
Feel free to demonstrate how the two things contradict each other.
 
In the first problem statement input: url output: is spam ?
second statement, input: url, output: is not spam.

A bloom filter will not produce the first output.
 
10:51 PM
@MarkR Let me phrase it to you another way so that perhaps you can see the error in your logic. If I say if ($a > $b) would the code if ($b < $a) not give us the same exact result?
@SorinNunca The problem statement never changed. On account of the fact that I never restated the problem. I merely proposed a solution to you. Which changed everything about how you understood the problem.
 
We can move goal posts all day long.
 
No one has moved any goal posts.
 
A bloom filter as I understand it only proves it is NOT in the list, it does not prove that it is IN the list, which was the original question
 
@MarkR Was it though?
 
yeah, @Sherif just can't admit he stated the initial problem wrong.
you could leave it open ended, and open for this kind of discussion
 
10:54 PM
Yes, it was, to quote you once again:

> You're writing a web crawler that needs to check if a given URL is in a list of Known Spam URLs.
 
@MarkR So if a given URL is definitely NOT in the list, what does that mean?
Think for a second.
 
It means its not in the list, that doesn't mean everything else is definitely in the l ist
 
Just give if even the most feeble of attempt to answer my question.
What does it mean if the URL is DEFINITELY NOT in the list?
 
If you state the problem as: We have a list of spam URLs, and we want to make sure whatever we index isn't spam, you could definitely have this discussion you're proposing.
 
@MarkR That's not answer to my question though. What does it mean if a given URL is not in the list of spam URLs?
What can we say for sure in that case?
 
10:56 PM
You must be terrible to play football with. "Goaaaaal" ... Nope, wait, there's that Sherif guy moving the goalpoasts to Mexico!
 
Once again, I urge you to try and focus on the problem rather than focusing on me.
Doing otherwise only proves one thing. You aren't interested in the problem. Which makes this entire discussion pointless.
 
You're making it hard tbh
 
I'm actually making it very easy. I've not only provided the working solution, I'm trying to help them understand it.
I don't know how to be any more accommodating than that.
All you have to do is work with me to arrive at collaboration.
If you don't want to that's fine, but then that tells you this is the end of the interview. There's no point in continuing any further.
 
You're making it hard not to argue with you*
Also I don't want to as I don't see how on earth this interview mock came to be
 
I have no interesting arguing with anyone.
I'm here to be objectively helpful.
I have much better things to do with my time than argue with strangers over the Internet.
 
11:00 PM
Admitting you were wrong is very difficult for everyone, for some even more.
 
Having said that, after 6hours after the initial problem has been stated you're still effectively arguing with strangers on the internet telling you the initial setup was bogus
 
@SorinNunca I'm not infallible. Though if you are going to accuse me of wrong doing I'm more than interested in knowing where my error was so that I can correct it. Notice I've given everyone with a claim every opportunity to prove it.
@Girgias Once again, I have zero interest in being argumentative. My only motivation here is to be helpful. I took everyone's feedback as a genuine curiosity.
 
I can see the point in: here's what management is telling you to do (meaning non tech savy ppl) find a way to implement it to the best of what you've been told (clearly knowing the goal probably needs to be reframed).
Comparing that to a supposedly Tech interviewer which knows the limits framing a problem which is effectively not solvable in it's current requirement
Now if that's what you are looking for
State the initial problem differently IMHO
But what do I know
 
@Girgias You're making the assumption that these requirements come from non-technical people. That's not true. If it did how is it not only the correct solution, but the most efficient? Nothing I'm asking here comes from a non-technical person.
 
Where the hell did I make that assumption?
 
11:05 PM
Never start with the assumption that in a technical interview, the interviewer is setting you up for failure.
 
I literally made the opposite one
 
@Girgias OK, my apologies.
 
I'm still trying to research Bloom filters to see if I'm making an error, and granted i'm basing this on wikipedia. According to wikipedia, the query returns:

A query returns either "possibly in set" or "definitely not in set."

So the simple question is, will it *always* return "definitely not in set" if it's not in the set?
 
@MarkR Yes, it will.
It can give you false positives, but never a false negative.
 
So why would there be a "possibly in set" ?
 
11:09 PM
Because it is probabilistic by design.
It attempts to sacrifice accuracy for low-memory-footprint.
The way it works is you hash the input with K number of hashing algorithms. Then you map the hashes to K number of bits in the bloom filter.
The probability that you will have a collision is actually huge.
However...
The probability that you will have a false negative is ZERO.
Because to miss all K hashes is probabilistically nill.
The bits only need turned once. Once they're on they stay on forever.
 
That's where you've lost me. If it's probability based, how can it meet the requirement of "is in the list"? Let's say you pass it a thousand URLs, and it immediately says 900 of them are definitely not in the list, fine, they get let through.

Now you've got 100 left, the "possibly in set" ones, and to know if it's in the list (the original requirement), what alternative is there to now searching the list itself?
 
@MarkR :)) Let's try my question one last time: "What does it tell you if a URL is definitely not in the list?"
What can we say for sure, if that answer is true.
 
Just making a side note as I'm trying to rewrite the f(put|get)csv() functions to accept multi bytes enclosures and delimiters. But what on earth does the enclosure do/is meant to be?
For once the doc has no examples which is kinda sad :(
 
@Sherif Free to crawl given URL?
 
@Girgias It's supposed to prevent spaces from breaking the delimiter. However, it doesn't actually comply with proper CSV the way it's implemented now.
@Tpojka DING DING DING
 
11:16 PM
Can you throw me a spec?
 
@Tpojka It's DEFINITELY not spam, right?
 
Cause the Wikipedia article ain't helpful
 
@Girgias Hmm.. I don't have the RFC off hand, but let me see if I can dig it up.
 
@Sherif much appreciated
 
@Sherif Listening to you all what have you said, yes. And tomorrow bloom theory for one here. :)
Good night.
 
11:17 PM
Here's the confusion, if something is definitely not in the list, I don't see how the alternative return could be "possibly in the list"
 
Yeah. And the requirement you stated was: [...] that needs to check if a given URL is in a list of Known Spam URLs
 
I know Joey had brought this up before. He was working on a fix many many moons ago.
 
state that as that needs to check if a given URL can be crawled / is not in a list of Known Spam URLs
 
Oh there is something on the wikipedia article
Just deep in the article
 
@MarkR Let's say you hash an input using 3 different hashing algorithms. Now, you hash another input using the same 3 hashing algorithms. What happens if 2 out of 3 of them come out the same hash? You get a collision, right?
 
11:20 PM
2 collisions, but yes.
 
@Girgias That looks right o.0 but I'm double checking
@MarkR Right. Now imagine that a third input now produces the 1 hash that didn't collide with the other two.
 
Okay okay
 
@MarkR Now all 3 are technically there. That means if you ask it does this 3rd input (which I have yet to put into the bloom filter) exist?
It's going to tell you... probably
But it doesn't exist
 
But how do you translate that probably, into definitely?
 
Because more than one input has turned on 2 out of 3 of those bits. And the 3rd input triggers the 3rd bit. Making it look like it exists.
@MarkR You don't.
The definitely is the exact opposite question.
 
11:23 PM
Okay, another question, a filter, if it's not 100% certain that it's not in the list, it will return "maybe in list" correct?
 
@MarkR There's no such thing.
@Girgias Yea, this is it
 
Much appreciated :)
 
np
 
Will try to get some work on it
 
I don't follow what you mean by isn't such a thing
 
11:24 PM
@MarkR The bloom filter only ever gives you 1 of 2 answers. Either it's probably in the list or it's definitely NOT in the list
There is no maybe not in the list
Because for something to NOT be in the list means that ALL of the hashes were a miss.
YOu can't possibly get that unless no input ever stored in the filter ever turned on those bits
 
"maybe in list"
 
That's a for sure
 
can we agree that probably in the list is the same as maybe in list?
 
Okay, so I can get rid of all of those which are guaranteed never to be in the list. That leaves me with a certain percentage after that may be in the list, or may not be, is that also correct?
 
No one disagreed
@MarkR No
 
11:26 PM
If no, why is it only a probability and not a definite?
 
Because if it's not in the list it's 100% guaranteed. If it is in the list it's only within a given probability.
@MarkR The simplest answer? Collisions.
 
So how do you weed out the collisions to verify that it definitely is, which was the original Q ?
 
@MarkR We don't. We don't need to :)
We only need to know that something is not in the list to know that it is not spam.
Otherwise, it might be spam.
Make sense now?
Remember, we don't care that it might be spam. To us spam and maybe spam are classified as the same thing. The only thing that actually matters here is that it's definitely not spam.
 
It does, but unless im missing something, and I'm appreciative that I may be, it just doesn't seem to correlate with the original parameters.
 
@MarkR How so?
Give me one parameter it doesn't comply with.
Note: there is only one.
The crawler CANNOT crawl spam.
This is the one and only requirement we care about.
It's OK if it doesn't crawl some things that aren't spam from time to time.
That's an acceptable trade off here.
 
11:32 PM
"if a given URL is in a list" was the original requirement. Your filter seems to prove it's not in the list, not that it actually is.
 
@MarkR No it wasn't. Read that in context.
"if a given URL is in the list ....." what do we do?
What do we care about?
Why are we asking this question in the first place?
 
anyone else see 2018 and think "last year"?
 
You're so intent on focusing on the literal sentence fragment "find something in a list" that you're allowing yourself to lose sight of the actual problem we're solving here.
Instead, ask yourself, why are even checking this list?
What was the point
 
The question was "How would you fit this list in memory?" was it not? No additional context was given.

>
Here's a real world problem: You're writing a web crawler that needs to check if a given URL is in a list of Known Spam URLs. This list is currently 1 trillion URLs long and must fit in memory on a server that only has 32 GB of RAM. How will you fit this list in memory?
 
@MarkR Yes
How is with a bloom filter. We did that already.
Now, was the point to fit into memory so we can sit and stare at it?
Surely not
We want to use it for something. What we use it for is to know that the URL the crawler was given is definitely not spam. Because we don't want the crawler to crawl spam.
Are we good so far?
 
11:36 PM
So you get something that says "maybe in the list" , what then?
 
@MarkR Then it's spam.
 
Then I don't understand. Maybe isn't definitely.
 
6 mins ago, by Sherif
Remember, we don't care that it might be spam. To us spam and maybe spam are classified as the same thing. The only thing that actually matters here is that it's definitely not spam.
@MarkR You keep rereading the part where I say "a web crawler that needs to check if a given URL is in a list of Known Spam URLs" but you keep neglecting to comprehend what that means.
What does it mean if the URL is NOT in the list of known spam URls?
If I have list of people I banned from the club and you're NOT on that list, what does that mean?
Do I let you in? Or are you banned?
Are there any doubts about that?
 
That it may be spam, in the context of your original question, that's different from is definitely spam.
 
@MarkR NO!
How can it be spam if it's not on the list?
It can't.
How can you be banned if you are ****NOT**** on my list?
You can't.
There is no doubt about that.
It's not subject to debate.
Now, if you are on my list you might be banned. Or maybe I wrote your name down wrong. Or maybe you have the same name as someone else.
Who cares. You're banned. You're not allowed in.
Good bye.
See ya
Are you getting it now?
We are OK with the idea that some URLs which are not spam being considered spam
 
11:43 PM
@Sherif If you're going to have shades of gray in one direction then there should be in the other direction.
 
@Trowski I should not. These are tradeoffs we're making to satisfy the requirements. They are not subject to debate.
 
Maybe not, but they should have been included in your original question, not 5 hours later.
 
I'm not asking you to produce the requirements to my problem.. I'm handing them to you and asking you to fulfill them. Don't get confused what your job is.
@MarkR Everything was included in my question :)
I misled you about nothing.
Once you get that you get why this question is so good at testing your ability to deconstruct a complex problem.
 
@Sherif Guess I need context, where's the original question?
 
@Sherif it was here
 
11:46 PM
@MarkR Was what?
7 hours ago, by Sherif
Here's a real world problem: You're writing a web crawler that needs to check if a given URL is in a list of Known Spam URLs. This list is currently 1 trillion URLs long and must fit in memory on a server that only has 32 GB of RAM. How will you fit this list in memory?
 
I was just replying to the original comment so it would link for Trowski
 
ahh ok
@MarkR You see, what this exercise showed me is that you are more interested in arguing with the interviewer about how they phrased the problem to you than you were interested in the problem itself.
Now, this is not meant to discourage you in anyway. It's actually an excellent learning opportunity.
If you can show me that you are excited about solving a problem ... I know I want to work with you.
Even if you can't solve that problem.
You might show me that you can deconstruct it enough that you have all the pieces, but none of the muster to put them together.
That's OK.
I can work with that.
 
@Trowski What we've been arguing about is the nature of the Q. Which is effectively the difference between a blacklist and a whitelist.
 
But if all I got from you was "argumentative and makes things personal" ....
Guess what... not so inclined to want to work with you
@MarkR Is it though?
You keep going back to that, but you aren't thinking hard enough here.
Am I actually telling you to make a black list or a white list?
Or am I saying .... here's a list.
How can I get X out of that list.
Huge difference.
The difference between "I can do this" and "this is stupid" is that one stands a chance of being productive in a highly complex and fault-tolerant environment.
 
@Sherif In that context I agree. The only thing you need to know is that the URL is not on the list.
 
11:52 PM
@Trowski :)
@MarkR BTW, this was the interview question for a lead engineering position at Google. Don't feel bad. It's not an easy one.
I would never actually ask that of a junior/senior engineer.
 
Well I need to go kill some level 18 witch hunters, I will simply say, if you've managed to cause this much of an argument between the half dozen or so people that have chimed in, the question needs work :D
 
And yet it was incredibly effective at finding the best candidate for the position.
It comes from a real world problem I worked on at Spotify.
So, I'll take the advice of 8 senior Google engineers on the hiring committee over yours :) No offense.
 
@bwoebi High sales tax makes it more difficult for people to afford things and reduces consumer spending. I don't know about Europe, but in the US, necessities like food and clothing often do not have sales tax.
 

« first day (3390 days earlier)      last day (1555 days later) »