Romok007's blog

Help needed with an interview problem
By Romok007, history, 4 years ago, In English

Hello everyone, I have a rough solution in the end, but I need your views on this. Thanks in advance :)

You are given a tree of N nodes. The tree is rooted at node 1. Each tree node has a value associated with it and is represented as value. For each node, you are required to determine the closest ancestor that contains values that are co-prime to the current node value. If no such nodes exist, then print -1. Two integers a and b are relatively prime, mutually prime, or co-prime if the only positive integer (factor) that can divide both the integers is 1.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a node v is the last difference from v vertex the path from the root to vertex v. Children of vertex v are all nodes for which v is the parent. A vertex is a leaf if it has no children.

Input format

• The first line contains an integer T denoting the number of test cases.

• The first line of each test contains an integer N denoting the number of nodes in the tree.

• The next line of each test case contains N space-separated integers where the ih integer denotes the value at node i represented as value;

• Next N — 1 lines of each test case contain two space separated integers u and v denoting the edge

between node u and node u.

Output format

For each test case, print N space-separated integers where the i' integer denotes the closet ancestor contains coprime values. If no such ancestors exist then print -1.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
1 <= u, v <= N
1 <= valuei <= 100

My solution : 

1. Create a list of co-primes for each value from 1 to 100 (Precompute)
2. Traverse the tree and for each node we maintain a hashmap of ancestors(value -> depth). When we visit a node it will contain the path from the root of the tree to this current node. We now traverse the list of co-primes for the current node and select the node that exists in the map as well in the precomputed list of the particular node(value) and select the value which has the maximum depth(closest ancestor).

However the time complexity of the solution per test case is O(N*valuei) which I think might not pass the problem. Can you please help with some optimized approach?

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

This is from google hiring challenge

And i got this problem, your solution is correct ( partially)

Basically for each node keep a list of values co prime to it

Then use this vector<pair<int,int>> stc[], when u visit a node (say src) at level (say level) with value (say v[i]) , insert it like this

stc[v[i]].push_back(make_pair(src,level))

Now just iterate over all x in in numbers co prime to $$$val[i]$$$ and check the last element in $$$stc[x]$$$ pick the one with closest level. And you're done

And don't forget to pop stuff out when backtracking

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes I am talking about this solution only. Did you submit this solution during the challenge and got full marks?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Yup, what language u coded into,

      Also i did lots of precomputation, and used arrays instead of maps

      → Reply