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)

Python stack and queue

Finding if palindrome with stacks and queues in python

import sys
class stackandqueue:
    def __init__(self):
        self.stack = [ ]
        self.queue = [ ]
   
    def pushChar(self, s):
        self.stack.append(s)
       
    def popChar(self):
        return self.stack.pop()
   
    def enqueueChar(self, s):
        self.queue.insert(0,s)
   
    def dequeueChar(self):
        return self.queue.pop()

s=raw_input()
obj=stackandqueue()  

l=len(s)

for i in range(l):
    obj.pushChar(s[i])
    obj.enqueueChar(s[i])
   
isPalindrome=True
'''
pop the top character from stack
dequeue the first character from queue
compare both the characters
'''
for i in range(l / 2):
    if obj.popChar()!=obj.dequeueChar():
        isPalindrome=False
        break
#finally print whether string s is palindrome or not.
if isPalindrome:
    sys.stdout.write ("The word, "+s+", is a palindrome.")
else:
    sys.stdout.write ("The word, "+s+", is not a palindrome.")   
   

Multithreaded file indexer

File Indexer in C++ :

Create a multi-threaded text file indexing command line application that works as
follows:
1. Accept as input a file path on the command line. Please name the executable ssfi. For
example, we'd be able to run your application like this: ./ssfi  <doc file path as input>
2. Have one thread that is responsible for searching the file path, including any sub-
directories, for text files (ending in '.txt')
3. When a text file is found, it should be handed off to a worker thread for processing, and
the search thread should continue searching.
4. There should be a fixed number (N) of worker threads (say, N=3) that handle text file
processing. Adding a command line option to specify N is recommended. For example,
to specify worker threads, ./ssfi -t 3 <doc file path as input>
5. When a worker thread receives a text file to process, it opens the file and reads the
contents to parse the words inside. Words are delimited by any character other than A-
Z, a-z, or 0-9. Words should be matched case insensitive.
6. Once the file search is complete and all text files finish processing, the program prints
out the top 10 words and their counts. Please output the top 10 list of words as
separate lines containing the word, followed by a tab, followed by the count. For
example:
The 1000
Place 650
...
7. A Makefile should be provided to compile your program. Please, no Cmake, Scons, Ant,
bjam, Shell scripts, etc. A simple Makefile is all that is needed.
8. Any libraries used like Boost, should be available to any modern Linux distribution.
Fedora, Ubuntu, Gentoo, Arch, CentOS, etc.


exercise : https://github.com/SabyTech/file-indexer