I have mentioned in recent posts that this year the temperature in the Twin Cities of Minneapolis and St. Paul has not dropped down to 0F yet. Well, that is changing this Sunday. It seems that the high temperature for the day will be -6F and the low -20F. The good news is that according to the forecast, the temperature will increase rapidly in the following days.
Last weekend I spend several hours on work stuff. Hopefully the following weekend will be a normal one. Not sure if my wife and I will be venturing out on the forecasted cold.
As I mentioned in the previous post, the subject for this entry is shuffling an array. We will cover LeetCode 384. Shuffle an Array problem.
Given an integer array nums, design an algorithm to randomly shuffle the array. Implement the Solution class: Solution(int[] nums) Initializes the object with the integer array nums. int[] reset() Resets the array to its original configuration and returns it. int[] shuffle() Returns a random shuffling of the array. Constraints: o 1 <= nums.length <= 200 o -106 <= nums[i] <= 106 o All the elements of nums are unique. o At most 5 * 104 calls will be made to reset and shuffle.
The idea is to develop three methods and associated data in a class. It seems we will need the constructor, a shuffle and a reset method.
I will be tackling the problem using the Java programming language on a Windows 10 machine using the VSCode IDE. Probably the simplest approach would be to solve the problem directly in the LeetCode site using the provided IDE. Since I like to keep the code and tests together, I will develop a test scaffolding. When done testing I will copy my solution to the LeetCode site and check if it is accepted.
class Solution {
public Solution(int[] nums) {
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int[] param_1 = obj.reset();
* int[] param_2 = obj.shuffle();
*/
The signature for the class and methods is as expected. In addition we can see how LeetCode will be testing our code.
4 Solution 1,2,3 shuffle reset shuffle main <<< N: 4 main <<< cmd ==>Solution<== main <<< nums: [1, 2, 3] main <<< cmd ==>shuffle<== main <<< shuffle: [2, 1, 3] main <<< cmd ==>reset<== main <<< reset: [1, 2, 3] main <<< cmd ==>shuffle<== main <<< shuffle: [1, 3, 2]
For our test code we will be providing the number of operations followed by the operations. Only one of the operations requires arguments so we will provide them on the following line.
Our test scaffolding after reading and displaying the number of arguments it loops reading the commands. After each command is read the command is displayed. When we encounter the “Solution” command we need to read the integers for an int[]. The array is then displayed.
As we execute the different commands we display the returned values. In a nutshell, after processing “Solution” we display the nums[] array. After the “shuffle” command we display the shuffled array, and finally after processing the “reset” command we display the original array.
/**
* Test scaffolding.
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
int[] nums = null;
Solution obj = null;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the number of command ****
int N = Integer.parseInt(br.readLine().trim());
// ???? ????
System.out.println("main <<< N: " + N);
// **** loop once per command ****
for (int i = 0; i < N; i++) {
// **** read command ****
String cmd = br.readLine().trim();
// ???? ????
System.out.println("main <<< cmd ==>" + cmd + "<==");
// **** read nums[] (if needed) *****
if (cmd.equals("Solution") == true) {
nums = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
}
// **** process command ****
switch (cmd) {
case "Solution":
obj = new Solution(nums);
break;
case "shuffle":
System.out.println("main <<< shuffle: " + Arrays.toString(obj.shuffle()));
break;
case "reset":
System.out.println("main <<< reset: " + Arrays.toString(obj.reset()));
break;
default:
System.out.println("main <<< unexpected cmd ==>" + cmd + "<==");
break;
}
}
// **** close buffered reader ****
br.close();
}
The test scaffolding is NOT PART OF THE SOLUTION! We use a buffered reader to read the input lines.
We start buy reading the number of commands we are going to process. The value is then displayed.
We then enter a loop. In each pass we read and display the command. For the “Solution” command we need to read and populate the nums[] array. We then display the contents of the nums[] array.
We are now ready to process the commands. Note that after processing the “shuffle” and “reset” commands the results are displayed.
// **** class members ****
int[] nums;
Random rand;
int len;
The nums[] array will hold the values for the current array. The rand class member is used to generate random numbers, and the len variable is used to keep the number of elements in the array. Actually we could just use this.nums.length instead. I was just experimenting attempting to reduce executions time. The execution time seems to be associated with your code and the load on the LeetCode site.
/**
* constructor
*/
public Solution(int[] nums) {
this.nums = nums;
this.rand = new Random();
this.len = nums.length;
}
The constructor initializes the class variables. Not all variables are used in the two implementations we will look at.
/**
* reset
*/
public int[] reset() {
return this.nums;
}
The reset method returns the original array.
/**
* shuffle
*/
public int[] shuffle() {
// // **** array[] to list<Integer> ****
// List<Integer> lst = Arrays.stream(this.nums).boxed().collect(Collectors.toList());
// // **** shuffle the list<Integer> ****
// Collections.shuffle(lst);
// // **** return list to int[] ****
// return lst.stream().mapToInt(Integer::valueOf).toArray();
// **** initialization ****
int[] arr = this.nums.clone();
// **** shuffle the array ****
for (int i = 0; i < this.len; i++) {
int j = rand.nextInt(this.len);
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// **** return shuffled array ****
return arr;
}
The shuffle method shows two implementations. The first one has been commented out. The idea is to generate a list of integers. We then shuffle the list. Finally we convert the list to an int[] and return it as the shuffled array.
In the second approach, that is somewhat faster than the first, we make a copy of the nums[] into the arr[] array.
We enter a loop in which we exchange the contents of the current with a random position in the array. When done we return the shuffled array.
If interested in the relative runtimes of these two implementations you can find it by looking at the GitHub repository associated with this post.
Hope you enjoyed solving this problem as much as I did. As I just mentioned, the entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 6,287 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com