Sudoku solver

April 2, 2018

Introduction

It is such great experience to work on Sudoku solver in mock interview. I wrote the algorithm in less than 30 minutes.

Code review

Here is my analysis with C# code.

Being interviewer: Sudoku solver

March 25, 2018

Introduction

It is such great experience to work with a software engineer from Israel 10:00 am mock interview.  The peer also told me that she works for one of top four software company in the world. She worked on Sudoku solver.

As an interviewer, I like to write down some highlights for my code review.

Code review

Here is the solution I reviewed. First of all, the peer wrote down the analysis very clearly and asked me if I followed her idea after she wrote some of the code from line 21 to 44. After she wrote the solution to call recursive for next iteration, she asked me the feedback.

Highlights of my code review:

1. line 25 to line 26, I added those two lines. I explained that there is a bug to find next position of '.' char. Line 23, I changed column = j to column = 0, and add line 25 and line 26 to start from (i, j).

2. line 56, I explained to the peer that no need to check, HashSet.Remove can handle the case if the char is not in hashset.

3. line 88 to 91, I explained to the peer why backtracking is necessary. Her argument is that next iteration the element will be replaced by the available number. And then I gave her the example, first row with first two elements 5 and 3, and 3 empty space with '.', if we work on the third '.' and try the last available number but fails, we need to put '.' back and then continue to work on second '.'. Recover the original status.

Using graph like the following:
5 3 _  _   _
              _ fail ->'.', work on third dot, (0, 4)
          next iteration to work on second '.'

4. work on nextRow and nextCol calculation. Originally the peer wrote (emptyRow + 1)% n, (emptyColumn + 1) %m,

Actionable Items

It is very good to work with the peer on this algorithm. Today is Sunday. I choose to stay at home and work on mock interview. Yesterday I spent over 90 minutes to work with a peer on budget cap calculation. Later I talked to my roommate Emma, she told me that I have to think for other people. If I meet  a strong player on algorithm and data structure, I will talk over 90 minutes. Think about the other way, same applies to the peer I met as well.

Emma is a very good IELTS teacher, and she told me to work on cleaning the living room table together. What I did is to learn and stay organized. We both laughed about the shopping I did in Seattle, and I did make a mistake to purchase too many Nike shoes for myself. I bought 3 pairs of Nike shoes, one pair I wore two days, it broke my skin near my ankle. I went to Seattle with my friend from Shanghai, she laughed about me how I can wear 3 pairs of sneakers. It turned out not cheap for 3 pairs of shoes, $150 Canadian dollars.

Leetcode 37: Sudoku Solver

July 19, 2015

Problem statement:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

Solution 1: 

Great blog to read:

http://blog.csdn.net/fightforyourdream/article/details/16916985

And then, start to implement the solution using C# code:

https://github.com/jianminchen/sudokuSolver/blob/master/Program.cs

Solution 2: 

Read the blog,
http://blog.csdn.net/linhuanmars/article/details/20748761

and then, implement the solution using c# code:

https://github.com/jianminchen/sudokuSolver/blob/master/Program2.cs

Solution 3: (good workout on C# KeyValuePair class)

and then, convert C++ code to C# code from the blog:
https://github.com/yinlinglin/LeetCode/blob/master/SudokuSolver.h

Excellent code in C++, using class for node on the board. Learn a few things, fun to play with the code

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program3.cs

solution 4:
https://github.com/jianminchen/sudokuSolver/blob/master/Program4.cs
source code from the blog:
https://github.com/xiaoxq/leetcode-cpp/blob/master/src/SudokuSolver.cpp

Solution 5:
read the blog: (Good coding! practice more based on this blog)
https://github.com/zwxxx/LeetCode/blob/master/Sudoku_Solver.cpp

and convert the C++ code to C# code, (great workout on C# LinkedList for blank nodes)

https://github.com/jianminchen/sudokuSolver/blob/master/Program5.cs

Solution 6:
read the blog:
http://shanjiaxin.blogspot.ca/2014/04/sudoku-solver-leetcode.html

and convert Java code to C# code, great workout on C# and logic checking "return false"

https://github.com/jianminchen/sudokuSolver/blob/master/Program6.cs

Solution 7:
blog:
http://www.jiuzhang.com/solutions/sudoku-solver/
C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program7.cs

Solution 8:
Thanks for the blog's highlight line of code on back tracking; finally, I got it! My logic thinking has flaws on back tracking; extra backtracking is not a good. Minimize the back tracking, only do it when "return false". It makes sense to do that.

blog:
http://bangbingsyb.blogspot.ca/2014/11/leetcode-valid-sudoku-sudoku-solver.html
C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program8.cs

Solution 9:
blog:
http://www.cnblogs.com/TenosDoIt/p/3800485.html

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program9.cs

Solution 10:
blog: (Excellent implementation! no extra line or number in the code! Best for memorization! Go through other solutions later. )
https://github.com/rffffffff007/leetcode/blob/master/Sudoku%20Solver.java

C# code:
https://github.com/jianminchen/sudokuSolver/blob/master/Program10.cs

算法理解了, 代码可以记住了; 开始看不同的题解, 看看高手的代码; 从不同的题解中, 模仿模仿! 像打网球, 多接触不同的打法, 开阔眼界; 接着看这道题的题解. 试着从不同角度看一个问题, 多练习改代码; 看自己能不能有自己的看法, 去尝试一点更改, 玩一点花样; 增加练习C#编程的机会.

Also, the code written has been work on readability, learned through my favorite book reading:
http://shop.oreilly.com/product/9780596802301.do

Those favorite rules I like to learn, pick up and follow:
Big fan of DRY (Do not repeat yourself) principle, do one thing a time, break giant expression, using explaining variable or summary variable, and abstract the thing to a function, extract a subproblem to a function. The code is also modified to fit into short memory, less mental baggage to read through. 



Read solutions:

https://github.com/jordandong/myleetcodes/blob/master/SudokuSolver.cpp

https://github.com/Sayericplz/myleetcode/blob/master/isValidSudoku.cpp


BFS, using queue - try to convert it to C#
http://yucoding.blogspot.ca/2013/12/leetcode-question-sudoku-solver.html