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 '20 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? – YouKnowWhoIAm Dec 14 '20 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? – YouKnowWhoIAm Dec 14 '20 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 '20 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 '20 at 18:19
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 '20 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 '20 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 '20 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. – YouKnowWhoIAm Dec 15 '20 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? – YouKnowWhoIAm Dec 15 '20 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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