Category Archives: Algorithm

Sudoku Solver

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.

250px-Sudoku-by-L2G-20050714.svg

A sudoku puzzle…

250px-Sudoku-by-L2G-20050714_solution.svg

…and its solution numbers marked in red.

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Q: What is the unknown?

A: A program that solves Sudoku.

Q: What are the data?

A: A Sudoku puzzle. Actually a 9 x 9 character matrix, with partially filled cells. Empty cells are represented as ‘.’

Q: Any constraints?

A: None except for the Sudoku rules:

  • Each row must have the numbers 1-9 occuring just once.
  • Each column must have the numbers 1-9 occuring just once.
  • Each block (check the link above for details about block) must have the numbers 1-9 occuring just once.

Q: Have you played Sudoku before?

A: Not even once. I guess this is my first and last attempt to play Sudoku. Based on the rules, I guess I have an idea for solve it. Just like the N-queens problem we solved last time, we will probably need backtracking: At an empty cell, I try to find a suitable number from a set of candidates to put it there and then move on to the next empty cell. If one does not work out, I find the next suitable number. If none of the candidates works out, then the number I placed at the previous empty cell was a bad choice and I need to go back to deal with it. This seems like a pattern that requires backtracking.

Q: Good, now to work with backtracking, are there anything you need?

A: Yes, I believe we need something to keep track of whether I could place a number in an empty cell or not, and a set of candidates for each empty cell.

Q: How do you know if you can place a number in an empty cell or not?

A: Hmm I have to check the row, column and block it resides in to see if that number already exists. The empty cells on the same row will share the info of this row. The same applies to columns and blocks. So we need three 9 x 9 boolean matrix: rowStatus, colStatus and blockStatus. Initially all values are set to false. If a number n is placed at cell (i, j), then we go and update rowStatus[i][n-1] = true, colStatus[j][n-1]=true, and blockStatus[getBlockInd(i,j)][n-1]=true.

Q: Good. Now what about the candidates for each empty cells you mentioned? It seems like you need to keep a lot of numbers at hand.

A: Hmm not necessarily. For each cell, there are only 9 options at most. I could try all of them every time but that seems a bit brutal. I could keep track of a number called startInd to save the index of the last number I tried at a certain cell. Next time I need another number at this cell, just get the number at the next index. If the next index is out of bound, that means none is a good fit. In that case, we set the  startInd of this cell to 0 and go backtracking to the previous cell.

Q: Sounds good. Now can you write some pseudo-code?

A: Sure.

// Initialization
// scan through the board and keep track of all the empty cells
emptyCells = getEmptyCells(board);
// update the status based on the initial board
updateStatus(rowStatus, colStatus, blockStatus, board);

int i = 0; // the index of an empty cell we are dealing with
while(true){
    Cell cell = emptyCells.get(i);
    int row = cell.row;
    int col = cell.col;
    char num = getSuitableNum(row, col, rowStatus, colStatus, blockStatus);
    if(num == '.'){ // no suitable num, previous bad choice
        if(isOutofBound(--i, emptyCells.size())) return;
        Cell previousCell = emptyCells.get(i);
        row = previousCell.row;
        col = previousCell.col;
        char previousVal = board[row][col];
        board[row][col]='.';
        undoStatusChange(rowStatus, colStatus, blockStatus, row, col, previousVal);
    }else{
        board[row][col] = num;
        updateStatusChange(rowStatus, colStatus, blockStatus, row, col, num);
        if(isOutofBound(++i, emptyCells.size())) return;
    }
}

// for details of utility functions like undoStatusChange, isOutofBound, and getSuitableNum, please check the real Java code at the bottom link.

Q: I see you are passing the rowStatus, colStatus and blockStatus around a lot. Is there anyway that we can organize them in a better way?

A: Hmm maybe I should put them all in one Class so I could just pass in one object instead.

Q: Sounds good, now let’s solve this with real code.

A: OK 🙂

Code on github:

 

 

Enhanced by Zemanta

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

8-queens

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

A follow-up question: Now, instead outputting board configurations, return the total number of distinct solutions.

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Well, this is a classic problem, isn’t it? However, all I know is that it’s classic and I’ve never really read about any article of NQueens, except for the title NQueens. So lucky for me, I got the chance to solve it with no prior knowledge.

Q: What is the unknown?

A: All possible board configurations that satisfy the requirements.

Q: What are the data?

A: An N x N chess board (or just an N x N matrix).

Q: What are the constraints?

A: No two queens on the board can attack each other. In other words, no two queens can be on the same row, column or cross.

Q: Good. Since you’ve never seen this question before, what’s your initial thought about this question? Anything’s fine.

A: I don’t have anything fancy, but possibly a naive way of solving it: for example, I could put a Queen in an available cell (no other Queens can attack) on the chess board. Then cross out all other cells this Queen can attack. Then on the second row, I place another Queen in an available cell and then cross out cells she can attack. On the next row I do the same thing until we place all N Queens on the chess board.

Q: What if on a certain row, there is nowhere you can place a new Queen?

A:  Hmm, that means the placement of the Queen on the previous row was a bad move.

Q: So what should you do about it?

A: Well, undo it then. Undo the cross out of board cells caused by that bad move. Get the queen up and place it somewhere else on that row, if there are any available cells left.

Q: What if there are no available cells neither?

A: Hmm, then the bad move’s previous move was bad. We have to do the same thing for it as above.

Q: Good. Now, can you summarize your thought and maybe find out the pattern in it?

A: I place a Queen in an available cell on a row, and cross out cells she can attack. Then on the next row, again I place a Queen in an available cell and cross out cells she can attack. If I cannot place any Queen, that means the previous move was bad and we undo that move and its cross-out, then place that Queen in another available cell. If that’s not possible, then the previous previous move was bad and we should….  OK I get it. This has something to do with recursion, doesn’t it? And in fact, even if we find a solution, we still need to undo previous move and its cross-out since we are looking for all possible solutions, not just one. Other moves may also lead to solutions. 

Q: Good catch. Now can you think of an abstract version of your thoughts? Possibly some pseudo code?

A: OK. So if we are dealing with recursion, we should always think about base case and recursive case. The base case should be that N queens are all on the board. Maybe we should keep track of how many Queens on the board? Or on the second thought, maybe not. Based on my thoughts above, since we are moving to the next row if and only if we can place a Queen on the current row, a solution is found if we are on row N (row index from 0 to N-1). This is the time we stop recursion and return the current board configuration.

// suppose we call this function solveNQueens

// base case
if (rowInd == N) {
    SaveTheBoard(board);
    return;
}

OK, moving on to the recursive case. I don’t want to repeat myself again so let’s look at some pseudo codes.

// since we want all possible solution, we should check all possible cells. Therefore we use the loop. Say we are on row K.
for(int i = 0; i < N; i++){
    if (isAvailable(board[K][i])){
        placeTheQueen(board, K, i);
        crossOutCells(board, K, i);
        solveNQueens(board, K + 1, N);
        undoPlaceAndCrossOut(board, K, N); // always undo
    }
}

Q: Good. Just one question before we move on to real code. How do you plan to do the cross out and undoCrossOut?

A: Oh I could create a boolean matrix[N][N] and if a cell is crossed out, set the corresponding cell to true. In undoCrossOut just set it to false.

Q: Hmm, not quite. Think about this: A cell C2 on the second row is set to true (crossed out by a Queen on the first row). You place a Queen on the second row somewhere and C2 gets crossed out again (set to true). Later you find that your move on the second row isn’t ideal. You undo the move and C2 is set to false. That doesn’t seem right. Since it can be attacked by the Queen on the first row.

A: Hmm, then I guess I can use an integer matrix then. Every time a cell gets crossed out, we increase the value in the corresponding cell. As long as the value in a cell is greater than 0, it is not available.

Q: Sounds good. Now go on to do some real coding.

Code on github:

Now for the follow up question, it is actually simpler. We don’t even need the board. All we need is just a counter and we increase the counter only in the base case. But sure to return the counter. (The code below mentions a mistake I made about Integer type)

Enhanced by Zemanta

Path simplify

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Corner Cases:

  • Did you consider the case where path = "/../"?
    In this case, you should return "/".
  • Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
    In this case, you should ignore redundant slashes and return "/home/foo".

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

Well it’s not difficult, but there are something worth noting. The examples above should also tell us that the path may or may not end with ‘/’. So be sure to deal with cases like /abc/…

So when we are evaluating the path ourselves,  we do in the following way (e.g., ‘/a/./b/../../c/’)

  1. ‘a’ means /a
  2. ‘.’ means we stay on the current level, so still ‘/a’
  3. ‘b’ leads to ‘/a/b’
  4. ‘..’ means we have to go up, so we get ‘/a’ again
  5. ‘..’ the same as above, so we get ‘/’
  6. ‘c’ leads to ‘/c’
  7. There is no more, so we end with ‘/c’

I don’t know if you notice anything here but I was reading about data structures for a while and one thing that caught my eyes was the string ‘..’ and its effect on the final path. If the string between two ‘/’ are not empty string, ‘.’ or ‘..’, we are adding them to the end of the final path. If it is ‘..’, we are removing it from the path. Well this sounds like push and pop operation to me. That’s it. Nothing fancy.

We will scan through the input and look for the strings (I used a StringBuilder here and be sure to initialize a new one for the new string you are trying to find here, otherwise the former string is still in the builder and you will get bugs) between two ‘/’s and push/pop them to/from the stack based on their values. Once the scan is completed, we can move the items in the stack to an array and use a StringBuilder to create the final path.

Code on github:

Enhanced by Zemanta

Detect the first node of the cycle in a singly-linked list

If a singly-linked data structure contains a cycle, determine the first node that participates in the cycle. you may use only a constant number of pointers into the list (and no other variables). The running time of your algorithm should be linear in the number of nodes in the data structure. You are given the pointer to the first node of the list.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

This is the third time I encountered this question and once again, failed. Well I remembered how to write the code, but I couldn’t figure out the complete reasoning, which made the code kind of useless. Memorizing the code is never my intention but it seems that my brain disagrees…The following is a conversation:

Q: What is the unknown? What are the data? Any conditions or constraints?

A: The unknown is the where the cycle begins. The data is a pointer to the first node of the list. The constraints are that we can only use constant numbers of pointers and the running time should be linear.

Q: Have you seen a similar question before? If yes, can we use its result or method here?

A: Yes, a similar question is to detect if a cycle exists. Hmm, we used a fast runner and slow runner approach. I guess it’s a common strategy to use when dealing with cycles. So we can still consider using it here.

Q: Describe the approach above.

A: We have two pointers F and S, with S moving at rate 1 and F moving at rate 2.

Q: OK, can we introduce a symbol for our unknown? Quantify it?

A: Sure, suppose that node is k steps away from the first node of the list.

Q: Now suppose S moved k steps, where are F?

A: In that case, S is at that starting node of the cycle while F is k steps into the cycle because F moved 2k steps when S moved k steps.

Q: Relatively speaking, what’s the location of F according to S and vice-versa?

A: Then S is k steps behind F and F is CYCLE_SIZE – k steps behind S.

Q: What if k is bigger than CYCLE_SIZE?

A: Hmm, then we can replace k with K = k % CYCLE_SIZE. Whether k or K steps into the cycle points to the same node.

Q: Good, now rephrase the answer to the relative location question.

A: OK, S is K steps behind F and F is CYCLE_SIZE – K steps behind S.

Q: If F and S keep moving, they will meet somewhere in the cycle. When and where will they meet?

A: Aha, suddenly it looks like a junior high physics question…F will catch up S at a rate of 1. So after CYCLE_SIZE – K unit times, they will meet. Since at the beginning S is at entrance of the cycle, after CYCLE_SIZE – K time, S is CYCLE_SIZE – K steps into the cycle. Hmm so when F and S meet, they are simply K steps behind the entrance of the cycle.

Q: Great. Now who else is K steps behind the entrance of the cycle besides F and S?

A: Eh, no one?

Q: OK look at our data. Did we use all the data?

A: Eh the data is the first node of the list. Hmm, but it’s k steps from the cycle…

Q: What’s the relationship between k and K?

A: Oh right, K = k % CYCLE_SIZE. In the cycle, K and k are interchangeable. So F, S and the first node of the list are all k steps behind the cycle! If now we start from the first node of the list with a pointer T and keep move, the place where S and T meet is our answer!

Q: You got it.

Summary: 

  • Locate the unknown. Symbolize and quantify it!
  • When dealing with loops or cycles, think about multiple pointers with different moving rates.
  • In this catch and run problem, ask both when and where.
  • In a cycle, K (= k % CYCLE_SIZE) and k steps into the cycle point to the same node.
  • To find a location, imagine how you get there and when you get there, what are other things like? (when S is at the entrance of the cycle, where is F?)

Code on github:

Enhanced by Zemanta

Best Time to Buy and Sell Stock I

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

Well in fact there are 3 questions in the series. I was actually working on the 3rd one because the OJ randomly picked it for me. I couldn’t figure it out but it helped me solving this one. Two thing worth mentioning:

  • if you buy high sell low, your profit is 0, not negative (well that’s what the test result told me and you should ask this first in reality).
  • You are not really making transactions until you figure out where to buy in and sell out to maximize the profit.

So suppose you can predict the future and have the price array in hand:

[5, 4, 1, 2, 8, 6, 9]

In this case you should buy in at price 1 and sell out at 9. It looks like a simple question looking for just min and max value. However, consider the following:

[5, 4, 9, 2, 8, 6, 1]

Well in this case, you should buy in at price 2 but sell out at 8, but the min is still 1 and max is still 9. So be careful.

The simplest way would be using 2 loops and find out the max profit of you buying at each price. But that would take O(n^2) time. So can we do better than that?

From here I have two ways of thinking: one that is a bit more logical that following the above question (but I figured it out after I solved the problem) and the other that is a bit jumpy (but that was how I solved the problem in the first place).

================================================================

The first way:

Well what is taking so long is that we are going two passes, what if we could just use one pass? We scan the array and keep updating the max profit along the way? How can we do that? Well surely we need something to keep track of the max profit. Do we need something else? I’m stuck here. And when you are stuck, try a simple example:

[5, 4, 1, 2, 8, 6, 9]

Suppose we are scanning and at price 8. And this moment, what is the max profit we can get? It’s 7. How do we get it? We buy in at price 1 and sell at 8.  But wait, right now we only keep track of the max profit. We don’t know where we are planning to buy (well I know, and you know, in the brain, but the computer doesn’t since nothing is keeping track of it). So, it looks like we should keep track of two things:

  • Based on what we have scanned, the price we are going to buy in (the current minimum).
  • Based on what we have scanned, the current maximum profit we can make.

How to update?

  • If the current price is lower than the current min, we can’t make any profit, so we keep the current max profit but update the current min price (and hope this new min can give us a higher profit later. Sadly we can’t go back in the opposite direction. See the first two examples).
  • If the current price is higher than the current min, then we can make a profit: If the new profit is higher, we update the current max profit but keep the same min price. Otherwise, we do no update on both variables.

I believe this is an O(n) time algorithm since we are doing one scan and nothing more.

================================================================

The second way:

Well this one is a bit jumpy. I have been reading about recursion lately. So I thought why not try solving it with recursion? So use recursion, we need to identify a similar problem with a smaller size. For example, to find the max profit of [5, 4, 1, 2, 8, 6, 9], is to find the max profit of [4, 1, 2, 8, 6, 9] and then do something with 5. But what exactly? Well, our goal is to get the max profit. Is it possible that we could update the max profit with 5? That depends. If the difference between 5 and the maximum of [4, 1, 2, 8, 6, 9] is greater than the older max profit, we update. Otherwise we don’t. This indicate that we need to keep track of the max profit and the maximum price at the same time. Unfortunately, Java cannot return multiple values but we can wrap them in an object, or wrap one of them in an Integer object. This algorithm works, until it hit a big input and reported a stackoverflow error. We will fix it later.

We can also think of another way: a similar problem but in the opposite direction. We look at [5, 4, 1, 2, 8, 6] and 9. We get the max profit of the latter and do something with 9. Whether to update the max profit depends on the difference between 9 and the previous low price we are supposed to buy in. This algorithm works, and it has a nice tail recursion form, until it hit a big input with stackoverflow error.

Usually when this happens, we could think about converting the recursion to iterative form, especially if we have tail recursions:

  • If our recursion is not tail recursion, try making it tail recursion. One tip I find useful is to look at similar problem with smaller size in the opposite direction, like the example above. And the recursion function should take the returning value as an argument along with whatever we are keeping track of. Then return the result in the base case. It’s a bit vague here so see the code for clarification.  I got this though from the Scala course on Coursera. Maybe it helped. Well correlation doesn’t mean causation.
  • Once we have the tail recursion, we change it to iterative form by using our own Stack. We may need more than one stack, depending on how many variables we are keeping track of, in our case, two–one for max profit and the other for the low price to buy in. Put the body of the recursion in a while loop. At the beginning of the loop, pop out values from the Stack. For those tail recursion calls, we can just push the values of the arguments we are passing back to the stack. Again, check the code.

This actually ends up with the same iterative algorithm in the first approach. It has been a very interesting experience. I learned a lot in the second approach but it took longer. However, if I started with the first approach in the first place, would I be able to figure out the solution?

Summary:

  • Always keep recursion in your toolkit and think about smaller problems in both directions.
  • You can convert tail recursion into iterative algorithm.
  • Start with brutal-force and think about where and how we can improve (the running time of each procedure and which one can be faster?). By think, I mean really put ourselves in the situation and walk through (like “if we can solve it in one pass, what would it be like? To realize it, what do we need? Can we get it somehow?”).

Code on github:

Enhanced by Zemanta

Search in 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

Well I guess anyone knows binary search can think of a straightforward solution: just think of this matrix as a long array with m*n elements and apply binary search on it. So it takes O(logmn) = O(logm) + O(logn) But we should probably ask: is m*n still in the range of Integer in Java? If true, good. Go ahead.

If not, and if m and n are in the range of Integer in Java, we could do it in another way: use two passes of binary search, one to locate the possible row that the target could reside in, and the other to search the target on that row. But this one is a bit tricky and be sure to check boundary cases.

Code on github:

Enhanced by Zemanta

Subsets I

Given a set of distinct integers, S, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

A good start point is to compare the Subsets of [1, 2, 3] with the Subsets of [2, 3] ([], [2], [3], [2, 3]). You will find that while retaining all elements in the latter, the former has additional elements which add the integer 1 to each element in the latter. So this may suggest a recursive algorithm:

Subsets(1,2,3,…,N) = Subsets(1,2,3,…,N-1) + adding N to each element of Subsets(1,2,3,…,N-1)

But there is no guarantee that the array is sorted. So be sure to sort it to ascending order first.

Code on github:

The only thing I’m concerned about is the running time. It seems like the algorithm is an exponential one? Or it should be exponential anyway?

Enhanced by Zemanta