INFOSYS OA : Hardcore
Summary
I attempted Infosys's online assessment which contained three problems; I solved the easy one but got TLE on the hard DP/matrix exponentiation problem and did not pass the assessment.
Full Experience
So there were three problems which can be simply ranked as
- Easy
- Insane Hard DP (almost impossible to solve without TLE if you haven't seen anything like that before). TLEd(5/12)
- Hard DP
So the main topic of discussion here is Q2, Q3 can be worked out, but Q2 idk N <= 1e5(Focus on this) Count number of sequences possible to place A, B, C where an accepted sequence is where the cost % 4 = 0 For placing A cost is 1, for placing B = 0, C = 0 But if cost % 4 == 3 , then C cannot be placed no matter what
Now this is simply DP, many problems are available on LC or codeforces itself of this type, but now lets see how did they screw up the whole thing, N wasn't upto 1e5 i am sure of it, it had to be greater than 1e6 , because i did precompute upto 1e6, still had TLE. So now , the problem setter had testcases going upto 1e8 or even higher, and for that this problem required Matrix Exponentiation(obviously i didn't knew it so i got it 5/12 only). This is idk what kind of question is this, wrong constraint, and if someone deduces wrong constraints, then the topic is Matrix Exponentiation, infact i haven't seen less than 1900 rated matrix exponentiation question on codeofrces. Dissapointed with this.
Interview Questions (1)
Count sequences with modulo 4 cost constraint
Given an integer N (potentially up to 1e8), count the number of sequences of length N formed using the characters A, B, and C. The cost of the sequence is defined as the sum of individual character costs: A contributes 1, B contributes 0, and C contributes 0. A sequence is accepted if the total cost modulo 4 equals 0. Additionally, if at any point the running cost modulo 4 becomes 3, the character C cannot be placed in the remaining positions. Compute the total number of accepted sequences modulo a suitable large prime (if required).