1

I was asked this question in an interview of Crypto company for the role of backend developer.

Please suggest me another stack-site if this is not the place to ask this question.

There is a subsystem A which sends the data to another subsystem B as a file in.txt. Subsystem B then processes this file and produces an output and writes this into out.txt file which will then be read by subsystem C which does some tasks on its own.

Lets suppose that all that in.txt contains is a numbers separated by new line, and subsystem B has sum all the numbers and write the output into out.txt. You have the basic logic to do this and a new requirement has come or some change occurred in the system so that the size of the input file is not fixed and can be 10kb or can be 10gb.

But this processing has to be done in a fixed amount of time x (say a minute or few minutes), you have to process the entire file and write the output into out.txt within the timeframe. After the x period of time (at x+1 time) your data is not unusable and will be discarded automatically. Your normal adding algorithm might more than given time. So how would you solve the problem and output the summation of all numbers within the given time frame.

My approach is to divide the file into multiple chunks and read through multiple threads (or instances?) and process each chunk on its own and each thread will add the value to out.txt. My approach seems too basic, I'm still learning backend development and want to know how to approach this problem, also could you please provide references or any material so I could dive more into the topic.

10
  • please don't cross-post: stackoverflow.com/questions/65293244/… "Cross-posting is frowned upon as it leads to fragmented answers splattered all over the network..."
    – gnat
    Dec 14, 2020 at 17:10
  • @gnat I don't where to post these type of questions, can you help on which site should I keep and which should be deleted, Also if you can since you're already here help me find the answer to this? Dec 14, 2020 at 17:11
  • Also it is said "If you spot a user cross-posting, please consider politely explaining to them in a comment why we dislike cross-posting" but you down-voted my question as doesn't show research effort or not useful, how is this polite? Dec 14, 2020 at 17:19
  • 1
    That sounds like an acceptable answer to me. Interview questions are allowed to be basic. They're trying to find out whether you know about multi-threading. They also might want to find out whether you know about distributed processing. If multi-threading is still too slow, you could use multiple servers.
    – user253751
    Dec 14, 2020 at 17:40
  • 5
    I strongly suspect this question was more about your thought process and followup questions than the answer. Perhaps the interviewer wanted you to go deeper and describe how you might distribute the cost of parsing the list across workers. (Much more costly than adding numbers, isn't it?) Or, perhaps the interviewer was looking for you to ask "What's the max reasonable file size? What's our SLA? Do we get to set our own SLA? After all, there will simply physical limits." Etc..
    – svidgen
    Dec 14, 2020 at 18:19

1 Answer 1

4

Your approach looks reasonable. Note if the file size is small, there is no need to multi-thread processing it at all.

Something else worth considering:

IO bound?

It's better to profile how much time it is spent on disk access vs sum the numbers, along with how chunk size affects the IO time. So you can decide the best possible subfiles you want to split into.

Data processing

One possible optimization is to process the chunk file as binary data. Every time a byte buffer is allocated to read the preceding x MB from the file.

A Java example with integers:

private long sumInBinary() throws IOException 
{
    var f = new RandomAccessFile(file, "r");
    int fileLength = (int) f.length();
    byte buf[] = new byte[16 * 1024];
    int acc = 0;
    long total = 0;
    int read = 0;
    while (read < fileLength) 
    {
        int len = Math.min(buf.length, fileLength - read);
        f.readFully(buf, 0, len);
        read += len;
        for (int i = 0; i < len; i++) {
            if ((buf[i] >= 48) && (buf[i] <= 57))
            {
                acc = acc * 10 + buf[i] - 48;
            }   
            else 
            {
                total += acc;
                acc = 0;
            }
        }
    }
    f.close()
    return total;
}

Multithread

Other than multithread chunks reading, it's also possible to apply multithreaded data process for each chunk. And this involves some parameters (e.g, buffer size) tweaking too.

6
  • 3
    It also involves deciding what to do if the chunk ends in the middle of a number (which it will, most of the time)
    – user253751
    Dec 14, 2020 at 20:21
  • 1
    In this simplistic example is extremely hard to imagine that the processing time to add numbers is even remotely relevant, compared to the disk IO.
    – user949300
    Dec 14, 2020 at 22:25
  • 6
    I mean I don't know but it's worth testing for large number case where string parsing could add overhead
    – lennon310
    Dec 14, 2020 at 22:39
  • I agree with you both, @lennon310 can add little bit more to your answer as how would you answer in the interview, not like a program but the various techniques and methodologies or use cases you would provide to show case your knowledge in this case. Also could you provide ( if any ) references to more of these type of questions. Dec 15, 2020 at 0:57
  • @lennon310 also the interviewer said the file size can be 10kb or 10gb so my thoughts are how would you make your multithreading work, how would you divide your tasks between these thread when size is small, or do you divide. Also is multithreading actually a good solution? Dec 15, 2020 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.