Today it is Friday. I woke up around 04:30 AM. I wanted to generate this post before breakfast. In addition the cleaning lady will be here around 08:00 AM. In addition I have to prepare breakfast for my wife and me and shower.
I started to read an article regarding Facebook on the last issue of Communications of the Association for Computer Machinery. The article Does Facebook use sensitive data for advertising purposes? called my attention. I have not finished reading the article. I will make some comments when done.
Yesterday evening, I decided to tackle the coding practice problem Balanced Split by Facebook.
The problem has an example and two test cases. Due to this fact I might have missed something. If you encounter an issue I would appreciate if you could please send me a test case illustrating the problem.
I could have solved this problem on-line using the Facebook IDE. I decided to solve it on my computer using the VSCode IDE and the Java language. I had to generate a test scaffolding to run tests. That said; I could have copied, pasted and executed the code on-line, but I like to have all the tools and code on my machine so I can address issues or perform further exploration without having to locate a page that could have been dropped.
Given an array of integers (which may include repeated integers), determine if there's a way to split the array into two subsequences A and B such that the sum of the integers in both arrays is the same, and all of the integers in A are strictly smaller than all of the integers in B. Note: Strictly smaller denotes that every integer in A must be less than, and not equal to, every integer in B. Input: All integers in array are in the range [0, 1,000,000,000]. Output: Return true if such a split is possible, and false otherwise.
We are given a set of integers. Some may repeat. The numbers are in no particular order. That said; we need to determine if we could split the integers into two groups that add up to the same value. But wait, there is more. The integers in the set A must be strictly smaller than the ones in set B.
Note that I was not able to determine by reading the requirements, the minimum number of integers we could be provided.
bool balancedSplitExists(int[] arr) {
}
The signature for the function / method we need to develop is simple. Note that it does not comply with Java. Java does not have a bool data type or class. That said; Java is a supported language by the Facebook IDE.
1, 5, 7, 1 main <<< strArr: [1, 5, 7, 1] main <<< arr: [1, 5, 7, 1] main <<< output: true main <<< output: true main <<< output: true 12, 7, 6, 7, 6 main <<< strArr: [12, 7, 6, 7, 6] main <<< arr: [12, 7, 6, 7, 6] main <<< output: false main <<< output: false main <<< output: false 12, 7, 6, 7, 6 main <<< strArr: [12, 7, 6, 7, 6] main <<< arr: [12, 7, 6, 7, 6] main <<< output: false main <<< output: false main <<< output: false 3, 6, 3, 4, 4 main <<< strArr: [3, 6, 3, 4, 4] main <<< arr: [3, 6, 3, 4, 4] main <<< output: false main <<< output: false main <<< output: false 0 main <<< strArr: [0] main <<< arr: [0] main <<< output: false main <<< output: false balancedSplitExists2 <<< EXCEPTION e: java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 1 1 main <<< strArr: [1] main <<< arr: [1] main <<< output: false main <<< output: false main <<< output: false 1, 2 main <<< strArr: [1, 2] main <<< arr: [1, 2] main <<< output: false main <<< output: false main <<< output: false 0, 0 main <<< strArr: [0, 0] main <<< arr: [0, 0] main <<< output: false main <<< output: false balancedSplitExists2 <<< EXCEPTION e: java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 2 0, 1 main <<< strArr: [0, 1] main <<< arr: [0, 1] main <<< output: false main <<< output: false main <<< output: false 1, 1 main <<< strArr: [1, 1] main <<< arr: [1, 1] main <<< output: false main <<< output: false main <<< output: false 2 main <<< strArr: [2] main <<< arr: [2] main <<< output: false main <<< output: false main <<< output: false 20, 2 main <<< strArr: [20, 2] main <<< arr: [20, 2] main <<< output: false main <<< output: false main <<< output: false 5, 7, 20, 12, 5, 7, 6, 14, 5, 5, 6 main <<< strArr: [5, 7, 20, 12, 5, 7, 6, 14, 5, 5, 6] main <<< arr: [5, 7, 20, 12, 5, 7, 6, 14, 5, 5, 6] main <<< output: true main <<< output: true main <<< output: true 5, 7, 20, 12, 5, 7, 6, 7, 14, 5, 5, 6 main <<< strArr: [5, 7, 20, 12, 5, 7, 6, 7, 14, 5, 5, 6] main <<< arr: [5, 7, 20, 12, 5, 7, 6, 7, 14, 5, 5, 6] main <<< output: false main <<< output: false main <<< output: false 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 main <<< strArr: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] main <<< arr: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] main <<< output: false main <<< output: false main <<< output: false
Facebook provides two examples. Two additional examples are found in the unit test section. I created several test cases to address possible end conditions regarding the number of integers in the set. Some came from a site which I will mention later on.
It seems that we are provided with a set of integer values. Our test code seems to be able to read the integers and put them into a String[] array. The contents of the String[] are then displayed. All seems to be well so far.
The test code seems to generate and display an int[] using the values collected in the String[] array. The values appear to match.
The three next lines seem to invoke a version of our solution and display the results. Most of them match. We will get additional insights as we look at the different implementations.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read String[] array ****
String[] strArr = br.readLine().trim().split(", ");
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< strArr: " + Arrays.toString(strArr));
// **** create and populate int[] (if needed) ****
int[] arr = {};
if (!strArr[0].equals("")) {
arr = new int[strArr.length];
for (int i = 0; i < strArr.length; i++) {
if (strArr[i].equals(""))
continue;
arr[i] = Integer.parseInt(strArr[i]);
}
}
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** generate and display result ****
System.out.println("main <<< output: " + balancedSplitExists(arr));
// **** generate and display result ****
System.out.println("main <<< output: " + balancedSplitExists1(arr));
// **** generate and display result ****
System.out.println("main <<< output: " + balancedSplitExists2(arr));
}
Our test scaffolding does what we implied earlier in this post. Note that the generation of the int[] array from the data in the String[] is somewhat convoluted when compared to the test code we have in other posts. The reason for it is to be able to generate int[] arrays in which the int[] is null, contains 0, 1, 2 or more elements.
We make a call to three different implementations. The first two seem to always work. The third one seems it might have an issue.
/**
* Balanced split function.
* Time complexity: O(n)
*/
static boolean balancedSplitExists(int[] arr) {
// **** sanity check(s) ****
if (arr == null || arr.length <= 2)
return false;
// **** initialization ****
int i = -1;
int j = arr.length;
int lastA = Integer.MIN_VALUE;
int lastB = Integer.MAX_VALUE;
int sumA = 0;
int sumB = 0;
// **** sort the array O(n log(n) ****
Arrays.sort(arr);
// **** select numbers from outside to inside O(n) ****
while (i + 1 < j && lastA != lastB) {
// **** increment sumA or sumB ****
if (sumA > sumB) {
sumB += arr[--j];
lastB = arr[j];
} else if (sumA < sumB) {
sumA += arr[++i];
lastA = arr[i];
} else {
sumA += arr[++i];
lastA = arr[i];
}
}
// **** ****
return (sumA == sumB && lastA != lastB);
}
This was my first pass at the problem. The idea is to sort the array. Once it is sorted we traverse the array attempting to maintain the requirements for set A and B. When done we return a boolean indicating if the final tally for both sets adds to the same value, and because the values were sorted, that the last values processed in the sets are or are not equal.
/**
* Balanced split function.
* Time complexity:
*/
static boolean balancedSplitExists1(int[] arr) {
// **** sanity check(s) ****
if (arr == null || arr.length <= 2)
return false;
// **** initialization ****
int sumA = 0;
int sumB = 0;
int i = 0;
// **** compute sumA O(n) ****
for (i = 0; i < arr.length; i++)
sumA += arr[i];
// **** sort the array O(n log(n) ****
Arrays.sort(arr);
// **** decrement sumA while incrementing sumB O(n) ****
for (i = arr.length - 1; sumA > sumB; i--) {
sumA -= arr[i];
sumB += arr[i];
}
// **** ****
return (sumA == sumB && arr[i] != arr[i + 1]);
}
This is a simpler to understand implementation. We start by performing the same set of sanity checks as we did in the previous implementation. In this case we will include in the sumA all the integer values. We then sort the array. We could have changed the order of these two statements achieving the same results.
In the final loop we start moving values from set A to set B. At some point the sums will not meet the condition in the for() loop.
After we exit the loop we check if the sums match and that the last values in each set are different (the values are sorted).
Note that both implementations are similar.
Since I wanted to find more rigorous tests to verify our solutions, I found a solution on-line. The solution was not written in Java. I decided to make a port because the associated test cases appear to be missing to test some conditions.
Please note that I might have induced problems when porting such code. If you find an issue please let me know.
/**
* https://leetcode.com/discuss/interview-question/718692/facebook-training-balanced-split
*
* This implementation was ported to Java.
* It seems it MIGHT have an issue :o(
*/
static boolean balancedSplitExists2(int[] arr) {
// **** initialization ****
int leftSum = 0;
int rightSum = 0;
// **** sort the array O(n log(n) ****
Arrays.sort(arr);
// **** ****
for (int i = 0; i < arr.length; i++)
leftSum += arr[i];
// **** ****
for (int i = arr.length - 1; i >= 0; i--) {
// **** ****
leftSum -= arr[i];
rightSum += arr[i];
// **** ****
if (leftSum == rightSum) {
try {
if (arr[i - 1] < arr[i])
return true;
} catch (Exception e) {
System.out.println("balancedSplitExists2 <<< EXCEPTION e: " + e.toString());
System.exit(-1);
}
}
}
// **** ****
return false;
}
The function performs initialization steps. It sorts the array. It uses an array to compute the sum of all integers from left to right. This is similar to the second approach.
In the final loop it transfers values from the left to the right sum. It then checks if the sums match. If they do, a check is made to see if the last integers in the sets are different. That causes the function to throw an exception.
If we do not run into end conditions, which could have been addressed by performing some sanity checks, the results would match the other two methods.
Hope you enjoyed solving this problem as much as I did. 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 the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 5,854 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
One possible optimization, which will work in 50% in O(n) time and in O(1) space, would be to check If the total array sum is even or odd. If sum % 2 == 1, then we already know it’s impossible to balance subarays, so just return false without further sorting.