« first day (3391 days earlier)      last day (1539 days later) » 
00:00 - 11:0011:00 - 00:00

12:00 AM
Question, did you quote the original question as it was presented to them?
 
@MarkR Yes, I'm the one that presented the question. It was approved by my seniors.
And the person that solved did not spent a single second arguing with me about how they found it confusing. They managed to understand it and solve it rather quickly.
They asked me one follow up question, I think.
 
So you were interviewing people for the lead engineering position at Google?
 
Yes.
 
Impressive.
 
Interviewing is hard stuff. Conducting interviews even harder. But both are learnable skills, I assure you. I learned them.
 
12:04 AM
@Sherif My first thought was a table of hashes. It would have false positives, but if a hash wasn't on the list, then it must not be in the original list.
 
@Trowski Sure, but show me a hash that can store several hundred terabytes of data in 10s of gigabytes.
Hashing is a good first stab it.
If you can get there you're half way there.
The Google crawler, believe it or not, actually uses this methodology in practice to weed out spam.
They just have a far far more complex implementation of it.
 
I'd have just gone for a single hash then B-tree'd it for several layers in memory and then used that for a disk lookup
 
B-trees are only good at fast search. What we care about here is efficient use of memory.
So I'd urge you to focus on the hashing-bit and ignore the b-tree bit.
Take your interviewers advice wisely. They are there to help you focus on what's important and they want you to succeed.
Think of it like this: while you are being interviewed, this is your chance to interview them. You want to know "can I work with this person" just as much as they do.
If they're kind, courteous, helpful, and knowledgeable ... A+!
 
And here I thought you wanted to just throw out something extremely complicated because DaveRandom said he wasn't interested in a non-real-world problem :D
 
If they're mean, dismissive, and arrogant well... I'll keep looking thank you very much
@MarkR That's not the kind of person I am :)
I rather enjoy being helpful. Nobody pays me to be online and help people. The only incentive I get for it is the joy knowing I helped someone else excel.
You being smarter, actually makes my job easier believe it or not. Because there is only so much of my time I can devote to any given problem.
Note: I'm not saying you aren't already smart.
If I thought you weren't I wouldn't have bothered to have this conversation with you.
 
12:13 AM
I think people are appreciative of the help, and I'd imagine most people on here are up for debate on complex matters, being told they're wrong because of a disparity between the Q and the expectation, that could certainly put people off.
 
I agree. Telling people they are wrong is mean spirited.
That's why I don't bother to argue about wrong and right. I only aspire to constructive conversation.
If I'm wrong, please by all means help me do better.
People that have err'ed, in my experience, eventually realize their errors and correct them if given the chance. So what's the point in focusing on who's right? Instead, focus on the right solution to the problem. One you can agree makes sense.
There's nothing that builds rapport better between team members than working together to solve a hard problem :)
 
If you were managing a team and you laid out a set of requirements, and your team immediately began making comments that were accurate based on their understanding, but that understanding didn't correlate to your expectations, you would presumably withdraw the original Q (as it stood to confusion) and re-issue it anew in a different manner
 
@MarkR Well, there's a huge difference between that and a technical interview.
In a technical interview you aim to asses 3 basic things: 1) Can this person write good code, 2) How does this person deconstruct complex problems, and 3) Are they effective communicators (i.e. do they ask good follow up questions or do they just assume they know everything?)
This question hits all 3 quite nicely at a high level.
 
Part 3 is somewhat dependent on the interviewer not walking out the room for 5 hours ;D
 
@Sherif You wouldn't store the entire hash, rather b-trees of hashes that are in the table.
 
12:21 AM
@MarkR I do have to work for a living
 
Maybe I'm totally off, but that was my first thought.
 
@Trowski Well, let's do the math. What's the size of this hash?
 
Unacceptable. Once a question is posed to R11 it must be solved or debated till the heat death of the universe.
See: Generics
 
@MarkR If you want to pay my bills I'm happy to be here 24/7
 
@Sherif Say SHA256, so collisions are fewer.
That might be a bit big…
 
12:24 AM
@Trowski Wonderful. So 256 bits per hash then. Whats 1 trillion times 256?
Have we exceeded 32GB yet?
;)
 
But that's not how it would be stored…
 
Mind you we haven't even factored in the pointers for the btree yet.
@Trowski Oh? How will it be stored?
 
As I originally commented, B-tree in memory and disk for the rest.
 
@MarkR We do not have disk. We must fit the entire thing into memory.
 
I think we've determined you can do your filters < 32GB using the... let's say expanded version of your Q. Just talking about generic storage and searching of hashes now.
 
12:27 AM
Well, there's a reason why it needs to be in memory.
Disks are slow.
And this solution has to scale to millions of requests per second.
Memory runs at an average bus speed about ~200 usec per block
Disks... good luck!
But hey you were involved in the spec design and architecture all-hands on this, right? You know what you're doing ;)
 
I've just got a reasonable understanding how DBs split their in-memory indexes from disk store.
 
There's a reason why requirements are not always up for debate. Someone smarter than you has already covered the really hard stuff. Stand on the shoulders of geniuses and call yourself tall my friend. That's a good thing!
@MarkR And you're suggesting that I don't?
There's a reason why Google invented their own database.
There's also a reason why the crawler does not use one.
None of those reasons are due to a lack of understanding existing DBMS solutions.
You can't run a business by arguing about stuff all day and never actually solving anything. That's why we have specializations.
 
4 tiers of B tree at 256 slots, 8 byte pointer each consumes your 32gb. With a trillion results equally spaced that brings it down to... about 230 slots in each end bucket... I think?
 
@Sherif Well, I was thinking a tree, but giving that some thought it would still be too big for memory. Beyond that, I don't have anything off the top of my head, I'd have to give it a lot of thought as to how you could build some structure that you could compare to.
 
@MarkR 8 bytes * 1 trillion == 32GB?
I'd love to know how that math exists
 
12:33 AM
Smaller hash function, a partial tree… shrug
 
@Trowski I assure you trees are not the answer. Ask yourself what are trees actually good at?
Logarithmic search.
 
256 * 256 * 256 * 256 for 4 layers of btree operating on 1 byte of a binary encoded hash, each one represented by an 8 byte pointer to give 32gb
 
OK... but do we care about search here?
Is that even a problem we're trying to solve?
@MarkR OK, how do we fit 1 trillion hashes into that space?
Your math is spot on so far. 256^4 * 8 = 32GB
And I'm completely ignoring the fact that you have no pointers to the child nodes of this tree btw ;)
 
@Sherif Reading up I saw you mentioned a bloom filter. That would make a lot of sense. If you got a positive, you could then go to disk to confirm (if it was important to confirm).
 
Fair point but it's only another 16MB, didn't consider the OS either but can always do modulus <lower number> on the b yte value to reduce the number of branches
 
12:37 AM
@Trowski That sounds reasonable. But we don't actually care to confirm here. We can safely assume a false positive is equal to a positive in this case.
@MarkR It's fine. I'm trying to get to next steps. Even if we run into a slight problem. How do we fit the hashes into that space though?
That's a harder problem to solve.
And again, is the Trie actually helping us with any of this? Is it even necessary?
Could you remove the trie entirely and still use that space more efficiently?
Space is space, right?
 
@Sherif If I were actually writing a web crawler, I wouldn't want it unfairly excluding a URL by chance.
Granted that's outside of the scope of the original question – but just sayin'
 
@Trowski It's an acceptable trade off in this case, because we have other means of indexing those URLs out of band.
 
I wouldn't. I'd store the entire list separately backed by some other storage and then access an offset of that based on the final tier of pointers. Realistically I'd not use 256^4 and would leave half my memory free for caching.
 
@Trowski Our primary concern is with not crawling spam
 
Sure, makes sense.
 
12:40 AM
If memory serves, Google uses giant indexing servers that don't hold any data whatsoever, and then direct queries to the servers that do
 
@MarkR But we don't have any other storage.
The only storage we have is 32GB of RAM on each node.
 
Just talking general data storage and indexing mechanism at this point Sherif.
 
Here's another friendly piece of advice. When someone is telling you what you have to work with... at least try to work with it ;)
 
@MarkR You're focusing too much on what you'd actually do, rather than just solving the original question, whether it makes sense or not.
 
No, I get it. He's trying to solve the problem. It's a struggle to do so with so many constraints. But welcome to the real world :)
You don't just get to upgrade the RAM or add a new disk just to make your job easier
You have to work with what you got in reality
and sometimes it's crude, but we make it work
This is a test of your skills. Not your ability to spend the company's money.
 
12:43 AM
@Trowski We've already determined that pretty much everyone in the room who chimed in on the original question at the time interpreted it differently to how Sherif intended. But after 36 years of non-stop arguing we changed the problem we were trying to solve.
 
Not sure who "we" are. But I certainly never changed the problem.
The problem has remained the same all along.
 
No, the people who were arguing against you changed the problem they were trying to solve.
To be the one you had originally intended, but that had not been properly received
 
Well, I don't just get to go to my bosses and say "Hey, I'd like to change the problem because this one's too hard"
Kinda hard to convince them of that one
Hard problems are hard for a reason. But if you stick with them long enough you learn something.
Think about it like this: you don't get to change the question on an exam just because you don't like it. Why should your job be any different?
 
There's an episode of Star Trek, the Sheliak are going to obliterate a planet and the Enterprise is there to evacuate the humans living there but they can't beam people through the atmosphere. LaForge works night and day to try and find a way to beam them off. He says he can do it... It'll take 20 years and a research team of 11, meanwhile Picard has found a way to eliminate the problem entirely using another method.
 
That's a great moral story I'm sure, but in this story ask yourself... which one are you?
Have you actually found another method?
Because if you did, hey I applaud you my friend. I'm all about show me how we can do it bettter.
So far I have yet to see "a way", let alone better.
 
12:50 AM
You're talking to a guy who failed his A level ICT exams because I spent 10 minutes on the exam, and then the remaining 50 scribbling over why there were factual errors on the said exam :P
 
LOL
 
That was ever such a long time ago, that exam really was shit though.
 
@MarkR I'm not going to read through the last 7 hours of chat, but the question is clear. Maybe missing information on what accuracy is acceptable, but given the constraints it's obvious that sacrifices will need to be made.
 
You have the benefit of seeing the discussion about sacrifices and what is acceptable :)
 
True, but I think that would have been one of my first questions.
 
12:53 AM
Asking questions is pivotal in solving problems.
Because in the real world the answers are not going to grow legs and find their way to you. You must hunt the down with hard work and dedication.
An interview is no different
I want to test you the same way the real world is going to test you.
i give you the test first and the lesson later
 
Fortunately I doubt I'm ever going to have to do a software engineering interview again \o/
 
You won the lottery?
You work for the only company on earth that's failure-proof?
 
Nah, but after 15 years of working in software development, after another 5 or so I suspect I'll be done and want to move out the field into something else.
 
If so I'm jealous.
@MarkR Dark matter?
 
Was thinking dark energy, it has more expansion potential (badum tish)
 
1:04 AM
oh I see what you did there
You know had I bought Apple stock back in 99 at about a buck a share, I'd be able to retire today.
 
and if I'd bought AMD stock 5 years ago so would I. Cest la vie.
 
AMD only went up like 50 times in 5 years. Apple stock bought back in 99 would be worth like 3000 times today what was it worth then.
A mere $1,000 investment would net you $3M easy
only if we knew
 
But wouldn't you want to invest in something slightly less exploitative than apple? ... Say a company that specialises in child slavery?
 
@MarkR Does there money spend any better?
Besides, I'm pretty sure all corporations are exploiting people these days. Otherwise they wouldn't be so filthy rich.
 
So, question. You were RAM limited, were you CPU limited? For a trillion rows, it seems like you'd need a fairly substantial number of discrete hashes. GPU accelerated?
 
1:14 AM
@MarkR The computational cost is not a bottleneck here. It's O(k), which is fine. Memory, however, is expensive and scarce.
CPU does not increase with size of data, BTW.
 
For such large datasets the number of distinct hashes produced would need to be increased would it not? Unless I'm not following this right
 
@MarkR They would. There's a formula to how many hashing algorithms you need to use to get to a certain minimum level of probabilistic failure.
But, that's nothing compared to the memory problem.
It's like a paper cut vs a bullet wound
 
Without GPU offload I would have naturally thought memory would be by far the cheapest of the lot
 
You don't need a GPU here.
This was all done on quad core machines IIRC.
all commodity hardware
There was a bit of a sneaky performance optimization, however, the filters themselves were filtered.
So there was some network latency involved, but it was still negligible.
Those servers are basically wired together by mm precision. So at the speed of light that's no big deal.
 
What about the leftovers, did they go through another process hitting the full list, or just get discarded as acceptable losses?
 
1:21 AM
You mean the false positives?
 
Yeah
 
Well... that was actually handled in really convoluted way.
See the crawler doesn't actually know, half the time, if the stuff it crawled succeeded or not.
So there's an out of band redundancy involved.
The trick was to catch false positives by way of consensus among the crawlers.
I can't give you the exact implementation, but that's the gist of it.
 
Did the crawlers not share the same dataset?
 
Nope
They're distributed
I mean... technically they have access to the same data. They just take a small chunk of it in clusters.
 
I'm not sure I understand where the spam list came from in that case. I mean I could understand if upon scanning a page and determining it to be spam, it added it to its own spam records for future, but how do multiple serves achieve a quorum if they don't have the same data?
 
1:25 AM
They don't all have the same data at the same time.
At this scale data is chopped up and distributed into small chunks, processed, stored, reprocessed, and restored.
It's the only feasible way to do it.
For example, in a search engine you store 2 indexes. Something called a forward-index and something called a reverse-index.
 
and the memory available to the total number of servers wasn't enough to distribute the entire list?
 
They're the same thing, but backwards.
@MarkR Can't distribute that list.
Unfortunately that's the problem.
You gotta keep a local copy on each node and that's where the bloom filter comes in.
 
Were you limited to horizontal scale-out?
 
Pretty much
 
So couldn't just say... have 5 machines with 32GB each?
 
1:28 AM
It can actually be done vertically but...
This problem is so complicated I'm not even allowed to explain why they don't do it that way
 
That's fair, probably best not to break NDAs on a public chat site
 
Yea, this is all public domain. The stuff I can't share is like 40 times more complicated than this.
In reality it's not even really done like that anymore.
@MarkR This is Sergey and Larry's original white paper on their first search engine design: infolab.stanford.edu/~backrub/google.html
Gives you a fair idea of just how complicated a search engine can be
And that was like 20 years ago
 
I assumed that even google had no effing idea how most their search worked anymore and it was all done by AI
 
It is now
This stuff changes so quick you can't keep up
It's also a highly competitive business. As much Google talks about transparency they're most secretive company I know.
 
Less chance of people finding out every query is being piped to the NSA
 
1:33 AM
I think Google's search precision has gotten worse. When I search for similar but not the same things, I get the same result. To some degree this unification can be good, but for tech stuff it is worse than before, imo.
 
They don't even allow you to walk in the data center without 16 points of ID.
 
I guess that's more to do with what else is running on it than their own stuff nowadays
 
I dunno man. I just remember all the other companies I worked at if you wanted to go visit the DC it was cool. Take your employee badge and you're in.
:S
Now it's like: I need 3 pints of blood, 2 lbs of flesh and your first born
 
Search appliance with some public documents on, who gives a shit.... the server next to it containing the gdocs of a major company, and bye-bye cloud hosting business.
 
Yea, they have a lot to protect. That's for sure.
It is a trillion dollar company after all.
Even Larry doesn't want to run this place no more.
 
1:39 AM
Ive been quite impressed by their rollout of new security features. Their enhanced protection on email is the stuff dreams are made of
 
"Too big to fail"\
@MarkR I'm particularly impressed with their Titan chip
That stuff's fascinating
 
I use a pair of Yubikeys for it instead.
 
instead?
Those aren't interchangeable
 
They are for the FIDO spec
 
The Titan chip protects you from things like firmware tampering i.e."Evil Maid Attack"
 
1:43 AM
Are we talking about the same thing? I'm on about Google's Titan security bundle, which is their 2-part MFA security key
From what you said I assume they also have something akin to TPM?
 
I should clarify, Titan is a loaded term these days
 
Ah right, yeah effectively a TPM
 
They started with a security chip for their own servers and then made many different variations of it for their consumer products like the Pixel and the Chromebook
 
probably minus the TPM standard
 
Yes, it's a TPM
Not unlike Apple's A1 chip
 
1:47 AM
I think I'm using AMD fTPM at the moment, I really should get a separate one for the board
Then again there's nothing on it other than secureboot
 
All these IoT devices these days... They really need more security hardening.
 
hahaha... funny
 
I mean hey if you can manipulate Google Home with lasers... cnet.com/news/… well I'm worried
 
Honestly, that'll only happen when a large country requires it by law. Probably the EU.
 
I know someone who's home when the Internet goes out... you can't turn on the AC or the lights.
That scares me
 
1:51 AM
I mean, when $50,000 cars can have their doors opened by replay attacks because no-one thought to add a f**king nonce and timestamp to it, what hope does the $50 iot lightbulb have
 
True
 
one of the reasons why I do my absolute best to avoid smart devices... sure they're convenient, but I'm not trading someone hacking into my stuff and keeping me from it
e.g. turning my lights on sporadically, locking me out of my home... I'll take physical means
 
Same, no IOT devices in my home, and my internet connection TV gets put on a separate network.
 
granted, smart devices can be made secure, but a lot of them cut corners to stay cheap
 
What scares me the most is another NSA fuckup
 
1:55 AM
Experian :/
 
Once the cookie is out the cookie jar and every cybercriminal on earth gets its hands on nation-state level cyberweapons because some dipshit uploaded the wrong thing on his home laptop.
aka EternalBlue
 
yeah
 
I struggle to convince my boss that the 13 year old l33t h4x0r down the street is using code that's got the same security level as WMDs.
 
script kiddie just doesn't mean the same anymore? :P
 
Certainly doesn't when they're running Kali loaded up with the latest leaks from the TAO
It genuinely terrifies me. You can't defend against that.
Well, I've spent 3 nights trying to get through Leonard Susskins lecture on penrose diagrams and I keep falling asleep, going to try it a bit earlier tonight. Goodnight all o/
@Sherif The latter half of the conversation was very enjoyable.
 
2:18 AM
@MarkR 👍
 
 
1 hour later…
3:43 AM
o/
 
 
2 hours later…
6:11 AM
HI
does some one knows how to use the this library https://github.com/dnaextrim/php_zklib ???
I want to create an attendance system using Php and fingerprint device
 
6:58 AM
posted on January 28, 2020

 
Hi I am new here
 
7:49 AM
\o
 
8:12 AM
o/
 
@DarwinBuelo welcome
 
 
1 hour later…
9:30 AM
Good morning.
 
cmb
\o
 
0/
 
\8
 
9:52 AM
WHAT ... AN EIGHT ?
change confuses and angers me ...
 
it's just a top bun on a tiny o/ :-)
 
possibly an angel
 
nothing is possibly an angel, your logic is faulty ...
 
fine, definitely an angel.
undeniably
and I am a ghost
a lemon scented ghost
with 50% extra free
I didn't sleep much last night, I may not make much sense today
 
Just so you all know. It is my angel
 
10:04 AM
@Ekin he it just referred to you as "it", I trust you will make him it pay
 
ô/
 
you made it cute, I'm less annoyed
 
:-D
 
@salathe œ/
 
stop it
 
10:08 AM
stœp what?
 
you're earning yourself a very hard kick in the shins
I'll do it ...
nah, I won't
 
I know you would never ruin this pretty face of mine
 
is that # an asshole, and what is that flying off it ?
 
lol
did not even notice the #
 
10:12 AM
@PeeHaa \∞
 
I know this one, it's dead angel
 
no its the invisible man with paint on his arm and sunglasses on
you were close though
 
yeah, I almost had it
 
then there's this one I refer to as "self portrait": 🖕/
 
@salathe sorry to be such a drag, a couple days ago I've submitted more information on my account request (sorin). Please let me know if there's any more info needed from me, I'm also available here :). Again, sorry for being a pain.
 
10:21 AM
FYI: PHP exceptions should not be used inside FFI C callbacks that return any values. #sigh
 
@lisachenko This kind of comment makes me angry
 
@NikiC why, could you please describe? It is reasonable why it should be restricted. And I'm agree that the best option is to terminate execution of code immediately.
 
There is no defined operation such like str_replace in zend operators right? Can I change php_str_to_str_ex() to a PHP_API and use it in file.c? (for the multi-byte enclosure/delimiter in fputscsv() )
 
@NikiC I'm looking at different bindings of FFI for different languages and situation is common: do not unwind this error back to C code.. (
 
Yes
If you understand that, it's okay
Unwinding across FFI boundaries is an extremely hard problem
 
10:29 AM
@NikiC I agree with this, because it's the only solution here. Only small chance to implement something like a coroutine/exception with return value to catch this exception ourselves and return a valid value to C code (or try to clean result)
 
10:43 AM
ah so while you can populate the globals the longjmp isn't possible ?
not sure why it would get as far as bailout, or why it would matter ... I know nothing about ffi ...
 
morning
 
Today's selection of "responxibility" was brought to you be @PeeHaa's drinking habit
 
@JoeWatkins just imagine that C code waits for specific structure to be returned on the stack and we have a PHP exception instead, then FFI won't be able to return required C structure back on top of the stack or returned value will be a garbage.
 
"FFI MAGIC"
got it
 
00:00 - 11:0011:00 - 00:00

« first day (3391 days earlier)      last day (1539 days later) »