Gave a hackerrank test for Lytx
I received a call and a subsequent HRank test for this company Lytx. There was a DSA problem where: For a given MxN matrix containing only 1s or 0s, we had to identify the minimum number of left or right cyclical shifts required on the row for getting at least 1 column with all ones. Sample Input: ['1001,'0101,'0000'] I used chat gpt and still couldn't figure out an exact solution, leave aside solving it on my own. Question for the community: Say they select me for a further round anyways, will the interview as well be this brutal in terms of DSA ? Are these companies expecting programming prodigies or am I just not there in terms of my problem solving journey ? Hoping for some brutally honest responses.
I'm curious about the question
So basically the question is
Output = Sum of Shifts require in every row, right?
For instance in your example the answer is -1? Because last row has zero 1s? So it's not possible at all
But in this example
Input: ['1001', '0101', '0010']
The answer is 1 as I can move last row on the right and get the last column with all 1s
2nd example
Input: ['1000', '0001', '0010']
The output = 2 (shifting first row once the left & last row once on the right - 1 + 1 = 2)
i.e ['0001', '0001', '0001']
Is my understanding correct?
If yes, here's my approach (ik it's unrelated to your query, but just in case you are curious about it)
- For each row, I'll calculate the minimum shift I need for each position.
- How to calculate this?
For positions which are already 1, the ans is zero. And for zeroes, I'll just first traverse from left to right, then right to left, and pick the minimum of them
Time: O(n*m)
- To handle cyclical stuff in the previous step I'll just concatenate the array thrice & then do the previous step, but will only be in interested in the middle array.
- Then for each column, I have already calculated the minimum steps needed for each row. So again I'll create a new array with the size of column. And for each column I'll sum the values for each row.
Time: O(n*m)
- I'll return the minimum value of the array
Time: O(m)
Space : O(n*m) [for storing the minimum moves] actually this can be improved to O(n) as I will just store the current traversal in this array and before moving to the next row, I'll update the matrix
Discover More
Curated from across
