[Leetcode] Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Analysis:
Compare each character in first string to all others, return the sub string that is matching all strings.

Solution:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        
     
        string first;
        
        if(strs.size() == 0)
        {
            return first;
        }
        
        first = strs[0];
        
        if(strs.size() == 1)
        {
            return first;
        }
        
        int len = 0;
        bool loop_break = false;
        
        for(int i = 0; i < first.size(); i++)
        {
            for(int j = 1; j < strs.size(); j++)
            {
                if(i < strs[j].size())
                {
                    // find mismatch on ith character, break the loop
                    if(first[i] != strs[j][i])
                    {
                        loop_break = true;
                        break;
                        
                    }

                }
                else
                {
                    // find a string of length that is less than i, break the loop
                    loop_break = true;
                    break;
                }
            }
            
            // no loop break, meaning ith character is matching in all strings
            if(loop_break == false)
              len++;
     
            else
              break;
            
        }
        
        return first.substr(0, len);
        
    }
};

[Leetcode] Restore IP addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Analysis:
The problem assumes input is an IPv4 address, wnhich has four octets and each of them is a non-negative number less than 256.
Idea is to scan the string from left to right, whenever we found a octet, if total found octets are still less than 4, check if any more valid octets can be found from right substring. We can validate the length of right substring and how many octets we have left before jumping into it.

Solution:

class Solution {
public:

  // Check if string s is a valid IP address
  bool is_valid(string s)
    {
    if (s.size() > 3) return false;
        if (s.size()==3)
        {   
        if(atoi(s.c_str())>255 || atoi(s.c_str())==0 || s[0] == '0')
              return false;
        } 
        if (s.size()==2)
        {
        if(atoi(s.c_str())==0 || s[0] == '0')
         return false;
        }
        return true;
    }
    
    void findAllIPs(string s, int index, int len, vector<string> & result, string &octet, int num)
    {
        if(num == 0 && index != len)
           return;
           
        if(index == len)
        {
        cout<<"find one IP: "<<octet<<endl;
            result.push_back(octet);
            return;
        }
        
        string temp;
        
        for(int i = index; i < len; i++)
        {
             temp = s.substr(index, i - index + 1);
             // proceed if sub string temp is a valid IPv4 address
             // length of right substring is a possible match for left octets 
             if(is_valid(temp) && s.substr(i+1).size() <= 3 * (num-1) && s.substr(i+1).size() >= num - 1)
             {
                 string original = octet;
                 if(index !=0)
                 {
                   octet = octet + "." + temp;
                  
                 }
                 else
                 {
                  octet = temp;
                 }
            
                 num--;
                 findAllIPs(s, i+1 , len, result, octet, num);
                 num++;
                 
                 octet = original;
             }
             else
             {
              continue;
             }
        }
    }
    
    vector<string> restoreIpAddresses(string s) {
        
        vector<string> result;
        string octet;
        
        int len = s.size();
        
        // invalid string length, skip
        if(len < 4 || len > 12)
        {
            return result;
        }
        
        int num = 4;
        findAllIPs(s, 0, len, result, octet, num);
      
        return result;    
    }
};

[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).