multithread synchronization using semaphore

 

#include <iostream>

#include<pthread.h>

#include<semaphore.h>

using namespace std;

pthread_t t[5];

sem_t sem[5];

int c = 0;

#define NUM 30

void* inc(void* p)

{

    while(c < NUM)

    {

        if(sem_wait(&sem[0]) == 0)

        {

            cout<<"T0 inc:"<<++c<<endl;

            sem_post(&sem[1]);

        }

    }

    

    pthread_exit(NULL);

}

void* odd(void* p)

{

    while(c < NUM)

    {

        if (sem_wait(&sem[1]) == 0)

        {

            if (0 != c % 2)

            {

                cout<<c<<":T1 odd"<<endl;

            }

            sem_post(&sem[2]);

        }

    }

    

    pthread_exit(NULL);

}

void* even(void* p)

{

    while(c < NUM)

    {

        if (sem_wait(&sem[2]) == 0)

        {

            if (0 == c % 2)

            {

                cout<<c<<":T2 even"<<endl;

            }

            sem_post(&sem[3]);

        }

    }

    

    pthread_exit(NULL);

}

void* mul2(void* p)

{

    while(c < NUM)

    {

        if (sem_wait(&sem[3]) == 0)

        {

            if (0 == c % 2)

            {

                cout<<c<<": T3 mul by 2"<<endl;

            }

            sem_post(&sem[4]);

        }

    }

    

    pthread_exit(NULL);

}

void* mul5(void* p)

{

    while(c < NUM)

    {

        if (sem_wait(&sem[4]) == 0)

        {

            if (0 == c % 5)

            {

                cout<<c<<": T4 mul by 5"<<endl;

            }

            sem_post(&sem[0]);

        }

    }

    

    pthread_exit(NULL);

}

int main()

{

    sem_init(&sem[0], 0, 1);

    sem_init(&sem[1], 0, 0);

    sem_init(&sem[2], 0, 0);

    sem_init(&sem[3], 0, 0);

    sem_init(&sem[4], 0, 0);

    pthread_create(&t[0], NULL, &inc, NULL);

    pthread_create(&t[1], NULL, &odd, NULL);

    pthread_create(&t[2], NULL, &even, NULL);

    pthread_create(&t[3], NULL, &mul2, NULL);

    pthread_create(&t[4], NULL, &mul5, NULL);

    pthread_join(t[0], NULL);

    pthread_join(t[1], NULL);

    pthread_join(t[2], NULL);

    pthread_join(t[3], NULL);

    pthread_join(t[4], NULL);

    

    pthread_exit(NULL);

    return 0;

}

Digital Root using Recursion

You are given a number n. You need to find the digital root of n.
DigitalRoot of a number is the recursive sum of its digits until we get a single digit number.
Eg.DigitalRoot(191)=1+9+1=>11=>1+1=>2

int digitalRoot(int n)
{
    int sum = 0;
    if (n < 10)
        return n;
     
    sum = digitalRoot(n / 10) + n % 10;
 
    if (sum / 10 != 0)
    {
        return digitalRoot(sum);
    }
    else
    {
        return sum;
    }
}

Implement atoi which converts a string to an integer

Implement atoi which converts a string to an integer

Example 1:

Input: "42"
Output: 42

Example 2:

Input: "   -42                    "
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

class Solution {
public:
    int myAtoi(string str) {

        str.erase(0, str.find_first_not_of(' '));
        str.erase(str.find_last_not_of(' ')+1);

        int len = str.length();
        long long res = 0;
        bool isnegative = str[0] == '-' ? true : false;
        bool ispositive = str[0] == '+' ? true : false;
        int i;
        if (isnegative || ispositive)
            i = 1;
        else
            i = 0;
        long check = isnegative ? 2147483648 : 2147483647;

        for (; i < len; i++)
        {
            if ((str[i] == ' ') || (str[i] - '0' < 0) || (str[i] - '0' > 9))
                break;
           
            if (((res * 10) < check) && (((res * 10 + str[i] - '0') < check)))
            {
                res =  (res * 10 + str[i] - '0');
            }
            else
            {
                res = (true == isnegative) ? INT_MIN : INT_MAX;
                return res;
            }
        }
       
        if (true == isnegative)
        {
            res = -res;
        }
       
        return res;
    }
};

Best time to buy and sell the stock - Multiple Transaction

Best time to buy and sell the stock : 

Multiple Transaction : 

If you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note:  you must sell the stock before you buy again

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buyIdx     = 0;
        int currProfit = 0;
        int profit     = 0;
        int maxProfit  = 0;
        
        for (int i = 1; i < prices.size(); i++)
        {
            currProfit = prices[i] - prices[buyIdx];
            
            if (currProfit > profit)
            {
                profit = currProfit;
            }
            else 
            {
                buyIdx = i;
                maxProfit += profit;
                profit = 0;
            }
        }
        
        maxProfit += profit;

        return maxProfit;
    }
};

Flip an Image / 2 D matrix

Flip an Image / 2 D matrix

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
        for (int row = 0; row < A.size(); row++)
        {
            int numCol = A[row].size();
            int col;
            for (col = 0; col <  (numCol + 1) / 2; col++)
            {
                int temp = A[row][col] ^ 1;
                A[row][col] = A[row][numCol -1 - col] ^ 1;
                A[row][numCol - 1 - col] = temp;     
            }
        }
        return A;
    }
};

Add two numbers represented as linked List

Add two numbers represented as linked List :

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
         if (!l1)
             return l2;
         if (!l2)
             return l1;
        int sum = 0, carry = 0;

        ListNode* head1 = reverse(l1);
        ListNode* head2 = reverse(l2);
        ListNode* result = NULL;
        ListNode* temp = NULL;   
        while (head1 || head2 || carry) {
            int v1 = !head1 ? 0 : head1->val;
            int v2 = !head2 ? 0 : head2->val;
            sum = v1 + v2;
            temp = new ListNode((sum + carry) % 10);
            temp->next = result;
            result = temp;
            carry = (sum + carry) / 10;
            head1 = !head1? NULL : head1->next;
            head2 = !head2? NULL : head2->next;
        }
        return result;
    }
   
    ListNode* reverse(ListNode* head) {
        if (!head) return NULL;
        ListNode* newHead = NULL;
        ListNode* next = NULL;
        while (head) {
            next = head->next;
            head->next = newHead;
            newHead = head;
            head = next;
        }
        return newHead;
    }
};

Given a binary tree, check whether it is a mirror of itself/symmetric

Below binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
         TreeNode* left, *right;
         if (!root)
            return true;
       
         queue<TreeNode*>q1, q2;
         q1.push(root->left);
         q2.push(root->right);
        
        while (!q1.empty() && !q2.empty()) {
            left = q1.front();
            q1.pop();
            right = q2.front();
            q2.pop();
            if (!left && !right)
              continue;
            if (!left || !right)
                return false;
            if (left->val != right->val)
                return false;
            q1.push(left->left);
            q1.push(left->right);
            q2.push(right->right);
            q2.push(right->left); 
        }
        return true;
    }
};


======================================================================================

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
         if (!root)
            return true;
         if (!root->left && !root->right)
             return true;
         if (!root->left || !root->right)
            return false;
         queue<TreeNode*>q1, q2;
         q1.push(root->left);
         q2.push(root->right);
       
    }

};

Determine the perimeter of the island

Given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:
 

 class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        if (grid.empty()) return 0;
        int sum = 0, sr = 0, sc = 0;
        for (int i =0; i < row; i ++) {
            for (int j =0; j < col; j++) {
                if (grid[i][j] == 1) {
                    sr = i;
                    sc = j;
                    break;
                }              
            }
        }
      
        sum += addPerimeter(grid, sr, sc, row, col);
        return sum;
    }
  
    int addPerimeter (vector<vector<int>>&grid, int i , int j, int row, int col) {
        if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0)
            return 1;
        if (grid[i][j] == -1)
            return 0;
      
        grid[i][j] = -1;
      
        return addPerimeter(grid, i+1, j, row, col) +
            addPerimeter(grid, i-1, j, row, col) +
            addPerimeter(grid, i, j+1, row, col) +
            addPerimeter(grid, i, j-1, row, col);   
      
    }
  
};

Perform Flood Fill for a given 2D image/matrix using DFS

solution for Flood fill question using DFS approach :

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor. return the modified image.

Example :

Input: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 3
Output: [[3,3,3],[3,3,0],[3,0,1]]
Explanation: 
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 3, because it is not 4-directionally connected
to the starting pixel.

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int row = image.size();
        int col = image[0].size();
        if (sr < 0 || sr >= row || sc < 0 || sc >=col )
            return image;
        int m = image[sr][sc];
        fillcolor(image, sr , sc , row,col, m, newColor);
        return image;
    }
   
    void fillcolor(vector<vector<int>>& image, int r, int c , int row, int col, int m, int newColor) {
        if (r < 0 || r >= row || c < 0 || c >= col || (image[r][c] != m) || (image[r][c] == newColor))
            return;
        image[r][c] = newColor;
        fillcolor(image, r+1, c, row, col, m, newColor);
        fillcolor(image, r-1, c, row, col, m,newColor);
        fillcolor(image, r, c+1, row, col, m,newColor);
        fillcolor(image, r, c-1, row, col, m,newColor);
       
    }
};

Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 4,
Return

[    [1],
    [1,1],
   [1,2,1],
  [1,3,3,1] ]

C program : 

int** generate(int numRows, int** columnSizes) {
    int i, j;
    int numColumns = 0;
    *columnSizes = malloc(numRows*sizeof(int));
    int** result = (int**)malloc(numRows*sizeof(int*));
   
    for (i = 0; i < numRows; i++)
        result[i] = (int*)malloc((i+1)*sizeof(int));
   
    for (i = 0; i < numRows; i++) {
       
        result[i][0] = result[i][i] = 1;
        for (j = 0; j < i; j++) {
         result[i][j] = result[i-1][j-1] + result[i-1][j];
        }
        numColumns++;
        *(*columnSizes+i) = numColumns;
    }
    return result;
}


C++ program : 

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>>result(numRows);
        for (int i = 0; i < numRows; i++) {
            result[i].resize(i+1);
            result[i][0] = result[i][i] = 1;
            for (int j = 0; j < i ; j++) {
                result[i][j] = result[i-1][j-1] + result[i-1][j];
            }
        }
       
        return result;
    }
};

Remove all elements from a linked list of integers that have value val.

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */ // 6,2,6,1,2,6
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode **list = &head;
        ListNode *temp = NULL;
       
        while (*list)
        {
            if ((*list)->val == val)
            {
                temp = (*list);
                (*list) = (*list)->next;
                free(temp);
            }
            else
            {
                list = &(*list)->next;
            }
        }

    return head;
    }
};

Merge two sorted linked lists and return it as a new list

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void MoveNode (ListNode** destNode, ListNode** srcNode) {
        ListNode* newNode = *srcNode;
        if (!newNode)
            return;
        *srcNode = newNode->next;
        newNode->next = *destNode;
        (*destNode) = newNode;
       
           
    }
       
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* t1 = l1;
        ListNode* t2 = l2;
        ListNode* result = new ListNode(0);
        ListNode* t3 = result;
       
        if (!t1 && !t2) return t1;
        if (!t1 && t2) return t2;
        if (t1 && !t2) return t1;
       
        while (t1 && t2) {
            if (t1->val <= t2->val) {
                MoveNode(&(t3->next), &t1);
            } else {
                MoveNode(&(t3->next), &t2);
            }
            t3 = t3->next;
        }
       
        while (t1) {
            MoveNode(&(t3->next), &t1);
            t3 = t3->next;
        }
       
        while (t2) {
            MoveNode(&(t3->next), &t2);
            t3 = t3->next;
        }

    return result->next;
    }
};

Add two integers represented as strings and return the sum as new string

C++ solution :

class Solution {
public:
    string addBinary(string a, string b) {
       
        int lena = a.size() - 1;
        int lenb = b.size() - 1;
        string s = "";
        int sum = 0, carry = 0;
        while(lena >= 0 || lenb >= 0 || carry==1) {
            int n1 = lena >= 0 ? a[lena--] - '0' : 0;
            int n2 = lenb >= 0 ? b[lenb--] - '0' : 0;
            sum = n1^n2^carry;
            carry = n1&n2|n1&carry|n2&carry;
            char c = ((sum % 2) + '0');
            s = c + s;
        }
        return s;       
    }
};

or

class Solution {
public:
    string addBinary(string a, string b) {
       
        int lena = a.size() - 1;
        int lenb = b.size() - 1;
        string s = "";
        int sum = 0, carry = 0;
        while(lena >= 0 || lenb >= 0 || carry==1) {
            int n1 = lena >= 0 ? a[lena--] - '0' : 0;
            int n2 = lenb >= 0 ? b[lenb--] - '0' : 0;
            sum = n1 + n2 + carry;
            carry = sum / 2;
            char c = ((sum % 2) + '0');
            s = c + s;
        }
        return s;       
    }
};


C solution : 

char* addStrings(char* num1, char* num2) {
    int len1 = 0;
    int len2 = 0;
    int i,j;
    for(i=0;num1[i]!= NULL;i++)
        len1++;
    for(j=0;num2[j]!= NULL;j++)
        len2++;
   
    printf("len1 %d, len2 %d", len1, len2);
    int finalSize = (len1 > len2) ? len1:len2;
   
    char* result = malloc((finalSize+1)*sizeof(char));
    int k = finalSize - 1;
    int carry = 0;
    int carry_temp = 0;
    int sum = 0;
    while(len1 && len2) { //584, 18
        sum = (num1[len1 - 1] - '0') + (num2[len2 - 1] - '0');
        if (sum >= 10) {
            carry_temp = sum / 10;
            sum = sum % 10;
        }
        if((sum+carry)>=10) {
            sum = sum + carry;
            carry_temp = sum / 10;
            sum = sum % 10;
            carry = 0;
        }
        result[k] = ((sum + carry) +'0');
        carry = carry_temp;
        carry_temp = 0;
        len1--;
        len2--;
        k--;
    }
    while (len1) {
        sum = ((num1[len1-1] - '0') + carry);
        if (sum >= 10) {
            carry_temp = sum / 10;
            sum = sum % 10;
        }
        result[k] = (sum +'0');
        carry = carry_temp;
        carry_temp = 0;
        k--;
        len1--;
    }
   
    while (len2) {
        sum = ((num2[len2-1] - '0') + carry);
        if (sum >= 10) {
            carry_temp = sum / 10;
            sum = sum % 10;
        }
        result[k] = (sum +'0');
        carry = carry_temp;
        carry_temp = 0;
        k--;
        len2--;
    }

    if (carry) {
        char *result_new = malloc((finalSize+2)*sizeof(char));
        int l = 0;
       
        while(l < finalSize-1) {
            result_new[l+1] = result[l];
            l++;
        }
        result_new[l+1] = result[l];
        result_new[0] = carry + '0';
        result_new[finalSize+1] = NULL;
        return result_new;
    }
    result[finalSize] = NULL;
    return result;
}

Movnig the zeores in the given array towards the end without changing non zero number orders in the array

void moveZeroes(int* nums, int numsSize) {
    int i;
    int j = 0;
    if (!nums || numsSize < 2)
        return;
    for(i=0; i<numsSize; i++) {
        if (nums[i]!=0) {
            nums[j] = nums[i];
            j++;
        }       
    }
   for(;j< numsSize; j++) {
       nums[j] = 0;
   }
}