Problem 4: Min/Max/Sum

Grokking Multithreading and Concurrency for Coding Interviews

Ask Author

Back to course home

0% completed

Table of Contents

Overview

Multithreading in Min/Max/Sum Finding

Pseudocode

Algorithm Walkthrough

Overview

Finding the minimum, maximum, and sum of elements in an array can be parallelized efficiently using multithreading. Each thread is given a portion of the array to process and returns partial results, which are then combined to get the final result.

Multithreading in Min/Max/Sum Finding

Divide the Work: As before, split the array into chunks for each thread.
Concurrent Execution: Threads will independently compute the min, max, and sum for their assigned chunks.
Combine Results: After all threads finish execution, combine their results to obtain the global min, max, and sum.
Synchronization: Utilize synchronization mechanisms to ensure thread-safe access to shared variables if necessary.

Pseudocode

FUNCTION ThreadedMin(data: ARRAY of INTEGER, number_of_threads: INTEGER) -> INTEGER
    SPLIT data into number_of_threads parts
    FOR EACH part
        START a thread that finds the MINIMUM of the part and saves it
    JOIN all threads
    RETURN the MINIMUM of all thread results
END FUNCTION

FUNCTION ThreadedMax(data: ARRAY of INTEGER, number_of_threads: INTEGER) -> INTEGER
    SPLIT data into number_of_threads parts
    FOR EACH part
        START a thread that finds the MAXIMUM of the part and saves it
    JOIN all threads
    RETURN the MAXIMUM of all thread results
END FUNCTION

FUNCTION ThreadedSum(data: ARRAY of INTEGER, number_of_threads: INTEGER) -> INTEGER
    SPLIT data into number_of_threads parts
    FOR EACH part
        START a thread that finds the SUM of the part and saves it
    JOIN all threads
    RETURN the SUM of all thread results
END FUNCTION

Algorithm Walkthrough

Input:

Let's consider an array data = [4, 5, 2, 6, 1, 7, 8, 3, 9, 10]
We'll use number_of_threads = 2 for simplicity.

1. ThreadedMin Function:

Step 1: Split data into 2 parts:

part1 = [4, 5, 2, 6, 1]
part2 = [7, 8, 3, 9, 10]

Step 2: Start 2 threads:

Thread1 finds the minimum of part1, which is 1.
Thread2 finds the minimum of part2, which is 3.

Step 3: Join all threads.

Step 4: Return the minimum of thread results:

Minimum of 1 and 3 is 1.

Thus, ThreadedMin(data, 2) returns 1.

2. ThreadedMax Function:

Step 1: Split data into 2 parts:

part1 = [4, 5, 2, 6, 1]
part2 = [7, 8, 3, 9, 10]

Step 2: Start 2 threads:

Thread1 finds the maximum of part1, which is 6.
Thread2 finds the maximum of part2, which is 10.

Step 3: Join all threads.

Step 4: Return the maximum of thread results:

Maximum of 6 and 10 is 10.

Thus, ThreadedMax(data, 2) returns 10.

3. ThreadedSum Function:

Step 1: Split data into 2 parts:

part1 = [4, 5, 2, 6, 1]
part2 = [7, 8, 3, 9, 10]

Step 2: Start 2 threads:

Thread1 calculates the sum of part1, which is 18.
Thread2 calculates the sum of part2, which is 37.

Step 3: Join all threads.

Step 4: Return the sum of thread results:

Sum of 18 and 37 is 55.

Thus, ThreadedSum(data, 2) returns 55.

The main idea behind these functions is to split the data into smaller chunks, process each chunk in parallel using multiple threads, and then aggregate the results. The use of threads speeds up the computations for large datasets by taking advantage of parallel processing capabilities.

Enter caption here

1 of 5

Python3

. . . .

Mark as Completed

Table of Contents

Overview

Multithreading in Min/Max/Sum Finding

Pseudocode

Algorithm Walkthrough