Get the Previous Character in a Stream - Nerd Paradise : Coding Interview 12

Nerd Paradise : Coding Interview 12: Get the Previous Character in a Stream
Suppose you have an array of bytes. Implement a stream with the following methods:

bool HasNext()
char GetNext()
bool HasPrevious()
char GetPrevious()

However, there is a catch. These characters can be 16 bit. The way to tell if a character is 16 bit is if the first byte of a pair of bytes has a 1 as the first bit.

Do not allocate more memory than necessary.
Do not modify the bytes array.

public bool HasNext()
{
    return this.index < this.bytes.Length;
}

public bool GetNext()
{
    int charValue = this.bytes[this.index++];
    if ((charValue & 0x80) != 0)
    {
        charValue = (charValue << 8) + this.bytes[this.index++];
    }
    return (char)charValue;
}
public bool HasPrevious()
{
    return this.index > 0;
}

public bool GetPrevious()
{
    int charValue = this.bytes[--this.index];
   
    ...
}

Getting the previous byte before this.index is easy. And then if it begins with a 1, then it's obvious that this is the 2nd byte of a 2-byte character, because the index can't be pointing between two characters. However, if it's a 0, then it doesn't necessarily mean it's a one-byte character. It could be the 2nd byte of a 2-byte character that happens to begin with a 0. 

• If you find the beginning of the array, that's a beginning of a character.
• If you find a zero anywhere you can't say anything about whether it's the only byte in the character or if it's the 2nd byte of a 2-byte character, but you can definitively say that the byte after it MUST be the start of a new character.

// Helper methods are unbelievable helpful during whiteboard interviews. 
// They save writing and in the even that you crash and burn and have to
// erase your main function and start over, you get to keep your helper 
// function which hopefully will be useful in your 2nd attempt as well. 
private bool BeginsWith1(int index)
{
    return (this.bytes[index] & 0x80) != 0;
}

private char GetCurrent()
{
    int value = this.bytes[index];
    if (this.BeginsWith1(this.index))
    {
        value = (value << 8) + this.bytes[index + 1];
    }
    return (char) value;
}

public char GetPrevious()
{
    int index = --this.index;

    // if the previous byte begins with a 1, you know for certain
    // that it's the 2nd byte of a 2-byte character
    if (this.BeginsWith1(index))
    {
        --this.index;
        return this.GetCurrent();
    }

    // ...but if it's a 0, then it could mean anything. 

    int characterBeginsAt = -1;

    // Using the 2 rules stated above, trace backwards and find the first point
    // where we can definitively say a character begins.
    while (characterBeginsAt == -1)
    {
        if (index == 0)
        {
            characterBeginsAt = 0;
        }
        else if (!this.BeginsWith1(index - 1))
        {
            characterBeginsAt = index;
        }
        --index;
    }

    // Once you find a point where a character begins, use the first-bit rules
    // to trace back to the current index to determine where the previous byte begins. 
    while (true)
    {
        if (characterBeginsAt == this.index)
        {
            return this.GetCurrent();
        }
        else if (characterBeginsAt == this.index - 1)
        {
            if (this.BeginsWith1(this.index - 1))
            {
                --this.index;
                return this.GetCurrent();
            }
        }

        characterBeginsAt += this.BeginsWith1(this.index) ? 2 : 1;
    }
}
Read full article from Nerd Paradise : Coding Interview 12: Get the Previous Character in a Stream