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; 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.size(); i++){ char c = str[i]; for (int j = 1; j < n; j ++) if (i == str[j].size() || str[j][i] != c) return str.substr(0, i); } return str; } 

## 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; }