Deutsche Bank || OA || FTE ||

Round 1

Questions: Q1: You are given a String and Integer N and K where N is the Length of the String. Find the total number of k-periodic Subsequences of the given String S. If s1 is a k-periodic Subsequence then for all i from 1 to (|t|-k) s1[i] == s[i+k] where |t| is the length of the string t.

Q2: String S1 of length L1 consisting of uppercase alphabets only. String S2 of length L2 consisting of characters 'T' and 'F' only. Generate a lexicographically smallest string S of length (L1 + L2 - 1) such that a substring of length L1 in string S starting at index (0 <= i < L2) is equal to S1 if and only if ith element of S2 is 'T'. If generating a string is not possible return -1.

Example 1: Input: S1 = "ABCA" S2 = "TFFF"

Output: "ABCAAAA"

Explanation: S="ABCAAAA" is lexicographically smallest string that satisfies the given condition:

• Character at index 0 of S2 = 'T' and Substring starting at index 0: "ABCA" is equal to S1.
• Character at index 1 of S2 = 'F'.
• Character at index 2 of S2 = 'F'.
• Character at index 3 of S2 = 'F'.

Example 2: Input: S1 = "ABA" S2 = "TFT" Output: "ABABA"

Example 3: Input: S1 = "ABC" S2 = "TFT" Output: -1

Constraints: 1 <= L1 <= 10^4 1 <= L2 <= 100

Q3: You are given a tree of N nodes in which root Node is 1. For every node, the value of Node is given in the val array. You are given queries for every i in Query, you need to find the total number of pairs (u,v) such that GCD of all nodes between u and v (both inclusive) equals Queries[i] and where u is the ancestor of v.

Input: N is the number of Nodes K is the size of the Queries Next N values are given for values of respective nodes Next N-1 lines will be given edge between u and v Next K lines will be given queries

I don't remember the Test Cases.