Welcome back to our course on algorithmic problem-solving with PHP data structures. Today, we sharpen our focus on Associative Arrays — a robust data structure you're already familiar with from our prior discussions. This lesson will demonstrate how we can leverage associative arrays to efficiently solve common algorithmic problems you might face in a coding interview.

Let's put it in a familiar scenario: at a party, it's easy to notice that one person everyone seems to know. This person, akin to the "celebrity" at the party, serves as the analogy for an element in an array that appears more than half the time — our task is to identify this celebrity element amid a crowd of numbers.

The naive way to identify this celebrity is to count the occurrences of each number by looping over the array for each element and seeing if it repeats sufficiently to be our star. Computationally, this translates to significant time (quadratic time complexity) for larger arrays — an apparent inefficiency.

Now, let's be savvy about this. Enter the Associative Array: your sophisticated voting tally system. With it, you can keep a running total of each element's appearance as you go through the array once rather than reviewing the entire list for each integer.

Let's build the findCelebrityElement function step by step:

php
Copy to clipboard
1function findCelebrityElement($arr) {
2    $countMap = [];
3    $majorityThreshold = count($arr) / 2;

Start by initializing an associative array countMap to keep track of the frequency of each number, and compute the majorityThreshold to determine when a number is the celebrity element.

php
Copy to clipboard
1    foreach ($arr as $num) {
2        if (!isset($countMap[$num])) {
3            $countMap[$num] = 0;
4        }
5        $countMap[$num]++;

Iterate over each element in the array, checking if it's already recorded in countMap. If not, add it with an initial count of zero. Increase the count each time the element appears.

php
Copy to clipboard
1        if ($countMap[$num] > $majorityThreshold) {
2            return $num;
3        }
4    }

As we update counts, we check if any element's count surpasses the majorityThreshold. If one does, return it as the celebrity element.

php
Copy to clipboard
1    return -1;
2}

If no element meets the necessary count to be considered the celebrity, return -1 to indicate its absence.

Here is the full code!

php
Copy to clipboard
1<?php
2function findCelebrityElement($arr) {
3    $countMap = [];
4    $majorityThreshold = count($arr) / 2;
5
6    foreach ($arr as $num) {
7        if (!isset($countMap[$num])) {
8            $countMap[$num] = 0;
9        }
10        $countMap[$num]++;
11
12        if ($countMap[$num] > $majorityThreshold) {
13            return $num;
14        }
15    }
16
17    return -1;
18}
19
20// Example usage
21$array = [3, 3, 4, 2, 3, 3, 3];
22$celebrityElement = findCelebrityElement($array);
23echo "The celebrity element is: " . ($celebrityElement !== -1 ? $celebrityElement : "None") . "\n";
24?>

Now, let's transition to a digital library setting, where you want to find all articles that mention a specific word, say "sustainability." Just like a librarian who quickly locates books on a topic, we need an efficient system to index words to documents in which they appear — a task vital for modern search engines to function effectively.

Manually scanning through each document to note every word's occurrence, akin to flipping through each book's pages, is our naive approach. This might be manageable for a small number of short documents, but as the library grows, this approach becomes untenable — not to mention it can lead to errors and duplicates.

Employing associative arrays in PHP is akin to using a digital catalog system — swift, error-free, and capable of efficiently handling extensive volumes of data. This approach provides the quick lookup functionality to link words with documents effectively.

We start by declaring our associative array, which will act as our digital catalog system:

php
Copy to clipboard
1function createKeywordIndex($documents) {
2    $index = [];

Then, we iterate over each document, splitting the text into individual words and cataloging them systematically:

php
Copy to clipboard
1    foreach ($documents as $docIndex => $doc) {
2        $words = preg_split('/\s+/', $doc);
3        foreach ($words as $word) {
4            if (!isset($index[$word])) {
5                $index[$word] = [];
6            }
7            if (!in_array($docIndex, $index[$word])) {
8                $index[$word][] = $docIndex;
9            }
10        }
11    }
12
13    return $index;
14}

By the end, we've constructed a robust index that can effortlessly tell us where to find any given word, illustrating the usefulness of associative arrays and the importance of effective data structuring.

Here is the full code!

php
Copy to clipboard
1<?php
2function createKeywordIndex($documents) {
3    $index = [];
4
5    foreach ($documents as $docIndex => $doc) {
6        $words = preg_split('/\s+/', $doc);
7        foreach ($words as $word) {
8            if (!isset($index[$word])) {
9                $index[$word] = [];
10            }
11            if (!in_array($docIndex, $index[$word])) {
12                $index[$word][] = $docIndex;
13            }
14        }
15    }
16
17    return $index;
18}
19
20// Example usage
21$documents = [
22    "The quick brown fox jumps over the lazy dog",
23    "The quick red fox",
24    "Lazy dogs sleep",
25];
26
27$keywordIndex = createKeywordIndex($documents);
28$searchWord = "fox";
29if (isset($keywordIndex[$searchWord])) {
30    echo "The word '$searchWord' is found in documents: " . implode(', ', $keywordIndex[$searchWord]) . "\n";
31} else {
32    echo "The word '$searchWord' is not found in any document.\n";
33}
34?>

Through these two algorithmic challenges, we’ve seen firsthand how PHP associative arrays can be strategically used to simplify complex problems and achieve computational efficiency. The findCelebrityElement function is an example of optimizing search algorithms, while createKeywordIndex demonstrates data structuring for quick access — both are invaluable skills in a programmer's toolkit. As we draw this theoretical session to a close, you should feel more equipped to utilize PHP associative arrays to solve coding problems with confidence and precision.