diff options
Diffstat (limited to 'sender_largest_word_cnt.c')
-rw-r--r-- | sender_largest_word_cnt.c | 145 |
1 files changed, 145 insertions, 0 deletions
diff --git a/sender_largest_word_cnt.c b/sender_largest_word_cnt.c new file mode 100644 index 0000000..7635b63 --- /dev/null +++ b/sender_largest_word_cnt.c @@ -0,0 +1,145 @@ +// 2284. Sender With Largest Word Count +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/* + * you have a chat log of 'n' messages. you are given two string arrays + * 'messages' and 'senders' where 'messages[i]' is a message sent by + * 'senders[i]'. a message is a list of words that are separated by a single + * space with no leading or trailing spaces. the word count of a sender is the + * total number of words sent by the sender. note that a sender may send more + * than one message. return the sender with the largest word count. if there is + * more than one sender with the largest word count, return the one with the + * lexicographically largest name + */ + +typedef struct { + uint val; + char *str; + int cnt; +} dict; + +uint rs_hash(char *str) { + uint a = 63689, b = 378551, hash = 0; + while (*str) { + hash = hash * a + (*str++); + a *= b; + } + return (hash & 0x7FFFFFFF); +} + +int cmp(const void *a, const void *b) { + dict aa = **(dict **)a; + dict bb = **(dict **)b; + if (aa.cnt == bb.cnt) + return strcmp(aa.str, bb.str); + return aa.cnt - bb.cnt; +} + +char *largestWordCount(char **messages, int messages_size, char **senders, + int senders_size) { + int n = senders_size, *words = calloc(n, sizeof(int)); + for (int i = 0; i < n; i++) { + int len = strlen(messages[i]); + if (!len) { + words[i] = 0; + continue; + } + words[i] = 1; + for (int j = 0; j < len; j++) + if (messages[i][j] == ' ') + words[i]++; + dict **hash = malloc(n * sizeof(dict *)); + for (int i = 0; i < n; i++) { + hash[i] = malloc(sizeof(dict)); + hash[i]->cnt = 0; + } + int max = 0, pos = 0; + dict **max_data = malloc(n * sizeof(dict *)); + for (int i = 0; i < n; i++) { + uint h = rs_hash(senders[i]); + if (!hash[h % n]->cnt) { + hash[h % n]->cnt = words[i]; + int len = strlen(senders[i]); + hash[h % n]->str = malloc((len + 1) * sizeof(char)); + strcpy(hash[h % n]->str, senders[i]); + hash[h % n]->val = h; + if (hash[h % n]->cnt == max) { + max_data[pos] = hash[h % n]; + pos++; + } + if (hash[h % n]->cnt > max) { + pos = 0; + max = hash[h % n]->cnt; + max_data[pos] = hash[h % n]; + pos++; + } + } else if (hash[h % n]->val == h) { + hash[h % n]->cnt += words[i]; + if (hash[h % n]->cnt == max) { + max_data[pos] = hash[h % n]; + pos++; + } + if (hash[h % n]->cnt > max) { + pos = 0; + max = hash[h % n]->cnt; + max_data[pos] = hash[h % n]; + pos++; + } + } else { + int k = (h + 1) % n; + bool done = false; + while (hash[k]->cnt) { + if (hash[k]->val == h) { + hash[k]->cnt += words[i]; + if (hash[k]->cnt == max) { + max_data[pos] = hash[k]; + pos++; + } + if (hash[k]->cnt > max) { + pos = 0; + max = hash[k]->cnt; + max_data[pos] = hash[k]; + pos++; + } + done = true; + break; + } + k = (k + 1) % n; + } + if (!done) { + hash[k]->val = h; + hash[k]->cnt = words[i]; + int len = strlen(senders[i]); + hash[k]->str = malloc((len + 1) * sizeof(char)); + strcpy(hash[k]->str, senders[i]); + if (hash[k]->cnt == max) { + max_data[pos] = hash[k]; + pos++; + } + if (hash[k]->cnt > max) { + pos = 0; + max = hash[k]->cnt; + max_data[pos] = hash[k]; + pos++; + } + } + } + } + qsort(max_data, pos, sizeof(dict *), cmp); + return max_data[pos - 1]->str; + } +} + +int main() { + char m1[4][19] = {"Hello userTwooo", "Hi userThree", "Wonderful day Alice", + "Nice day userThree"}; + char s1[4][9] = {"Alice", "userTwo", "userThree", "Alice"}; + char m2[2][31] = {"How is leetcode for everyone", + "Leetcode is useful for practice"}; + char s2[2][7] = {"Bob", "Charlie"}; + printf("%s\n", largestWordCount(m1, 4, s1, 4)); // expect: Alice + printf("%s\n", largestWordCount(m2, 2, s2, 2)); // expect: Charlie +} |