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&lt;string&gt;&amp; strs) {
string result = &quot;&quot;;
if (strs.size() == 0) return result;
for (int idx = 0; idx &lt; strs.size(); result += strs[idx], idx++) {
for (int v_sz = 1; v_sz &lt; strs.size(); v_sz++) {
if(idx &gt;= strs[v_sz].size() || strs[v_sz][idx] != strs[idx]) {
return result.substr(0, idx);
}
}
}
return result;
}
};

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

Things to learn:

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-&gt;next;
*node = *node-&gt;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,

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

class two_sum {
unordered_map&lt;int, int&gt; 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&lt;int, int&gt;::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-&gt;first;
if (num_count_map.find(num_to_find)) {
if (num_to_find != map_iter-&gt;first) {
return true;
} else {
if (map_iter-&gt;second &gt; 1) {
return true;
}
}
} else {
return false;
}
}
}
}

Things to learn:

167. (Locked)Two Sum II – Input array is sorted

Difficulty: Medium

Frequency: N/A

Similar to Question [1. Two Sum], except that the input array is already sorted in ascending order.

solution 1:
For each element, do a binary search in the array

solution 2:
Two pointers. Same with 001.

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&lt;string&gt; findMissingRanges(array&lt;int&gt; vals, int start, int end) {
vector&lt;string&gt; results;
int prev = start - 1;
for (int i = 0; i &lt;= 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 &gt; 2) {
string val = to_string(prev + 1) + &quot;-&gt;&quot; + 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() &lt; t.size()) s.swap(t);
if (s.size() - t.size() &gt; 1)
return false;
int distance = 0;
for (int i = 0, j = 0; i &lt; s.size(); i++, j++) {
if (s[i] == t[j]) continue;
else if (distance &gt; 1) return false;
else {
distance++;
i = s.size() &gt; 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.