Have you ever faced any problem in a technical interview with difficulty more than DIV2 D/E? I once faced a maxflow problem. Please share the most difficult/challenging problem you faced in an interview.

I have a tuple T, consisting of

1. An integer id in range [1, 70 × 10⁶]
2. A double score₁ in range [0.0, 1.0]
3. A double score₂ in range [0.0, 1.0]
4. An integer x in range [0, 2]

What can be the most efficient way to store such tuple T =  < id, score₁, score₂, x >  given that only 5 digits after the decimal are sufficient for score₁ and score₂.

Currently, I am storing this tuple as a long which takes 8 bytes of memory. 27 bits for id, 17 bits for score₁, 17 bits for score₂ (considering values upto 5 decimal digits), and 2 bits for x, Overall 63 bits.

I'm trying to optimize the memory usage as there are millions of such tuples in an array. Also, If your way can store digits more than 5 decimal places, please tell me.

Is there a way, by which we can store the tuple T using float or some other data type? given that if the tuple is hashed to float, I should be able to get back id, x accurately and score₁, score₂ without much errors.

Thanks for your time, have a nice day.

Hello, codeforces community

• I've a 2D sparse matrix of 0's and 1's of size NxN, where N = 16 Million i.e 16,000,000.
• The number of non zeros(NNZ) in the matrix are ~450 Million. i.e 450,000,000.

What is the most efficient way to store the such matrix, given that I'll get the queries like:

• What are the non-zero elements in row number x.
• What are the non-zero elements in column number y.

Currently I'm storing the matrix in CSR format. Which takes an integer array of size NNZ and another array of size N.

Which is taking

• (450000000 * 4 Bytes) / (1024 * 1024) ~ 1716MB of memory for row storage, and same amount of memory for column storage.

The overall memory to store such structure is about 3.5GB.

I want to compress it in a way such that the memory consumption is reduced and the queries can still be fast. I am looking for some kind of serialization technique or something which can reduce the memory consumption or time complexity.

Any help regarding this is most welcome.

The two Pointer algorithm is quite popular technique. Although the idea is straightforward, Its implementation is prone to bugs. Few such bugs includes:

• Index out of range error leading to SEGSEV
• Never ending while loops leading to SIGKILL

How to write in a way such that there is less chances of bugs?

This blog is a sister blog of Binary Search Elegant Implementation. Your thoughts and implementations are valuable to community, hence welcome.

Thanks. Have a great time ahead!