159. (Locked)Longest Substring with At Most Two Distinct Characters

Difficulty: Hard

Frequency: N/A

Given a string S, find the length of the longest substring T that contains at most two distinct characters.

For example,
Given S = “eceba”,
T is “ece” which its length is 3.


Solution 1:
Data structure:
string, unordered_map
Steps:
1. Loop through the string using head and tail index to keep a sliding window.
2. For each char in the string
  2.1 If it is not in the map, insert it, num_distinct++
  2.2 map[s[tail]]++
  2.3 while (num_distinct > 2) map[s[head]]–
    2.3.1 If map[s[head]] == 0, num_distince–
    2.3.2 head++
  2.4 max_length = max(tail – head + 1, max_length)
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
Corner cases:
Code:
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int max_length = 0, head = 0, num_distinct = 0;
        unordered_map<char, int> count_map;
        for (int tail = 0; tail < s.size(); tail++) {
            if (!count_map.count(s[tail])) {
                num_distinct++;
            }
            count_map[s[tail]]++;
            while (distinct > 2) {
                count_map[s[head]]--;
                if (!count_map.count([s[head]]))
                    num_distinct--;
                i++;
            }
            max_length = max(max_length, tail - head + 1);
        }
        return max_length;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

013. Roman to Integer

Difficulty: Easy

Frequency: N/A

My solution:
Data structure:
unordered_map,string
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:
class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> roman_map = {{'I', 1},
                                              {'V', 5},
                                              {'X', 10},
                                              {'L', 50},
                                              {'C', 100},
                                              {'D', 500},
                                              {'M', 1000}};
        int result = 0;
        for (int i = 0; i < s.size(); i++) {
            if (i != s.size() && roman_map[s[i]] < roman_map[s[i + 1]]) {
                result -= roman_map[s[i]];
            } else {
                result += roman_map[s[i]];
            }
        }
        return result;
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

158. (Locked)Read N Characters Given Read4 II – Call multiple times

Difficulty: Hard

Frequency: N/A

Similar to Question [15. Read N Characters Given Read4], but the read function may be called multiple times.


My solution:
Data structure:
array
Steps:
1. Read from the internal buffer
2. Read from file
3. Push the superfluous to the internal buffer
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:

class Solution {
private:
    queue<char> leftover;

public:
    int read(char *buf, int n) {
        int read_sz = 0, actual_sz = 0;

        // Read from the leftover
        while (!leftover.empty()) {
            if (actual_sz == n) return actual_sz;
            buf[actual_sz++] = leftover.front();
            leftover.pop();
        }

        // Read from the file
        while (actual_sz < n) {
            read_sz = read4(buf + actual_sz);
            actual_sz += read_sz;
            if (read_sz < 4) break;
        }

        // Push the leftover the queue
        if (actual_sz < n) {
            for (int i = n; i < actual_sz; i++) {
                leftover.push(buf[i]);
            }
        }

        int end = min(actual_sz, n);
        buf[end] = '\0';
        return end;
    }
}


Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
code:

Things to learn:

157. (Locked)Read N Characters Given Read4

Difficulty: Easy

Frequency: N/A

The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there

is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note: The read function will only be called once for each test case.


My solution:
Data structure:
array
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
1. total length 102, try to read 103
2. total length 102, try to read 101
Code:

class Solution {
public:
    int read(char *buf, int n) {
        int total = 0;
        bool eof = false;
        while (!eof && total < n) {
            int read_sz = read4(buf);
            if (return_sz < 4) eof = true;
            int need_size = min(read_sz, n - total);           
            total = total + need_size;
            buf = buf + need_size;
        }
        return total;
    }
}

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

151. Reverse Words in a String

Difficulty: Medium

Frequency: High 

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Clarification:

  • What constitutes a word?
    A sequence of non-space characters constitutes a word.
  • Could the input string contain leading or trailing spaces?
    Yes. However, your reversed string should not contain leading or trailing spaces.
  • How about multiple spaces between two words?
    Reduce them to a single space in the reversed string.

My solution:

data structure:

string

steps:

loop through the string in a reversed order.

1. append the word

2. append a space if there is a word followed

complexity:

Runtime: O(n)

Space: O(n)

 

Code:

class Solution {
public:
    void reverseWords(string &s) {
        int end = s.size();
        string temp;
        for (int i = end - 1; i >= 0; i--) {
            if (s[i] == ' ') {
                end = i;
            } else if (i == 0 || s[i - 1] == ' ') {
                if (!temp.empty()) {
                    temp.append(1, ' ');
                }
                temp.append(s.substr(i, end - i));
            }
        }
        s = temp;
    }
};



 

Things to learn:

125. Valid Palindrome

Difficulty: Easy

Frequency: Medium 

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.


My solution:
data structure:
string
steps:
complexity:
Runtime: O(n)
Space: O(1)
Code:
 

class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0, j = s.size() - 1;

        while (i < j) {
            if (!isalnum(s[i])) {
                i++;
                continue;
            }

            if (!isalnum(s[j])) {
                j--;
                 continue;
            }

            if (tolower(s[i]) == tolower(s[j])) {
                i++;
                j--;
            } else {
                return false;
            }
        }
         return true;
    }
};


Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

class Solution {
public:
    bool isPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
            while (!isalnum(s[i]) && i < j) i++;
            while (!isalnum(s[j]) && i < j) j--;
            if (tolower(s[i]) != tolower(s[j])) return false;
        }
        return true;
    }
};


Things to learn:

065. Valid Number

Difficulty: Easy

Frequency: Low

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Example Questions Candidate Might Ask:

Difficulty: Easy, Frequency: Low

Q: How to account for whitespaces in the string?
A: When deciding if a string is numeric, ignore both leading and trailing whitespaces.

Q: Should I ignore spaces in between numbers – such as “1 1”?
A: No, only ignore leading and trailing whitespaces. “1 1” is not numeric.

Q: If the string contains additional characters after a number, is it considered valid?

A: No. If the string contains any non-numeric characters (excluding whitespaces and decimal point), it is not numeric.

Q: Is it valid if a plus or minus sign appear before the number? A: Yes. “+1” and “-1” are both numeric.

Q: Should I consider only numbers in decimal? How about numbers in other bases such as hexadecimal (0xFF)?

A: Only consider decimal numbers. “0xFF” is not numeric.

Q: Should I consider exponent such as “1e10” as numeric?
A: No. But feel free to work on the challenge that takes exponent into consideration. (The Online Judge problem does take exponent into account.)


My solution:
Data structure:
string
Steps:
1. Ignore leading spaces
2. Handle the string before ‘e’
  2.1 ‘+’ ‘-‘ is ok
  2.2 Handle ‘.’
  2.3 Handle digit
  2.4 All the other characters are invalid
3. Handle the string after ‘e’
  3.1 ‘+’ ‘-‘ is ok
  3.2 Handle digit
  3.3 All the other characters are invalid
4. Ignore the trailing spaces
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
“234”=> true
“-234” => true
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Corner cases:
. => false
e => false
+ => false
.5 => true
5. => true
e5 =>false
5e =>false
2.5.6 =>false
2ee6 =>false
2e-6 =>true
2E6 => false
2e.6 => false
2.e6 => true
Code:
class Solution {
public:
    bool isNumber(string s) {
        bool ret = false;
        // ignore the leading spaces
        int i = s.find_first_not_of(' ');

        // handle the string before 'e': '+' '-' at beginning is ok, '.' is ok.
        if (i < s.size() && s[i] == '+' || s[i] == '-') {
            i++;
        }
        while (i < s.size() && isdigit(s[i])) {
            i++;
            ret = true;
        }

        if (i < s.size() && s[i] == '.') {
            i++;
            while (i < s.size() && isdigit(s[i])) {
                i++;
                ret = true;
            }
        }
        // handle 'e'
        if (ret && i < s.size() && s[i] == 'e') {
            i++;
            ret = false;
            // handle the string after 'e': '+' '-' at beginning is ok
            if (i < s.size() && s[i] == '+' || s[i] == '-') {
                i++;
            }
            while (i < s.size() && isdigit(s[i])) {
                i++;
                ret = true;
            }
        }

        // ignore the trailing spaces
        while (i < s.size() && isspace(s[i])) {
            i++;
        }

        return ret && i == s.size();
    }
};

Things to learn:
1. Implement after clarification.