SDE - 1

Algorithm :

1) Generate all the prime numbers in the range of values of the given array using Sieve Of Eratosthenes.

2) Now make an iteration for ‘arr1’ and check the elements in ‘arr1’ which are prime and store the elements in an array, say ‘finalA’.
 

3) Now make an iteration for ‘arr2’ and check the elements in ‘arr2’ which are prime and store the elements in an array, say ‘finalB’.
 

4) Now calculate the LCS for the two arrays: ‘finalA’ and ‘finalB’ with the help of ‘lcs()’ function using Dynamic Programming.
 

5) Return the array after calculating the longest common subsequence.


TC : O(N*M) , where N=size of array 1 and M=size of array 2
SC : O(N*M)

Algorithm:

1) Find the maximum number max in the array.

2) Create a new auxiliary array dp of size max+1 and store frequencies of unique elements in the array, where dp[i] denotes the number of times i as an element is present in the input array.
 

3) Iterate the dp array(we will use this array to store the results), now for each index i from 2 to MAX we have two choices: dp[i] = max(dp[i-1], dp[i-2] + dp[i]*i).
 

4) Return dp[MAX], which have the maximum sum of the selected numbers.


TC : O(max(MAX, N)), where “MAX” is the maximum element and N is the size of the array.
SC : O(MAX)

Approach 1(Using Hashing) :

We are going to maintain a lookup table(a Hashmap) that basically tells if we have already visited a node or not, during the course of traversal.

Steps :
1) Visit every node one by one, until null is not reached.

2) Check if the current node is present in the loop up table, if present then there is a cycle and will return true, otherwise, put the node reference into the lookup table and repeat the process.
 

3) If we reach at the end of the list or null, then we can come out of the process or loop and finally, we can say the loop doesn't exist.


TC : O(N), where N is the total number of nodes.
SC : O(N)



Approach 2 (Using Slow and Fast Pointers) :

Steps :

1) The idea is to have 2 pointers: slow and fast. Slow pointer takes a single jump and corresponding to every jump slow pointer takes, fast pointer takes 2 jumps. If there exists a cycle, both slow and fast
pointers will reach the exact same node. If there is no cycle in the given linked list, then fast pointer will reach the end of the linked list well before the slow pointer reaches the end or null.
 

2) Initialize slow and fast at the beginning.
 

3) Start moving slow to every next node and moving fast 2 jumps, while making sure that fast and its next is not null.
 

4) If after adjusting slow and fast, if they are referring to the same node, there is a cycle otherwise repeat the process
 

5) If fast reaches the end or null then the execution stops and we can conclude that no cycle exists.


TC : O(N), where N is the total number of nodes.
SC : O(1)

Approach (Using Stack) : 

1) Initialize an empty stack of integers.

2) Initialize a variable lowerBound to store the value of the root of the current tree. Initialize is as INT_MIN. 

3) Iterate through i = 0 to N - 1
3.1) If ARR[i] is smaller than lowerBound, then we will return 0. 

3.2) Repeatedly,
If the stack is non-empty, then remove the element at the top of the stack if it is smaller than ARR[i] and make the removed element as the new lowerBound. 

3.3) Push ARR[i] to the stack. Note that the stack will always contain elements sorted in descending order.

4) Return 1 if we have not returned 0 till now.


TC : O(N), where N = size of the array
SC : O(N)

Vtable : It is a table that contains the memory addresses of all virtual functions of a class in the order in which they are declared in a class. This table is used to resolve function calls in dynamic/late binding manner. Every class that has virtual function will get its own Vtable.


VPTR : After creating Vtable address of that table gets stored inside a pointer i.e. VPTR (Virtual Pointer). When you create an object of a class which contains virtual function then a hidden pointer gets created automatically in that object by the compiler. That pointer points to a virtual table of that particular class.


Some important points about Vtable and VPTR are as follows :

1) Vtable is created by compiler at compile time.
 

2) VPTR is a hidden pointer created by compiler implicitly.
 

3) If base class pointer pointing to a function which is not available in base class then it will generate error over there.
 

4) Memory of Vtable and VPTR gets allocated inside the process address space.
 

5) Vtable gets created for each class which has virtual functions.
 

6) To achieve run time polymorphism effect there should be single level inheritance in our code.

1) Friend functions of the class are granted permission to access private and protected members of the class in C++. They are defined globally outside the class scope. Friend functions are not member functions of the class.

2) A friend function is a function that is declared outside a class but is capable of accessing the private and protected members of the class.

3) There could be situations in programming wherein we want two classes to share their members. These members may be data members, class functions or function templates. In such cases, we make the desired function, a friend to both these classes which will allow accessing private and protected data members of the class.

4) Generally, non-member functions cannot access the private members of a particular class. Once declared as a friend function, the function is able to access the private and the protected members of these classes.

Some Characteristics of Friend Function in C++ :

1) The function is not in the ‘scope’ of the class to which it has been declared a friend.

2) Friend functionality is not restricted to only one class

3) Friend functions can be a member of a class or a function that is declared outside the scope of class.

4) It cannot be invoked using the object as it is not in the scope of that class.

5) We can invoke it like any normal function of the class.

Approach 1 : 

1) Like vertical Order Traversal, we need to put nodes of same horizontal distance together. 

2) We do a level order traversal so that the topmost node at a horizontal node is visited before any other node of same horizontal distance below it. 

3) Hashing is used to check if a node at given horizontal distance is seen or not. 

TC : O(N*log(N)), where N = number of nodes in the binary tree
SC : O(N)



Approach 2 : 

1) This approach is based on the level order traversal. 

2) We’ll keep record of current max so far left, right horizontal distances from the root.

3) And if we found less distance (or greater in magnitude) then max left so far distance then update it and also push data on this node to a stack (stack is used because in level order traversal the left nodes will appear in reverse order), or if we found greater distance then max right so far distance then update it and also push data on this node to a vector.

In this approach, no map is used.


TC : O(N), where N = number of nodes in the binary tree
SC : O(N)

I solved it using DP as I was able to figure out what my dp table would store and the dp transition state .

Approach :
1) Create a 2-D dp boolean vector(with all false initially) where dp[i][j] states whether s[i...j] is a palindrome or not .

2) Base Case : For every i from 0 to n-1 fill dp[i][i]=1 ( as a single character is always a palindrome )and increment the counter where counter=0 initially

3) Now, run 2 loops first one from i=n-1 to i=0 (i.e., tarverse from the back of the string) and the second one from j=i+1 to n .

4) For every s[i]==s[j] , check if(j-i==1 i.e., if s[i] and s[ j] are two consecutive same letters) or if(dp[i+1][j-1]==1 or not i.e., if the string s[i+1,....j-1] is palindrome or not .

5) Because if the string s[i+1,....j-1] is a palindrome and s[i]==s[j] then s[i] and s[j] can be appended at the starting and the ending position of s[i+1,...j-1] and s[i...j] will then be a palindrome , so mark dp[i][j]=1 and increment the counter

6) Finally return the counter


TC : O(N^2) where N=length of the string s
SC : O(N^2)

DELETE command :

1) This command is needed to delete rows from a table based on the condition provided by the WHERE clause.

2) It can be rolled back if required.
 

3) It maintains a log to lock the row of the table before deleting it and hence it’s slow.

 

TRUNCATE command :

1) This command is needed to remove complete data from a table in a database. It is like a DELETE command which
has no WHERE clause.
 

2) It removes complete data from a table in a database.
 

3) It can be rolled back even if required.
 

4) It doesn’t maintain a log and deletes the whole table at once and hence it’s fast.

NORMALIZATION :
 

1) Normalization is a process of reducing redundancy by organizing the data into multiple tables.

2) Normalization leads to better usage of disk spaces and makes it easier to maintain the integrity of the database.


DENORMALIZATION :

1) Denormalization is the reverse process of normalization as it combines the tables which have been normalized into a single table so that data retrieval becomes faster.
 

2) JOIN operation allows us to create a denormalized form of the data by reversing the normalization.