131–140 of 181 posts
Edit: More generally, I feel like these sorts of tricks are getting less relevant over time. With the prevalence of Unicode text how many clever interview question optimizations that assume characters are just another way of saying u8 are no longer relevant?
On a related note, almost any task around shuffling or shifting bits can be improved with xor. For example the straightforward way to remove bit i is mask = -1 > 1) & mask); but with xor we can do it in one less instruction: mask = -1 > 1)) & mask) ^ x;
If ascii characters aren't guaranteed, would this solution still be able to scale? I wonder how the overhead from scanning the input to find the domain to use for the bitset compares to overhead of allocating a bunch of sets. Edit: More generally, I feel like these sorts of tricks are getting less relevant over time. With the prevalence of Unicode text how many clever interview question optimizations that assume char…
Something about seeing fun bit tricks solving higher level problems is exciting. As someone who writes higher level software in general using golang/rust/python to solve "boring business" problems, seeing someone using XORs to accomplish something feels like leaving my house and going camping for the weekend.
This seems a bit overcomplicated to me. Using a bitmap to track letters you've seen is a great idea. But the parity and counting gives me a headache. How about you start with a zero-size window at the start of the string, then iteratively try to grow it by moving the end forward until it's long enough, and if the character added would be a duplicate, moving the start forward until it's no longer a duplicate? Sort of…
> i mask the bitmap in the inner loop condition, but you could just test letterToRemove against letterToAdd and break if they're the same
You still need to check ((lettersSeen & letterToAdd) != 0) once to know whether you need to enter that loop at all. Worst case (a long string of the same letter) you do this twice per letter in the input anyway.
Earlier quoted context omitted.
Yes, but then the last algorithm runs in the same time as the one before it. Using xor here really only gives you a constant factor improvement (which is still nice!). Reminds me of the problem “find the only missing number in a scrambled list of 1..n”. You can get an “O(n)” solution using xor, but once bit size becomes a concern, there are less hacky solutions that are just as fast.
"Bit tricks" are worth a factor `log n`. Let me explain: If you have an array of `n` integers in {0,1}, and you want to count the number of 1s, you need `n` time. But if you have an array of `n` bits, with bit level operations you can do `n/W` time, where `W` is your word size. We often have W=32, 64 or 256 on some architectures, but you may still argue it's just a constant. The thing is that we usually saw you have…
We usually assume the pointer size to be infinite (e.g. RAM machine), to avoid having to deal with access time. But if we don't, then it must be a constant size (and we have to adjust the big O formulas accordingly). In neither of those cases do you get free arbitrary length xor operations. Just like you don't get e.g. free arbitrary length multiplications either.
One nice property of xor, however, is that you can parallelize the heck out of it. So you can get arbitrary constant factor improvements by adding a bunch of CPUs.
Earlier quoted context omitted.
Right, but if the universe of possible characters grow much larger than the window size (as it does in many applications), we want a method that only pays in terms of window size, not universe size.
So you use a sparse bitmap, ie a hash set. The size of the hash set is bounded to the size of the window, so this should be pretty efficient. If you have a huge string, a huge alphabet, and also a huge window, then probabilistic techniques start to make sense. But let's not run while we can successfully walk!
It's possible to store a doubly-linked list using only a single pointer per node. For entry B, &B = &A ^ &C. You can walk the list in either direction as long as you have pointers to two neighbouring nodes in the list. Half as much memory overhead compared to an implementation where each node stores two pointers.
> There's no moral to the story, other than "xor is cool" The moral is knowledge is king and no matter how much iron you throw at a problem a well-designed algorithm will beat it.
members = [0]*len(alphabet)
for i in 0...input length:
members[input[i-window_size]] = 0 if bounds ok
members[input[i]] = 1
if sum(members) == window_size:
return i