FastPrep
Problem · Tree

Find Palindromes

Learn this problem
● HardGoogleOA
See Google hiring insights

Problem statement

You are given a tree T with N nodes and the tree rooted at node 1. Every node has a character C[i] assigned to it. You are given Q queries of the following format:

Query: u

You must find whether string S that is generated for node u is palindromic or not. String S for a node u is generated as follows:

S = Empty
makeString(u)
{
For all v = Child of u
makeString(v)

S += C[u];
}

Children of u should be traversed in order of increasing node number.

Input format

  • The first line contains an integer N.
  • Next N — 1 lines contain two space-separated integers u and v denoting an edge between node u and node v.
  • The next line contains N space-separated characters denoting C[i] for all i from 1 to N.
  • The next line contains an integer Q.
  • Next Q lines contain an integer u denoting the node for the query.

    • Return Value

    Return an integer array of length Q. For each query, return 1 if its generated string S is palindromic; otherwise, return 0.

    Note: Use fast I/O

    Function

    isPalindrome(n: int, edges: int[][], c: char[], queries: int[]) → int[]

    Examples

    Example 1

    n = 5edges = [[1, 2], [1, 3], [2, 4], [2, 5]]c = ["a","b","a","b","c"]queries = [1, 2]return = [0, 1]

    For node 1, S = "bcbaa"
    For node 2, S = "bcb"

    Constraints

    1 ≤ N, Q ≤ 200000
    |C[i]| contains lowercase Latin Letters.

    More Google problems

    drafts saved locally
    public int[] isPalindrome(int n, int[][] edges, char[] c, int[] queries) {
  // write your code here
}
    n5
    edges[[1, 2], [1, 3], [2, 4], [2, 5]]
    c["a","b","a","b","c"]
    queries[1, 2]
    expected[0, 1]
    checking account