twoslow's blog

By twoslow, history, 6 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • -14
  • Vote: I do not like it

By twoslow, history, 6 years ago, In English

I have a tuple T, consisting of

  1. An integer id in range [1, 70 × 106]
  2. A double score1 in range [0.0, 1.0]
  3. A double score2 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, score1, score2, x >  given that only 5 digits after the decimal are sufficient for score1 and score2.


Currently, I am storing this tuple as a long which takes 8 bytes of memory. 27 bits for id, 17 bits for score1, 17 bits for score2 (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 score1, score2 without much errors.

Thanks for your time, have a nice day.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By twoslow, history, 6 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By twoslow, 6 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +21
  • Vote: I do not like it