I assume your input is actually 3 3 (3x3 matrix) 2 1 0 (3 rows) 1 2 0 (3 cols)
or 3 2 (3x2 matrix) 2 1 0 (3 rows) 1 2 (2 cols) The answer will be XXO OXO OOO or XX OX OO In order to have a valid solution, 1. you need to first check if the sum of rows and sum of cols are equal. If not, there is no doubt that such matrix wouldn't exist 2. For each number X in rows, check if there are at least X cols that is still non-zero, if not, there is no valid matrix; if yes, subtract 1 from the X highest cols. 3. repeat step 2 until all cols goes to 0 > There is a coding problem where we are given some inputs and we have to tell > if a matrix can be made or not. > we are given the size of the matrix. Then the second line of the input, > signifies the row of the matrix. It some numbers. And the third line > signifies column. > > Example: 3 3 (size of matrix) > 2 1 0 (rows of the matrix) > 1 2 (column of the matrix) > > > > In the second line, 2 implies that the two elements of the first row has to > be filled with X while others will be zero. 1 says that only one element of > the second row will be populated with X and similarly, 0 means the third row > has no X populated. > > Similarly, in 3rd line, 1 refers to that only 1 element in the first column > should be filled with X. and 2 says that two elements in the second column > are filled with X. > > > So if we follow this, we wont have any combination that will satisfy our > matrix. > > Any idea how can I implement such an algorithm that will check if the matrix > is possible or not. When I am creating examples, I feel that there is a > pattern in the input that i am missing. So it will be great if anyone can > suggest me if i am missing anything. > > Thanks in advance. > > I was asked this question in an amazon interview. I am really confused how > much more do I need to practise. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/8c8d81bf-5db5-4a8e-bad1-47da0a3f9d89%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
