Grapevine
Download
IT Company Discussion
IT Company Discussion
on
GoofyCupcake
GoofyCupcake
Stealth

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.

6mo ago
3.4Kviews
Find out if you are being paid fairly.Download Grapevine
JazzyNarwhal
JazzyNarwhal
Stealth6mo

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?

JazzyNarwhal
JazzyNarwhal
Stealth6mo

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