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