[C++] Initialize member variable with constructor initialization list

Member initializer list is useful in case of initializing member variables of const or reference type, and for class has no member initialization inside its default constructor. 


Example:

#include <iostream>
using namespace std;

class Point {

    private:
      int _x;
      int _y;
      
    public:
      Point(int x, int y): _x(x), _y(y) {};
      
      void print();
      
};

void Point::print()
{
cout<<"x: "<<_x<<" y: "<<_y<<endl;
}

int main() {

Point *p = new Point(3,4);
p->print();
 
return 0;
}


We can write our constructor in two ways as below.

The difference between them is that in Method B,  the 'initialization' for _x and _y happened after object is created and their values are actually changed by assignment operation.  While in Method A _x and _y is initialized before constructor runs.

Method A:
    public:
      Point(int x, int y): _x(x), _y(y) {};

Method B:
    public:
      Point(int x, int y): 
     {
            _x = x;
            _y = y;
     }

[GeeksforGeeks] Buy and Sell stocks twice for max profit

Buy and Sell stocks twice for max profit

Analysis:
The question can be solved by DP using two arrays left[] and right[].
left[i] represents max profit to be made between day [0..i]
right[i] represents max profit to be made between day [i, n-1].

The ultimate max profit would be max sum of left[i] + right[i]

Solution:
#include<iostream>
using namespace std;

// Returns maximum profit with two transactions on a given
// list of stock prices, price[0..n-1]
int maxProfit(int price[], int n)
{
    int left[n];
    int right[n];
    
    int i;
    for(i = 0; i < n;i++)
    {
    left[i] = 0;
    right[i] = 0;
    }
    
    int min_price = price[0], max_price = price[n-1];
    int max_profit = 0;
    
    for(i = 0; i < n; i++)
    {
    min_price = min_price < price[i] ? min_price : price[i];
    left[i] = price[i] - min_price > max_profit ? price[i] - min_price: max_profit;
    }
    
    max_profit = 0;
    right[n-1] = 0;
    
    for(i = n-2; i >=0; i--)
    {
    max_price = max_price > price[i] ? max_price : price[i];
    right[i] = max_price - price[i] > right[i+1] ? max_price - price[i] : right[i+1];
   
    }
    
    max_profit = 0;
    for(i = 0; i < n; i++)
    {
    max_profit = max_profit > left[i] + right[i] ? max_profit : left[i] + right[i];
    }
    
    return max_profit;
    
    
}

// Drive program
int main()
{
    int price[] = {2, 30, 15, 10, 8, 25, 80};
    int n = sizeof(price)/sizeof(price[0]);
    cout << "Maximum Profit = " << maxProfit(price, n);
    return 0;
}

[GeeksforGeeks] print all permutations of a string

Print all permutations of a string

Analysis:
A basic interview question on recursion.

Solution:
#include <stdio.h>
#include <string.h>

void permutation(char *s, int i, int n)
{
if(i == n)
{
printf("%s\n", s);
return;
}

int j;
char temp;
for(j = i; j < n; j++)
{
temp = s[j];
s[j] = s[i];
s[i] = temp;

permutation(s, i+1, n);

        temp = s[j];
s[j] = s[i];
s[i] = temp;

}
}

int main(void) {

char s[] = "abc";
    
        int len = strlen(s);
permutation(s, 0, len);

return 0;
}

[Leetcode] Find Minimum in Rotated Sorted Array II

Find Minimum in Rotated Sorted Array II

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element. The array may contain duplicates.
Analysis:
A preferred solution is using binary search. Tricky part is to remove duplicate and when to stop out from while loop.  It cost me several failed submissions to figure that out.

Solution:
int findMin(int* nums, int numsSize) {

    int start = 0, end = numsSize - 1;    
    int mid; 
    while(start + 1 < end)
    {
        mid = start + (end - start)/2; 
        // if right portion is sorted, minimum must be on left portion
        if(nums[mid] < nums[end])
        {
            end = mid;
        }
        // otherwise check right portion 
        else if(nums[mid] > nums[end])
        {
            start = mid;
        }
        // or if they are equal, we don't know which direction to go, reduce end and check next time
        else if(nums[mid] == nums[end])
        {
            end--;
        }
    }
    return nums[start] < nums[end] ? nums[start] : nums[end];
}

[System design] Use Bitmap to store integers

Use Bitmap to store integers

Read an article the other day about Bitmap, the idea is to squeeze every bit of an integer to store an integer, hence for N integer we can save them using one N/8 size array.  Looks pretty interesting.

Solution:
int main() {

    int i, j, temp;
    
    int bitmap[1000/8];
    
    for(i = 0; i < 1000; i++)
    {
        // store integer to bit map
       // if i is multiple of 8,  then i, i+1...i+7 only differ in last 3 bits,                                                    // after divided by 8 (right shift by 3), they return same index, 
       // i & 7 (i & 0b111) retrieves 'value' of last 3 bits and store it in 'value' th position     
       bitmap[i/8] |= 1<<(i & 7);    
                                                        
    }
    
    
    for(i = 0; i < 1000/8; i++)
    {
    // read from bitmap
        for(j = 0; j < 8; j++)
        {
        if(1<<j & bitmap[i])
        {
        temp = i * 8 + j;
        printf("%d ", temp);
        }
        else
        {
        printf("no hit!\n");
        }
        }
   
    printf("\n");
    }
    
return 0;
}

[Leetcode] Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

Analysis:  
straightforward question, if it's a sorted array we don't need hashtable but keep comparing next node with current node to remove duplicates.

Solution: 
ListNode *deleteDuplicates(ListNode *head) {

        ListNode *dummy = new ListNode(0);        
        dummy->next = head;               // use dummy head to avoid taking care of first node later
        ListNode *current = head;         // use single pointer to traverse the list

        while(current)               // two while loops, it still takes O(n) cuz every node once is visited once
        {
            while(current->next)   // In this loop comparing adjacent nodes to remove duplicates
            {
               if(current->next->val == current->val)  // Removing next node cuz it's a duplicate
               {
                   ListNode *temp = current->next;
                   current->next = current->next->next;
                   
                   delete temp;
                   continue;
               }
               else
               {
                   break;                         // Or the next node is NOT a duplicate, break and move forward
               }
            }  
            current = current->next;

        }        
        return dummy->next;           // return next element of dummy header which is beginning of new list


    }

[Leetcode] Clone Graph

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

Analysis: 
A typical graph problem, either DFS or BFS does the trick.

Solution:
class Solution {
public:
    UndirectedGraphNode *DFS(UndirectedGraphNode *node, unordered_map<int, UndirectedGraphNode*> &visited)
    {
        UndirectedGraphNode *ret = new UndirectedGraphNode(node->label);
        visited[node->label] = ret;
        
        for(int i = 0; i < node->neighbors.size(); i++)
        {
            UndirectedGraphNode *temp = node->neighbors[i];
            if(visited[temp->label])
            {
               ret->neighbors.push_back(visited[temp->label]); 
            }
            else
            {
               ret->neighbors.push_back(DFS(node->neighbors[i], visited));
            }
        }
        return ret;
    }
    
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(node == NULL)
           return NULL;
       UndirectedGraphNode *ret;
       unordered_map<int, UndirectedGraphNode*> visited; 
       ret = DFS(node, visited);
       return ret; 
    }

};

[Leetcode] Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum
The path may start and end at any node in the tree.


Analysis:
Top down approach as stated from online sources.

Solution:

// return max path sum starts from root
int findMax(struct TreeNode *root, int *max_sum)
{
    if(root == NULL)
       return 0;
       
    int left = findMax(root->left, max_sum);  
    int right = findMax(root->right, max_sum);
    
     // compare max_sum with current path sum root->val + left + right
    *max_sum = *max_sum > (root->val + left + right) ? *max_sum : root->val + left + right;
    
    // notice we only pick either left or right subtree
    int max_sub = left > right ? left : right;
    
    int max_root_sub = root->val + max_sub;
    
    // if root->val + max_sub is less than 0, we shouldn't add it to root's parent as it reduces            sum of the path, return 0 instead
    return max_root_sub > 0 ? max_root_sub : 0;
}

int maxPathSum(struct TreeNode *root) {
    
    int max_sum = INT_MIN;
    
    findMax(root, &max_sum);
    
    return max_sum;
    

}

[Leetcode] Single Number II

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Analysis: 
One linear solution is to count total sum of each bit for all elements, and divide that by 3,  as every element appear three times except one,  the remaining bit is honored by the integer appeared only once.

Solution:

    int singleNumber(int A[], int n) {
       int result = 0;
       int i;
       int x;
       int sum;
       int size = 8 * sizeof(int);
    
       // Walk through every bit
       for (i = 0; i <size ; i++)
       {
          sum = 0;       // reset sum for current bits
          
          x = (1<<i);     
          for (int j=0; j< n; j++ )   
          {
             if (A[j] & x)  //  ith bit is set for A[j], add it to the sum
                 sum++;
          }
          if (sum % 3)  // append the remaining bit to result using OR operation
          result |= x;
      
       }

       return result;
        
    }

[Linux] Top command display by sorting

top -> hold shift + f and select field to sort by

[GeeksforGeeks] Maximum sum such that no two elements are adjacent

Maximum sum such that no two elements are adjacent

Question: Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

Analysis:  
DP comes to the picture. A similar problem would be 'Maximum sum of consecutive elements in a array', the difference is that when scans an element A[i], current maximum sum is chosen between previous max sum includes A[i-1] and a different max sum that does NOT include A[i-1].

Solution: 

int max(int a, int b)
{
return (a > b) ? a : b;
}

int maxSum(int *a, int n)
{
if(n <= 0)
     return 0;

     // include_sum is current max sum that includes a[i]
int include_sum = a[0];

     // exclude_sum is current max sum that does NOT include a[i]
int exclude_sum = 0;

int max_val = max(include_sum,  exclude_sum);

int i;
for(i = 1; i < n; i++)
{
                // Add two temp variables for readiness
               int prev_inc = include_sum;
                int prev_excl = exclude_sum;

                // current max sum that includes a[i]
include_sum = max(prev_excl + a[i], a[i]);  

               // current max sum that does NOT include a[i]
exclude_sum = max(prev_inc,  prev_excl);

  // max sum is chosen from above
max_val = max(max_val, max(include_sum, exclude_sum));
}

return max_val;

}

[Leetcode] Reverse Bits

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.
Analysis:  a typical question focus on bit operations, be careful about boundaries.
Solution:
uint32_t reverseBits(uint32_t n) {
    
    int size = sizeof(uint32_t) * 8;
    
    int result = 0;
    
    int i;
    int val;
    
    for(i = 0; i < size; i ++)
    {
        val = (1<<i) & n;                    // if ith bit in n is set, val > 0, otherwise val = 0
        
        if(val > 0)                              // be careful don't use if(val == 1)
        {
           result |= 1<<(size - i -1);   // set (size - i -1)th bit in resullt if ith bit is set in n
        }
    }
    
    return result;
    
}

[Leetcode] Sort Colors

Sort Colors

 Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. 

Analysis: 
At first glance it feels so similar to 'Remove duplicates from a string'.  I wrote my own solution with 2 iterations.
Solution 1:
void sortColors(int A[], int n) {
     int i = 0, j = 0;   
    for(i = 0; i < n; i++)            -> 1st loop move all 0s to the front
    {
        if(A[i] == 0)
        {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            j++;
        }
    }
    
    for(i = j; i < n; i++)           -> 2nd loop move all 1s to the front (after 0s)
    {
        if(A[i] == 1)
        {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            j++;
        }
    }
}

For this specific problem (all elements fall into exactly 3 categories), it can be improved to single iteration, below is a sample from online source:

Solution 2:
void swap(int *a, int i, int j)
{
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}


void sortColors(int A[], int n) {

    
    if(n == 1)
      return;
      
    int i = 0, isOne = 0, isTwo = n-1;
    
    while(i < isTwo+1)
    {
        if(A[i] == 0)                     -> move 0s to the front
        {
            swap(A, i, isOne);
            isOne++;
            i++;
            continue;
        }
        if(A[i] == 2)                     -> move 2s to the end
        {
            swap(A, i, isTwo);
            isTwo--;                      -> after swapping, we don't move pointer isTwo cuz the new value can be 1,
            continue;                        we will compare it with i in next loop                          
            
        }
        else
        {
            i++;
        }
        
    }
      
}


Final thoughts:
For this specific problem solution 2 is better because of better time complexity. However if number of categories is k ( k > 3),  solution 1 is the only choice and time complexity would be O(kn).

[Leetcode] Minimum Depth of Binary Tree

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

Analysis:
A pretty simple question, isn't ? Not really, if you come up with below solution (lots of online sources did), it's incorrect.

Solution 1:
    int min(int a, int b)
    {
        return (a <  b) ? a : b;
    }
 
    int minDepth(TreeNode *root) {
     
        if(root == NULL)
          return 0;
       
        int left = minDepth(root->left);
        int right = minDepth(root->right);
 
        return 1 + min(left, right);
     
    }

What is missing above is when root->left is NULL (or root->right is NULL), your min depth always returns 1 instead of calculating real minimum depth.  Correct way is to add this sanity checks.

Solution 2:
    int min(int a, int b)
    {
        return (a <  b) ? a : b;
    }
 
    int minDepth(TreeNode *root) {
     
        if(root == NULL)
          return 0;
       
        int left = minDepth(root->left);
        int right = minDepth(root->right);
     
        if(left == 0)
            return 1 + right;
 
        if(right == 0)
            return 1 + left;
         
        return 1 + min(left, right);
     
    }

Final thoughts:
I been thinking solution 1 is correct for years until very recently.  The sanity check is not needed for maxDepth but minDepth.

[Leetcode] Rorate Array by k steps

Rotate Array

Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]

Analysis:
This is a tricky question and is hard to come up with a neat solution at first glance.

Turns out the answer is pretty simple,  be careful about sanity check for value of k.

Solution:

void reverse(int *nums, int start, int end)
{
    if(start > end)
      return;
   
    int i = start, j = end;
    while(i < j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        i++;
        j--;
    }
}

void rotate(int nums[], int n, int k) {
 
    k = k % n;                                 -> The sanity check is a bit tricky
    if(k>0 && k< n)                
    {
      // reverse whole thing first
      reverse(nums, 0, n -1);
 
     // reverse first k elements, then reverse the rest
      reverse(nums, 0, k-1);
      reverse(nums, k, n-1);
    }
}

Further thoughts:
Not much to say about question like this. Most ppl could finish it with hint.

[Leetcode] Binary Tree Right Side View

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Given the following binary tree,

 1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Analysis:
BFS level traversal and print last node on each level. A tricky part is how to find out last node on that part easily.  We can insert 'dummy' nodes between levels, or, Introducing two variables 'count' and 'nextcount' makes it easier. 

Solution:
    void bfs(TreeNode *root, vector<int> &result)
    {
        if(root == NULL)
           return;           
        queue<TreeNode *> nodes;

        nodes.push(root);
        int count = 1, nextcount = 0;  ->  Init count to 1 for root, nextcount to zero

        while(!nodes.empty())
        {
            TreeNode *current = nodes.front();
            nodes.pop();
            if(current != NULL)
            {
                count--;                         - > Reduce count for node(s) on current level
                if(current->left)
                {
                    nodes.push(current->left);
                    nextcount++;             - > Increase count for node(s) on next level
                }
                if(current->right)
                {
                    nodes.push(current->right);
                    nextcount++;            - > Increase count for node(s) on next level
                }
                
                // reaching last node at the level, add it to the output
                if(count == 0)               - > When count is 0, meaning we reach last node on that level 
                {
                    result.push_back(current->val);
                    count = nextcount;    - > Now assign node(s) count from next level to next 'current' level
                    nextcount = 0;
                }           
            }
        }
    }

Final thoughts:
  How about left view of the tree ? We can print first node on each level instead of the last.
  Introducing a new variable 'flag' to do the trick.

void bfs(TreeNode *root, vector<int> &result)
    {
        if(root == NULL)
           return;           
        queue<TreeNode *> nodes;

        nodes.push(root);
        int count = 1, nextcount = 0;  ->  Init count to 1 for root, nextcount to zero
        int flag = 1;                            ->  Init flag to 1
        while(!nodes.empty())
        {
            TreeNode *current = nodes.front();
            nodes.pop();
            if(current != NULL)
            {
               if(flag)
               {
                    result.push_back(current_val);    ->  First node on that level, print and reset flag
                    flag = 0;
               } 
               count--;                         
                if(current->left)
                {
                    nodes.push(current->left);
                    nextcount++;             
                }
                if(current->right)
                {
                    nodes.push(current->right);
                    nextcount++;           
                }

                if(count == 0)              
                {
                   flag = 1;               ->  Last node at current level, next node starts from first node of next level, hence set flag back to 1
                    count = nextcount;    
                    nextcount = 0;
                }           
            }
        }
    }