Week 3 | Grind 169 | Blind 75

Posted on Dec 25, 2020

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

 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

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

int setBits(int N) {

    int count = 0;
    while(N){
      count += (N & 1);
      N = N >> 1;
    }
  return count;
}

Brian Kernighan’s Algorithm

int setBits(int N) {
    int count = 0;
    while (N) {
      N &= (N - 1);
      count++;
    }
  return count;
}

STL

int hammingWeight(uint32_t n) {
  return __builtin_popcount(n);
}

Converting to string

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

    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

    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.

int singleNumber(vector<int>& nums) {
    int ans = 0;

    for(auto e: nums)
        ans ^= e;

    return ans;
}