In the past few days there have been several announcements by both car and device manufacturers that self driving cars are almost a reality and to make that possible new and cheaper devices are being introduced to help.
It seems that newer LIDAR devices are improving in range and precision while their prices are coming down. This should help. On the other hand researchers are working on algorithms to check that sensors are getting more reliable. I read an article today that LIDAR systems can be tricked to not detect something or to detect something that is not there.
We also have some car manufacturers that keep on promising features that
they cannot deliver and chances are that they will not in the foreseeable future.
Some companies are starting to concentrate in long haul trucks that operate on highways. Traffic is simpler than when driving in a crowded city street and having to interact with other vehicles and people.
I also read an article about an experiment in China. They are developing special marked areas were autonomous vehicles can operate. By not having to share the area with other vehicles and people the systems can be an order of magnitude simpler.
Once you clear all the hype of autonomous vehicles there are many new problems that will need to be addressed. For example, autonomous vehicles will increase traffic. Most autonomous vehicles will use batteries. What is the actual cost to the owners and the environment for production, charge and eventual disposal? How are autonomous vehicles and ordinary ones going to interact? It seems that the issue is humans. Will we ever be able to have a mix of autonomous vehicles, regular ones and people interact with one another?
Hopefully in the next decade or so we will achieve a balance that will allow a mix of vehicles of all types interact in some ways with each other and humans.
OK enough about autonomous vehicles. Let’s get to the main subject of this post.
I picked up the Almost Sorted problem from HackerRank. Spent a good amount of time understanding what needed to be done. For a while I thought the problem could easily be solved by picking up a good data structure. A standard one did not seem to be able to do the trick.
As always, read the problem several times. Make sure you understand what is required. Then plan on an approach. I do this by using a simple layout of comments. Then try implementing some function s/ methods. You should be able to refine them as you work towards the complete solution.
2 4 2 yes swap 1 2 3 1 4 2 yes swap 2 3 4 1 4 2 9 yes swap 2 3 3 3 1 2 no 6 1 5 4 3 2 6 yes reverse 2 5 11 1 2 3 4 9 6 7 8 5 10 11 yes swap 5 9 13 2 3 5 7 41 13 17 19 23 29 31 37 11 yes swap 5 13
HackerRank provides three examples. They seem to provide all what you need to test your solution. That said, I created a few variations to make sure all was progressing well.
// **** open a scanner ****
private static final Scanner scanner = new Scanner(System.in);
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** read the number of elements to process ****
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
// ???? ????
System.out.println("main <<< n: " + n);
// **** read the array ****
int[] arr = new int[n];
String[] arrItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
// **** populate the array ****
for (int i = 0; i < n; i++) {
int arrItem = Integer.parseInt(arrItems[i]);
arr[i] = arrItem;
}
// **** determine if the array can be sorted ****
almostSorted(arr);
// **** close the scanner ****
scanner.close();
}
As usual the test scaffolding was provided by HackerRank. The first line contains the number of entries in an array that is almost sorted. The second line contains the integers for the array.
The output is somewhat complex. After some experimentation it became very clear what to do with the different examples.
/*
* Complete the almostSorted function below.
*/
static void almostSorted(int[] arr) {
// **** check if array is sorted ****
boolean sorted = isSorted(arr);
// **** array is sorted ****
if (sorted) {
System.out.println("yes");
return;
}
// **** declare start and end elements ****
int start = 0;
int end = 0;
// **** look for start element out of order (left to right) ****
for (int i = 0; i < (arr.length - 1); i++) { if (arr[i] > arr[i + 1]) {
start = i;
break;
}
}
// // ???? ????
// System.out.println("almostSorted <<< start: " + start); // **** look for end element out of order (right to left ) **** for (int i = arr.length - 1; i > 0; i--) {
if (arr[i] < arr[i - 1]) {
end = i;
break;
}
}
// // ???? ????
// System.out.println("almostSorted <<< end: " + end);
// **** swap elements ****
sorted = swap(arr, start, end);
// **** check if array is sorted ****
if (sorted) {
System.out.println("yes");
System.out.println("swap " + (start + 1) + " " + (end + 1));
return;
}
// **** reverse elements ****
sorted = reverse(arr, start, end);
// **** check if array is sorted ****
if (sorted) {
System.out.println("yes");
System.out.println("reverse " + (start + 1) + " " + (end + 1));
return;
}
// **** could not find a way to sort the array ****
System.out.println("no");
}
The heart of the problem is the implementation of the almostSorted() function. You have to make sure you understand exactly what needs to be done by reading the requirements. We need to check if the initial array is sorted. If it is, we just print “yes” and exit. It seems that we need a function that will allow us to determine if an array is sorted.
We then need to swap two numbers in the array and check if the array is ordered. The swap operation can only be performed once and if an array can be ordered by swapping or reversing, then we must pick swapping. By the way, the reversing and swapping operations can only be performed once. In other words, we can swap or we can reverse, but we cannot swap and reverse. This implies that we need to check if the swap will sort the array and if not we must restore it. We could also copy the array but that would require additional space and we would have to copy the array by adding O(n) complexity.
Note that since reversion is the last operation, if it fails we do not need to restore it.
Now we just need to select the start and end numbers to swap and if needed reverse to complete sorting the array.
I first tried looking for the start and end numbers going from left to right. It is simpler and easier to get the start by going from left to right and the end from right to left.
OK, we now have the starting and ending numbers so we can swap them.
/*
* Swap the two values in the specified array. If array is sorted return true;
* otherwise undo the swap and return false.
*/
static boolean swap(int[] arr, int start, int end) {
// **** swap the specified entries in the array ****
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
// **** determine if array if sorted ****
boolean sorted = isSorted(arr);
// **** check if array is sorted ****
if (sorted) {
return true;
}
// **** undo swap ****
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
// **** array was NOT sorted after swap ****
return false;
}
To swap two integers we just need a temporary value. After performing the swap we check if the array is now sorted. If the array is sorted we return a true value. If the array is not sorted, we need to undo the swap and then return a false value.
Back in the almostSorted() function if the array is sorted we display the required output. Note that the output contains a “yes”, a word describing what we did “swap” and the positions of the numbers that we swapped (not the actual numbers). Note that the arrays in Java are 0-based and the expected result is not, ,so we need to add a 1 to the start and end values.
If the almostSorted() function returned false, the array is back to what we started with and we can now try reversion the numbers in the sub array [start : end].
/*
* Reverse the specified elements in an array. If the array is sorted return
* true; otherwise undo the reversal and return false.
*/
static boolean reverse(int[] arr, int start, int end) {
// **** reverse the elements in the specified range ****
for (int i = start, j = end; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// **** determine if array if sorted ****
boolean sorted = isSorted(arr);
// **** check if array is now sorted ****
if (sorted) {
return true;
}
// **** undo reversal of elements (not needed because there are no additional operations) ****
for (int i = start, j = end; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// **** array was NOT sorted after reversal ****
return false;
}
We loop reversing the elements in the sub array. After the loop we check to determine if the array is sorted. If sorted we return true. If not sorted I undid the reversal which is not required due to the fact that there are no operations that will follow. We then return false to indicate that the array was not sorted.
Back in the almostSorted() function, if we returned a true value, we need to display two lines. The “yes” string indicates we were able to sort the array. The second indicates that we used “reverse” to achieve it and we also need to provide the start and end indices in the array corrected by 1.
/*
* Check if array is sorted.
*/
static boolean isSorted(int[] arr) {
// **** check if array has a single entry ****
if (arr.length == 1) {
return true;
}
// **** traverse the array checking consecutive elements ****
for (int i = 1; i < arr.length; i++) { // **** check if out of order **** if (arr[i - 1] > arr[i]) {
// **** array is NOT sorted ****
return false;
}
}
// **** array is sorted ****
return true;
}
This auxiliary function checks if the array is sorted. If it is we return true; otherwise we return false.
I did enjoy working on this problem. Once you are done it seems quite simple but it took some time. The solution did not appear just after reading the requirements once.
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 serve of assistance 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 message using the following address: john.canessa@gmail.com. All messages will remain private.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
John
Twitter: @john_canessa