Sponsored
Sponsored
This approach involves iterating through the given table and using a hash map (or dictionary) to count how many times each actor-director pair appears. After counting, you can filter these pairs to only include those that have a count of three or more.
Time Complexity: O(n), where n is the number of entries in the table.
Space Complexity: O(m), where m is the number of distinct actor-director pairs.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define TABLE_SIZE 1000
6
7typedef struct Pair {
8 int actor_id;
9 int director_id;
10} Pair;
11
12typedef struct Node {
13 Pair pair;
14 int count;
15 struct Node* next;
16} Node;
17
18Node* hashMap[TABLE_SIZE] = {NULL};
19
20unsigned int hash(Pair pair) {
21 return (pair.actor_id * 31 + pair.director_id) % TABLE_SIZE;
22}
23
24void insertOrIncrement(Pair pair) {
25 unsigned int index = hash(pair);
26 Node* node = hashMap[index];
27 while (node != NULL) {
28 if (node->pair.actor_id == pair.actor_id && node->pair.director_id == pair.director_id) {
29 node->count++;
30 return;
31 }
32 node = node->next;
33 }
34 Node* newNode = (Node*)malloc(sizeof(Node));
35 newNode->pair = pair;
36 newNode->count = 1;
37 newNode->next = hashMap[index];
38 hashMap[index] = newNode;
39}
40
41void findPairs(Pair* pairs, int size) {
42 for (int i = 0; i < size; ++i) {
43 insertOrIncrement(pairs[i]);
44 }
45 printf("+-------------+-------------+\n");
46 printf("| actor_id | director_id |\n");
47 printf("+-------------+-------------+\n");
48 for (int i = 0; i < TABLE_SIZE; ++i) {
49 Node* node = hashMap[i];
50 while (node != NULL) {
51 if (node->count >= 3) {
52 printf("| %11d | %11d |\n", node->pair.actor_id, node->pair.director_id);
53 }
54 node = node->next;
55 }
56 }
57}
58
59int main() {
60 Pair pairs[] = {
61 {1, 1}, {1, 1}, {1, 1},
62 {1, 2}, {1, 2},
63 {2, 1}, {2, 1}
64 };
65 int size = sizeof(pairs) / sizeof(pairs[0]);
66 findPairs(pairs, size);
67 return 0;
68}This C solution uses a hash map implemented with an array of linked lists to count occurrences of actor-director pairs. The hash function determines the index in the array, where a linked list stores pairs. As we iterate through the input, if a pair already exists in the structure, its count is incremented. Finally, all pairs with counts of three or higher are outputted.
If this were a SQL-based system, an efficient way to find the actors and directors who have cooperated at least three times is by using SQL's GROUP BY and HAVING clauses. The GROUP BY clause allows us to group rows that have the same values in specified columns, while the HAVING clause will filter these groups based on a given condition.
Time Complexity: O(n log n), due to potential sorting in the GROUP BY operation.
Space Complexity: O(k), where k is the number of groups formed from distinct pairs of actors and directors.
1SELECT actor_id, director_id
2FROM ActorDirector
3GROUP BY actor_id,In this SQL solution, we group the entries in the ActorDirector table by actor_id and director_id. The HAVING clause ensures that only pairs with three or more entries in the table are selected for the final result.