DataStrcuture and Algorithum

arslanaslam007 commented 5 years ago

Top Short Points

arslanaslam007 commented 5 years ago

Basic

Programming Fundamental

Flow Charts
Pseudo Codes
Data Types
Variables
Constants

Questions

GCD of Two Numbers https://www.programiz.com/c-programming/examples/hcf-gcd LCM of Two Numbers https://www.programiz.com/c-programming/examples/lcm Number is Prime or Not Number is Armstrong or Not

DataStructure What is Data Structure ? Best Data structure and Why ? Linear and Non Linear Data Structure ?

what is the differnce between stack and heap?? binary search

arslanaslam007 commented 5 years ago

Code

Qs3: Write a method which check that given string is palindrome or not ?

Qs4: If you have to check that linked list is palindrome then how you will check it ?

Array contains counting from 1 to 100 with 1 element repeating, find that element in O(n) 30. Write all possible values for n, where n&(n-1) = 0; ‘&’ is bit wise operator.

Reverse char array, link list Insertion in BST

Given an array, find max sum made from any two indeces withour repeating. T(n) = O(n)

Qs1: Write a function of fibonacci.

Qs2: Write a function to get the height of tree.

Qs3: Write a function to print tree in level order traversal.

Qs1: (int *) method () { int a = 10; return &a; }

how you will call this method and used the value of a

Qs2: You have an array of size 1000000, having values 1..100 how you will return distinct values from the array, Complexity ?

a) Please write code or pseudocode to convert integer into binary. b) I want to get distinct numbers from an array, i dont know about array(may be sorted, may not be sorted, can have millions of numbers, don't know about its range) just know that it is an integer array

1) Given an integer array rotate it to some given numbers K

2) Given an array find the largest number that can be made by the combinations of all the integers of array

3) You are given a number. Find a path in BST so that the sum of weights of nodes is equal to that given number.

Reverse a given paragraph inplace

Prime Number Printing Code

FIND THE WORD THAT IS MOST REPEATED IN A STRING ARRAY IN O(N).
Given an array like 1,2,3,5,8, and a number n, find all such combinations whose sum is equal to n. like lets say n = 10, then 2,8 3,7 3,5,2 2,3,5 and etc.
y = sin(x) + x^2, write function to find the area under curve given by this function.

file read and write add two number without using operator

let's write some code?

1) main() { main() }

is this possible or not??? If so the what will be the size of stack??

Print numbers from 1 t0 1000 without using loop.

alphanumeric string me sy integers dhoondh k unko sum krna hai

how to check a number is in power of 2

Make BST of given string values. 2. Angle between minute and hour hands when time is 3:42 pm

Palindrome Code Anagram Code

Given an array, find max sum made from any two indeces withour repeating. T(n) = O(n)

arslanaslam007 commented 5 years ago

Stack

Introduction https://www.geeksforgeeks.org/lifo-last-in-first-out-approach-in-programming/

Question

Sort a Stack using temporary stack https://www.geeksforgeeks.org/sort-stack-using-temporary-stack/

Check String is Palindrome or Not https://omkarnathsingh.wordpress.com/2016/11/02/c-program-to-check-whether-given-string-is-palindrome-or-not-using-stack/

Implement Stack using Arrays and Linked List https://www.geeksforgeeks.org/stack-data-structure-introduction-program/

Array Implementation Amortized analysis

Push
 if (isFull() ) 
 reSize(capacity*2);

Pop
 if (top > 0 && top == capacity/4) 
 reSize(capacity/2);

Linked List Hint

To keep the Last In First Out order, a stack can be implemented using linked list in two ways: a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from beginning. b) In push operation, if new nodes are inserted at the end of linked list, then in pop operation, nodes must be removed from end.

Implement stack using queues https://www.geeksforgeeks.org/implement-stack-using-queue/

Revserse Stack using recursion https://www.geeksforgeeks.org/reverse-a-stack-using-recursion/

Find Min/Max in a Stack in Big 1 https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/ https://www.geeksforgeeks.org/find-maximum-in-a-stack-in-o1-time-and-o1-extra-space/

Reverse a String https://www.geeksforgeeks.org/stack-set-3-reverse-string-using-stack/

Prefix & Postfix Expression https://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/ https://www.geeksforgeeks.org/stack-set-4-evaluation-postfix-expression/

Backtracking https://www.geeksforgeeks.org/rat-in-a-maze-backtracking-using-stack/

Clone a Stack without using extra stack https://www.geeksforgeeks.org/clone-a-stack-without-extra-space/

arslanaslam007 commented 5 years ago

Queue https://www.geeksforgeeks.org/queue-data-structure/

DECK A Double Ended Queue (Deque (also called as DECK)) is a queue in which you can insert and remove elements both at the front and at the rear end of the queue. You task is to create a class DECK, with the following interface:

 insertAtTail (val)
 insertAtHead(val)
 deleteAtTail()
deleteAtHead( )

Questions

Implement Queue using Linked List https://www.geeksforgeeks.org/queue-set-2-linked-list-implementation/

Hint Insert at tail & delete at Head Insert at Head & delete at tail

Implement Queue using Stack https://www.geeksforgeeks.org/queue-using-stacks/

Sort Queue Without Extra Space https://www.geeksforgeeks.org/sorting-queue-without-extra-space/

Reverse a Queue https://www.geeksforgeeks.org/reversing-a-queue/

Reverse Queue using Recursion https://www.geeksforgeeks.org/reversing-queue-using-recursion/

Reverse First K Elements of a Queue https://www.geeksforgeeks.org/reversing-first-k-elements-queue/

Priority Queue

Introdunction https://www.geeksforgeeks.org/priority-queue-set-1-introduction/

arslanaslam007 commented 5 years ago

Sorting

Classification Parameters

Time Complexity Time Complexity of Algorithums
Stability Stable sort algorithms sort repeated elements in the same order that they appear in the input.
In Place using no auxiliary data structure
Recursive Recursive or non-recursive
External Sorting When all data is not placed in-memory, then sorting is called internal sorting.
Internal Sorting When all data is placed in-memory, then sorting is called internal sorting.

Sorting Algorithm Types QuickSort

Worst Scenerios

Array is already sorted.
All elements in the array are the same.
Array is sorted in reverse order.

MergeSort

Best Scenerios In Case of External Sorting https://www.geeksforgeeks.org/external-sorting/

HeapSort

Insertion Sort Best Scenerios performs very well for smaller input sizes

Selection Sort https://www.geeksforgeeks.org/selection-sort/

Bubble Sort Best Scenerios performs very well for smaller input sizes and sorted data

https://en.wikipedia.org/wiki/Bubble_sort

Heap Sort https://en.wikipedia.org/wiki/Heapsort https://www.geeksforgeeks.org/heap-sort/

Counting sort https://en.wikipedia.org/wiki/Counting_sort https://www.geeksforgeeks.org/counting-sort/

Radix Sort https://www.geeksforgeeks.org/radix-sort/

Bucket Sort https://www.geeksforgeeks.org/bucket-sort-2/

Reference https://en.wikipedia.org/wiki/Sorting_algorithm https://www.toptal.com/developers/sorting-algorithms https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/

arslanaslam007 commented 5 years ago

Time Complexity

Little o Big o Big Theta Little Omega Big Omega

arslanaslam007 commented 5 years ago

Graph

BFS Traversal ? DFS Traversal ?

arslanaslam007 commented 5 years ago

Recursion

arslanaslam007 commented 5 years ago

Dynamic Programming

arslanaslam007 commented 5 years ago

Tree

Binary Tree ? Root Node and Child Node ? Binary Search Tree ? AVL Tree ? B-Tree ? Red Black Tree ?

Traversals of trees ? (IN PRE POST and LEVEL Order)

find the distance between two nodes of a BST.

arslanaslam007 commented 5 years ago

Linked List

No Contiguous Memory No Same Data Types

https://stackoverflow.com/questions/1131313/is-it-possible-to-have-a-linked-list-of-different-data-types

Types

Linear Single Linked List

Node {
int info;
Node* next
}

LSLL
{ Node * head;
}

Next of Last Node Null

         **Insert At Node**

         void insertAt(int value)
    {
        if (head == NULL)
        {
            head = new Node(Next=NULL,Value=value);
            return;
        }

        Node* root = head;

        while (root->next)
        {
            root = root->next;
        }

        root->next = new Node(Next=NULL,Value=value);
    }

        **deleteAt**

        void deleteAt()
    {
        if (head->next == NULL)
        {
            delete head;
            head = NULL;
            return;
        }
        Node * root = head;
        Node*prev = root;

        while (root->next)
        {
            prev = root;
            root = root->next;
        }

        delete root;
        prev->next = NULL;

    }

Linear Double Linked List

Node {
int info;
Node* next;
Node* prev;
}

LDLL
{ Node * head;
}

Next of Last Node will be Null
Prev of Last Node will be Point to Second Last

Do Practise Insert and Remove Functions https://www.geeksforgeeks.org/doubly-linked-list/

Circular Single Linked List

Node {
int info;
Node* next
}

CSLL
{ Node * head;
}

Last Node of Next will point to Head

        **insert into CSLL**
    void insertAt(int value)
    {
        Node * val = new Node;

        val->next = NULL;
        val->value = value;

        if (head == NULL)
        {
            head = val;
            head->next = head;
            return;
        }

        Node* root = head;
        Node * prev = head;

        do
        {
            prev = root;
            root = root->next;

        } while (root!=head);

        val->next = head;
        prev->next = val;
}

        **delete in CSLL**
    void deleteAt()
    {
        if (head->next == head)
        {
            delete head;
            head = NULL;
            return;
        }

        Node * root = head;
        Node*prev = root;

        while (root->next != head)
        {
            prev = root;
            root = root->next;
        }

        prev->next = head;
        delete root;

    }

       **reverse recursively**
        Node* reverse(Node * root)
    {

        if (root->next == head)
        {
            head = root;
            return head;
        }

        Node * n1=reverse(root->next);

        n1->next = root;
        root->next = head;

        return root;

    }

Reference https://www.geeksforgeeks.org/circular-linked-list/

Circular Double Linked List

Node {
int info;
Node* next
Node* prev
}

CDLL
{ Node * head;
}

Last Node of Next will point to Head
Last Node of Next will point to Second Last Node

Prev of Head Node will Point to Last Node

Reference https://www.geeksforgeeks.org/data-structures/linked-list/

Questions

Solve as many Questions from here as Possible https://www.geeksforgeeks.org/data-structures/linked-list/

Delete a node in O(1). Provided that the linked list is singly, and you have the refrence of only that node which is to be deleted. https://www.geeksforgeeks.org/in-a-linked-list-given-only-a-pointer-to-a-node-to-be-deleted-in-a-singly-linked-list-how-do-you-delete-it/

arslanaslam007 commented 5 years ago

Heap

min heapify max heapify

arslanaslam007 commented 5 years ago

HashTable

Perfect hash functions How to solve the problem of collisions in Hash Tables?

arslanaslam007 commented 5 years ago

Sets

arslanaslam007 commented 5 years ago

Pointer

Pointer Size Depends Upon Hardware... Pointer Datatype helps in deference...

Important

address + any integer like

Consider Pointer case XXXabc01010 + 1 Now the Next ADDRESS will be one jump away from base address but what that jump cast does it cast one byte does it cast two byte does it cast four byte

all it depends upon datatype of address...

Dangling Pointer A pointer pointing to a memory location that has been deleted (or freed) is called dangling pointer.

Reasons Behind Dangling Pointer

Deallocation of Memory
Function Call
Variable gets out of Scope

Void Pointer A pointer that points to some data location in storage, which doesn’t have any specific type

Null Pointer int *p=NULL; NULL Pointer is a pointer which is pointing to nothing

Wild Pointer A pointer which has not been initialized to anything (not even NULL) is known as wild pointer.

Reference https://www.geeksforgeeks.org/dangling-void-null-wild-pointers/

Pointer Usage

Pointer Arithmetic https://www.tutorialspoint.com/cprogramming/c_pointer_arithmetic.htm

Array of Pointers https://www.tutorialspoint.com/cprogramming/c_array_of_pointers.htm

Pointer to Pointer https://www.tutorialspoint.com/cprogramming/c_pointer_to_pointer.htm

Passing Pointer to Function https://www.tutorialspoint.com/cprogramming/c_passing_pointers_to_functions.htm

Return Pointer from Function https://www.tutorialspoint.com/cprogramming/c_return_pointer_from_functions.htm

// Pointer to an integer int *p;

// Pointer to an array of 5 integers int (*ptr)[5];
int arr[5];

// Points to 0th element of the arr. p = arr;

// Points to the whole array arr. ptr = &arr;

p is pointer to int ptr is pointer to array

ptr

` int a[6] = { 1,2,3,4,5,6 };

int * p = a;
int(*ptr)[6] = &a;

for (int i = 0; i < 6; i++)
{
    cout << p[i];
}

for (int i=0;i<6;i++)
{
    cout << (*ptr)[i];
}

Both will Produce same output. `

Reference https://www.geeksforgeeks.org/pointer-array-array-pointer/

Pointer Data Types

int const s; s is a non constant pointer to constant pointer to integer non constant

int (*p)[4]; p is a pointer to row-size 4 of type integer non constant

Stack int a; int arr[12];

Heap int p= new int; int p = new int [12];

Shallow Copy & Deep Copy https://stackoverflow.com/questions/184710/what-is-the-difference-between-a-deep-copy-and-a-shallow-copy

Applications of Pointer

Dynamic Memory Allocation
Efficiency Purpose
Multiple Return

https://www.geeksforgeeks.org/applications-of-pointers-in-c-cpp/

Questions

Where does a custom object is created? on stack or on heap? https://stackoverflow.com/questions/10157122/object-creation-on-the-stack-heap

int a = 10; int* ptr = &a;

Value of a through ptr address of a through ptr address of ptr is **ptr is valid

Answers *ptr ptr &ptr No

arslanaslam007 commented 5 years ago

Bitwise Operator

arslanaslam007 commented 5 years ago

Array

Definition Contiguous Same Data Types

Advantages We can access an element of Array by using an index.

Disadvantage We have to declare Size of an array in advance.

Declare Array int arr[5];

Access Elements

cout<<arr[0];
cout<<(*arr+0);

Questions

Check Whether a Number is Prime or Not https://www.programiz.com/cpp-programming/examples/prime-number

Check Whether a Number is Armstrong Number or Not https://www.programiz.com/c-programming/examples/check-armstrong-number Clock Angle

Hr arm

12. Hr. =. 360 °

1hr. = 30°

7hr 20 min=. 7 +20/60 ,= 7.33 hr

=. 7.33*30. =. 219.9 °

Min arm

60 min = 360°

1min = 6°

20 min. =20*6. =120°

Difference. =. 219.9–120=99.9°

Difference between hr arm & min arm

Is 99.9° .

https://www.quora.com/What-is-the-angle-between-the-minute-and-hour-hand-at-7-20

Binary Search https://www.geeksforgeeks.org/binary-search/

Array Rotation https://www.geeksforgeeks.org/array-rotation/

Find Element in a Sorted and Rotated Array https://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/

arslanaslam007 commented 5 years ago

Matrix

Stack 2D Array

int mat[2][3] = { {1,2,3},{4,5,6} };

for (int i = 0; i < 2; i++)
{
    for (int j = 0; j < 3; j++)
        cout << mat[i][j];
}

int *psingle=(int *)mat;

for (int i = 0; i < 6; i++)
{
    cout << psingle[i];
}

int (*parray)[3]=mat;

for (int i = 0; i < 2; i++)
{
    for(int j=0;j<3;j++)
        cout << parray[i][j];
}

int (*pmat)[2][3]=&mat;

for (int i = 0; i < 2; i++)
{
    for (int j = 0; j < 3; j++)
        cout << (*pmat)[i][j];
}

All will Produce Same Output

Heap 2D Array

` int *mat = new int[2];

for (int i = 0; i < 2; i++)
{
    mat[i] = new int[3];
}

int c = 1;
for (int i = 0; i < 2; i++)
{
    for (int j = 0; j < 3; j++)
        mat[i][j] = c++;
}

for (int i = 0; i < 2; i++)
{
    for (int j = 0; j < 3; j++)
        cout << mat[i][j];
}

int *psingle = (int *)mat;

for (int i = 0; i < 2; i++)
{
    for (int j = 0; j < 3; j++)
        cout << ((int *)(psingle[i]))[j];
}

//Not Possible to Traverse with pointer to array

` All will Produce Same Output

Accessing array elements using pointers

In a single dimensional array a[100], the element a[i] can be accessed as a[i] or (a+i) or (i+a) Address of a[i] can be accessed as &a[i] or (a+i) or (i+a)

In two dimensional array a[100][100], the element a[i][j] can be accessed as a[i][j] or ((a+i)+j) or (a[i]+j) Address of a[i][j] can be accessed as &a[i][j] or a[i]+j or (a+i)+j In two dimensional array, address of ith row can be accessed as a[i] or *(a+i)

Row Major Order Column Major Order

int Mat[2][3]={1,2,3,4,5,6};

Find Address of Mat[0][2]; m row n column

Consider Row Major Order mat + (im) + j Consider Column Major Order mat + (jn) + i

https://stackoverflow.com/questions/2151084/map-a-2d-array-onto-a-1d-array

Reference https://en.wikipedia.org/wiki/Row-_and_column-major_order

arslanaslam007 commented 5 years ago

Functions

Argument & Parameter

A parameter is a variable in a method definition. When a method is called, the arguments are the data you pass into the method's parameters.

public void MyMethod(string myParam) { }

...

string myArg1 = "this is my argument";
myClass.MyMethod(myArg1);

Signature it includes the name of the function and the types of the parameters (optionally in C)

Function Deceleration it includes return type , the name of the function and the types of the parameters (optionally in C)

Call By Value swap(x,y); void swap(int x, int y);

Call By Reference swap(&x,&y); void swap(int x, int y);

and one more way swap(x,y); void swap(int & x, int & y);

https://www.tutorialspoint.com/cprogramming/c_function_call_by_value.htm https://www.tutorialspoint.com/cprogramming/c_function_call_by_reference.htm

Function Overloading Function can be overloaded on the basis of signature

Default Argument https://www.geeksforgeeks.org/default-arguments-c/

arslanaslam007 commented 5 years ago

Heap

arslanaslam007 commented 5 years ago

AVL Tree

1 Height of Left Tree is Higher Height of Left Tree Left Child is Higher Height of Left Tree Right Child is Higher 2 Height of Right Tree is Higher Height of Right Tree Left Child is Higher Height Of Right Tree Right Child is Higher

Left Left Height of Parent is Greater than 0 Height of Parent Left is Greater than 0

Make Parent my Right Child Make My child my parent left Child

Left Right Height of Patent is Greater than 0 Height of Parent Left is Less than Zero

FIRST perform RR and than LL

Right Right Height of Parent is less than Zero Height of Parent Right is less than zero

Make Parent my left Child Make My child my parent right Child

Right Left Height of Patent is less than 0 Height of Parent Left is greater than Zero

FIRST perform Ll and than RR

arslanaslam007 / IT_Material