Check whether string can be generated from given grammar ?

Write a code to check whether given string can be generated from given grammar ?

Grammar  :

S – > 122S
S – > 12S
S – > 1S
S – > “”

==================================================================================
Input :
12221
Output :
0

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

Input :
121
Output:
1

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

O = > False (Cannot be generated)

1 = > True (Can be generated)

 

 

 

Knight tour problem code in c

What is Knight tour problem ?

Read here

Constraint of code:

In below code knight starts from top-left position.

 

 

 

Find the occurence of each number from array in O(n) ?

Find the the occurrence of each number from given array of size n , where elements ranges from 0 to n-1 ?
Complexity : O(n)
Space complexity : O(1)
e.g.
Input:
5 3 3 2 1 3 8 7 3
Output:
3 occurs 4 times

Solution :

Code provided by : Arpit Agrawal

Dereferencing void pointer

Here is the sample code for dereferencing void pointer.

 

Graph and its representation

Graph and its representation

What is Graph?

Graph consists of a set of nodes or vertices and edges or arcs. Edge joints two vertices, edge (v,u) is said to be go from v to u. Graph may also associate some weight to edges.

Types of Graphs:

Directed, Undirected, Weighted, Unweighted

Some of the graph Algorithms:

Depth First Search (DFS), Breadth First Search (BFS), Dijkstra’s Algorithm, Floyd – Warshall algorithm

 

Graph and its representation

Representation of Graph in Programming:

Adjacency Matrix

Adjacency List

Adjacency Matrix:

A 2D matrix in which row presents source vertices and column represents destination vertices.

If cell(I,j) ==1 it means there is a edge from i to j.

If cell(I,j)==0 it means there is no edge from i to j.

 

Graph :

Graph and its representation

 

 

Adjacency Matrix Representation of Graph

1             2             3             4             5              6

1              0              1              0              0              1              0

2              1              0              1              0              1              0

3              0              1              0              1              0              0

4              0              0              1              0              1              1

5              1              1              0              1              0              0

6              0              0              0              1              0              0

 

Adjacency List Representation of Graph:

Vertices are stored as list of array, and every vertex contains point to list of adjacent vertices.

 

1 => 2 => 5

2 => 1 => 3 => 5

3 => 2 => 4

4 => 3 => 5 => 6

5 => 1 => 2 => 4

6 => 4

Dangling pointer

What is dangling pointer ?

In programming dangling pointer is pointer which doesn’t point to valid object or memory. Dangling pointer arises when some memory is deallocated or deleted and pointing pointers value is not modified. So pointing pointer still points to the deleted memory address which is invalid. This pointer is known as dangling pointer. When some process tries to modify the address which is pointed by dangling pointer it causes segmentation fault in your program.

 

Causes of dangling pointer :

1. when global variable points the some variable in function or local block.

Solution :

initialize ptr=NULL immediate after block completion

2. Deallocating dynamic memory using free()

Solution :

After deallocation  of memory, immediate initialize pointer to NULL.

3. declaration of pointer

Solution :

 

 

C code to hide input password

C program to hide input password with *
In this code Password accepts all character except ‘\n’ .

password

 

 

 

Narcissistic Number (Armstrong Number)

Narcissistic Number is a number that is the sum of its own digits each raised to the power of the number of digits.

e.g.

153 = 13+53+33
1634 = 14+64+34+44

C code for finding whether given number is Narcissistic Number or not.

Code provided by : Manoj

infix to postfix conversion

infix to postfix conversion of expression code

Infix notation : Infix notation is the common arithmetic and logical notation, in which operator is written between operand.

e.g.
1+2

1+2*3

Postfix notation: Operators are written after their operands.

e.g.
1 2 3 + * 4 /

Some Examples of conversion of infix to postfix expression

Infix Postfix
A * B + C / D 

A * (B + C) / D

A B * C D / + 

A B C + * D /

 

Infix to postfix conversion of expression code in C