Over the weekend I watched the YouTube video “Dealing with Negative Comments | AMA #3 – Ask Me Anything with Lex Fridman”. I have watched a few of his videos. I do enjoy them to the point that I have subscribed to them. There is one in which Lex interviews Donald Knuth and other where he interviews Andrew Ng. Both videos are over an hour so I will watch them over the weekend.
If you are interested in getting information about Lex Fridman you can find it here or there.
I picked the challenge “A or B” from HackerRank after receiving an email message. I guess that if you solve a few of their problems they like you to continue visiting their site and solving additional challenges. I like to work on one or two a week. I believe it is the only way to learn and / or refresh material.
The requirements are well described in the HackerRank web site. We will 
develop a solution in Java 8 using the Microsoft Visual Studio Code IDE. On a side note, yesterday I read a very good post on Python interfaces so I will be adding Python support to VSCode in the next day or so. More on this in future posts.
I logged into GitHub and created the AorB repository. I also wrote a simple README.md file which will contain a link to this post. I have to add the link after the post it on WordPress.
# **** **** C:\Users\John\workspace7>dir 02/29/2020 06:05 AM <DIR> . 02/29/2020 06:05 AM <DIR> .. 01/30/2020 01:32 PM <DIR> .metadata 01/31/2020 09:02 AM <DIR> .vscode 01/05/2020 07:15 AM <DIR> 3DSurfaceArea 01/06/2020 11:52 AM <DIR> AlmostSorted 02/06/2020 07:16 AM <DIR> AndProduct 01/24/2020 12:49 PM <DIR> AStarSearch 12/05/2019 01:23 PM <DIR> BiggerIsGreater 02/25/2020 02:49 PM <DIR> BinaryTreeSum 02/14/2020 03:00 PM <DIR> Cipher 12/22/2019 08:35 AM <DIR> DeterminingDNAHealth 01/08/2020 07:07 AM <DIR> EmasSupercomputer 02/12/2020 02:46 PM <DIR> FirstDuplicate 02/03/2020 09:07 AM <DIR> FlippingBits 02/20/2020 08:14 AM <DIR> FullCountingSort 02/16/2020 09:09 AM <DIR> GitHubTest 01/31/2020 02:57 PM <DIR> guava-mini 01/31/2020 10:44 AM <DIR> HelloMaven 02/17/2020 10:43 AM 2,339,925 ij.jar 02/17/2020 10:52 AM <DIR> ImageJ 02/29/2020 06:05 AM <DIR> IsPermutation 02/22/2020 07:45 AM <DIR> JavaStreams 02/04/2020 02:04 PM <DIR> JumpingOnTheClouds 01/23/2020 08:05 AM <DIR> LarrysArray 12/03/2019 04:26 PM <DIR> MatrixLayerRotation 02/03/2020 10:42 AM <DIR> MiniMaxSum 01/25/2020 08:07 AM <DIR> PriorityQ 01/30/2020 01:42 PM <DIR> rtree2 02/03/2020 01:44 PM <DIR> SansaXOR 01/19/2020 09:16 AM <DIR> StacksReverseOrder 02/19/2020 08:08 AM <DIR> SumOfTwo 01/04/2020 07:51 AM <DIR> TheGridSearch 12/11/2019 10:09 AM <DIR> ToTrieOrNotToTrie # **** **** C:\Users\John\workspace7>git clone https://github.com/JohnCanessa/AorB.git Cloning into 'AorB'... remote: Enumerating objects: 3, done. remote: Counting objects: 100% (3/3), done. remote: Compressing objects: 100% (2/2), done. remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0 Unpacking objects: 100% (3/3), done. # **** **** C:\Users\John\workspace7>dir 02/29/2020 09:10 AM <DIR> . 02/29/2020 09:10 AM <DIR> .. 01/30/2020 01:32 PM <DIR> .metadata 01/31/2020 09:02 AM <DIR> .vscode 01/05/2020 07:15 AM <DIR> 3DSurfaceArea 01/06/2020 11:52 AM <DIR> AlmostSorted 02/06/2020 07:16 AM <DIR> AndProduct 02/29/2020 09:10 AM <DIR> AorB 01/24/2020 12:49 PM <DIR> AStarSearch 12/05/2019 01:23 PM <DIR> BiggerIsGreater 02/25/2020 02:49 PM <DIR> BinaryTreeSum 02/14/2020 03:00 PM <DIR> Cipher 12/22/2019 08:35 AM <DIR> DeterminingDNAHealth 01/08/2020 07:07 AM <DIR> EmasSupercomputer 02/12/2020 02:46 PM <DIR> FirstDuplicate 02/03/2020 09:07 AM <DIR> FlippingBits 02/20/2020 08:14 AM <DIR> FullCountingSort 02/16/2020 09:09 AM <DIR> GitHubTest 01/31/2020 02:57 PM <DIR> guava-mini 01/31/2020 10:44 AM <DIR> HelloMaven 02/17/2020 10:43 AM 2,339,925 ij.jar 02/17/2020 10:52 AM <DIR> ImageJ 02/29/2020 06:05 AM <DIR> IsPermutation 02/22/2020 07:45 AM <DIR> JavaStreams 02/04/2020 02:04 PM <DIR> JumpingOnTheClouds 01/23/2020 08:05 AM <DIR> LarrysArray 12/03/2019 04:26 PM <DIR> MatrixLayerRotation 02/03/2020 10:42 AM <DIR> MiniMaxSum 01/25/2020 08:07 AM <DIR> PriorityQ 01/30/2020 01:42 PM <DIR> rtree2 02/03/2020 01:44 PM <DIR> SansaXOR 01/19/2020 09:16 AM <DIR> StacksReverseOrder 02/19/2020 08:08 AM <DIR> SumOfTwo 01/04/2020 07:51 AM <DIR> TheGridSearch 12/11/2019 10:09 AM <DIR> ToTrieOrNotToTrie # **** **** C:\Users\John\workspace7>cd AorB # **** **** C:\Users\John\workspace7\AorB>dir /A 02/29/2020 09:10 AM <DIR> . 02/29/2020 09:10 AM <DIR> .. 02/29/2020 09:10 AM <DIR> .git 02/29/2020 09:10 AM 285 README.md
Once done I cloned the repository from GitHub. We are missing the code which we will implement in a Solution.java file to be created using VSCode.
3 8 2B 9F 58 5 B9 40 5A 2 91 BE A8 8 58 18 42 -1 3 25 B631EB5AE 601C227E1 707AC8792 12 CAF7028FD 59B5AC1CE CAF1B7B7F 3 81B9BB94E 8AB3CA95E 8BBBFB95E C8582 707A00790 8AF10287D 48B1B534E B9BB94E 8BB3CA95E
The first example is from the challenge. The first line contains the number of test cases. Each test contains four lines. The first is the number of bits that we can flip. The following two numbers is hexadecimal represent the A and B values. The last number of the set represents the C value. The set of numbers repeats for the three cases.
The second example is one I purchased using 5 hackos. When I implemented the code it worked with the sample case, but I was going to use two consecutive loops and for starters only implemented the first one which is fine using the test on the requirements page. Perhaps I did not need to purchase the test case, but I did. After that I implemented the second loop and it timed out on 4 out of 21 test cases. More on this as we see the solution.
Also note that in the first test case, the last set of numbers does not produce a viable solution. For this reason we just print a -1.
The test scaffolding provided is simple and to the point.
// **** open scanner ****
private static final Scanner sc = new Scanner(System.in);
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** read the number of test cases ****
int q = Integer.parseInt(sc.nextLine().trim());
// ???? ????
// System.out.println("main <<< q: " + q);
// **** loop onec per test case ****
for (int i = 0; i < q; i++) {
// **** read k ****
int k = Integer.parseInt(sc.nextLine().trim());
// **** read string for A ****
String a = sc.nextLine();
// **** read string for B ****
String b = sc.nextLine();
// **** read string for C ****
String c = sc.nextLine();
// **** ****
aOrB(k, a, b, c);
}
// **** close scanner ****
sc.close();
}
As usual I added some comments. Not sure there is much to add.
/**
* Complete the aOrb function below.
*
* Uses StringBuilder for bit manipulations (seem to be too slow).
* Passed 17 or 21 test cases; 4 test cases timed out :o(
*
* Use character arrays for bit manipulations.
* Passed all 21 test cases :o)
*/
static void aOrB(int k, String a, String b, String c) {
// **** hex string to big integer ****
BigInteger abi = new BigInteger(a, 16);
BigInteger bbi = new BigInteger(b, 16);
BigInteger cbi = new BigInteger(c, 16);
// **** big integer to string builder ****
StringBuilder asb = new StringBuilder(abi.toString(2));
StringBuilder bsb = new StringBuilder(bbi.toString(2));
StringBuilder csb = new StringBuilder(cbi.toString(2));
// ***** compute the max length for the strings ****
int maxLength = Math.max(asb.length(), bsb.length());
maxLength = Math.max(maxLength, csb.length());
// **** get all strings to the same length (prepend 0s) ****
while (asb.length() < maxLength) {
asb.insert(0, 0);
}
while (bsb.length() < maxLength) {
bsb.insert(0, 0);
}
while (csb.length() < maxLength) {
csb.insert(0, 0);
}
// **** convert string builders to character arrays ****
char[] aca = asb.toString().toCharArray();
char[] bca = bsb.toString().toCharArray();
char[] cca = csb.toString().toCharArray();
// **** first pass O(n) ****
for (int i = 0; (i < maxLength) && (k >= 0); i++) {
// **** for ease of use ****
char aChar = aca[i]; // asb.charAt(i);
char bChar = bca[i]; // bsb.charAt(i);
char cChar = cca[i]; // csb.charAt(i);
// **** cChar == '0' ****
if (cChar == '0') {
// **** 0 | 1 case ****
if (aChar == '0' && bChar == '1') {
bca[i] = '0'; // bsb.replace(i, i + 1, "0");
k--;
}
// **** 1 | 0 case ****
else if (aChar == '1' && bChar == '0') {
aca[i] = '0'; // asb.replace(i, i + 1, "0");
k--;
}
// **** 1 | 1 case ****
else if (aChar == '1' && bChar == '1') {
aca[i] = '0'; // asb.replace(i, i + 1, "0");
bca[i] = '0'; // bsb.replace(i, i + 1, "0");
k -= 2;
}
}
// **** cChar == '1' ****
else {
// **** 0 | 0 case ****
if (aChar == '0' && bChar == '0') {
bca[i] = '1'; // bsb.replace(i, i + 1, "1");
k--;
}
}
// **** check if no valid answer ****
if (k < 0) {
// **** output result ****
System.out.println("-1");
// **** nothing else to do ****
return;
}
}
// **** second pass O(n) ****
for (int i = 0; (i < maxLength) && (k > 0); i++) {
// **** for ease of use ****
char aChar = aca[i]; // asb.charAt(i);
char bChar = bca[i]; // bsb.charAt(i);
char cChar = cca[i]; // csb.charAt(i);
// **** 1 | 0 case ****
if (cChar == '1' && aChar == '1' && bChar == '0' && k >= 2) {
aca[i] = '0'; // asb.replace(i, i + 1, "0");
bca[i] = '1'; // bsb.replace(i, i + 1, "1");
k -= 2;
}
// **** 1 | 1 case ****
else if (cChar == '1' && aChar == '1' && bChar == '1') {
aca[i] = '0'; // asb.replace(i, i + 1, "0");
k--;
}
}
// **** convert char array to string builder ****
asb = new StringBuilder(new String(aca));
bsb = new StringBuilder(new String(bca));
// **** convert string builder string to big integer ****
abi = new BigInteger(asb.toString(), 2);
bbi = new BigInteger(bsb.toString(), 2);
// **** output results in hexadecimal format ****
System.out.println(abi.toString(16).toUpperCase());
System.out.println(bbi.toString(16).toUpperCase());
}
The comment for the function / method states that I attempted to use first use manipulations on StringBuilder objects. That allowed the code to pass all except 4 test cases. They timed out. I was going to rewrite the method on a second copy but decided to just modify the existing one. I left commented out the original code segments. As you can tell the logic is quite similar, just applied to a different data structure (in this case to character arrays).
I started converting the strings to BigIntegers. That took care of the hex conversion.
The StringBuilders provided a way to get to a binary representation of the hexadecimal values.
I then compute the length of the maximum string. We want all binary strings
to have the same length. With that value in hand we prepend ‘0’s until all strings have the same count of bits.
Now we populate character arrays for the three values. The operations should be quite faster than using StringBuilders.
The first loop is used to replace bits in the A and B values in order to match C. If the target bit in C is ‘0’ we have three cases to address. If the bit value in C is ‘1’ we only have a single case. Note that we are decrementing the value of k as we process bits. If we exceed the maximum number of changes we print -1 and return.
If we have additional bits to change we go for a second round. We start by extracting the values into variables. We could just work directly with the arrays but if the tests pass we can leave them. It is easier to follow and maintain, not that we will need to maintain this code after it is completed.
We have to address two cases. What we want is to reduce the value of A and B using the remaining number of changes.
Once the loop is completed, we convert the character array to a StringBuilder of binary values. We then convert the binary values to hexadecimal. Finally we display the results in UPPER case. Not sure if that was stated in the requirements. The first test case only generates values that can be expressed in decimal. The second test case displays hexadecimal values in UPPER case. This implies that we need to convert them to UPPER case.
The code passed all test cases.
We now need to update the code in our repository.
# **** ****
C:\Users\John\workspace7\AorB>dir
02/29/2020 09:10 AM 285 README.md
03/03/2020 08:19 AM 5,361 Solution.java
# **** ****
C:\Users\John\workspace7\AorB>git status
On branch master
Your branch is up to date with 'origin/master'.
Untracked files:
(use "git add <file>..." to include in what will be committed)
Solution.java
nothing added to commit but untracked files present (use "git add" to track)
# **** ****
C:\Users\John\workspace7\AorB>git add Solution.java
# **** ****
C:\Users\John\workspace7\AorB>git status
On branch master
Your branch is up to date with 'origin/master'.
Changes to be committed:
(use "git reset HEAD <file>..." to unstage)
new file: Solution.java
# **** ****
C:\Users\John\workspace7\AorB>git commit -m "initial pass"
[master 23f86a9] initial pass
1 file changed, 183 insertions(+)
create mode 100644 Solution.java
# **** ****
C:\Users\John\workspace7\AorB>git push origin master
Enumerating objects: 4, done.
Counting objects: 100% (4/4), done.
Delta compression using up to 8 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 1.54 KiB | 790.00 KiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/AorB.git
4a1e271..23f86a9 master -> master
# **** ****
C:\Users\John\workspace7\AorB>git log
commit 23f86a935ee4c64eceb1de53d8771524ffcf31d8 (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date: Tue Mar 3 08:24:57 2020 -0600
initial pass
commit 4a1e2710b34990cf65d8930eee63b361abb95a20
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date: Sat Feb 29 09:09:33 2020 -0600
Create README.md
We commit the Solutions.java file and push the change to our GitHub repo. We are almost done. After generating the post in WordPress I will put the link to it in the README.md file. I will do that by editing it in GitHub.
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 private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
One last thing, thanks to all 375 subscribers to my blog!!!
John
Twitter: @john_canessa