Flipkart Coding Question – Solved

Question

Houses in Hackerland The city of Hackerland has many houses, each of which is connected via roads. There are house_nodes number of houses, numbered 0 to house_nodes - 1, where each pair of houses is connected and has a unique shortest path between them. Thus, the network of houses and roads forms an undirected tree structure comprising house_nodes nodes and (house_nodes - 1) edges. Each of the edges has a value denoted by val[i], which can either be 0 or 1.  To summarize, the overall tree is represented as follows: house_nodes: the number of nodes house_from, house_to: the arrays representing an undirected edge between house_from[i] and house_to[i] for 1 ≤ i ≤ house_nodes - 1. val[]: the value of each edge in the tree, which can be either 0 or 1.  Problem Statement Given the network of houses and roads, the task is to find the number of sequences of length k (h[1], h[2], ... h[k]) such that while visiting: From house h[1] to h[2], Then from h[2] to h[3], And so on until reaching house h[k], Using the unique shortest path between them, at least one edge with value '1' is visited.

TreasuresBase Expert · Accepted Answer

import math import os import random import re import sys # # Complete the 'countSequences' function below. # # The function is expected to return an INTEGER. # The function accepts following parameters: # 1. INTEGER k # 2. UNWEIGHTED_INTEGER_GRAPH house # 3. INTEGER_ARRAY val # # # For the unweighted graph, : # # 1. The number of nodes is _nodes. # 2. The number of edges is _edges. # 3. An edge exists between _from[i] and _to[i]. # # from collections import defaultdict from functools import lru_cache def countSequences(K, house_nodes, house_from, house_to, val): # Write your code here h = defaultdict(set) st = set() for i,j,k in zip(house_from, house_to, val): if k == 0: h[i].add(j) h[j].add(i) st.add(i) st.add(j) cnt = [] visited = set() for node in st: if node not in visited: temp = set() stack = [node] while stack: t = stack.pop() temp.add(t) visited.add(t) for x in h[t]: if x not in temp: stack.append(x) temp.add(x) cnt.append(len(temp)) mod = 10**9+7 first = pow(house_nodes, K, mod) first -= house_nodes for t in cnt: x = pow(t, K, mod) x -=t x += mod first -= x first += mod first %= mod return first if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') k = int(input().strip()) house_nodes, house_edges = map(int, input().rstrip().split()) house_from = [0] * house_edges house_to = [0] * house_edges for i in range(house_edges): house_from[i], house_to[i] = map(int, input().rstrip().split()) val_count = int(input().strip()) val = [] for _ in range(val_count): val_item = int(input().strip()) val.append(val_item) result = countSequences(k, house_nodes, house_from, house_to, val) fptr.write(str(result) + ' ') fptr.close()

Flipkart Coding Question – Solved

Image of the Question

All Testcases Passed ✔

Solution

🔒 Please login to view the solution

Explanation

Related Questions