Wednesday, January 6, 2021

Leetcode discuss: 158. Read N Characters Given Read4 II - Call multiple times

 Here is the link. 

First practice - C# - Failed - Test case

Dec. 31, 2020
Introduction
I spent over 30 minutes to work on the algorithm in my mock interview. I could not figure out how to solve failed test case in limited time constraint. I will follow up with ideas how to fix it later.

Failed test case
63/81
Input:
"abc"
[1,2,1]
Output:
["a","b","c"]
Expected:
["a","bc",""]

Follow up
Jan. 5, 2020

  1. Trouble shooting, Read function, first if statement should be a while loop.
  2. In Read function, do not change variable n's value, make a copy of n and work on while loop.
  3. It is important to be patient, actually I wrote a simulation for me to debug the code. I learned a few things through this Facebook mock onsite interview algorithm.
/**
 * The Read4 API is defined in the parent class Reader4.
 *     int Read4(char[] buf4);
 */

public class Solution : Reader4 {
    private List<char> buffer = new List<char>(); 
    
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    public int Read(char[] buf, int n) {
        // read 5, twice, first one 4, second one
        // read 5, twice, first one 4, second 4 - but only save 5        
        
        var index = 0; 
        
        // read from buffer <- leave n unchange, declare a copy variable: copy = n; work on copy
        if(buffer.Count > 0 && n > 0) // <- this should be while statement - added on Jan. 5, 2020
        {
            buf[index++] = buffer[0];
            buffer.RemoveAt(0);
            n--; 
        }
        
        var totalTimes = (n + 3)/ 4; 
        
        for(int i = 0; i < totalTimes; i++)
        {
            var tmp = new char[4];
            var actual = Read4(tmp);            
           
            for(int j = 0; j < actual; j++)    
            {
                if(index < n)  // <- this requires that n should not be changed. Added on Jan. 5, 2020
                {
                    buf[index++] = tmp[j];    
                }
                else
                {
                    buffer.Add(tmp[j]);
                }
            }
            
            if(actual != 4)
            {
                break; 
            }            
        }
        
        return index; 
    }
}

No comments:

Post a Comment