014. Longest Common Prefix

Difficulty: Easy

Frequency: N/A

Write a function to find the longest common prefix string amongst an array of strings.


My solution:
Data structure:
string, array
Steps:
Complexity:
Runtime: O(m)
Space: O(1)
Test cases:
Corner cases:
1. empty array
Code:
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string result = "";
        if (strs.size() == 0) return result;
        for (int idx = 0; idx < strs[0].size(); result += strs[0][idx], idx++) {
            for (int v_sz = 1; v_sz < strs.size(); v_sz++) {
                if(idx >= strs[v_sz].size() || strs[v_sz][idx] != strs[0][idx]) {
                    return result.substr(0, idx);
                }
            }
        }
        return result;
    }
};

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

Things to learn:
Advertisements

237. Delete node in a linked list

Difficulty: 

Frequency: 

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.


 

My solution:
Data structure:
list
Steps:
1. Copy the next node to current node
2. Delete next node
Complexity:
Runtime: O(1)
Space: O(n)
Test cases:
Corner cases:
Code:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode *temp = node->next;
        *node = *node->next;
        delete temp;
        temp = NULL;
    }
};



Things to learn:
1. Remember to free the data
 

186. (Locked)Reverse Words in a String II

Difficulty: Medium

Frequency: N/A 

Similar to Question [151. Reverse Words in a String], but with the following constraints:

“The input string does not contain leading or trailing spaces and the words are always separated by a single space.”

Could you do it in-place without allocating extra space?


 

Solution 1:

data structure:

string

steps:

1. reverse the whole string

2. reverse the single word

complexity:

Runtime: O(n)

Space: O(1)

Code:

Challenge:

Rotate an array to the right by k steps in-place without allocating extra space. For instance, with k = 3, the array [0, 1, 2, 3, 4, 5, 6] is rotated to [4, 5, 6, 0, 1, 2, 3].


Things to learn:

170. (Locked)Two Sum III – Data structure design

Difficulty: Easy

Frequency: N/A 

Design and implement a TwoSum class. It should support the following operations: add and find.

add(input) – Add the number input to an internal data structure.
find(value) – Find if there exists any pair of numbers which sum is equal to the value.

For example,
add(1); add(3); add(5); find(4)true; find(7)false


Solution 1:
Data structure:
unordered_map
Complexity:
Time:
add: O(1)
find: O(n) worst case  —->not O(1) ? average
Space: O(n)
Code:

class two_sum {
         unordered_map<int, int> num_count_map;

          void add(int new_num) {
                   if (num_count_map[new_num]) {
                             num_count_map[new_num] = num_count_map[new_num] + 1;
                   } else {
                             num_count_map[new_num] = 1;
                   }
          }

          bool find(int target) {
                   unordered_map<int, int>::iterator map_iter;
                   for (map_iter = num_count_map.begin(); map_iter != num_count_map.end(); map_iter++) {
                             int num_to_find = target - map_iter->first;
                             if (num_count_map.find(num_to_find)) {
                                       if (num_to_find != map_iter->first) {
                                                 return true;
                                       } else {
                                                 if (map_iter->second > 1) {
                                                          return true;
                                                 }
                                       }
                             } else {
                                       return false;
                             }
                    }
          }
}

Things to learn:

163. (Locked)Missing Ranges

Difficulty: Medium

Frequency: N/A

Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], return [“2”, “4->49”, “51->74”, “76->99”]

Example Questions Candidate Might Ask:

Q: What if the given array is empty?
A: Then you should return [“0->99”] as those ranges are missing.

Q: What if the given array contains all elements from the ranges? A: Return an empty list, which means no range is missing.


My solution:
Data structure:
array, list
Steps:
1. For each two adjacent ints in the array(including start – 1 and end + 1), calculate the range
2. how to calculate the range between a and b
  2.1 If b – a == 1, nothing
  2.2 If b – a == 2, return (b + a) /2
  2.3 If b – a > 2, return (a + 1)->(b – 1)
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
[0, 1, 3, 50, 75]
Corner cases:
[]
[0, 1, …, 99]
Code:

class Solution {
public:
    vector<string> findMissingRanges(array<int> vals, int start, int end) {
        vector<string> results;
        int prev = start - 1;
        for (int i = 0; i <= vals.size(); i++) {
            // handle the last element(end)
            int curr = (i == vals.size()) ? end + 1 : vals[i];
            if (curr - prev == 2) {
                results.push_back(to_string(prev + 1));
            } else if (curr - prev > 2) {
                string val = to_string(prev + 1) + "->" + to_string(curr - 1);
                results.push_back(val);
            }
            prev = curr;
        }
        return results;
    }
}

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

Things to learn:
1. It is very import to unify the problem, then do not need to handle special case
2. Need to know handy c++ functions

161. (Locked)One Edit Distance

Difficulty: Medium

Frequency: N/A

Given two strings S and T, determine if they are both one edit distance apart.

 


My solution:
Data structure:
string
Steps:
1. compare the size of S and T.
1.1 If s.size() == t.size(), there should be only one replace operation
1.2 If s.size() – t.size() == 1, or t.size() – s.size() == 1, one insertion or deletion
1.3. otherwise, return false.
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
“” “”
“a” “”
“a” “b”
Code:

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size() < t.size()) s.swap(t);
        if (s.size() - t.size() > 1)
            return false;
        int distance = 0;
        for (int i = 0, j = 0; i < s.size(); i++, j++) {
            if (s[i] == t[j]) continue;
            else if (distance > 1) return false;
            else {
                distance++;
                i = s.size() > t.size() ? i++: i;
            }
        }
        return true;
    }
}

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

Things to learn:
1. By calling the function itself, you can swap the input parameters.