Today is Wednesday morning. It seems that the high temperature for the day will be 31F. Better than yesterday but my wife and I live in the Twin Cities of Minneapolis and St. Paul and winters are rather harsh in this part of the country.
This morning I decided to move from solving Facebook technical interview questions to Microsoft. I will try to solve a couple problems a day if time allows. Will see how it goes. My source will be LeetCode. At some point I might switch to HackerRank.
Without further ado, let’s get to the problem at hand.
I randomly chose LeetCode problem 717 1-bit and 2-bit Characters.
We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11). Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero. Note: o 1 <= len(bits) <= 1000. o bits[i] is always 0 or 1.
It seems that there is a single 1-bit character with a value of 0. It seems we have two 2-bit characters represented as 10 and 11 respectively.
Our task, if we wish to accept it, is to determine if the string of bits represented by an integer array ends in a 1 or a 2 bit character. If interested in this problem please visit the LeetCode site and get the requirements directly from the source.
public boolean isOneBitCharacter(int[] bits) {
}
This is the signature for the function / method we have to implement.
You can solve the problem directly in the LeetCode site. I prefer to solve it in my computer. I will solve the problem using Java on a Windows 10 machine using the VSCode IDE. When I feel comfortable with the code I will paste and run it on LeetCode. Because of this, I will have to generate a test scaffolding to collect the input data, convert it to the format required by the argument to the function we need to solve, call the function and display the result. Please note that the test scaffolding IS NOT PART OF THE SOLUTION.
1,0,0 main <<< arr: [1, 0, 0] main <<< output: true 1,1,1,0 main <<< arr: [1, 1, 1, 0] main <<< output: false
The LeetCode site provides two test cases. Those are the ones I used to test my solution.
It seems that the first line contains a string with the bit values. The test program appears to read the data and return an integer array. The array is then displayed to make sure all is well so far.
It appears that the test scaffolding then calls the function in question and displays the returned value. The returned values appear to match the expected results so we could give it a try. I did and the solution was accepted.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read line and split into String[] ****
String[] strArr = br.readLine().trim().split(",");
// **** close buffered reader ****
br.close();
// **** create and populate int[] ****
int[] arr = Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** call function and display results ****
System.out.println("main <<< output: " + isOneBitCharacter(arr));
}
Not much to say. The test code opens a buffered reader and reads the input line generating a string array with the bit values. We then close the buffered reader.
We then create an array of integers and populate it with the integer values for the associated bits. The array is displayed. It seems to match the input so all is well so far.
Finally we make a call to the isOneBitCharacter() function and display the returned value.
/**
* Return whether the last character must be a
* one-bit character or not.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.2 MB, less than 86.36% of Java online submissions.
*/
static boolean isOneBitCharacter(int[] bits) {
// **** initialization ****
boolean oneBit = false;
// **** traverse the array O(n) ****
for (int i = 0; i < bits.length; ) {
// **** is this a 1-bit character? ****
if (bits[i] == 0) {
oneBit = true;
i++;
}
// **** this is a 2-bit character ****
else {
oneBit = false;
i += 2;
}
}
// **** return result ****
return oneBit;
}
This function implements the solution for the problem. We initialize a variable which we will use in a loop. Note that given the requirements and implementation we could have initialized it to true. In general it is best to initialize variables to the worse possible scenario. I thought false would be best.
We then enter a loop. If the bit is 0 we have a 1-bit character. We flag it and increment our index by 1.
If the bit is not 0, then it must be a 2-bit character. We flag it and increment the index by 2.
When we process all bits we return the current value of the oneBit variable.
If you have questions give it a try with a pen and piece of paper. You should be able to get to the same solution as the one generated by the code.
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,045 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
Regards;
John
john.canessa@gmail.com