Still tagged hard, huh? My approach to this problem, with tests


  • 3

    First I thought, "What? That's impossible! If I am only allowed to read 4 characters, how on Earth am I going to read less than that?" Then I realized that nowhere does it say that I'm not allowed to buffer data. Then I made a ridiculously simple solution of 15 lines which wasn't accepted because of one stupid mistake that caused compilation error. After fixing that, it was accepted all right. Took me about 5 minutes or so.

    So what is "hard" about this? This is not just easy, this is ridiculously easy. Even simple atoi() problems are much harder because there are many ways you can screw up that.

    OK, here is an update. I'm going to show how my approach to this problem. Instead of starting with the tests (TDD style), I start with a class skeleton. The time is 44 minutes, forget about hours and time zones.

    I create a class and copy the code there. Then add the read4 function. It looks like this:

    public abstract class Read4 {
    
        public int read(char[] buf, int n) {
            return 0;
        }
    
        abstract int read4(char[] buf);
    }
    

    Instead of inheriting a non-existent class, I will inherit it in the test. No big deal since I'm going to copy only the relevant part to submit it. OK, here's a test skeleton (using TestNG and AssertJ):

    char[] data;
    
    @Test(dataProvider = "data")
    public void read(String data, List<Integer> reads, List<String> expecteds) {
        this.data = data.toCharArray();
        Read4 read4 = new TestingRead4();
        for (int i = 0; i < reads.size(); ++i) {
            int len = reads.get(i);
            char[] expected = expecteds.get(i).toCharArray();
            char[] buf = new char[len];
            int read = read4.read(buf, len);
            assertThat(read).as("i = " + i).isEqualTo(expected.length);
            assertThat(Arrays.copyOf(buf, read)).as("i = " + i).isEqualTo(expected);
        }
    }
    
    @DataProvider
    public Object[][] data() {
        return new Object[][] {
            {"", Arrays.asList(0), Arrays.asList("")},
        };
    }
    
    private class TestingRead4 extends Read4 {
        private int index = 0;
    
        @Override
        int read4(char[] buf) {
            int read = Math.min(data.length - index, 4);
            System.arraycopy(data, index, buf, 0, read);
            index += read;
            return read;
        }
        
    }
    

    The time is 54 minutes. OK, now instead of trying to come up with simplest code, I'll try to get the cleanest code and then move on from that. That's what is not exactly TDD, but screw TDD.

    The time is 8 minutes. The code looks like this:

    private final char[] buffer = new char[4];
    private int lenOfDataInBuffer = 0;
    private int posInBuffer = 0;
    
    public int read(char[] buf, int n) {
        int read = 0;
        while (read < n) {
            fillBufferIfNeeded();
            if (remainingInBuffer() == 0)
                break;
            read += readFromBuffer(buf, read, n - read);
        }
        return read;
    }
    
    private void fillBufferIfNeeded() {
        if (remainingInBuffer() == 0) {
            lenOfDataInBuffer = read4(buffer);
            posInBuffer = 0;
        }
    }
    
    private int remainingInBuffer() {
        return lenOfDataInBuffer - posInBuffer;
    }
    
    private int readFromBuffer(char[] buf, int offset, int n) {
        int toRead = Math.min(n, remainingInBuffer());
        System.arraycopy(buffer, posInBuffer, buf, offset, toRead);
        posInBuffer += toRead;
        return toRead;
    }
    

    It didn't take me much refactoring to get to it. I was just writing my thoughts in Java, creating private functions as needed. I only had to rename a few methods and variables in the end because my lenOfDataInBuffer was called bufferSize and remainingInBuffer was called dataInBuffer which didn't make much sense as I was reading it afterwards.

    Well, it's time to try to break it. Hmm... it passes all these tests:

            {"", Arrays.asList(0), Arrays.asList("")},
            {"", Arrays.asList(1, 1), Arrays.asList("", "")},
            {"a", Arrays.asList(1, 1), Arrays.asList("a", "")},
            {"a", Arrays.asList(2), Arrays.asList("a")},
            {"ab", Arrays.asList(1, 1), Arrays.asList("a", "b")},
            {"abcde", Arrays.asList(1, 4), Arrays.asList("a", "bcde")},
            {"abcde", Arrays.asList(2, 3), Arrays.asList("ab", "cde")},
            {"abcde", Arrays.asList(3, 2), Arrays.asList("abc", "de")},
            {"abcde", Arrays.asList(4, 1), Arrays.asList("abcd", "e")},
            {"abcde", Arrays.asList(5), Arrays.asList("abcde")},
            {"abcdef", Arrays.asList(3, 3), Arrays.asList("abc", "def")},
            {"123456789", Arrays.asList(10, 10), Arrays.asList("123456789", "")},
    

    The time is 13 minutes now. Well, let's submit it. Yay! It's accepted. The total time is about half an hour, and that includes the time needed to write this update because I was writing it as I was coding.


  • 0
    C

    If it's easy for you. Can you share your code and point out why the following is wrong?

    Thanks

    int read(char *buf, int n) {
            
            int  currPos = 0; 
            bool bNoMoreData = false; 
            for (int i=0; i<n/4; i++)
            {
                int tempNum = read4(buf+currPos);
                currPos += tempNum; 
                if (tempNum<4)
                {
                    bNoMoreData = true; 
                    break;
                }
            }
            if (!bNoMoreData)
            {
                char tempBuf[4];
                int tempNum = read4(tempBuf);
                int rest = n%4;
                int finalNum = tempNum>rest? rest : tempNum;
                memcpy(buf+currPos, tempBuf, finalNum);        
                currPos += finalNum; 
             }
             return currPos;        
        }

  • 0

    No point in sharing my code since there is a lot of solutions already. As for yours, your read() will not continue reading when called a second time and so on because some of the data you read may be inevitably lost. You need to store your buffer somewhere and continue reading from the buffer where you stopped last time. It's a typical buffered reading.


  • 0
    M

    K, now we know you are good.


  • 0

    Okay, now we know you are genius.


  • 0
    D

    now we know you are smart


  • 0
    K

    let's not be sarcastic... it's simpler than the average hard problem i think


  • 0

    My point exactly. If it was tagged medium, I would still think it's too much, but I wouldn't make any fuss about it. But hard? On LeetCode hard usually means hours of trying to solve the problem and wondering how on Earth is it possible to do it within the 30 minutes limit! But this! Buffering? Hard? Really?


  • 0
    M

    Could you lend me a thought on this?

    I've spent days looking at the the following piece of code.
    It's far from a concise solution.
    But, what on earth is wrong?
    I've been putting it in IDE and test it. But it's just not passing on leetcode.

    Input:
    "ab"
    [read(1),read(2)]
    Output:
    ["a","a"]
    Expected:
    ["a","b"]

    /* The read4 API is defined in the parent class Reader4.
          int read4(char[] buf); */
    
    public class Solution extends Reader4 {
        
        int globalIndex = 0; //start of next read
        char[] holder = null;
        boolean eof = false;
        //char[] buff;
        
        /**
         * @param buf Destination buffer
         * @param n   Maximum number of characters to read
         * @return    The number of characters read
         */
        public int read(char[] buf, int n) {
            int totalNumsRead = 0; //start of next read
            
            if (n == 0 || (eof == true && holder == null)) {
                return 0;
            }
    
            //read4 til end of file or n whichever comes first
            while(true) {
                
                char[] temp = new char[4];
                int totalNumsLeft = n - totalNumsRead;
                int toRead = Math.min(totalNumsLeft, 4);  //nums to read in this iteration
                
                if (holder != null) { //read from holder
                    int len = holder.length;
                    if (len < toRead) { 
                        //read all from holder, update nums read
                        System.arraycopy(holder,0,buf,globalIndex,len);
                        totalNumsRead = totalNumsRead + len;
                        toRead -= len;
                        globalIndex += len;
                        holder = null;
                        if (eof) {
                            return len;
                        }
                    } else if (len > toRead) {
                        //read part from holder, update nums and return
                        System.arraycopy(holder,0,buf,globalIndex,toRead);
                        totalNumsRead = totalNumsRead + toRead;
                        globalIndex += toRead;
                        char[] holderTemp = new char[len-toRead];
                        for (int i = 0; i < len-toRead; i++) {
                            holderTemp[i] = holder[toRead+i];
                        }
                        holder = holderTemp;
                        return toRead;
                        
                    } else {
                        //read all from holder, update nums read and return
                        System.arraycopy(holder,0,buf,globalIndex,len);
                        totalNumsRead = totalNumsRead + len;
                        globalIndex += len;
                        holder = null;
                        return len;
                    }
                }
                
                int actualRead = read4(temp);  //read file into temp
                if (actualRead < 4) {
                    eof = true;
                }
                int validRead = Math.min(toRead, actualRead); 
                
                if (validRead < actualRead) {  //update holder if needed
                    int holding = actualRead - validRead;
                    holder = new char[holding];
                    System.arraycopy(temp,validRead,holder,0,holding);
                }
                
                totalNumsRead = totalNumsRead + validRead;   
                
                for (int i = 0; i < validRead; i++) {
                    buf[globalIndex+i] = temp[i];
                }
                globalIndex += validRead;
    
                if (validRead < 4) {
                    break;
                }
          }
          return totalNumsRead;
        }
        
    }

  • 0

    @mylemoncake Besides the obvious overwhelming complexity of this code, there is one major problem. The globalIndex variable looks like it is there to remember the last position in the output buffer. Well, it's not how a typical reading API works. You're supposed to assume that the output buffer is a new one each time, so you have to start with index 0, not from where you stopped last time. Because the buffer size for the second call is 2, you happily write 'b' at index 1, but the OJ checks at index 0.

    See my update for some ideas on how to approach this kind of problems.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.