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.
 

028. Implement strStr()

Difficulty: Easy

Frequency: High 

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.


My solution:
data structure:
string
steps:
Complexity:
Runtime: O(nm)
Space: O(1)
Code:
class Solution {
public:
    int strStr(string haystack, string needle) {
        int h_size = haystack.size(), n_size = needle.size();
        if (h_size < n_size) return -1;
        if (n_size == 0) return 0;
        for (int start = 0; start + n_size - 1 < h_size; start++) {
            for (int i = 0, j = start; i < n_size; i++, j++) {
                if (haystack[j] != needle[i]) {
                    break;
                }
                if (i == n_size - 1) return start;
            }
        }
        return -1;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int strStr(string haystack, string needle) {
        for (int i = 0; ; i++) {
            for (int j = 0; ; j++) {
                if (j == needle.size()) return i;
                if (i + j == haystack.size()) return -1;
                if (needle[j] != haystack[i + j]) break;
            }
        }
    }
};

Things to learn:

008. String to Integer (atoi)

Difficulty: Easy

Frequency: High

Implement atoi to convert a string to an integer.
Requirements for atoi:The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.


My solution:
Data structure:
string
Steps:
Loop through the string
1. Decide whether it is positive or negative
2. Find the all the digits
3. If the result > MAX or result < MIN, return MAX or MIN
4. stop when encounter non-digit
 
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
24980
+24980
-24980
Corner cases:
1. empty string: ” “
2. no digit in string: sda
3. digit and other characters mixed: +54ab8, ft-50a
4. leading or trailing space
4. INT_MAX(2147483647) and INT_MIN(-2147483648)
Code:
class Solution {
public:
    int myAtoi(string str) {
        long result = 0;
        bool negative = false;
        bool valid = false;
        for (int i = 0; i &lt; str.size(); i++) {
            if (isspace(str[i]) &amp;&amp; !valid) {
                continue;
            } else if (str[i] == '-' &amp;&amp; !valid) {
                negative = true;
                valid = true;
            } else if (str[i] == '+' &amp;&amp; !valid) {
                valid = true;
            } else if (isdigit(str[i])) {
                valid = true;
                result = result * 10 + (str[i] - 48);
                if (!negative &amp;&amp; result &gt; INT_MAX) {
                    return INT_MAX;
                } else if (negative &amp;&amp; -result &lt; INT_MIN) {
                     return INT_MIN;
                }
            } else {
                break;
            }
        }
        return (int)(negative? -result: result);
    }
};

Another solution:
Data structure:
string
Steps:
1. Find the first non-space character
2. Decide the sign
Complexity:
Runtime: O(n)
Space: O(n)
Code:
class Solution {
public:
    int myAtoi(string str) {
        int ret = 0, sign = 1, i = str.find_first_not_of(' '), base = INT_MAX / 10;
        if (str[i] == '+' || str[i] == '-')
            sign = str[i++] == '+' ?: -1;
        while (isdigit(str[i])) {
            if (ret &gt; base || (ret == base &amp;&amp; str[i] - '0' &gt; INT_MAX%10))
                return sign &gt; 0 ? INT_MAX : INT_MIN;
            ret = 10 * ret + (str[i++] - '0');
        }
        return sign * ret;
    }
};

Things to learn:
1. using int sign = 1, not bool negative = false;
2. how to handle overflow in conversion
3. using c++ function to simplify code/logic, ex: find_first_not_of
4. convert char to int: -‘0’
5. conditional operator: default is 1 for the first result

005. Longest Palindromic Substring

Difficulty: Medium

Frequency: Medium

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Test cases:
1. a
2. aa
3. aaa
4. aba
5. abba

Solution 1:

Data structure:
string
Method:
Two pointers
Steps:
1. For each center, expand and test whether it is a palindrome and then record its length if it is the current max.
Complexity:
Runtime: O(n^2) 168 ms
Space: O(1)
Code:
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) return s;
        string result;
        for (int i = 0; i < 2 * n - 1; i++) {
            int left = i / 2 - (i + 1) % 2, right = i / 2 + 1;
            while (left >= 0 && right < n) {
                if (s[left] != s[right]) break;
                else {
                    left--;
                    right++;
                    result = result.size() < right - left - 1 ? s.substr(left + 1, right - left - 1): result;
                }
            }
        }
        return result;
    }
};

Solution 2:
Data structure:
string
Method:
Manacher’s algorithm
steps:
see links.
Complexity:
Runtime: O(n) 16 ms
Space: O(n)
Code:
class Solution {
public:
    string longestPalindrome(string s) {
        string t;
        for (int i = 0; i < s.size(); i++) {
            t += "#" + s.substr(i, 1);
        }
        t.push_back('#');
        
        vector<int> p(t.size(), 0);
        int center = 0, boundry = 0, maxLen = 0, resCenter = 0;
        for (int i = 1; i < t.size() - 1; i++) {
            int iMirror = 2 * center - i;
            p[i] = boundry - i > 0 ? min(boundry - i, p[iMirror]) : 0;
            // expand p[i]
            while (i - 1 - p[i] >= 0 && i + 1 + p[i] <= t.size() - 1 && t[i - 1 - p[i]] == t[i + 1 + p[i]]) {
                p[i]++;
            }
            // update center and boundry
            if (p[i] + i > boundry) {
                boundry = p[i] + i;
                center = i;
            }
            if (p[i] > maxLen) {
                maxLen = p[i];
                resCenter = i;
            }
        }
        return s.substr((resCenter - maxLen) / 2, maxLen);
    }
};

Submission errors:
1. seg fault. Need to be careful with the range.
2. TLE. Solution is not good enough.

Things to learn:

1. When need to handle even and odd in string or array, examples will help.
2. Manacher’s algorithm is quite interesting, but don’t know whether it is useful for other problems.

003. Longest Substring Without Repeating Characters

 Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Questions:

1. upper case and lower case characters are same or not?

2. whether there is only 1 solution.


Test cases:

1. empty string
2. a
3. bbbbbb
4. abcabcbcbb: dup is in the window
5. tmmzuxt: dup is not in the window

Solution 1:

Data structure:
string, unordered_map
Method:
two pointers, hash table
Steps:
1. loop through the string using head and tail, for each char
  2.1 fix head, move tail
  2.1 if it is not in the hash map, insert(char, index)
  2.2 if it is in the hash map, and index >= head, move head to old_index + 1, and replace with new index,
  2.2 max_length = max(max_length, tail – head + 1)
Complexity:
runtime: O(N)
space: O(N)
Code:
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        if (!n) return 0;
        unordered_map<char, int> m;
        int head = 0, tail = 0, result = 0;
        while (tail < n) {
            if (m.find(s[tail]) != m.end() && m[s[tail]] >= head) {
                    head = m[s[tail]] + 1;
            }
            m[s[tail]] = tail;
            result = max(result, tail - head + 1);
            tail++;
        }
        return result;
    }
};

Solution 2:
Data structure:
string, array
Method:
two pointers
Steps:
same with Method 1, but using array instead of unordered_map.
Complexity:
runtime: O(N)
space: O(N)
Code:
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        if (!n) return 0;
        vector<int> m(256, -1);
        int head = 0, tail = 0, result = 0;
        while (tail < n) {
            head = max(head, m[s[tail]] + 1);
            m[s[tail]] = tail;
            result = max(result, tail - head + 1);
            tail++;
        }
        return result;
    }
};

Submission errors:

1. wrong answer. Did not consider the case that dup is not in the window.

Things to learn:
1. good test case can help find bug.
2. when input range is known, we can use array instead of hash map to improve the performance.
3. the ASCII table has 128 characters, with values from 0 through 127. Thus, 7 bits are sufficient to represent a character in ASCII; however, most computers typically reserve 1 byte, (8 bits), for an ASCII character.

002. Add Two Numbers

Difficulty: Easy

Frequency: High 

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8


Test cases:

1. both empty
2. one empty
3. both single digit
4. same length
5. different length
6. last digit has carry

Solution 1:
Data structure:
linked list
Method:
Math
Steps:
1. Add two node from beginning to the end
2. handle extra digit
Complexity:
Runtime: O(n) 36 ms
Space: O(n)
Code:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0), *cur = dummy;
        int extra = 0;
        while (l1 || l2 || extra) {
            if (l1) {
                extra += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                extra += l2->val;
                l2 = l2->next;
            }
            cur->next = new ListNode(extra % 10);
            extra /= 10;
            cur = cur->next;
        }
        return dummy->next;
    }
};

Submission errors:

1. Segmentation fault due to null pointer.

Things to learn:

1. Try to write more concise code, ex. using conditional operator instead of if else.
2. Using dummy head for linked list can simplify code.

001. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].


Questions:

1. whether there is only one solution if the question does not declare it.


Test Cases:

1. [2, 7, 11, 15] 9
2. [11, 2, 15, 7] 9
3. [2, 7] 9
4. [2, 4, 4, 3] 8

Solution 1:
Data structure:
array, unordered_map
Method:
hash table
Steps:
1. for each number, lookup target-number in the hash table
2. if it is in the hash table, return result, else insert it in the hash table.
Complexity:
runtime: O(N)
space: O(N)
Code:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
       unordered_map<int, int> my_map;
       vector<int> res;
       for (int i = 0; i < nums.size(); i++) {
           int numToFind = target - nums[i];
           if (my_map.find(numToFind) != my_map.end()) {
               res.push_back(my_map[numToFind]);
               res.push_back(i);
               return res;
           }
           my_map[nums[i]] = i;
       }
       return res;
    }
};

Solution 2:

Data structure:
array
Method:
two pointers
Steps:
1. copy out the array
2. sort the array
3. iterate from beginning and end, and find the two integers
4. iterate through the original array, and find the two indexes
Complexity:
runtime: O(NlogN)
space: O(N)
Code:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> cp(nums);
        sort(cp.begin(), cp.end());
        vector<int> results;
        int n = nums.size();
        if (!n) return results;
        int left = 0, right = n - 1;
        while (left < right) {
            if (cp[left] + cp[right] == target) break;
            else if (cp[left] + cp[right] < target) left++;
            else right--;
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] == cp[left]) results.push_back(i);
            else if (nums[i] == cp[right]) results.push_back(i);
            if (results.size() == 2) break;
        }
        return results;
    }
};

Solution 3:

Data structure:
array
Method:
brute force
Steps:
1. two nested loops to find the two nums.
Complexity:
runtime: O(N^2)
space: O(1)
Code:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> results;
        int n = nums.size();
        if (!n) return results;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    results.push_back(i);
                    results.push_back(j);
                    return results;
                }
            }
        }
        return results;
    }
};

Things to learn:
1. copy an array: vector cp(nums).
2. the element using iterator: iter = num.end() – 1
3. unordered_map.find() complexity: average constant, worst linear.