Java Multithreading Notes From Lecture One

This is part of the notes from an online course (Java Multithreading) I’m taking on Udemy. Nothing complicated.


 

There are normally three ways to create threads (Examples on gist):

  • Create a class that extends the Thread class
  • Create a class that implements the Runnable interface
  • Create a Thread anonymously

Whichever we choose to use, we must override or implement the public void run method.

Multithreading:

All Java programs have a main thread, but we can create and invoke other threads from the main thread.

To do that, we need to call the start() method of each thread we want to invoke from main thread. It will look for the run() method and run that in its own special thread, not in the main thread (refer to the App.java in the gist).

The start() method will return immediately so the main thread will continue its execution of the next line of code.

However, if we accidentally call the run() method of those threads, then the method run() will be executed in the main thread, not in its own special thread! So be careful.

 

Gas station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

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

Q: What is the unknown?

A: The index of the gas station from which we can circle around the route.

Q: What are the data?

A: There are N gas stations. At each station i (i = 0, 1, 2, 3, …, N-1) the amount of gas is gas[i]. The tank is unlimited. To get from station i to i+1, it needs cost[i] amount of gas. We start from an empty gas tank.

Q: Are there any constraints?

A: Yes, the solution is unique and if none satisfies the requirements, return -1.

Q: What do you think is the key point of this problem?

A: That whether we can circle around from a station with index i.

Q: And how would you like to do that?

A: Hmm, we start at index i with L amount of gas in the tank (initially L is zero). If L + gas[i] >= cost[i], that means we can move from index i to i + 1. We repeat this process until we meet the following cases:

  1. At station k % N (k % N < i), L + gas[k%N] < cost[k%N].  This means that we cannot circle around the route from station i.
  2. k % N == i. In this case we have circled around the route from station i and we should return i.

Based on this, we can think of a straightforward algorithm. At each station, check if we can circle around the route as stated above.

Q: OK. What is the time complexity of this algorithm?

A: If we are extremely unlucky, we may have to almost circle around the route every time we perform a station check. That takes O(N) time. Since we have to do it for all N stations, I would say this algorithm takes O(N^2) time.

Q: Can we do better than this?

A: Hmm, I don’t think we can improve the station check since we do have to go around all the stations in the circle. But maybe we don’t have to do a station check for each station in the circle. There might be a way to skip some of them based on the result of the previous station checks.

Q: That’s a good thought. Can you think of an example to prove your idea?

A: OK, suppose I’m at station i and I can reach to station j at most where i <= j. That means the left amount of gas L at station j plus gas[j] is less than cost[j]. But then what?

Q: OK, normally we would just go check station i+1 (suppose i + 1 <= j), right? Now can you deduct how far we can get starting from i+1 based on the result of station i?

A:  I’m not sure…

Q: When we are at station i + 1 with a fresh start, the amount of gas left in the tank L is zero. We also know that we can go from i to i + 1. So from i to i+1, the amount of gas left in the tank L at station i + 1 must be no less than zero (otherwise we cannot go from i to i + 1). In this case if we can at most get to station j from i, how far do you think we can get to from station i+1?

A: Eh…at most j as well. Ah I get it. If we can go from station i to station j but not circling around the route we should skip all stations from i + 1 to j and only start the next station check at station j + 1.

Q: You got it. So what about the running time of this algorithm?

A: Hmm, in this algorithm each station is checked at most once. So I would say it is an O(N) algorithm.

Q: OK. Go implement this algorithm.

Code on github:

 

Valid Parentheses

Valid Parentheses
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

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

Q: What is the unknown?
A: determine if the input string is valid.
Q: What does it mean by valid?
A: Parentheses must be in the correct order:
1. Each (, [, { must correspond to one ), ], }.
2. ), ], } cannot exist without a preceding (, [, {.
3. The parentheses must not intertwine like ([)], however {([])} is allowed.
Q: So these are also the constraints then. What about the data, input and output?
A: The input data is a string and the output is a boolean.
Q: Special cases we should pay attention to?
A: Null string, empty string, string with odd length, string with characters other than (), [] and {}. The algorithm should return false in these cases.

Q: OK. Have you seen it before? Or something similar?
A: Yes I’ve seen something similar. In that problem, using a Stack is helpful.
Q: And why is that?
A: Well, the validation actually happens when we meet one of the three characters ), ] and }. At that point, we need to check if there is a preceding (, [, or {. A stack helps us to keep track of what we have seen previously and easily get back to it.
Q: Fair enough. So how would you use the stack here? How does it operate?
A: Hmm, whenever we meet a (, [ or {, we push it into the stack. In other cases, we first check if the stack is empty. If yes, then return false. If no, then check the top character of the stack matches in pair with the current character. If yes, we pop the stack. Otherwise, return false.
Q: OK, then when do we return true?
A: When we finish scanning the string, if the stack is empty then we return true. We must check this otherwise it will fail on test case like “((“.
Q: Good. What is the complexity of this algorithm?
A: The time and space complexities are both O(n) where n is the length of the string since we only scan the string once but we need the stack to save the characters.

Code on github:

Update:
Q: can we do better?
A: well we’ve already achieved O(n) time complexity. I’m not sure if we can make it even faster. After all, we do have to check all characters.
Q: Then what about space? Is the stack really necessary?
A: Hmm, you are saying that we should use something else to keep track of previous characters?
Q: Yep, the characters are in the string, right? I can access them easily using index.
A: OK, I see where this is going. So instead of using a stack, we should consider using indices to keep track of previous left characters?
Q: Yeah.
A: Hmm, in that case, we need the index of the latest left character and its previous character and this shall apply to all seen left characters and we will need extra space to either create a wrapper class to hold the index and this will cost O(n) space too. So it’s not better.
Q: OK, fair enough. But it’s always good to think about possible improvement.
A: Of course.

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:

 

Interactive documents: An incredibly easy way to use Shiny

Awesome new features!

RStudio Blog

R Markdown’s new interactive documents provide a quick, light-weight way to use Shiny. An interactive document embeds Shiny elements in an R Markdown report. The report becomes “live”, a choose your own adventure that readers can control and explore. Interactive documents are easy to create and easy to share.

Create an interactive document

To create an interactive document use RStudio to create a new R Markdown file, choose the Shiny document template, then click “Run Document” to show a preview:


storms.002

Embed R code chunks in your report where you like. Interactive documents use the same syntax as R Markdown and knitr. Set echo = FALSE. Your reader won’t see the code, just its results.

  storms2.001

Include Shiny widgets and outputs in your code chunks. R Markdown will insert the widgets directly into your final document. When a reader toggles a widget, the parts of the document that depend on it will…

View original post 297 more words

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