Ad Hierarchy Event Tracker: Worst-K Ads by CTR Under a Campaign or Ad Group

Implement an in-memory tracker for advertising performance over a hierarchy of ad entities. A campaign can contain ad groups and also ads directly, an ad group contains ads, and click and impression events arrive for individual ads, each tagged with a date. One possible hierarchy: ```text Campaign / \ AdGroup1 Ad1 / \ Ad2 Ad3 ``` Implement these three operations (signatures as reported, in Java): ```java // Register an ad node. It can be a campaign, an ad group, or an ad. void AddAdEntity(String nodeId, String parentId); // Consume an ad event. EventType is an enum: CLICK or IMPRESSION. void ConsumeEvent(String id, String date, EventType eventType); // Return the k worst-performing ads for the given date under the given node, // judged by ad stats such as impressions, clicks and click-through rate (CTR). // The node can be a campaign or an ad group. List<String> getWorstK(String nodeId, String date, int k); ``` Performance may be ranked by CTR, an ad's clicks divided by its impressions on that date, with a lower CTR meaning worse performance. `getWorstK` considers every ad anywhere below the node, not only its direct children: for the campaign above, that is Ad1, Ad2 and Ad3. ### Clarifying Questions - Is a campaign registered with a null parent, and can there be several campaigns? - Is every node registered before its children and before any event for it, and can a node ever move to a different parent? - Does `ConsumeEvent` always receive an ad id, or can events arrive for an ad group or a campaign? - How should an ad with no impressions on the date be treated, since its CTR is undefined, and should ads with no events that day appear at all? - How are ties in CTR broken, and what is returned when fewer than k ads exist under the node? - What format do dates have, and could a query ever cover a range of dates instead of one day? - Which call dominates in volume, events or queries? ### Part 1 — Register entities and record events Implement `AddAdEntity` and `ConsumeEvent` so that any node can be found by its id, each ad's impressions and clicks are kept per date, and the ads below any campaign or ad group can be reached. ```hint Follow one event Every call names a node by id. Think about what you need to find that node quickly, and which other nodes' answers can change when one ad receives an event. ``` #### What This Part Should Cover - A node representation and an id-to-node index built during registration - Per-date impression and click counters for each ad - Handling of unknown ids, duplicate registrations and events sent to a node that is not an ad ### Part 2 — Return the worst K ads Implement `getWorstK` for a campaign or an ad group: rank every ad below the node by its performance on the given date and return up to k ad ids, worst first. ```hint Pin the order first Before writing the query, decide exactly how two ads compare, including equal CTRs and an ad with zero impressions, so that the result is unique. ``` #### What This Part Should Cover - Correct scope: every descendant ad at any depth, such as Ad1 directly under the campaign as well as Ad2 and Ad3 under the ad group - A total ordering with explicit rules for ties and for ads without impressions, compared without floating-point surprises - Selecting the k worst without sorting the whole subtree when k is small ### Part 3 — Keep queries fast on large campaigns Suppose `getWorstK` is called often on campaigns with many ads. Discuss how to avoid walking and ranking the whole subtree on every query, and what that costs each time an event arrives. ```hint Where the work happens Compare paying the ranking cost when an event arrives with paying it when a query arrives. If you chose the first, which nodes would have to change on each event? ``` #### What This Part Should Cover - Query-time computation versus keeping a per-node, per-date ordering that is updated on write - The cost of moving one ad within that ordering when its CTR changes, across all of its ancestors - Memory growth across many dates, and how old dates are expired ### What a Strong Answer Covers - Clarifies the ranking key, the tie rule and the treatment of zero-impression ads before coding - Chooses a data model that matches an explicit parent-child hierarchy addressed by id, and justifies it - Correct, compilable code for all three operations - Time and space complexity per operation for both the query-time and the write-time approaches, with a reasoned choice between them - Edge cases: unknown ids, `k <= 0`, k larger than the number of ads, nodes without ads, and dates without events ### Follow-up Questions - Advertisers want the worst K over a range of dates rather than one day. What changes? - Events arrive from many threads at once. How do you make the tracker thread-safe without one global lock? - An ad can be moved from one ad group to another. What has to be updated? - A click and its impression can arrive out of order, or the same event can arrive twice. How do you keep CTR meaningful?