Grokking Multithreading and Concurrency for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Problem 3: Linear Search with Indices and Occurrences
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Overview

To enhance the linear search to find and count all occurrences, we'll store each occurrence in a shared collection and count the total number of occurrences in the end. This method will provide both the indices where the target element appears and the total number of appearances in the array. With multithreading, each thread will examine its chunk of the array, reducing the overall time for the search.

Multithreading in Linear Search for Indices and Occurrences

The process is similar to the multithreaded search for all occurrences, but with the addition of counting the total number of occurrences:

  1. Divide the Work: Split the array into smaller segments or "chunks" for each thread.
  2. Concurrent Execution: Threads will search their chunks for the target element.
  3. Collecting Results: Use a shared collection (e.g., a list) to append indices of occurrences. Use a shared variable (e.g., an integer) to store the count of occurrences.
  4. Synchronization: Ensure thread-safe updates to shared data structures using synchronization mechanisms.

Step-by-step Algorithm

  1. Initialize the array (arr) and the target element (key) to search for.

  2. Initialize a shared list (foundIndices) to store the indices of all occurrences.

  3. Initialize a shared variable (occurrencesCount) to store the count of occurrences.

  4. Define locks for synchronizing access to shared resources (indicesLock for foundIndices and countLock for occurrencesCount).

  5. Define a function SearchIndicesOccurrences(threadId, arr, key):

    • Calculate the size of the chunk each thread will work on (chunkSize) based on the number of threads.
    • Calculate the start and end indices for the thread's assigned chunk.
    • Initialize an empty list (localIndices) to store the indices found by this thread.
    • Initialize a variable (localCount) to count the occurrences found by this thread.
    • For each index (i) in the assigned range:
      • If arr[i] is equal to key:
        • Add i to localIndices.
        • Increment localCount.
    • Lock indicesLock:
      • Extend foundIndices with localIndices.
    • Lock countLock:
      • Add localCount to occurrencesCount.

  6. Create an array of threads (threads) with a size of NUM_THREADS.

  7. For each threadId from 0 to NUM_THREADS - 1:

    • Create a new thread that runs the SearchIndicesOccurrences function with threadId, arr, and key as arguments.
    • Store the thread in the threads array.

  8. Start all the created threads (i.e., thread.start()).

  9. For each thread in the threads array:

    • Wait for the thread to complete its execution (i.e., thread.join()).

  10. If foundIndices is empty:

    • Output "Element not found in the array."

  11. If foundIndices is not empty:

    • Output "Element found {occurrencesCount} times at indices: {foundIndices}".

  12. End the program.

Algorithm Walkthrough

Input:

  • Let's take arr = [4, 5, 4, 6, 4, 7, 8, 4, 9, 5] as our array.
  • Our target key to search for is 4.
  • We'll use NUM_THREADS = 2 for simplicity.

Step 1: We initialize arr and key.

  • arr = [4, 5, 4, 6, 4, 7, 8, 4, 9, 5]
  • key = 4

Step 2: We initialize foundIndices = [] and occurrencesCount = 0.

Step 3: Locks indicesLock and countLock are defined but not locked at this point.

Step 5: This is the core function, but we don't execute it yet. We'll come back to it when a thread is started.

Step 6: We create an array threads of size 2 (since NUM_THREADS = 2).

Step 7: We're creating 2 threads here.

For threadId = 0:

  • SearchIndicesOccurrences(0, arr, key) is called.

For threadId = 1:

  • SearchIndicesOccurrences(1, arr, key) is called.

Both threads are added to the threads array but not yet started.

Step 8: Start both threads:

For threadId = 0:

  • chunkSize = 10/2 = 5 (as there are 2 threads)
  • It works on the first half of arr: [4, 5, 4, 6, 4]
  • localIndices = [0, 2, 4]
  • localCount = 3
  • Lock indicesLock and add localIndices to foundIndices
  • Lock countLock and add localCount to occurrencesCount

For threadId = 1:

  • It works on the second half of arr: [7, 8, 4, 9, 5]
  • localIndices = [8]
  • localCount = 1
  • Lock indicesLock and add localIndices to foundIndices
  • Lock countLock and add localCount to occurrencesCount

Step 9: Wait for both threads to complete.

Step 10: Check if foundIndices is empty. It's not.

Step 11: Output result:

  • "Element found 4 times at indices: [0, 2, 4, 8]".

Step 12: End of the program.

This walkthrough assumes that the locks work correctly to avoid any race conditions or conflicts while accessing shared resources from different threads. The main idea here is to split the array into chunks and let each thread work on its chunk independently.

mediaLink

1 of 6

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible