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

container_of macro

kernel container_of macro

#define container_of(ptr, type, member) ({ \
    const typeof( ((type *)0)->member ) \
    *__mptr = (ptr);
    (type *)( (char *)__mptr - offsetof(type,member) );})

When you use the cointainer_of macro, you want to retrieve the structure that contains the pointer of a given field. For example:

struct numbers {  
   int one; 
   int two; 
   int three; 
} n;  

int *ptr = &n.two; 
struct numbers *n_ptr; 
n_ptr = container_of(ptr, struct numbers, two);

You have a pointer that points in the middle of a structure (and you know that is a pointer totwo
 [the field name in the structure]), but you want to retrieve the entire structure (numbers). So, you calculate the offset of the filed two in the structure:

offsetof(type,member)

and subtract this offset from the given pointer. The result is the pointer to the start of the structure. Finally, you cast this pointer to the structure type to have a valid variable.

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

Memory Segments in C

Memory Mapping of a Program

 

1. Code Segment

• The code segment, also referred as the text segment, is the area of memory which contains the frequently executed code.
• The code segment is often read-only to avoid risk of getting overridden by programming bugs like buffer-overflow, etc.
• The code segment does not contain program variables like local variable (also called as automatic variables in C), global variables, etc.
• Based on the C implementation, the code segment can also contain read-only string literals. For example, when you do printf("Hello, world") then string "Hello, world" gets created in the code/text segment. You can verify this using size command in Linux OS.
• Further reading

2. Data Segment

The data segment is divided in the below two parts and typically lies below the heap area or in some implementations above the stack, but the data segment never lies between the heap and stack area.

Uninitialized data segment

• This segment is also known as bss.
• This is the portion of memory which contains:
  1. Uninitialized global variables (including pointer variables)
  2. Uninitialized constant global variables.
  3. Uninitialized local static variables.
• Any global or static local variable which is not initialized will be stored in the uninitialized data segment
• For example: global variable int globalVar; or static local variable static int localStatic;will be stored in the uninitialized data segment.
• If you declare a global variable and initialize it as 0 or NULL then still it would go to uninitialized data segment or bss.
• Further reading

3. Initialized data segment

• This segment stores:
  1. Initialized global variables (including pointer variables)
  2. Initialized constant global variables.
  3. Initialized local static variables.
• For example: global variable int globalVar = 1; or static local variable static int localStatic = 1; will be stored in initialized data segment.
• This segment can be further classified into initialized read-only area and initialized read-write area. Initialized constant global variables will go in the initialized read-only area while variables whose values can be modified at runtime will go in the initialized read-write area.
• The size of this segment is determined by the size of the values in the program's source code, and does not change at run time.
• Further reading

4. Stack Segment

• Stack segment is used to store variables which are created inside functions (function could be main function or user-defined function), variable like
  1. Local variables of the function (including pointer variables)
  2. Arguments passed to function
  3. Return address
• Variables stored in the stack will be removed as soon as the function execution finishes.
• Further reading

5. Heap Segment

• This segment is to support dynamic memory allocation. If the programmer wants to allocate some memory dynamically then in C it is done using the malloc, calloc, or reallocmethods.
• For example, when int* prt = malloc(sizeof(int) * 2) then eight bytes will be allocated in heap and memory address of that location will be returned and stored in ptr variable. The ptr variable will be on either the stack or data segment depending on the way it is declared/used.
• Further reading

Binary Number with Alternating Bits

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values. 

Input: 5
Output: True
Explanation:
The binary representation of 5 is: 101

Input: 11
Output: False
Explanation:
The binary representation of 11 is: 1011. 

bool hasAlternatingBits(int n) {
   
    if (n == 1 || n == 2) return true;
    int mask = n << 1;
    int flag = n ^ mask;
   
    flag = (n & 0x1)?(flag & (flag+1)):(flag & (flag+2));
   
    if (flag)
        return false;
    else
        return true;
}


or


bool hasAlternatingBits(int n) {
    int mask = n >> 1;
    int flag = n + mask;
   
    if (flag&(flag+1))
        return false;
    else
        return true;
}

Flatten a Dictionary using python programming

Flatten a Dictionary using python programming

 

"""input:  dict = {
            "a" : "1",
            "b" : {
                "a1" : "2",
                "b1" : "3",
                "c1" : {
                    "d" : "3",
                    "e" : "1"
                }
            }
        }

output: {
            "a" : "1",
            "a.a1" : "2",
            "b.b1" : "3",
            "c.c1.d" : "3",
            "c.c1.e" : "1"
        }"""
  

def flatten_dictionary(inputdict):
  #1. create empty dictionary
  flatDictionary = {}

  flattendictionary("", inputdict, flatDictionary)
 
  return flatDictionary

def flattendictionary(initialKey, inputdict, flatDictionary):
  #2. check key to a valid dictionary
  for key, value in inputdict.iteritems():
          if not isinstance(value, type(inputdict)):
              if initialKey is None or initialKey is "":
                  flatDictionary[key] = value
              else:
                  if not key:
                    flatDictionary[initialKey] = value
                  else:
                    flatDictionary[initialKey + "." + key] = value
          else:
              if initialKey is None or initialKey is "":
                  flattendictionary(key, value, flatDictionary)
              else:
                  flattendictionary(initialKey + "." + key, value, flatDictionary)