vishudon's blog

By vishudon, history, 5 months ago, Hi,

Yesterday, I had a technical interview round with Amazon Team. In this round, I asked to solve one famous DP problem with some modifications.

Problem Statement: Given three strings S, x, and y. You have to return interweaving positions of x and y in S with noise symbol positions (which are not part of x and y). Output format will be like this: [S1, S2, S3] where S1 = interweaving positions of string x in S, S2 = interweaving positions of string y in S, S3 = remaining characters (which is noise) positions.

We say that a string S is an interweaving of x and y if its symbols can be partitioned into two (not necessarily contiguous) subsequence s' and s'' so that s' is a repetition of x and s'' is a repetition of y. There might be some noise in S as well.

Look at the test cases for better understandings:

Test Case 1: Input: S = "101010101010101", x = "101", y = "010".
Output: Here, S is an interweaving of x and y, [101|010|101|010|101].
So, we need to return [{1,2,3|7,8,9|13,14,15}, {4,5,6|10,11,12}, {}]. Here 3rd set S3 is empty because there is no noise in S.

Test Case 2: Input: S = "000000010101010101010111", x = "101", y = "010".
Output: Here, also, S is an interweaving of x and y, ignoring leading noise and trailing noise [000000|010|101|010|101|010|111].
So, we need to return [{10,11,12|16,17,18}, {7,8,9|13,14,15|19,20,21}, {1,2,3,4,5,6,22,23,24}]

Test Case 3: Input: S = "100110011001", x = "101", y = "010".
Output: Here, also, S is an interweaving of x and y, [{1,2,4 | 9,11,12}, {3,5,6 | 7,8,10}, {}]

Note: You can ignore | symbol if you want. I couldn't come out with a solution. I know that simple DP problem which contains only x and y in S (without any noise, and |x|+|y| = |S|), but couldn't solve this problem.

Anyone can suggest a solution for the same ? Any help will be appreciated. Thanks in advance. By vishudon, history, 6 months ago, Hello,

I am solving below problem, and I wrote a solution for the same. I can't understand on which test case or why/where it is giving runtime error. I tried very hard to debug this, but could not understand. I checked other's accepted solution for getting a test case on which my solution could fail, but still couldn't get such test case. Can someone please help me with this ? Any help will be appreciated. Thanks in advance.

My solution: https://codeforces.com/contest/1551/submission/124854239 ( giving run time error on test case #2 )

Note: Also, please don't downvote if you can't help, I really tried very hard to debug my code.

UPD: I caught the issue, it is inside my comparator function. Never mind. Thanks By vishudon, history, 6 months ago, Hello,

I am solving below problem and I have already solved this problem using DFS, but then I tried to solve it using BFS too. I know that below problem can be solved using both BFS and DFS.

I have written a solution using BFS, but my solution is failing at #19 test case (not complete visible test case). I tried hard to debug my code, but can't understand where is the problem in my code. I checked many BFS solutions for this problem, but none of the solution could help me resolving issue in my code. Can someone please help me with this ? Any help will be appreciated. Thanks in advance.

My Solution Link: https://codeforces.com/contest/510/submission/124016916 ( This solution is failing at #19 test case) By vishudon, history, 11 months ago, Dear community,

I hope you all are doing good and safe. I just want to know one thing. Recently I had a interview and the interviewer asked one question, how to solve inversion count problem.

I suggested two approaches to him (1. brute force, and 2. using merge sort). He was completely satisfied by my both the approaches.

But at last, he asked one question to me. Can we solve inversion count problem in O(n+k) where n <= k <= (n*n) ?

I couldn't suggest such approach to him. Also, my bad luck, I couldn't ask him about such approach. But, I am just curious to know is this really possible ? Can someone suggest some approach which could solve inversion count problem in O(n+k) where n <= k <= (n*n) ?

Thanks. By vishudon, history, 16 months ago, I was trying to solve a problem, but I encountered a weird error. I don't know why my code is giving me wrong output. Can someone help me what is wrong in my code ? Thanks in advance.

Code

If I am giving this input :

1 2
abc
cdf
edf

then my code is giving me this output : len1 = 2 , len2 = 2 ( while len1 must be 1 )

Note : If I am removing that common string checking part — these two lines ( line1 and line2 ) from 2nd for loop, then it is giving me correct output as len1 = 1 , len2 = 2 By vishudon, history, 22 months ago, 