Leetcode 393: UTF-8 Validation

Dec. 6, 2017

Introduction

The algorithm is to determine if the integer array has specified format with one to 4 byte data. I found out that best way to deal with nervousness is to read the problem statement again and again, more than four times. And then usually I understand the algorithm and bring back my confidence about bit manipulation problem solving. The problem statement is here.

Code review

It is time for me to review my practice of bit manipulation by looking up the blog using keyword: bit manipulation. The search result is here.

Review some basics from one of blogs.

Top coder - fun with bits, the article link is here.

Take some notes:
Use bits of an integer to represent a set. Not only does it produce an order-of-magnitude improvement in both speed and size, it can often simplify code at the same time.

Go over the most popular set manipulations in the following:

Set union         
A | B

Set intersection
A & B

Set subtraction
A & ~B

Set negation
ALL_BITS ^ A

Set bit
A |= 1 << bit

Clear bit
A &= ~(1 << bit)

Test bit
(A & 1 << bit) != 0

Extracting every last bit

Counting out the bits


It is time for Julia to learn bit manipulation again. What Julia likes to do is to read the article word by word and then spend 10 - 20 minutes to go over the terms and warm up the idea how to solve the problem to use integer to represent a set.

It is not so often Julia uses this technique at work, but it is easy to review again and get the idea.

Follow up 

Dec.16, 2017

I asked my mock interview partner to work on this algorithm together, and then we had some discussion. Here are the notes.

The input from the peer:

32 - Each integer has 32 bits

%256 - how to extract rightmost 8 bits?
/256   - move to next 8 bits
>>=8 - or right shift  8 bits

int = int[4] - one integer uses 4 integer

0****** < 128   - check the range
110**** >= 11000000 < 111000000
1110**** >= 11100000 < 11110000
11110*** >- 11110000 < 11111000
10****** >= 10000000 < 11000000

Julia's input:

- integer - bit mask
 set 8 bit - use an integer to represent a set, each integer 8 bits express different numbers

Set bit
A |= 1 << bit

Clear bit
A &= ~(1 << bit)

Test bit
(A & 1 << bit) != 0

Extracting every last bit

Counting out the bits

Apply the bit technique to current case:

test case 1 : (arr[i] & 1 << 7) == 0 - 0xxxxxxx  - figure out the leftmost bit is 0.

test case 2:   arr[i] >> 5 ^ 6  = 0,   judge  110xxxxx 10xxxxxx, there are four operations:
                  AND, OR, negative, XOR ->
The peer came out the idea to shift the first 8 bits to left 5 bits, and then XOR 110, it should be 0.

Reference:

Top coder article about bit manipulation. The link is here.

Editorial notes:

I worked with a peer with strong math and engineering background, the peer works hard; if I share some tips, the peer will come out the solution in less than 5 minutes.

Max Score - RookieRank 3

May 6, 2017


Plan to work on the algorithm: Max Score in next 1 - 2 hours. Time is 5/6/2017, 12:53 pm.

Follow up 

May 7, 2017 9:20am

C# code in the contest is here, scored 3.5 out of 35.

Follow up 

Study the discussion about the solution, the link is here.

1. The following implementation uses memoization, backtracking, and backward processing:

C# practice code is here which passes all test cases.

2. Continue to work on my code submission, change the key of memoization, relax to the sum instead of the string concatenated by various array's element.
Score 14 out of 30, timeout test cases 7 - 10.
C# practice code is here.

3. Bit mask - pass all test cases
C# practice code is here.

Bit manipulation 4 things to review

1. Get integer 2ⁱ:
//use left shift i times,
bitToCheck = 1 <<  i

2. Check ith bit is 1:
// int bitmask
bitmask & bitToCheck

3. Get ith bit:
bitmask |= bitToCheck,

4. Unmask the ith bit:
// backtracking
bitmask &= ~bitToCheck


4. Bit mask - replace the integer using int[], size of array is 20.
May 11, 2017
Timeout on test cases from 6 to 10. Score 10.50 out of 30.
C# practice code is here.
string.Join(",", bitmask) takes too much time.

Julia learned the lesson. Take some time to write bit manipulation instead of using int[]. Bit manipulation expedites the process, use int instead of int[].

5. Continued to work on code written in the contest,
May 12, 2017 11:11 pm
C# practice code is here. Score 10.50, pass test case 0 - 5, and timeout on test case 6 - 10.

Learn when to do memorization, it should be out-of-for-loop, memo on the used HashSet<int>, actually encode all used indexes of the array to a string. Move the memoization from inside for-loop to outside for-loop.

Algorithm analysis

It is most important to come out the recurrence formula for the algorithm. Try to work backwards instead of starting from the first number and forward.

The maximum score of k problem can be solved by choosing any number as the last kth number, and then work on the maximum score of k - 1 problem. Use bitmask as key to do memoization.

Actionable Items

Review previous practice, and find some cases to use bitmask.

Top coder - fun with bits, the article link is here.

Take some notes:
Use bits of an integer to represent a set. Not only does it produce an order-of-magnitude improvement in both speed and size, it can often simplify code at the same time.

Go over the most popular set manipulations in the following:

Set union        
A | B

Set intersection
A & B

Set subtraction
A & ~B

Set negation
ALL_BITS ^ A

Set bit
A |= 1 << bit

Clear bit
A &= ~(1 << bit)

Test bit
(A & 1 << bit) != 0

Extracting every last bit

Counting out the bits

2. Hackerearth.com dynamic programming and bit masking, article link is here.

Leetcode discuss: 698. Partition to K Equal Sum Subsets

 Here is the link. 

Third practice - C# play with bit manipulation solution

Oct. 29, 2020
698. Partition to K Equal Sum Subsets

It is my 30 minutes learning to write a C# solution to apply bit manipulation. I like to learn the design using a simple test case with the array [1, 2, 3, 4] and k = 2.

Case study
I have to go through the debugging using [1, 2, 3, 4] in order for me to understand the code. But somehow I still am not sure why return dp[n - 1].

size = 2^ 4 = 26
dp[0] = true;
total = new int[16];
In order to save subset sum, let us go over the example,
each number in the array take ith bit as 1.

{1}, first number in the array, take first bit, bit expression: 1 -> integer 1, total[1] = 1, dp[1] = true;
{2}, second number in the array, take second bit, bit expression: 10 -> integer 2, total[2] = 2, dp[2] = true;
{3}, third number in the array, take third bit, bit expression: 100 -> integer 4, total[3] = 3, dp[3] = true;
{4}, fourth number in the array, take fourth bit, bit expression: 1000 -> integer 8, total[8] = 4, dp[8] = true;

if(dp[i]) // in other words, there is a subset in binary format, we can tell what subset it is.
dp[5] - 5 can tell the subset {1, 3}, first bit and third bit is found in 5 { binary format: 101}

Debug result:

For example, total[6] = 5, subset {2, 3}, total is 5, bit expression for those numbers are 110.
dp[5] = true, in other words, there is a subset to match 5, {2, 3}.

How to understand dp[10] = false, dp[12] = false?
10 -> 1010 -> subset {2, 4}, sum = 6 > 5, so it is not selected. dp[10] = false;
12 -> 1100 -> subset {3, 4}, sum= 7 > 5, sp it is not selected. dp[12] = false;

Advice
It is better for me to go over a simple test case, so that I can learn from my experience. It should be easy for me to come out design next time.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _698_partition_k_subset___bit
{
    class Program
    {
        static void Main(string[] args)
        {
            var numbers = new int[] { 1, 2, 3, 4 };
            var result = CanPartitionKSubsets(numbers, 2);
        }

        /// <summary>
        /// Oct. 29, 2020
        /// study code
        /// https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/335668/DP-with-Bit-Masking-Solution-%3A-Best-for-Interviews
        /// </summary>
        /// <param name="numbers"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static bool CanPartitionKSubsets(int[] numbers, int k)
        {
            if (numbers == null || numbers.Length == 0)
            {
                return false;
            }
		
		    int n = numbers.Length;
		 
            var size = 1 << n; 

            // quick warmup:
            // set A {1,2,3,4,5}
            // the bitmask 01010 represents the subset {2,4}
            // set ith bit:
            // Let i=0, so, (1<<i) = 00001, 01010 | 00001 = 01011
            // unset ith bit:
            // b & !(1<<i)
            // make sure that I understand the above tutorial before I continue to read the code

		    var dp = new bool[size];
		    var total = new int[size];

		    dp[0] = true;
		
		    int sum = numbers.Sum();
		    
		    Array.Sort(numbers);

            if (sum % k != 0)
            {
                return false;
            }

            // continue to use same variable sum -> 1 of k share
		    sum /= k;
            if (numbers[n - 1] > sum)
            {
                return false;
            }

		    // Loop over power set
            for (int i = 0; i < size; i++) 
            {
			    if(dp[i]) 
                {
				    // Loop over each element to find subset
				    for(int j = 0; j < n; j++) 
                    {
					    // set the jth bit - add jth number in the subset
					    int temp = i | (1 << j);
                        var unvisited = temp != i;

                        if (unvisited)
                        {
                            var current = total[i];
                            var jth = numbers[j];
						    // if total sum is less than target store in dp and total array
                            if (jth <= (sum - (current % sum)))
                            {
                                dp[temp] = true;
                                total[temp] = jth + current;
                            }
                            else
                            {
                                break;
                            }
					    }
				    }
			    }
		    }

		    return dp[size - 1];
        }
    }
}

Swap odd bit and even bit of unsigned 32 bit integer

July 16, 2016

Work on bit manipulation is so much fun. Julia likes to get workout on bit manipulation, and work on the code one by one.

  This blog has everything, but it is hard to know what is going on.
http://juliachencoding.blogspot.ca/2016/07/reverse-unsigned-32-bit-integer.html

For the first step, you would do:

    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);

Julia's comment:  5 minutes workout - how to swap odd bit and even bits?
  5 = 101
How to swap odd bit and even bits?
In other words, odd bit becomes even bit; even bit goes to odd bit

First, odd bit shifts to left; even bit shifts to right.

32 bits: 0101 0101 0101 0101 0101 0101 0101 0101
  all odd bit number in x:
    x & 0x55555555
 left shift 1 bit: 
 (x & 0x55555555) << 1)

So, even bits shift to right; 
  A in bits presentation: 1010 
all even bit number in x:
  x & 0xAAAAAAAA

After the swap, the new value is 
   x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
-- end of Julia's comment --

Reverse unsigned 32 bit integer - facebook code lab - 5+ practice

July 16, 2016

Problem statement:

REVBITS

Reverse bits of an 32 bit unsigned integer

Example 1:

x = 0,

          00000000000000000000000000000000  
=>        00000000000000000000000000000000

return 0

Example 2:

x = 3,

          00000000000000000000000000000011 
=>        11000000000000000000000000000000

return 3221225472

Practice:

Java Practice:
1st practice: 
code is working, but Java code is using Math.pow(2, index).
https://gist.github.com/jianminchen/395ccf0277250e5d3d68498e0d2238f1

2nd practice: not working, error on 32 bit integer, left most significant bit 1 means negative number. 
https://gist.github.com/jianminchen/7bfdcd0c1643bf01c2bf6ba7acea6f70

Sorry, wrong answer. Your program's output doesn't match the expected output. You can try testing your code with custom input and try putting debug statements in your code.

Your submission failed for the following input:

A : 3

Your function returned the following :

-1073741824

The expected returned value :

3221225472

line 11:  ret += 1 << power;
1 is int with 32 bit.
http://stackoverflow.com/questions/1032982/is-a-java-int-always-32-bits

should be: ret += ((long)1) << power;

3rd practice: fail to fix the issue. 
https://gist.github.com/jianminchen/2b753978ffe983600a031a0fcda7b3a6

4th practice: Use bit manipulation - left shift to get 2^n value - code is working

https://gist.github.com/jianminchen/6a5c1ab71b01414f008b22386000ee59

5th practice:

First, study the solution provided by lab, great idea:

Reversing bits could be done by swapping the n/2 least significant bits with its most significant bits.

The trick is to implement a function called swapBits(i, j), which swaps the ‘i’th bit with the ‘j’th bit.

If you still remember how XOR operation works:

here

0 ^ 0 == 0, 
1 ^ 1 == 0, 
0 ^ 1 == 1, and 
1 ^ 0 == 1.

We only need to perform the swap when the ‘i’th bit and the ‘j’th bit are different.

To test if two bits are different, we could use the XOR operation. Then, we need to toggle both ‘i’th and ‘j’th bits.

We could apply the XOR operation again.

By XOR-ing the ‘i’th and ‘j’th bit with 1, both bits are toggled.

Bonus approach (The divide and conquer approach):

Remember how merge sort works? Let us use an example of n == 8 (one byte) to see how this works:

Remember how merge sort works? Let us use an example of n == 8 (one byte) to see how this works:

              01101001

             /        \

           0110       1001

          /   \       /   \

         01    10    10    01

        /\     /\    /\     /\

       0  1   1  0  1  0   0  1

The first step is to swap all odd and even bits. After that swap consecutive pairs of bits, and so on …

Therefore, only a total of log(n) operations are necessary.

Example:

For the first step, you would do:

    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);

Julia's comment:  5 minutes workout - how to swap odd bit and even bits?
  5 = 101
How to swap odd bit and even bits?
In other words, odd bit becomes even bit; even bit goes to odd bit

First, odd bit shifts to left; even bit shifts to right.

32 bits: 0101 0101 0101 0101 0101 0101 0101 0101
  all odd bit number in x:
    x & 0x55555555
 left shift 1 bit: 
 (x & 0x55555555) << 1)

So, even bits shift to right; 
  A in bits presentation: 1010 
all even bit number in x:
  x & 0xAAAAAAAA

After the swap, the new value is 
   x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
-- end of Julia's comment --

study the code in C++:
https://gist.github.com/jianminchen/3526dd68e72ae97563cdd61580052016

Fresh from his first grass court final, @milosraonic is thriving under coach McEnroe.#Wimbledonhttps://t.co/AWVQyfUugI

— Wimbledon (@Wimbledon) June 22, 2016

Leetcode discuss: 1542. Find Longest Awesome Substring

April 12, 2022

Here is the link. 

C# | First position | Bit manipulation | Failed: "9498331" | Lessons learned

April 12, 2022
Introduction
It is a hard level algorithm. I chose to work on it, since I just did solve a similar bit manipulation algorithm 1371. Find the Longest Substring Containing Vowels in Even Counts based on discuss post by votrubac. I chose to work on first position of bit manipulation, and I came cross this failed test case "9498331". I could not solve the issue, and I just could not believe that how others solve the problem but no warning on this first position idea and its bugg issue.

Brute force solution | O(N^2)
It takes O(N^2) to find all substrings, and then it can be calculated to maximum substring to be swapped to a palindrome.

Optimal solution | Hashmap to record count of digits
It is easy to come out the design to use 10 bits to represent 0 to 9 10 digits, even or odd count using 0 or 1 to represent.

Case study | "9498331" | Should return 3, not 4

The following code failed test case: 78 / 153 test cases passed.
Input:
"9498331"
Output: 4
Should be: 3

Lesson learned:
Analysis:
949833
94 - remove 9, so, 4 maps to a number 1<< 4 = 2^4 = 16.
949833 - remove 8, 94933 maps to a number 1 << 4 = 2^4 = 16
first position with 16's index = 1, and the current positon with 16's index = 5, so the answer is 4, but "9833" can not be a palindrome by the option to remove one char.

There are more than two issues in my design using those 10 bits mask to map 0 to 9 10 digits. It took me hours to figure out what is wrong, and how to address the issues.

Faulty design | Save substring with all possible one extra digit into HashMap
I just gave it a quick try without strictly proof that it should work. I even save extra key into HashMap to pad at the end one more digit - any digit from 0 to 9.

I chose to use first position, and then handle extra digit case. It is not easy to figure out so many things in such a short time. Just be patient. Learn from those failed submissions and those failed test cases, and I think that the failures should be best teacher for me. To prepare for Mata onsite in May 2022, I should try 10 hard level algorithms, and learn from all those mistakes in practice. Here is my discuss post related to Meta onsite 30 day preparation.

I should work on last position instead.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1542_find_longest_awesome_substring
{
    class Program
    {
        static void Main(string[] args)
        {
            //var maximumLength = LongestAwesome("3242415");
            //Debug.Assert(maximumLength == 5);

            var max = LongestAwesome("9498331");
            Debug.Assert(max == 3);
        }

        /// <summary>
        /// April 8, 2022
        /// Brute force solution O(N^2) 
        /// find all substrings and then check if it is an awesome substring
        /// Optimal solution should be O(N), go through the array once, and then 
        /// record all digits count in terms of even or odd, using one integer 10 bits 
        /// to contain all 10 bits - left to right, 0 - 9
        /// 
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static int LongestAwesome(string s)
        {
            if (s == null || s.Length == 0)
            {
                return 0;
            }
            
            var map = new Dictionary<int, int>();            

            map.Add(0, -1); //

            var length = s.Length;
            var bitsForDigits = 0;
            var maxLength = 0;

            // 0 ^ 0 = 0
            // 0 ^ 1 = 1
            // 1 ^ 1 = 1  // xor - determine odd or even in each bit
            for (int i = 0; i < length; i++)
            {
                var digit = s[i] - '0';
                bitsForDigits ^= 1 << digit;

                if (!map.ContainsKey(bitsForDigits))
                {
                    map.Add(bitsForDigits, i);
                }
                else
                {
                     maxLength = Math.Max(maxLength, i - map[bitsForDigits]);
                }
                  
                // search odd matching 
                // brute force all digits with 1 - at most 10 cases
                for (int shift = 0; shift <= 9; shift++)
                {
                    // mask one bit
                    if ((bitsForDigits & (1 << shift)) == 0)
                    {
                        continue;
                    }

                    var key = bitsForDigits ^ (1 << shift);  // remove one digit

                    if (!map.ContainsKey(key))
                    {
                        map.Add(key, i);
                    }
                    else
                    {
                        // 949833, remove 4, 99833, but 8's count is odd 
                        //if (key == 0)  // make sure that all digits have even count
                        {
                            maxLength = Math.Max(maxLength, i - map[key]);
                        }
                    }
                }
            }

            return maxLength;
        }
    }
}