Coding Test Practice - [1st] News Clustering
It's an implementation problem, but depending on how you solve it the solution gets really short, so there's a lot to learn from it
- Letter to index with bit operations
Regardless of letter case, the following always holds.
'A' & 31 = 1, 'a' & 31 = 1
'B' & 31 = 2, 'b' & 31 = 2
~
'Z' & 31 = 26, 'Z' & 31 = 26
It holds because the bits of 'A' and 'a' are as follows.
'A' = 1000001, 'a' = 1100001
31 in bits is 11111, so it means ignoring everything except the last 5 bits.
Once you ignore them, the bit value starts from 1.
- Flattening to a one-dimensional index
Say there's a 3D array a[3][2][4].
If the indices going into each are idx1, idx2, idx3,
and you compute the index as idx1 + idx22 + idx34,
you can shrink array a down to a[3+4+16] = a[23].
In this problem, you'd want to assign an index to each character of a string like "AB"
and put a value into an array, but you can store it in a one-dimensional array with something like 'A' + 'B' * 26.