My Youtube Channel - COMSCIGUIDE

Interview Puzzles :

These are the common questions that are asked in the HR interview. As puzzles are updated from interview to interview, in this playlist, recently asked puzzles are updated with the removal of others. 

For full playlist of Interview puzzles videos :

  

https://www.youtube.com/playlist?list=PL3v9ipJOEEPfI4zt4ExamGJwndkvg0SFc

24 standard interview puzzles:  

https://www.youtube.com/playlist?list=PL3v9ipJOEEPefIF4nscYOobim1iRBJTjw

Aptitude training playlist link : 

https://www.youtube.com/playlist?list=PL3v9ipJOEEPfumKHa02HWjCfPvGQiPZiG

For C and C++ questions, that are asked in the interviews, go through the posts in the link :  

http://comsciguide.blogspot.com/

For more videos, my youtube channel : 

https://www.youtube.com/channel/UCvMy2V7gYW7VR2WgyvLj3-A

This video helps you how to prepare for an interview.

How to prepare for an Interview

Read More

Dynamic memory allocation (Stack vs Heap)

          Application’s memory – The memory that is assigned to a program or application while running is divided into 4 segments.

Heap (dynamic allocated)

Stack  (functions and local variables)

Global / Static

Code ( text ) (instructions)

·       The amount of memory that is reserved for main function is called as Stack Frame.

·       Heap size is not fixed.

For example :

#include<iostream>

using namespace std;

int z;                 // global variables.

int mul(int a,int b)

{

int c;

c=a*b;

return c;

}

int init()

{

int a,b,c;

scanf("%d%d",&a,&b);

c=mul(a,b);

return c;

}

int main()

{

z= init();

printf("%d",z);

return 0;

}

While the program mul() is executing, the stack will have memory assigned as mentioned below :

mul() a, b, c

scanf()

init() a, b, c,

Main

The program starts with the main() function and is pushed into the stack. In main init() function is called next, so the main function stops executing and init() function resume and its variables are also declared in its memory declared for init(). Similarly for others.

·       The size of the stack for a method is calculated when the program is compiling. At any time, the function at the top of stack is executing, remaining are idle.

·       Once the function returns, the memory in stack is popped out and next function below it, will start executing.

·       Global variables are declared outside the stack are allocated in separate global memory section. So by this we can access global variables anywhere in the program, until it terminates.

·       Local variables declared inside each function, are allocated in their functions stack memory and also limited to those functions only.

·       When main functions returns, the program terminates and the global variables are also cleared.

·       If the stack calls goes beyond the memory, then an error will occurs i.e. stack overflow.

·       The size of Heap is not fixed. It will grow as long as it don’t run out of memory in the system itself.

·       we can keep the data in the heap till what time we need i.e. we can have control on the allocation and de-allocation.

·       Heap is also called as Dynamic memory and it’s allocation is called as Dynamic memory allocation. It’s different from heap (data structure).

In c, There are 4 functions that are used in dynamic memory allocation.

They are

       1) malloc()

       2) calloc()

3) re-alloc()

4) free()

In c++, there are extra 2 more operators including above.

New and delete

For example:

int main()

{

int a;

int *p, *q;

p = (int*)malloc(sizeof(int));

*p = 10;

q = (int*)calloc(3,sizeof(int));

*q = 10;

*(q+1) = 20;

*(q+2) = 30;

return 0;

}

·       Free(p) – It will deallocate the memory that is assigned to p.

·    p will have only the starting address of that memory block.

·       If we won’t mention free(p), in c or delete in c++ , the data will be still available until the program terminates (act like global variables ).

Recent posts :

3 ways to solve Recurrence relations

Differences between Complete, Balanced, Ordered, Full, Perfect Binary tree

Read More

Differences between Complete, Balanced, Ordered, Full, Perfect Binary tree

Binary Tree:

A Tree in which each node has a degree of atmost 2. i.e. it can have either 0,1 or 2 children.

Here, leaves are H, I, J. Except these, remaining internal nodes has atmost 2 nodes as their child.

Full Binary tree:

Every node should have exactly 2 nodes except the leaves. It is also called as Strict Binary Tree or 2- Binary Tree or Proper Binary Tree.

Complete Binary Tree:

It is a binary tree in which every level (except possibly the last) is completely filled, and all nodes are as far left as possible. 

   

The above 4 fig’s are Complete Binary Trees.

        Fig1                            fig2                               fig3

fig 4         fig 5

These are not complete trees as in fig1 at level 1, the 0 node has no children. In fig 2, nodes 2, 5, 9 doesn’t have left child. For a tree to be complete tree, right child is not necessary but left child is must if right child is present incase of last level. For fig 3, the node 0 doesn’t have a left child.same as for fig 4 and fig 5.

Ordered Binary Tree :

        It is a Binary Tree in which all the elements are arranged in an order i.e. For a node, All elements of left sub-tree should be smaller than the node and all elements of right sub-tree should be larger than the node.

In the above fig, Every node has smaller element as left child and larger element as right child.

·        An Ordered Tree may or may not be balanced. It may have time complexity of O(n) or O(logn). 

In the above Tree, we see that even though it is an Ordered Tree, it is not balanced. For adding,deleting and Searching operations, it has time complexity of O(n) same as linked list.

Balanced Binary Tree:

It is a Binary tree in which the elements are ordered and no leaf  is at “much greater” depth than any other leaf. It will have time complxity of O(logn).

Perfectly balanced binary tree:

It is a Balanced binary tree in which the difference in the left and right tree nodes’ count of any node is at most one.

In the given fig, the left binary tree is ordered whereas right binary tree is ordered and balanced.

To avoid imbalance in the tree to search, apply operations that rearrange some elements of the tree when adding or removing an item from it. These operations are called Rotations. The type of rotation should be further specified and depends on the implementation of the specific data structure. As examples for structures like these we can give Red-Black tree, AVL-tree, AA-tree, Splay-tree and others.

Non-binary balanced trees:

Non-binary balanced search trees also have multiple implementations with different special properties. Examples are B- Trees, B+ Trees and Interval Trees. All of them are ordered, balanced, but not binary. Their nodes can typically hold more than one key and can have more than two child nodes. These trees also perform operations like insert / search / delete very fast.

Perfect binary tree:

        In this tree, Every node has exactly two nodes and all levels are completely filled.

                                ( or )

A perfect binary tree is a binary tree in which all leaves have the same depth or same level.

·        In general A perfect binary tree satisfies all the properties of  complete and full binary trees.

   

·        For an Orderded perfect binary tree, time complexity for search, insert and remove operations has O(logn).

For Graph Terminology :  Click here

Why analysis of Algorithms : Click here

4 pillars of OOPS concept : Click here

Read More

Graph Terminology

Adjacent vertices :

        An adjacent vertex of a vertex v in a graph G is a vertex that is connected to v by an edge.

                                        ( or )

In simple if two vertices in an undirected graph are connected by an edge, then they are called as Adjacent vertices or Neighbors.

 fig 1

               

In fig1:

Adjacent vertices of a : b,c,e

Adjacent vertices of b : a

Adjacent vertices of c : a,d,e

Adjacent vertices of d : c,e

Adjacent vertices of e : a,c,d

·       But For an directed graph it is different .For example

Fig: 2

·       Here there is an edge between 3, 2 which is represented as  (3, 2) means 2 is adjacent to 3 but 3 is not adjacent to 2.

Predecessor and Successor :

       The vertex of which the arrow comes out is called Predecessor and the vertex that is pointing by the arrow is called Successor.

In Fig 2. Vertex 3 is the Predecessor and Vertex 1 is the Successor.

Degree of a Vertex :

        In graph theory, the Degree of a vertex of a graph is the Number of edges that are incident on that vertex.

·       If there is a loop, the edges of that loop is counted as twice.

·       The degree of a vertex v is denoted deg(v) or deg v.

·       The maximum degree of a graph G, denoted by Δ(G)

·       The minimum degree of a graph, denoted by δ(G)

Fig 3

In the above fig.3, the degree of vertex 5 is 5

Terminology on vertex :

·       A vertex with degree 0 is called an Isolated vertex.

In the above fig.3, The degree of vertex 0 is 0.

Fig .4

·       A vertex with degree 1 is called a Leaf vertex or End vertex, and the edge incident with that vertex is called a Pendant edge. In the graph (fig 4) on the right, {3,5} is a pendant edge.

·       A vertex with degree n − 1 in a graph on n vertices is called a Dominating vertex.

In-degree and Out-degree :

In a directed graph it is important to distinguish between In-degree and Out-degree. For any directed edge, it has two distinct ends:  a head (the end with an arrowhead) and a tail. Each end is counted separately. The sum of head endpoints count toward the In-degree of a vertex and the sum of tail endpoints count toward the Out-degree of a vertex.

·       The In-degree of a vertex V written by deg −(v).

·       The Out-degree of a vertex V written by deg +(v)

For example :

Fig .5

·       vertex 2 has In-degree 2.

·       vertex 2 has Out-degree 1.

Question :

Find the In -Degree, Out-degree, and degree of each vertex of a graph given below.

Fig.6

In-Degree of a vertex 'v1' = deg(v1) = 1 and Out-Degree of a vertex 'v1' = deg(v1) = 2

In-Degree of a vertex 'v2' = deg(v2) = 1 and Out-Degree of a vertex 'v2' = deg(v2) = 3

In-Degree of a vertex 'v3' = deg(v3) = 1 and Out-Degree of a vertex 'v3' = deg(v3) = 2

In-Degree of a vertex 'v4' = deg(v4) = 5 and Out-Degree of a vertex 'v4' = deg(v4) = 0

In-Degree of a vertex 'v5' = deg(v5) = 1 and Out-Degree of a vertex 'v5' = deg(v5) = 2

In-Degree of a vertex 'v6' = deg(v6) = 0 and Out-Degree of a vertex 'v6' = deg(v6) = 0

·       By the definition, the degree of a vertex is Deg(v) = deg−(v) + deg+(v). Therefore

Degree of a vertex 'v1' = deg(v1) = 1 + 2 = 3

Degree of a vertex 'v2' = deg(v2) = 1 + 3 = 4

Degree of a vertex 'v3' = deg(v3) = 1 + 2 = 3

Degree of a vertex 'v4' = deg(v4) = 5 + 0 = 5

Degree of a vertex 'v5' = deg(v5) = 1 + 2 = 3

Degree of a vertex 'v6' = deg(v6) = 0 + 0 = 0

Read More