---
# System prepended metadata

title: Untitled

---

Design an instant messaging service, user should be a send message (A->B, B->A), user should be able to receive a message, user should be retrieve messages when he/she is online.

[[1,3], [2,6], [8, 10], [15,18]] => [[1,6], [8,10], [15,18]]


Send Messages
Pull Messages

UserA -> Server -> Put messages to database -> Push messages to UserB -> UserB sends ACK to server

UserA -> send message1 -> network delay
UserA -> send message2 

retry
server -> msg1 (content, uuid) -> 10x -> uuid
server -> msg2 -> 
database -> msg (uuid, content, session message seqno)
session message seqno
UserB -> Server -> Pull last unreceived messages


UserA -> 1,2,3 -> UserB
UserA -> 4,5,6 -> UserC
UserB -> 7,8,9 -> UserC

Message {
    chat_id,
    sender_id,
    uuid,
    content,
    seqno,
    receiver_seqno: u64[],
}
last_ack_receiver_seqno

Chat {
    id,
    seqno,
    peers: [Peer],
}

Peer {
    user_id,
    last_ack,
}

PeerUnreadChat {
    chat_id
}

UserC -> Pull messages from last ack

A-> B, C
PullMessageFromChat(user_id, chat_id) {
    chat = query Chat(chat_id)
    peer = query chat.peers(user_id)
    messages = Messages(chat_id=chat_id, seqno in ( peer.last_ack..))
    return messages
}


      4
     / \
    8  5
  ./ \. \
  0.  1. 6

output = 5

Count number of nodes such that the average value of the subtree is equal to the value of the node.

struct TreeNode {
    int val,
    TreeNode* left,
    TreeNode* right,
}

O(n)

int res = 0;

int count_subtrees(TreeNode* root) {
    int count = 0;
    int sum = 0;
    tree_count_and_sum(root, *count, *sum);
    return res;
}

void tree_count_and_sum(TreeNode* root, int* count, int * sum) {
    if (root == nullptr) {
        return;
    }
    
    tree_count_and_sum(root->left, count, sum);
    tree_count_and_sum(root->right, count, sum);
    *sum += root->val;
    *count += 1;
    int avg = *sum / *count;
    if (*count == avg) {
        res += 1;
    }
}





















