Hi all! Today I gave the google coding challenge for interns, and I recieved the following two questions.
Question 1
There are N words in a dictionary such that each word is of fixed length M, and consists of only lower case english alphabets. A query word Q also has length M. Query word also contains only lower case english alphabets but at some places instead of an alphabet it has "?". match_count of Q, is the count of words in the dictionary (already populated with words of same length M) and contains the same english letters (excluding the letter that can be in the position of ?) in the same position as the letters are there in the query word Q. Your are given the query word Q and you have to find the match_count.

Input Format

• First line contains two space seperated integers N and M denoting the number of words in the dictionary and the length of each word
• Next N line contains the words in the dictionary
• Next line Q contains the number of query words
• Next Q lines contain one query word each

Output
For each query word output the match_count

Constrains
1<=N<=5x10^4
1<=M<=7
1<=Q<=10^5
Time Limit: 1 second

Sample Input:

cat
map
bat
man
pen
4
?at
ma?
?a?
??n

Sample Output

2
2
4
2

Solution:
We can build a trie from the words given in the dictionary and the nodes in the trie can be used to get the match_count. I had seen a similar DS design question in one of the montly leetcode challenge

Question 2
You are given a list S which initially contains 0. You must perform Q queries of the following type:

• 0 X: insert X in to the list
• 1 X: For every element A in S, replace A with A XOR X

After performing Q queries return the resulting array in a sorted manner

Constraints:
1<=T<=100
1<=Q<=10^6
0<=X<=10^9
Time Limit: 1 second

Sample Input

1
5
0 4
0 2
1 4
0 5
1 8

Sample Output
8 12 13 14

Soultion: I did the naive approach for query of type 0 I just appended the number to the list and for the query of type 1 I loop over the entire array and XOR each array element with the current query element. I was only able to solve this question partially as for last 5 test cases my solution was exceeding the time limit.

Could anyone help me with a more optimised approach for this problem?