2 minutes ago

admin 1.9k

Hyderabad

Question 1: Location Detection

Problem Statement:

The system should identify a user's region based on their IP address.

IPv4 addresses are written as four numbers separated by periods, like "127.10.20.30". Each number is called an octet. Based on the first octet, addresses fall into one of five regions:

1. 0.0.0.0 – 127.255.255.255
2. 128.0.0.0 – 191.255.255.255
3. 192.0.0.0 – 223.255.255.255
4. 224.0.0.0 – 239.255.255.255
5. 240.0.0.0 – 255.255.255.255

You are given a list of IP addresses. For each one, check if it is valid. If it is valid, return the region index (1 through 5). If it is not valid, return -1.

Question 2: No Ancestor Subset

Problem Statement:

Given a tree with tree_nodes nodes, where each node i has an associated weight weight[i] (1-based indexing). The tree is rooted at node 1.

A subset of nodes is called "good" if there is no pair of nodes where one node is an ancestor of the other.

Find the maximum sum of weights from nodes that form a good subset.

Note: A node u is an ancestor of node v if it lies on the direct path from the root to node v.

2 minutes ago

admin 1.9k

Hyderabad

Problem 1 Solution:

Location Detection

Topics Involved / Prerequisites

• String Parsing & Manipulation
• Validation Logic
• Conditional Mapping

Overview

The objective is to validate a given list of IPv4 address strings and classify them into one of five geographic regions based on their first octet. A valid IPv4 address must consist of exactly four numeric octets separated by periods (.), and each octet must be an integer between 0 and 255 (inclusive) with no invalid leading zeros.

Approach

1. Split the String: For each IP address, manually split the string by the . character into four distinct parts. If there are not exactly four parts, it's invalid.
2. Validate Each Octet: For each part, check if it is empty, exceeds 3 characters, contains non-numeric characters, or has a leading zero (e.g., "01"). Then, parse it to an integer and ensure it falls within log[0, 255]log.
3. Determine the Region: If the IP is fully valid, inspect the first octet. Use conditional checks to map the value to the correct region index (1 through 5).
4. Error Handling: If any validation check fails, immediately return -1 for that specific IP address.

Time and Space Complexity

• Time Complexity: logO(N * L)log — Where logNlog is the number of IP addresses and logLlog is the max length of an IP string (which is small, at most 15 characters). Thus, effectively logO(N)log.
• Space Complexity: logO(1)log auxiliary space per string, returning an logO(N)log array for the results.

Code Implementation (C++)

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Helper function to validate a single octet
bool isValidOctet(const string& s) {
    if (s.empty() || s.length() > 3) return false;
    // Prevent invalid leading zeros (e.g., "012")
    if (s.length() > 1 && s[0] == '0') return false; 
    
    for (char c : s) {
        if (!isdigit(c)) return false;
    }
    
    int val = stoi(s);
    return val >= 0 && val <= 255;
}

// Function to process a single IP address
int getRegion(const string& ip) {
    vector<string> octets;
    string current = "";
    
    for (char c : ip) {
        if (c == '.') {
            octets.push_back(current);
            current = "";
        } else {
            current += c;
        }
    }
    octets.push_back(current);

   
    if (octets.size() != 4) return -1;

    for (const string& octet : octets) {
        if (!isValidOctet(octet)) return -1;
    }

    int firstOctet = stoi(octets[0]);
    
    if (firstOctet >= 0 && firstOctet <= 127) return 1;
    if (firstOctet >= 128 && firstOctet <= 191) return 2;
    if (firstOctet >= 192 && firstOctet <= 223) return 3;
    if (firstOctet >= 224 && firstOctet <= 239) return 4;
    if (firstOctet >= 240 && firstOctet <= 255) return 5;

    return -1;
}

vector<int> detectLocations(const vector<string>& ips) {
    vector<int> results;
    for (const string& ip : ips) {
        results.push_back(getRegion(ip));
    }
    return results;
}

2 minutes ago

admin 1.9k

Hyderabad

Problem 2 Solution:

 No Ancestor Subset

Topics Involved / Prerequisites

• Trees / Graph Theory
• Depth-First Search (DFS)
• Dynamic Programming on Trees (Tree DP)

Overview

We are looking for a "good subset" of nodes in a rooted tree where no selected node is an ancestor of another selected node. To maximize the sum of weights, we have to make a binary choice at every node:

1. Pick the current node: We get its weight, but we are absolutely forbidden from picking any of its descendants.
2. Skip the current node: We don't get its weight, but we are free to pick the optimal valid subset from each of its independent subtrees.

Approach

1. Build the Tree: Construct an adjacency list representation of the tree using the provided edges.
2. Post-Order DFS (Tree DP): Start a DFS from the root (Node 1). The DFS function will calculate the maximum valid weight for the subtree rooted at u.
3. State Transitions: For any node u:
   • Calculate the sum of the maximum weights from all its children's subtrees (sum_children).
   • Compare the node's own weight against sum_children.
   • Return max(weight[u], sum_children). (Because if we pick u, we forfeit the children. If we skip u, we safely take the best combinations from the children).
4. Base Case: Leaf nodes have no children, so sum_children is 0. A leaf will just return its own weight (or 0 if the weight is negative).

Time and Space Complexity

• Time Complexity: O(V + E) — Standard DFS traversal. We visit every node and every edge exactly once.
• Space Complexity: O(V + E) — For storing the tree as an adjacency list, plus O(V) for the DFS recursion stack.

Code Implementation (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Helper DFS function for Tree DP
long long dfs(int u, int parent, const vector<vector<int>>& adj, const vector<int>& weight) {
    long long sum_children = 0;
    
    // Traverse all children of the current node
    for (int v : adj[u]) {
        if (v != parent) {
            sum_children += dfs(v, u, adj, weight);
        }
    }
    

    long long current_node_weight = weight[u - 1];

    return max(current_node_weight, sum_children);
}

long long maxGoodSubsetWeight(int tree_nodes, vector<int> weight, vector<int> tree_from, vector<int> tree_to) {
    vector<vector<int>> adj(tree_nodes + 1);
    
    // Build the adjacency list for the tree
    for (size_t i = 0; i < tree_from.size(); i++) {
        adj[tree_from[i]].push_back(tree_to[i]);
        adj[tree_to[i]].push_back(tree_from[i]);
    }
    
    // Start DFS from root (Node 1) with a dummy parent (0)
    return dfs(1, 0, adj, weight);
}