🧠 Agoda Technical Assessment (Back End) – Problem Breakdown & Solutions

Problem 1: Special Nodes in a Tree

Problem Summary

Given a tree with n nodes, a node is special if it is an endpoint of any diameter of the tree.

Return a binary array where:

• 1 → node is special
• 0 → node is not special

Key Definition

The diameter of a tree is the number of edges in the longest path.

Important detail:

There can be multiple diameter paths. We must mark endpoints of any of them.

🔍 Core Insight

In a tree:

1. Pick any node → find the farthest node A
2. From A, find the farthest node B
3. Distance between A and B = diameter D

Now compute:

• distA[i] = distance from A
• distB[i] = distance from B

A node is special if:

Why? Because nodes whose eccentricity equals the diameter are endpoints of some longest path.

⏱ Time Complexity

• 3 BFS traversals
• O(n)

Works up to 10⁵ nodes.

💡 Implementation (Python)

import collections

def isSpecial(tree_nodes, tree_from, tree_to):
    if tree_nodes <= 1:
        return [1] * tree_nodes

    adj = collections.defaultdict(list)
    for u, v in zip(tree_from, tree_to):
        adj[u].append(v)
        adj[v].append(u)

    def bfs(start):
        dist = [-1] * (tree_nodes + 1)
        queue = collections.deque([start])
        dist[start] = 0

        while queue:
            node = queue.popleft()
            for nei in adj[node]:
                if dist[nei] == -1:
                    dist[nei] = dist[node] + 1
                    queue.append(nei)

        return dist

    start = tree_from[0]
    d1 = bfs(start)
    A = max(range(1, tree_nodes + 1), key=lambda i: d1[i])

    distA = bfs(A)
    B = max(range(1, tree_nodes + 1), key=lambda i: distA[i])
    D = distA[B]

    distB = bfs(B)

    result = []
    for i in range(1, tree_nodes + 1):
        if max(distA[i], distB[i]) == D:
            result.append(1)
        else:
            result.append(0)

    return result

Problem 2: Best TV Show in a Genre (REST API)

Problem Summary

Use HTTP GET to query:

Results are paginated.

Given a genre:

• Find all shows containing that genre
• Return the show with highest IMDb rating
• If tie → return alphabetically smaller name

🔍 Key Requirements

• Must iterate all pages (?page=1, ?page=2, …)
• Genre is substring match (e.g., "Action" in "Action, Drama")
• Handle rating ties properly

⏱ Complexity

O(total_records)

Usually small dataset.

💡 Implementation (Python)

import requests

def bestInGenre(genre):
    base_url = "https://jsonmock.hackerrank.com/api/tvseries"
    
    page = 1
    best_name = ""
    best_rating = -1

    while True:
        response = requests.get(f"{base_url}?page={page}")
        data = response.json()

        for show in data["data"]:
            if genre in show["genre"]:
                rating = show["imdb_rating"]
                name = show["name"]

                if rating > best_rating:
                    best_rating = rating
                    best_name = name
                elif rating == best_rating and name < best_name:
                    best_name = name

        if page >= data["total_pages"]:
            break

        page += 1

    return best_name

Engineering Takeaways

1️⃣ Tree Problems

• Diameter problems almost always reduce to two BFS/DFS passes.
• Endpoint detection is often about eccentricity.

2️⃣ REST API Problems

• Always check pagination.
• Don’t overcomplicate with sorting.
• Track max in single pass.

3️⃣ Interview Strategy Insight

Assessments often test:

• Clean algorithm fundamentals
• Edge-case awareness
• API handling discipline
• Time complexity clarity

Final Thoughts

These problems aren’t about memorizing tricks.

They test:

• Whether you understand tree properties
• Whether you handle pagination carefully
• Whether you write production-safe logic

If you're preparing for backend interviews, mastering these fundamentals is essential.