Data Structures and Algorithms (DSA) For Placements | Basics To Ace It | Series in HinglishData Structures and Algorithms (DSA) For Placements | Basics To Ace It | Series in Hinglish

#include<bits/stdc++.h> -> for all the packages in cpp.

 1. Array and Vectors:

Array : Fixed size

Vectors : Dynamic Size/Dynamic array (C++ and Java) 

Similarly Arraylist : Dynamic array (Java)

Vectors: its capacity get double when new element is entered after exceeding old capacity .

Ex: 

here push_back() is used for inserting new element at the end of vector.

now the size will return the actual size of vector i.e 3 here for 3 elements.

but the capacity will return 4 i.e it get doubled after entering of 3rd value in vector.

> Binary search: O(log n)

>2 pointer approach[ O(n) for searching O(nlog n) for sorting (if required) So total O(nlogn) ] : iteration from both the sides to reduce time complexity-> start index , end index

Order of Big O Complexity

O(k) -> O(logn) -> O( n^1/2 )->O( n) -> O(nLogn) -> O(n^2) -> O(n^3) ...... ->O(2^n) -> O(exponential) -> O( factorial )

just start example for sum of 2 number equal to 'x' with O(nLogn) complexity.

1. if for happy case
2. for shifting left the end index
3. for shifting right the start index 

same example in java for returning index target as sum of two numbers.

Q . Find majority element in a List or Array.

A . 

    1. can be done using sorting and then counting using for loop for -> next element = prev element then     count++ ,So as the count > sizeOfArray/2 ,that element is majority element.

    2. best way sort array and take mid element it will always be the majority one :D.

   

> Merge Sort : Divide and conquer

>Quick Sort : 

>Moores Algo [ O(n) ] :How does Moore's voting algorithm work?

The Boyer–Moore majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space.

Logic : -> Iterate over array.

->taking iterating element as candidate for majority element

->Votes : +1 for same value as prev and -1 for different value.

->Vote for majority element (worst case ) : 1

So at the end majority element will be there present as candidate and vote > or =1.

Q . find weather string1 is anagram of string2.

        apple =>anagram => pleap (anagram : is any string having same characters and same no of times)

A .    

        1. we can sort both string [ O(nLogn) ] then compare each character in string [ O(n) ]

        2. we can create an integer array of 26 size for both the strings and store the frequency of occurrence of each alphabet then compare both array [ O(n) ]. As in image below :

        3 . We can use same above approach and use single array of size 26 we increase value each time we get same value for string1 as done above but for string2 we will decrease values at that character index so if at the end when we traverse whole array the array should be empty.

means each element present in string 1 were present in string 2 with same number of times.

        4. Same problem can be done using map by storing each key as alphabets and value as its count ,So each time the key repeats its value should be incremented by 1, and this will be done for both string then compare them both.

for a question in codechef found that array took less time to execute then vector.?