Home Week 3 | Grind 169 | Blind 75
Post
Cancel

Week 3 | Grind 169 | Blind 75

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.

  • Practice

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;
}
This post is licensed under CC BY 4.0 by the author.

Setting up Manjaro Linux

Vim Cheat Sheet