Implement a Sudoko puzzle validator - given a 9x9 matrix of numbers (1-9) and "." for empty spaces, return true for a valid puzzle matrix and false if it would not be a valid sudoku puzzle.
I basically just checked for duplicate numbers in each row, column, and then each 3x3 inner matrix. each iteration, i reset a dictionary of "seen" numbers. "." characters wouldn't matter, if i saw a number 1-9 i would check if it was already in the dictionary, if it was return false. return true at the very end if never encountered repeat numbers in rows, columns, or inner squares. when I explained this approach to the interviewer and he seemed satisfied with it although it was not easy to tell what the hell he was thinking or saying. i was working in a shared text file (i think it was codepen?), and even though the interviewer could have typed too, he didn't (even when i had to ask him repeatedly to spell a word i couldn't make out)..
Each iteration? You need just an iteration. Complexity o(n).
my solution was still O(n) - 3n to be exact. i "iterate" over the entire matrix 3 times - once to check for duplicates in the rows, once to check for duplicates in the columns, and once to check for duplicates within sub matrices. During each of those iterations I visit each element of the matrix exactly once and just check whether it's already in a dictionary of seen numbers which would be a constant time operation, so this is in total would be O(n). I can't think of how to check all those in just one iteration , if that's what you were saying you could do. (at least without using O(n) extra space.. mine only uses constant extra space) i would appreciate if you could elaborate
Given a tree with potentially multiple child nodes, write an algorithm that describes how you would completely reverse (or mirror image) the tree. That is, given a tree with a root node of A and three children, BCD, and two children of B named EF, he wanted to generate a new tree that looked like a root node of A, then DCB with "FE" being the reversed children under B.
You are in a game of Russian Roulette with a revolver that has 3 bullets placed in three consecutive chambers. The cylinder of the gun will be spun once at the beginning of the game. Then, the gun will be passed between two players until it fires. Would you prefer to go first or second?
given a matrix where the numbers ascend both in rows & columns, e.g. 1 3 5 7 9 11 13 15 18 20 22 24 26 28 30 31 33 36 38 39 42 44 47 49 50 If you're asked to write a function that provides a boolean (YES or NO) answer to "does this number exist in this matrix", explain how you would design an algorithm to be most optimal.
See Interview Questions for Similar Jobs
- Software Engineer
- Senior Software Engineer
- Software Developer
- Software Development Engineer
- IOS Developer
- Android Developer
- Ios Software Engineer
- Software Engineer Intern
- Web Developer
- Mobile Developer
- Mobile Engineer
- Android Engineer
- Associate Software Engineer
- Java Developer
- Applications Developer
- Senior Software Developer