1. Same Tree
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isSameTree(TreeNode* p, TreeNode* q) {
queue<TreeNode*> que;
if(p==NULL || q==NULL) return p==q;
que.push(p); que.push(q);
while(!que.empty()) {
TreeNode* left = que.front(); que.pop();
TreeNode *right = que.front(); que.pop();
if(left==NULL && right==NULL) continue;
if(left==NULL || right==NULL) return false;
if(left->val != right->val) return false;
que.push(left->left);
que.push(right->left);
que.push(left->right);
que.push(right->right);
}
return true;
}
Recursive
1
2
3
4
5
6
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == NULL && q== NULL) return true;
if(p == NULL || q== NULL) return false;
if(p->val != q->val) return false;
return isSameTree(p->right, q->right) && isSameTree(p->left, q->left) ;
}
2. Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).
Note:
Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer.
Naive
1
2
3
4
5
6
7
8
9
int setBits(int N) {
int count = 0;
while(N){
count += (N & 1);
N = N >> 1;
}
return count;
}
Brian Kernighan’s Algorithm
1
2
3
4
5
6
7
8
int setBits(int N) {
int count = 0;
while (N) {
N &= (N - 1);
count++;
}
return count;
}
STL
1
2
3
int hammingWeight(uint32_t n) {
return __builtin_popcount(n);
}
Converting to string
1
2
3
4
5
6
7
int hammingWeight(uint32_t n){
string bin = bitset<32>(n).to_string();
int counter = count(bin.begin(), bin.end(), '1');
return counter;
}
3. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".
Horizontal scanning
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
string longestCommonPrefix(vector<string>& str) {
int n = str.size();
if(n == 1) return str[0];
string ans = "";
int longest = INT_MAX, curr, j, k;
for(int i=0; i<n-1; i++){
curr = j = k = 0;
int a = str[i].size(), b = str[i+1].size();
while(j < a and k < b and str[i][j++] == str[i+1][k++])
curr++;
if(curr == 0) return "";
if(curr < longest){
ans = str[i].substr(0 , curr);
longest = curr;
}
}
return ans;
}
Vertical scanning
1
2
3
4
5
6
7
8
9
10
11
12
string longestCommonPrefix(vector<string>& str) {
int n = str.size();
if (n == 0) return "";
for (int i = 0; i < str[0].size(); i++){
char c = str[0][i];
for (int j = 1; j < n; j ++)
if (i == str[j].size() || str[j][i] != c)
return str[0].substr(0, i);
}
return str[0];
}
4. Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
1
2
3
4
5
6
7
8
int singleNumber(vector<int>& nums) {
int ans = 0;
for(auto e: nums)
ans ^= e;
return ans;
}