Madman: The Most Chatty Phone Number

Database Technologies
1

Madman: The Most Chatty Phone Number

Problem Description

In this problem, we are given a large number of mobile phone call records and asked to find the phone number with the most number of calls, also known as the “chatty” phone number. This problem can be solved using a binary search tree (BST) data structure.

Input Formats

  • The first line of input contains a positive integer N (≤10^5), representing the number of call records.
  • Each of the next N lines contains a call record, consisting of a dialed phone number and the recipient’s 11-digit number, separated by spaces.

Output Formats

  • The output consists of the chatty phone number and the number of calls, separated by a space.
  • If there are multiple phone numbers with the same number of calls, the output will contain the minimum number and the number of calls, as well as the additional number of parallel calls.

Sample Input

413,005,711,862 13,588,625,832
13,505,711,862 13,088,625,832
13,588,625,832 18,087,925,832
15,005,713,862 13,588,625,832

Sample Output

135886258323

Solution

To solve this problem, we can use a binary search tree (BST) data structure. We will create a BST with the following structure:

typedef long long ll;
struct node {
    ll num;
    int time;
    struct node *lc, *rc;
};

The num field represents the 11-digit phone number, and the time field represents the number of calls. The lc and rc fields represent the left and right child nodes of the current node.

We will use the following functions to insert a new node into the BST:

void Insert(node *&root, ll num) {
    node *p = new node;
    p->lc = NULL;
    p->rc = NULL;
    p->num = num;
    p->time = 1;
    if (root == NULL) {
        root = p;
        return;
    }
    node *T = root;
    node *LT = NULL;
    while (T) {
        if (num > T->num) {
            LT = T;
            T = T->rc;
        } else if (num < T->num) {
            LT = T;
            T = T->lc;
        } else if (num == T->num) {
            T->time++;
            return;
        }
    }
    if (num > LT->num) {
        LT->rc = p;
    } else {
        LT->lc = p;
    }
    return;
}

We will also use the following function to print the chatty phone number and the number of calls:

void Print(node *root, ll num, int time) {
    node *t = root;
    int nn = 1;
    queue<node *> q;
    q.push(root);
    while (!q.empty()) {
        t = q.front();
        q.pop();
        if (t->lc) q.push(t->lc);
        if (t->rc) q.push(t->rc);
        if (time < t->time) {
            nn = 1;
            time = t->time;
            num = t->num;
        } else if (time == t->time) {
            nn++;
            if (num > t->num) {
                num = t->num;
            }
        }
    }
    printf("%lld %d", num, time);
    if (nn != 1) printf("%d\n", nn);
    else printf("\n");
}

The main function reads the input and calls the Insert and Print functions:

int main() {
    int n;
    scanf("%d", &n);
    n *= 2;
    struct node *root = NULL;
    while (n--) {
        ll num;
        scanf("%lld", &num);
        Insert(root, num);
    }
    Print(root, 0, 0);
    return 0;
}

Explanation

The Insert function inserts a new node into the BST based on the phone number. If the phone number is already in the BST, it increments the time field of the existing node. If the phone number is not in the BST, it creates a new node and inserts it into the BST.

The Print function prints the chatty phone number and the number of calls. It uses a queue to traverse the BST and find the node with the maximum time field. If there are multiple nodes with the same time field, it prints the minimum number and the number of calls.

The main function reads the input and calls the Insert and Print functions. It reads the number of call records and inserts each record into the BST using the Insert function. Finally, it calls the Print function to print the chatty phone number and the number of calls.