51–60 of 82 posts
>> Nobody really wants a huge globally sorted output. We haven’t found a single use case for the problem as stated. Do anyone has a real world use case of global sorting other than top-k?
Earlier quoted context omitted.
I worked at Google, and performed quite a few interviews. At least at that time, the interviewer had no idea where in the company the software engineer would go. The people who got hired would go into a pool, and the managers who needed staff would then horse-trade for them. They needed to hire people who could be plugged in to tons of different positions, including some that genuinely had tough problems where if the…
The encoding actually used is that the first bit of every byte is a flag for if there's a next byte, for a maximum of 10 bytes. Fun facts: those are commonly known as "vbytes." They are the slowest kind of variable width integer encoding. The simplest (naive, and generally considered "wrong") implementations of variable-width-by-continuation-bits uses 10 bytes maximum. A proper implementation uses 9 bytes maximum. Th…
0xxxxxxS : 1 byte, 7 bits of data, -64 to 63
10xxxxxx xxxxxxxS : 2 bytes, 14 bits of data, -8192 to 8191
110xxxxx xxxxxxxx xxxxxxxS : 3 bytes, 21 bits of data, -(2^20) to 2^20 -1
1110xxxx xxxxxxxx xxxxxxxx xxxxxxxS : 4 bytes, 28 bits of data, -2^27 to 2^27-1
... and so on.
int64_t zigzag_decode(uint64_t in) {
/* Signed right-shift is implementation-defined behavior in C */
COMPILE_TIME_ASSERT( (1LL > 63 == -1, compiler_uses_signed_arith_shift );
return (int64_t) ((((int64_t) in > 63 ) ^ (in >> 1));
}
Earlier quoted context omitted.
The encoding actually used is that the first bit of every byte is a flag for if there's a next byte, for a maximum of 10 bytes. Fun facts: those are commonly known as "vbytes." They are the slowest kind of variable width integer encoding. The simplest (naive, and generally considered "wrong") implementations of variable-width-by-continuation-bits uses 10 bytes maximum. A proper implementation uses 9 bytes maximum. Th…
> Using this scheme also kills any "1 byte, standalone, variable width integer" capability (unless you're storing partial values in the first T/L byte, but then that limits you to a much lower max value for one byte). You can get the best of both worlds. The way to do it is: separate continuation bits (1's) from data bits with a 0. This gives identical encoding-length characteristics as what you are calling "vbytes"…
These can also have the "avoid 10 bytes" optimization by just reading the next 8 bytes exactly if the first byte is just all ones (no need for a zero separator; it would be in the way and push out the final bit to its own isolated byte again).
Earlier quoted context omitted.
The encoding actually used is that the first bit of every byte is a flag for if there's a next byte, for a maximum of 10 bytes. Fun facts: those are commonly known as "vbytes." They are the slowest kind of variable width integer encoding. The simplest (naive, and generally considered "wrong") implementations of variable-width-by-continuation-bits uses 10 bytes maximum. A proper implementation uses 9 bytes maximum. Th…
No, it's not a type-length-value encoding, just a length-value encoding. I should have been more explicit in my UTF-8 reference. I'm really talking about a UTF-8 like encoding, except that it doesn't specially mark any of the continuation bytes and generalizes to lengths of 9 bytes, so the encoding (plus using zigzag encoding to put the sign bit in the least significant bit) is: 0xxxxxxS : 1 byte, 7 bits of data, -64…
Or we can just store everything as int64_t natively anyway. It's only 8 bytes after all (and storage is big these days).
Earlier quoted context omitted.
> Using this scheme also kills any "1 byte, standalone, variable width integer" capability (unless you're storing partial values in the first T/L byte, but then that limits you to a much lower max value for one byte). You can get the best of both worlds. The way to do it is: separate continuation bits (1's) from data bits with a 0. This gives identical encoding-length characteristics as what you are calling "vbytes"…
That's clever too, but it seems we're back to masking/shifting things all over the place too (which seemed to be an anti-design goal listed above. These can also have the "avoid 10 bytes" optimization by just reading the next 8 bytes exactly if the first byte is just all ones (no need for a zero separator; it would be in the way and push out the final bit to its own isolated byte again).
Earlier quoted context omitted.
I worked at Google, and performed quite a few interviews. At least at that time, the interviewer had no idea where in the company the software engineer would go. The people who got hired would go into a pool, and the managers who needed staff would then horse-trade for them. They needed to hire people who could be plugged in to tons of different positions, including some that genuinely had tough problems where if the…
"an idea of the dimensions of your skillset" sounds like a really reductive way of thinking. It's as if the skillset is restricted to something easy to quickly explore and visualize, like a convex object in a few dimensions. Maybe those assumptions are necessary for interviewing but they're nothing to be proud of.
But, it's largely guestimates anyway. It's hard to come up with good metrics of employee performance that correlate well to company performance and even harder to come up with interview questions that have good predictive power for those metrics.
Ideally, they'd relax the hiring criteria and all employees would start as 1-year or 2-year contractors. On-job performance is the best indicator of on-job performance.
Earlier quoted context omitted.
No, it's not a type-length-value encoding, just a length-value encoding. I should have been more explicit in my UTF-8 reference. I'm really talking about a UTF-8 like encoding, except that it doesn't specially mark any of the continuation bytes and generalizes to lengths of 9 bytes, so the encoding (plus using zigzag encoding to put the sign bit in the least significant bit) is: 0xxxxxxS : 1 byte, 7 bits of data, -64…
well, the "type" is presumed by a schema or somewhere by the time you hit your decoder, so it's technically there even if physically absent (and "LV encoding" doesn't seem to be a thing with any meaningful search results). Or we can just store everything as int64_t natively anyway. It's only 8 bytes after all (and storage is big these days).
Earlier quoted context omitted.
I think what the GP was illustrating is that Google is extremely conservative. For them to hire people outside of the strict boundaries of, "dimensions of skills as represented in an interview," is kind of a rejection of the Robustness Principle for corporate purposes. I mean, heck, something like this? They interview multiple magnitudes of people necessary for this kind of job. I respect it as a hedge, but it probab…
Even so, it only pays to be conservative via an overly selective filter if that filter actually selects for what you want. If you zealously apply some filter, believing that you're being extra cautious, but the filter doesn't actually select for what you think, or the filter isn't actually as selective as you think, then it's just a form of selectivity theater. I've met plenty of ex-Googlers who were great at recitin…
Earlier quoted context omitted.
No, it's not a type-length-value encoding, just a length-value encoding. I should have been more explicit in my UTF-8 reference. I'm really talking about a UTF-8 like encoding, except that it doesn't specially mark any of the continuation bytes and generalizes to lengths of 9 bytes, so the encoding (plus using zigzag encoding to put the sign bit in the least significant bit) is: 0xxxxxxS : 1 byte, 7 bits of data, -64…
well, the "type" is presumed by a schema or somewhere by the time you hit your decoder, so it's technically there even if physically absent (and "LV encoding" doesn't seem to be a thing with any meaningful search results). Or we can just store everything as int64_t natively anyway. It's only 8 bytes after all (and storage is big these days).
Note that this sort [in 2012] was 500 times larger than the GraySort large-scale requirement and twice as fast in throughput as the **current 2015** official GraySort winner. (emphasis mine)