C Programming Important notes

1) void *realloc(void *ptr, size_t size);
-> realloc changes the size of the allocated memory pointed to by the argument ptr
-> newly allocated memory will be uninitialized
-> you can pass a NULL ptr safely to realloc
-> realloc may move your data to a new pointer and free the memory at the old pointer. It will return the new pointer, or the old pointer if the data is not moved.

2) Calloc
-> allocates a region of memory large enough to hold “n elements” of “size” bytes each. Also initializes contents of memory to zeroes.
-> void *calloc (number_of_blocks, size_of_each_block_in_bytes);
-> The allocated region is initialized to zero.
-> void pointer (void *). If the allocation succeeds, a pointer to the block of memory is returned.
void *calloc(size_t nelements, size_t bytes);

Malloc:
-> allocates “size” bytes of memory.
-> void *malloc (size_in_bytes);
-> The contents of allocated memory are not changed. i.e., the memory contains unpredictable or garbage values. This presents a risk.
-> void pointer (void *). If the allocation succeeds, a pointer to the block of memory is returned.
void *malloc(size_t size);

3) In theory, which is faster, the call to strcpy or the call to memcpy?

#include <string.h>
#include <stdlib.h>
int main(){
        char msg[12] = "Hello World";
        char buffer1[12];
        char buffer2[12];

        strcpy(buffer1, msg);
        memcpy(buffer2, msg, sizeof(msg));
        return 0;
}

Answer:
memcpy should be faster because it does not need to check every byte for a NULL, it is copying a known size of data.

4)Variables declared outside of functions or with the static specifier are always initialized to zero. Therefore this program has deterministic behavior.

#include <stdlib.h>
#include <stdio.h>
int* ptrToData;
int main(){

    if (!ptrToData){
        ptrToData = (int*)malloc(sizeof(int) * 10);
        printf("%p\n", ptrToData);
    }
    free(ptrToData);
    return 0;
}

5) Fortunately, C/C++/Java makes this simple.

* To write numbers in octal, precede the value with a 0. Thus, 023 is 238 (which is 19 in base 10).
* To write numbers in hexadecimal, precede the value with a 0x or 0X. Thus, 0x23 is 2316 (which is 35 in base 10).

6)
How to Write a Negative Value
When you write 0x23, you might wonder how to negate it. Should you write the minus sign before the 0x, or after it? The answer is before. 0x indicates that the digits afterwards are written in hex. – is an operator, so it applies to a non-negative representation. Thus, you write -0x23. which is equivalent to -35

7) Structure Member Alignment, Padding and Data Packing

http://www.geeksforgeeks.org/structure-member-alignment-padding-and-data-packing/
8: C Bit Fields : http://msdn.microsoft.com/en-us/library/yszfawxh.aspx
struct-declarator:declarator
type-specifier declarator opt : constant-expression

The constant-expression specifies the width of the field in bits. The type-specifier for the declarator must be unsigned int, signed int, or int, and the constant-expression must be a nonnegative integer value. If the value is zero, the declaration has no declarator. Arrays of bit fields, pointers to bit fields, and functions returning bit fields are not allowed. The optional declarator names the bit field. Bit fields can only be declared as part of a structure. The address-of operator (&) cannot be applied to bit-field components.
Unnamed bit fields cannot be referenced, and their contents at run time are unpredictable. They can be used as “dummy” fields, for alignment purposes. An unnamed bit field whose width is specified as 0 guarantees that storage for the member following it in the struct-declaration-list begins on an int boundary.

Bit fields must also be long enough to contain the bit pattern. For example, these two statements are not legal:

short a:17; /* Illegal! */
int long y:33; /* Illegal! */

This example defines a two-dimensional array of structures named screen.
struct
{
unsigned short icon : 8;
unsigned short color : 4;
unsigned short underline : 1;
unsigned short blink : 1;
} screen[25][80];

7) C bit field storage question: stackoverflow.com/questions/21164939/unexpected-behaviour-of-bit-field-operator-in-c

8)

#include<stdio.h>
struct st
{
    int x;
    static int y;
};
 
int main()
{
    printf("%d", sizeof(struct st));
    return 0;
}

->In C, struct and union types cannot have static members. In C++, struct types are allowed to have static members, but union cannot have static members in C++ also.

9: A structure cannot contain a member of its own type because if this is allowed then it becomes impossible for compiler to know
sizeof such struct. Although a pointer of same type can be a member because pointers of all types are of same size and compiler cancalculate size of struct

10) Size of array can’t be constant

#include<stdio.h>
void main(){
    int const SIZE=5;
    int expr;
    double value[SIZE]={2.0,4.0,6.0,8.0,10.0};
    expr=1|2|3|4;
    printf("%f",value[expr]);
}

Give compiler error

11) strlen(“nishant”) = 7
sizeof(“nishant”) = 8
strlen(“nishant “) = 8
sizeof(“nishant “) = 10
strlen(“nishantkumar”) = 7
sizeof(“nishant kumar”) = 16

12) Hexadecimal : 0X, \x,
Octate : 0 Followed by number less then 7 ex: 01001 = 513 , ‘\111’ = 73 here \ representing octate

#include<stdio.h>
#define WWW -1
enum {cat,rat};
void main(){
    int Dhoni[]={2,'b',0x3,01001,'\x1d','\111',rat,WWW};
    int i;
    for(i=0;i<8;i++)
         printf(" %d",Dhoni[i]);
}

2 98 3 513 29 73 1 -1

In c any character is starting with character ‘\’ represents octal number in character. As we know octal digits are: 0, 1, 2, 3, 4, 5, 6, and 7. So 8 is not an octal digit. Hence ‘\08’ is invalid octal character constant.

13) 

#include<stdio.h>
void main(){
    int a;
    a= (3,4,5);
    printf("%d",a);
}

[/sourcecode ]
a= 5


 #include<stdio.h>
void main(){
    int a;
    a= 3,4,5;
    printf("%d",a);
}

a=3

14) What will be output if you will compile and execute the following c code?

void main(){
char c=125;
    c=c+10;
    printf("%d",c);
}

15:

 #include "stdio.h"
#include "string.h"
void main(){
   char *str=NULL;
   strcpy(str,"cquestionbank");
   printf("%s",str);
}

Note:

void strcpy(char *target, char *source){
   while(*source)
   {
      *target = *source;
      source++;
      target++;
   }
   *target = '\0';}
  ***Note: In strcpy function target should not be character pointer.

16)

void main(){
int i=10;
static int x=i;
if(x==i)
printf("Equal");
else if(x>i)
printf("Greater than");
else
printf("Less than");
}

Output: Compile time error
Explanation:
static variables are load time entity while auto variables are run time entity. We can not initialize any load time variable by the run time variable.
In this example i is run time variable while x is load time variable.

17)

#include<stdio.h>
int main(){
    printf("%c",*"abcde");
return 0;
}

18) Label of GOTO: scope is function block it is not visible outside of function.

19) Scope of variable

19)

#include<stdio.h>
int main(){
    int i=0;
    {
         auto int a=20;
         XYZ:;
         printf("%d",a);
         a++;
         i++;
    }
    if (i<3)
         goto xyz;
    return 0;
}

Explanation: Variable a which declared inside inner block has scope only within that block. Ones program control comes out of that block variable will be dead. If with the help of goto statement we will go to inside that inner block in the printf statement complier will not known about variable a because it has been destroyed already. Hence complier will show an error message: undefined symbol a. But if you will write goto statement label before the declaration of variable then there is not any problem because variable a will again declared and initialize.

20) We cannot initialize extern variable locally i.e. within any block either at the time of declaration or separately. We can only initialize extern variable globally. For example:

(a)

#include <stdio.h>
int main(){
extern int i=10; //Try to initialize extern variable
                 //locally.
    printf("%d",i);
    return 0;
}

Output: Compilation error: Cannot initialize extern variable.

(b)

#include <stdio.h>
int main(){
    extern int i; //Declaration of extern variable i.
    int i=10;     //Try to locally initialization of
                  //extern variable i.
    printf("%d",i);
    return 0;
}

Output: Compilation error: Multiple declaration of variable i.

#include <stdio.h>
extern int i;
int main(){
    i=25;       //Assignment statement
    printf("%d",i);
    return 0;
}
int i=10;   //Initialization statement

Output: 25

21) Typedef is a storage class : http://itee.uq.edu.au/~comp2303/Leslie_C_ref/C/SYNTAX/typedef.html

What are P, NP, NP-complete, and NP-hard ?

P (Polynomial time decidable problems) is a class of problems which can be decided in polynomial time i.e., there’s an algorithm for such a problem which tells whether the solution of a given instance of a problem is true/false in O(n^k) time for some constant k.
For example, deciding whether there exists a path of at most k links between two vertices u and v is in P.

NP (Non-deterministic polynomial time decidable problems) is a class of problems which have short accepting certificates and efficient verification algorithms i.e., given a certificate of a solution, it is easy to check if the problem is satisfied.
Accepting certificate is information which can be used to decide if the answer is true or false.
Formally, a problem is in NP if there exists a verification algorithm A such that for any input x for which the answer is “true”, there is a certificate c such that |c| is polynomial and A(x,c) = true. For any x for which the answer is true, there is no certificate c such that |c| is polynomial and A(x,c) is true.
For example, given a graph G and a number k, deciding whether there exists a clique (complete subgraph) of size k, is in NP.

P is a subset of NP i.e., any problem that is in P is also in NP. It is easy to see that for any problem that can be decided in polynomial time, there exists a verification algorithm that given any certificate just ignores the certificate and returns the result of the polynomial-time algorithm.

Whether NP is also a subset of P (i.e., P = NP) is an open question. No one knows yet.

NP-hard is a class of problems which are hardest of all problems in NP. These are the problems such that if we can solve them fast, then we can solve all problems in NP fast and P would equal NP. NP-hard problems may be of any type: decision problems, search problems, or optimization problems so they may not even be in NP.
For example, the clique problem discussed above is NP-hard.

NP-complete is a class of problems which are in NP and are NP-hard. NP-complete problems transform to each-other by polynomial-time many-one reductions so if a polynomial-time algorithm exists for any one of them, then polynomial algorithms exist for all of them. However, no polynomial algorithm for any NP-complete problem has yet been found.
For example, the clique problem discussed above is NP-complete.

Huffman Code: Binary Tree construction for given message by huffman algorithm

Construction Of Huffman tree for a given message

Step You have to follow:

Arrange all letters in the increasing order of their frequency and then construct binary tree by assigning least frequency letter as left child to the tree. After constructing binary tree from root to leaf every left branch assigned with 0 and right branch assigned with 1.
Notes: You can also take minimum frequency at right side or assigned it with 0 but be consistent whatever you choose.

Example:   Message contains “EEEABBCCDDEEE” what will be total minimum bits required for store it.

Symbol    Frequency
A       ==   1
B       ==   2
C       ==   2
D       ==   2
E       ==   6

Step 1: Find two char with minimum frequency

   [3]
0/     \1
A       B

Now we have
Weight gain from adding two minimum char ==> [3]
C ==> 2

D ==> 2

E ==> 6

Now Find again 2 minimum and add it Here c => 2 and d => 2 is minimum

  [4]
0/   \1
C     D

Now we have wright [4] , [3], E=> 6 Here minimum is 4 and 3 so merge both above diagram.
      [7]
   0/      \1
  [3]       [4]
 0/ \1    0/   \1
 A   B    C     D

Now we have wright [7], E=> 6 Here we have remaining 2 so merge both above diagram.
   [13]
0/    \1
E      [7]
     0/   \1
    [3]   [4]
   0/ \1  0/ \1
   A   B  C   D

=================================================
Symbol Frequency Code Code Length total Length
A       1         100    3             3
B       2         101    3             6
C       2         110    3             6
D       2         111    3             6
E       6          0     1             6
=================================================
                                   Total=27 Bit required.


Another Good Resource

Programm For Finding Binary Number Addition

Programm For Finding Binary Number Addition
———————————————————————


#include <stdio.h>
int main ()
{
  int a[6]={1,0,0,1,1,1},b[6]={1,1,0,1,1,0},c[7], carry=0, j;
  for(j=5;j>=0;j--)
   {
       c[j+1]=a[j]^b[j]^carry;
       carry = (a[j]*(b[j]^carry))+(b[j]*carry);
   }
  c[j+1]=carry;
  for (j=6;j>=0;j--)
   {
     printf ("%d",c[j]);
   }
return 0;
}

Amazon Interview Questions

How many  distinct binary search tree can be possible by given n node.

Explanation:
n=(0,1,2,3,4, 5) is (1,2,5,14,42) which is the Catalan number
Cn = 2n! / (n+1)! n!

Calculate the minimum number of nodes in AVL Tree with height h.

Explanation:
N(H) =  1               height h=0
N(H) =  2               height h=1
1+ N(H-1) + N(H-2)      height > 1

Find the number of leaf node in given binary tree.

struct CellNode { 
   struct CellNode * leftChild;
   int data;
   struct CellNode * rightChild;
};

countLeafInBST(strcut CellNode *root)
{
      static int value=0;
       if (!root)
          return  0;
       else if (root->leftChild == NULL && root-> rightChild == NULL)
          return 1;
       else
         value = countLeafInBST(root->leftChild ) + countLeafInBST(root-> rightChild );

      return (value);
}

Importance of Loop Invariant in programming

Introduction:

It is hard to keep track of what is happening with loops. Loops which don’t terminate or terminate without achieving their goal behavior is a common problem in computer programming. Loop invariants help. A loop invariant is a formal statement about the relationship between variables in your program which holds true just before the loop is ever run (establishing the invariant) and is true again at the bottom of the loop, each time through the loop (maintaining the invariant).

Why Loop Invariant:
It captures what the loop does not do, i.e., what it leaves unchanged over any single execution of the loop body (and hence over the entire execution of the loop)

Loop Invariant

  •     Invariant means unchanged
  •     The person who writes the loop, also writes the loop invariant which describes what remains unchanged
  •     Permits understanding what the loop does without having to understand (at the same time) how it does it.
  •     We can reason about the loop’s effect on the larger program without hand tracing each loop iteration.

 General Pattern of loop invariant in Code

...
// the Loop Invariant must be true here
while ( TEST CONDITION ) {
// top of the loop
......
......
// bottom of the loop
// the Loop Invariant must be true here
}
// Termination + Loop Invariant = Goal
...
invariant + termination => goal

Below code is example of Loop Invariant

  
  int j = 10;
  for(int i=0; i<11; i++)
   {  
     // Your loop code stuff
     j--;
   } 
  At the end i+j = 10
  so here J= 10 is loop invariant

If you Understand Give me the answer of

 if (i % 2 == 0)
 {
   while (i>=0)
    {
       i = i/2;
       if (i%2 != 0)
         {
       i =i-1;
     }
       else
         {
           i= i-2
         }
    }
 }

 What is appropriate loop invariant for the while loop _________

Reference Link: http://www.cs.miami.edu/~burt/learning/Math120.1/Notes/LoopInvar.html

http://stackoverflow.com/questions/3221577/what-is-a-loop-invariant

Page keyword: What is loop invariant, loop invariant in while loop, loop invariant example, loop invariant code example

Understand Polynomial Vs Non-Polynomial Running time.

We have come across many types of algorithm for solving a problem like sorting array element, Searching in linked list , traversing in tree and many more In addition to this there are  some another algorithm which we generally don’t use and don’t much interested to  know like halting problem in Turing Matching, Finding whether a given grammar is ambiguous or not and many more.So we have categorized algorithm in different group based on there running time.Like categorized Fruit based on Vitamin which contains in side.In the same way we have categorized Algorithm based on there running time or solvable nature of problem.

Category 1: Polynomial Running time Algorithm (P Class)
All of the algorithms we have studied thus far have been polynomial-time algorithms: on inputs of size n, their worst-case running time is O(n^k) for some constant k. It is natural to wonder whether all problems can be solved in polynomial time. The answer is no. For example, there are problems, such as Halting Problem, 3-SAT , MAX-SAT problem are example of NP-Complete problem.

Category 2: Non-polynomial running time Algorithm (NP Class)
A problem which have not worst case running time in polynomial form or let say super polynomial form or that can’t be solved in polynomial time that type algorithm will come under NP Class or  Non-polynomial running time Algorithm Basically you can remember in this way A Problem which we can’t solve or by running it even huge amount of time is known as NP Class Problem .

Point Of Confusion:  

   Randomized quick-sort algorithm  has running time in worst case O(N log N) is it belongs to Polynomial Running time or P class.

Q: In which class you will put this problem ?

Consider final examination scheduling. A school has n courses and five days in which to schedule examinations. An optimal schedule would be one where no student has to take two examinations on the same day. This seems like an easy problem. But there are O(5n) possible different schedules. If we looked at them all with a computer which could check a million schedules every second, the time spent checking for a value of n = 50 would be about

                       200,000,000,000,000,000,000 years!

Thinking Question:  State Whether You can Solve this problem

1)  What is the fastest algorithm for multiplication of two n-digit numbers?
2)  What is the fastest algorithm for matrix multiplication?
3) Can the graph isomorphism problem be solved in polynomial time?

Some More thoughts:

  • The problems which have Yes or No answer are called decision Problem
  • Problems that have an efficient algorithm to solve it are called decidable problems.
  • Problems that can’t be solved with an algorithmm  are called undecidable problems.
  • The class of decision problems that can be solved by Non Deterministic machine in Polynomial time are called NP Problems.
  • A Problem is said to be NP-Complete if it is contained in NP Class and all other problems in NP can polynomially reduced to it (NP Hard)
  • A language is said to be NP Complte if L is in NP and for every language L` in NP there is a polynomial -time reduction of L` to L.
  • If any NP-Complte problem is in P, then P = NP 

Useful Resources : Here

Return number of word from given text in c#.

Some time we come across situation to return fixed number of word from text. Below function will return string which contain number of word which you have supplied during function calling.

        public static string ReturnAmountWordsFromGivenString(string text, int wordAmount)
        {
            string tmpStr;
            string[] stringArray;
            var tmpStrReturn = "";
            tmpStr = text.Replace("\t", " ").Trim();
            tmpStr = tmpStr.Replace("\n", " ");
            tmpStr = tmpStr.Replace("\r", " ");

            while (tmpStr.IndexOf("  ") != -1)
            {
                tmpStr = tmpStr.Replace("  ", " ");
            }
            stringArray = tmpStr.Split(' ');

            if (stringArray.Length < wordAmount)
            {
                wordAmount = stringArray.Length;
            }
            for (int i = 0; i < wordAmount; i++)
            {
                tmpStrReturn += stringArray[i] + " ";
            }
            return tmpStrReturn;
        }

Page Keyword: Return word from text in c#, Return fixed number of word from text program in c#. Return word from text.pgm in c# to count number of words in a text document

Build Heap Time Complexity

Given a set of n elements array, the problem here is to create a heap of these elements. For creating Heap we have two choice

1) obvious approach is to insert the n elements, one at a time, into an initially empty heap. Since the worstcase
complexity of inserts is O (log n), this approach has a worstcase running time of O ( n log n)

BUILD-HEAP(A)

    heap-size[A] <- 1

       for i=2 to length[A]

         do HEAP-INSERT(A, A[i])

Time Complexity: Heap Insert Take Big-oh (log n) So inserting n element will take Big-oh(nlog n).

2) Another approach, purposed by Floyd in 1964, is to use a procedure called ‘pushdown’ repeatedly,
starting with the array consisting of the given n elements in the input-order.

BUILD-HEAP(A)

  heap-size[A] = length[A]

       for i <- length[A]/2 downto 1

          do HEAPIFY(A, i)

Time Complexity: o(nlogn) this is asymptotically tight Note : small Big-oh(n logn)
So Big-oh(n) This is asymptotically tight. So This method will take linear time.