MR_MECHANICAL's blog

By MR_MECHANICAL, history, 4 years ago, In English

Hi All, I am new to Competitive Programming and today I attended an online interview in a company, I got two questions. but I did not solve even one of them completely. I was missing logic in both the question.

Q1. given an array of length N(always even length ) need to split this array into two N/2 subarrays (there are multiple orders we can split). for all the combinations of sub-array find the XOR value and print min and max value.

Eg: give array arr=[1,2,3,4] possible sub array splitting

(1,2) (3,4) finding xor for it (1^2) + (3^4) = 3+7 =10

(1,3) (2,4) finding xor for it (1^3) + (2^4) = 2+6 =8

(1,4) (2,3) finding xor for it (1^4) + (2^3) = 5+1 =6

Output: 6(min Val) , 10 (max Val)

Doubt: I don't even know how can I split it. if the array is of size 10 need to split subarray of size 5.

Q2. given two array, array1 has words and array2 has words with some char marked as "?", need to compare all the word in arry2 with array1 and output number of words in array2 matching array1. while comparing the position of the word in array1 and array2 also should need to be the same if "?" in a place means we can consider it as same char as arry1. Note: all the words are of the same length and of the smaller case only

Eg: array1 =["cat", "cap" , "map","man"] , array2=["c??","??p" ,"ma?"]

the word in array1 that matches are,

"c??" -> cat ,cap

"??p" -> cap, map

"ma?" -> map , man

Output: "c??" = 2 match

"??p" = 2 match

    "ma?" = 2 match

Note: Both the character and the position should need to be the same to get a match.

Doubt: I used trivial for a loop-based approach. it said Time limit exceed. don't know which algorithm to use to compare then quickly.

Please Help!!!!!

Full text and comments »

  • Vote: I like it
  • -22
  • Vote: I do not like it