Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

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

Q: What is the unknown?
A: the indices of the two numbers in the array that add up to a target value.
Q: What are the data?
A: An array of integers and a target value.
Q: What are the constraints? Ambiguities?
A: The index is not zero-based. The example gives us a sorted array but it may not be sorted in other cases. There may be duplicates in the array.
Q: Have you seen this problem before?
A: Yes, but I want to redo this problem like a clean slate rather than memorize the solution to it.
Q: How do we approach it?
A: One possible solution would be for each element in the array, subtract it from the target value and check if the remained value is also in the array. But that would take O(n^2) time (and O(1) space).
Q: So can we do better? If we can, what is the bottleneck?
A: The bottleneck is that we have to scan through the whole array to see if a value exist. If we can speed up this lookup process, it would help to speed up the whole algorithm. Current lookup is O(n) and possible upgrades are O(logn) and O(1). Now what algorithm or data structure can achieve O(logn) and O(1) lookup? I would say BST and Hashtable. Since both data structure uses O(n) space, we will consider hashtable since it is faster in lookup.
Q: OK, so how does hashtable lookup fit in here?
A: Well, I think we need to scan through the array first and count the frequency of each value. Then in the second pass, we calculate the remained value by subtract the current value from the target and check if the remained value exists in the hashtable. If not, we move on to the next one. If yes, then we have found one (here be careful about duplicates and values like 4-2=2).
Q: Yes, we can do that, but the problem asks for the index of the two numbers, not the numbers themselves.
A: Ah yes, we can use another hashtable to keep track of the indices of each value or we can scan through the array to find the index of these two values. The first way require extra O(n) space while the second way requires an extra pass of O(n) time.

Q: OK, one question: is it possible that an number overflow happens in your algorithm? If yes, how do you solve it?
A: Suppose that our target value is Integer.MIN_VALUE + 1 and our array is [3, -1, Integer.MIN_VALUE + 2]. In this case, if we subtract 3 from our target value, we will get out of Integer range. Similarly, if our target value is Integer.MAX_VALUE – 3 and our array is [-4, 1, Integer.MAX_VALUE – 4], we will get the same type of problem when we subtract -4 from our target value. So it looks like that we need to validate the range before subtracting.
Q: Yes, you got this part right. Now do you have any idea of how to do it?
A: Well, the target value is in range. Basically we need to check if we subtract the current value from the target, would it be outside of [Integer.MIN_VALUE, Integer.MAX_VALUE]? To get lower than Integer.MIN_VALUE, we need to subtract a positive number from the target. To get higher than Integer.MAX_VALUE, we need to subtract a negative number from the target. So if the current value is positive, we check if the MIN plus current is larger than the target. If yes, then it’s going to be out of bound if we do the subtraction. Similarly, if the current value is negative, we check if the MAX plus the current value is smaller than the target. If yes, then it’s going to be out of bound if we do the subtraction. Two examples here:
Say the range is [-10, 10]. target value is 3, current value is -8. 10-8 = 2 is smaller than 3, so this is going to be out of bound.
if the current value is 9, -10 + 9 = -1 is smaller than 3, so subtracting 9 from 3 is OK. We can even drop a graph to illustrate this idea.

Q: GOOD, you got it. Make sure you implement the code. Any other way to solve this problem?
A: Well, yeah we could sort the numbers first but that messes up the index and we have to keep track of the previous index somehow. So that’s not worth it in this problem. If we are only looking at the numbers, this approach may save us some spaces.

Code on github:

 

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

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

My thoughts and solution:

Q: What is the unknown?

A: To reverse nodes in a linked list k at a time and return the modified list.

Q: What are the data?

A: A linked list and an integer k.

Q: What are the constraints?

A: From the example above, we should probably assume this is a singly linked list. We cannot change the value in the node (Actually this is a very good idea in modifying linked list). Constant memory only. If at some point, the number of nodes is not the multiple of k, these nodes should remain the same order.

Q: Have you seen it before or at least something similar?

A: Yes I think I have. A similar problem is to reverse a singly linked list in place. I solved it before and it only took constant memory. I think we can apply the solution of that problem to each K nodes for reversing purpose.

Q: Good. For the whole problem, what kind of strategy should we use? Suppose we have reversed K nodes in the list, what about the rest of list?

A:  We do the same for the rest and connect with the k nodes reversed previously.

Q: Can you describe it in more details?

A: OK, for the rest of the linked list we reverse the nodes in k-Group and connect with previously reversed k nodes. Ah I see where this is heading. We are looking at a recursion here.

Q: Yes we are. Now think about the base case of this recursion.

A: That would be the number of remaining nodes is not a multiple of k and we should just connect them with the previously reversed part.

Q: What about the recursive case?

A: Hmm, we should reverse the current k nodes at hand. reverse the next k nodes and connect with them. Then return the current reversed part so the previously reversed part can connect with it.

Q: OK not super clear but I guess you have the idea.  In the base case, how do you determine if the number of remaining nodes is a multiple of k?

A: Starting from where we are, go k steps further. If at any point, we hit null, then we know there are enough nodes for reversal.

Q: Good. The take-away message here is that recursion could be a very handy trick for solving linked list related problems. So keep it in your toolbox.

Code on github:

Enhanced by Zemanta

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

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

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

My thoughts and solution:

Q: What’s the unknown?

A: The next permutation of the current sequence.

Q: What’re the data?

A: An integer array representing a number.

Q: Any Constraints?

A: No extra memory allocation allowed. But I think it means extra memory proportional to the input size N. Besides, at the beginning of solving this problem, we can ignore this constraint.

Q: True. Now what’s the meaning of next permutation?

A: Hmm, I think it means the next number sequence of the current sequence in lexicographic order, e.g., (1,2, 5, 3,4) -> (1,2, 5, 4,3), (1, 5, 3,4,2) -> (1, 5, 4,2,3) and (5, 4,3,2,1) -> (1,2,3,4,5).

Q: Now as a human being, how do you do this?

A: Eh..just think of the smallest number comprised of these digits that is greater than the current sequence. If there is none, we go back to the smallest possible number in all permutation.

Q: OK, but a computer can’t just “think of” the next number. Now how would a computer do that?

A: Hmm, I think we probably need to start with the least digit on the right side. But what next?

Q: Look at the example you listed above. What did you do with each example?

A: In (1,2, 5, 3,4) -> (1,2, 5, 4,3), I start with 4 and look at its left digit, 3. Since 3 < 4, I switch them. Hmm this works for all cases where the second digit is less than the first one. In (1, 5, 3,4,2) -> (1, 5, 4,2,3), I can’t switch 4 and 2 since (1,5,3,2,4) precedes (1,5,3,4,2). Well 3 < 4, I could switch them to get (1,5,4,3,2) but that’s not the correct answer. Hmm…

Q: So how do you get from (1,5,4,3,2) to (1,5,4,2,3)?

A: I could just switch 3 and 2.

Q: OK, what about (1,5,3,4,2,0) to (1,5,4,0,2,3)?

A: Hmm if I switch 3 and 4, I get (1,5,4,3,2,0). To get (1,5,4,0,2,3), I need to reverse 3,2,0 to 0,2,3. OK, I guess we should do like this: scan from the right, find the first digit at index Ind that is less than its previous digit, switch them and reverse the sequence to the right side of Ind.

Q: Well, almost there, but not yet. What about (1,6,3,5,4,0)? According to your algorithm above, the next permutation becomes (1,6,5,0,4,3) while it should be (1,6,4,0,3,5). See the problem?

A: Hmm, so 3 should be the switch point. I got that right, but it should switch with 4 instead of 5. Ah, so 3 should switch its ceiling in the sequence on its right side! We need to go back to find it and swap. Then do the reverse operation.

Q: Correct, what about the time complexity?

A: We scan the sequence and once find the switch point, we go back and find its ceiling, then switch and reverse. End of story. So it’s actually O(n), an linear time algorithm.

Code on github:

 

Enhanced by Zemanta

Nuts and bolts

Nuts and bolts. A disorganized carpenter has a mixed pile of N nuts and N bolts. The goal is to find the corresponding pairs of nuts and bolts. Each nut fits exactly one bolt and each bolt fits exactly one nut. By fitting a nut and a bolt together, the carpenter can see which one is bigger (but the carpenter cannot compare two nuts or two bolts directly). Design an algorithm for the problem that uses NlogN compares (probabilistically).

My thoughts and solution:

Well, according to the question, the nut and bolt has a one-to-one relation. So the first thing come into my mind is to sort the nuts and bolts into ascending order and then we can put them together to a pair one by one.

However, we cannot compare two nuts or bolts directly. So we have to think about indirect ways. Say we have two nuts N1 and N2. Well, since the nut and bolt has a one-to=one relation, there must exist two bolts B1 and B2 which exactly fit with N1 and N2. So if we try to fit both nuts with B1 (or B2), we can tell which nut is bigger. This is also suggested by the question that By fitting a nut and a bolt together, the carpenter can see which one is bigger”. The same works for comparing B1 and B2 indirectly.

OK, the question did mention NlogN compares probabilistically. Well that reminds me of QuickSort. So how does it apply here? QuickSort requires partitioning and recursion. OK, let’s look at partitioning.

To partition the nuts, we need to randomly select one nut, then compare it with the rest. But we cannot, at least not directly. So the alternative is to randomly select one bolt “B”, then compare each nut with it. In the end, we will have two small piles of nuts (one smaller than the bolt “S” and the other larger “L”) and the right one fits in the bolt “N”. Done!

Then we can do recursion, right? for both piles of nuts, randomly choose a bolt to partition…But wait! Whatever bolt we pick for “S” should come from the set of bolts that correspond to the nuts in “S” and so is the case for “L”. Otherwise, we cannot guarantee the correctness of the QuickSort algorithm.

So before we do the recursion, we have to find out the corresponding piles of bolts for “S” and “L”. How? Well, we do know the nut “N” that fits into “B” perfectly. We can do a partition of the bolts based on “N”. Then we will get our desired piles of bolts for “S” and “L”.

Now we can go on to the recursion.

About the comparison, it is O(NlogN). But I’m afraid we are using 2NlogN since we compared 2N in partitioning  the bolts and nuts. If you have some good ideas, please leave some comments.

Enhanced by Zemanta

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

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

My thoughts and solutions:

OK, how hard can this be, right? just find the first integer n such that n * n <= x and (n+1) * (n + 1) > x. Well mathematically this is correct, but if we transfer this idea to a program directly, we may run into the following two problems:

  • Time Limit Exceeded (well the OJ has a time limit for this question. O(N) is not acceptable)
  • Integer Overflow! It is possible that n*n is greater than the limit of Java integer (from -2^31 to 2^31 – 1).

I was stuck. Then someone on the discussion board mentioned: Think about math back in elementary school. n * n <= x is equivalent to what? Stupid me, n <= x / n. So if we avoid using plus and multiplication in comparison, we can avoid the integer overflow problem using subtraction and division. And I think this idea can extend to other primitive types as well. For something like (a+b)/2 we could re-write as a/2 + b/2.

As for the time limit problem, we can consider two improvements:

  • The naive algorithm would go from 1 to x. This is not necessary. We can simply check from 0 to x/2. Why? Because when x > 4, (x/2)^2 is always larger then x.
  • Is it necessary that we must go for a linear search? It’s a sorted sequence from 1 to x/2 and we are trying to find a number with a certain property. And this reminds me of binary search.

With these three improvements,  we can solve this question efficiently.

Code on github:

 

Enhanced by Zemanta