Showing posts with label Programming. Show all posts
Showing posts with label Programming. Show all posts

Sunday, March 21, 2021

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;

}

Monday, September 10, 2018

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

Sunday, September 9, 2018

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

Wednesday, September 5, 2018

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

Sunday, February 25, 2018

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

Friday, January 5, 2018

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

};

Saturday, December 30, 2017

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

Thursday, December 14, 2017

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

Thursday, November 30, 2017

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

Wednesday, December 28, 2016

Learning Python

Python is a general-purpose interpreted, interactive, object-oriented, and high-level programming language.Python was developed by Guido van Rossum in the late eighties and early nineties at the National Research Institute for Mathematics and Computer Science in the Netherlands

Python is processed at runtime by the interpreter.
Python is interactive shows prompt and interact with the interpreter directly to write your programs.
Python supports Object-Oriented style or technique of programming that encapsulates code within objects.


>>> print ("Hello, World!") 
#!/usr/bin/python3

counter = 100          # An integer assignment
miles   = 1000.0       # A floating point
name    = "John"       # A string

print (counter)
print (miles)
print (name)

Python has five standard data types − Numbers, String, List, Tuple, Dictionary
Numbers :
var1 = 1
var2 = 10
del var
del var_a, var_b
Python supports four different numerical types −
  • int (signed integers)
  • float (floating point real values)
  • complex (complex numbers)
string :
str = 'Hello World!'

print (str)          # Prints complete string
print (str[0])       # Prints first character of the string
print (str[2:5])     # Prints characters starting from 3rd to 5th
print (str[2:])      # Prints string starting from 3rd character
print (str * 2)      # Prints string two times
print (str + "TEST") # Prints concatenated string
list :
list = [ 'abcd', 786 , 2.23, 'john', 70.2 ]
tinylist = [123, 'john']

print (list)          # Prints complete list
print (list[0])       # Prints first element of the list
print (list[1:3])     # Prints elements starting from 2nd till 3rd 
print (list[2:])      # Prints elements starting from 3rd element
print (tinylist * 2)  # Prints list two times
print (list + tinylist) # Prints concatenated lists
Tuples
The main differences between lists and tuples are: Lists are enclosed in brackets ( [ ] ) and their elements and size can be changed, while tuples are enclosed in parentheses ( ( ) ) and cannot be updated. Tuples can be thought of as read-only lists. For example −
#!/usr/bin/python3

tuple = ( 'abcd', 786 , 2.23, 'john', 70.2  )
tinytuple = (123, 'john')

print (tuple)           # Prints complete tuple
print (tuple[0])        # Prints first element of the tuple
print (tuple[1:3])      # Prints elements starting from 2nd till 3rd 
print (tuple[2:])       # Prints elements starting from 3rd element
print (tinytuple * 2)   # Prints tuple two times
print (tuple + tinytuple) # Prints concatenated tuple
Dictionary :
Python's dictionaries are kind of hash table type. A dictionary key can be almost any Python type, but are usually numbers or strings. Values, on the other hand, can be any arbitrary Python object. Dictionaries are enclosed by curly braces ({ }) and values can be assigned and accessed using square braces ([]). For example −
#!/usr/bin/python3

dict = {}
dict['one'] = "This is one"
dict[2]     = "This is two"

tinydict = {'name': 'john','code':6734, 'dept': 'sales'}


print (dict['one'])       # Prints value for 'one' key
print (dict[2])           # Prints value for 2 key
print (tinydict)          # Prints complete dictionary
print (tinydict.keys())   # Prints all the keys
print (tinydict.values()) # Prints all the values
This produce the following result −
This is one
This is two
{'code': 6734, 'name': 'john', 'dept': 'sales'}
dict_keys(['code', 'name', 'dept'])
dict_values([6734, 'john', 'sales'])
Dictionaries have no concept of order among elements. It is incorrect to say that the elements are "out of order"; they are simply unordered.

Introductory Program showing function , loop, condition and printing :

Example 1 : given an input integer N, print output as 123.....N without using any special data types

from __future__ import print_function
if __name__ == '__main__':
    n = int(raw_input())
    i = 0
    j = 0
    result = 0
    num = 0
    while i <= n :
        num = i
        while num :
            j+=1
            num/=10
        result = result *(10**j) + i
        i+=1
        j = 0
    print (result)



Example 2 :  bear, honey and gold game :

from sys import exit

def gold_room():
print "This room is full of gold. How much do you take?"
next = raw_input("> ")
if "0" in next or "1" in next:
how_much = int(next)
else:
dead("Man, learn to type a number.")
if how_much < 50:
print "Nice, you are not greedy, you win!"
exit(0)
else:
dead("You are greedy bastard!")

def bear_room():
print "There is a bear here."
print "The bear has a bunch of honey."
print "The fat bear is in front of another door."
print "How are you going to move the bear?"
bear_moved = False

while True:
next = raw_input("> ")

if next == "take honey":
dead("The bear looks at you then slaps your face off.")
elif next == "taunt bear" and not bear_moved:
print "The bear has moved from the door. You can go through it now."
bear_moved = True
elif next == "taunt bear" and bear_moved:
dead("The bear gets pissed off and chews your leg off.")
elif next == "open door" and bear_moved:
gold_room()
else:
print "I got no idea what that means."

def cthulhu_room():
print "Here you see the great evil Cthulhu."
print "He, it, whatever stares at you and you go insane."
print "Do you flee for your life or eat your head?"

next = raw_input("> ")

if "flee" in next:
start()
elif "head" in next:
dead("Well that was tasty!")
else:
cthulhu_room()

def dead(why):
print why, "Good job!"
exit(0)

def start():
print "You are in a dark room."
print "There is a door to your right and left."
print "Which one do you take?"

next = raw_input("> ")

if next == "left":
bear_room()
elif next == "right":
cthulhu_room()
else:
dead("You stumble around the room untill you starve.")

start()