SDE - 1

Approach : 
1) In the bottom-up approach, extra space is used to store subproblems. However, we only need two previous values to calculate the count of derangements of the current value of ‘N’.
2) Instead of storing in an array, two variables are used to store the two previous values.
3) Initialize two variables, ‘prevOne’ and ‘prevTwo’ to 0 and 1 respectively.
4) Run a loop where ‘i’ ranges from 3 to ‘N’.
5) Find the count of derangements for the current value of ‘i’ using ‘CUR’ = ('i' - 1) * ('prevOne' + ‘prevTwo’).
6) Store the value of ‘prevOne’ in ‘prevTwo’ and the value of ‘CUR’ in ‘prevOne’.
7) Return ‘prevTwo’ which stores the total number of derangements of ‘N’ elements.

TC : O(N), where N=number of elements
SC : O(1)

Approach (Using Sieve of Eratosthenes) :

1) First, we will make a boolean array/list isPrime of size N + 1. This will mark if a number is prime or not. Initially, all values will be true.

2) Then, we initialize a variable num equal to 2 which represents the current processing prime number.

3) We will loop as num from 2 to N^½:
3.1) If num is not prime, we continue.
3.2) Else, we will mark all multiples of num in isPrime as false.

4) In the end, we will iterate through isPrime and store all primes in the result vector/list.

5) Finally, we return the result vector.

TC : O(N * log(log N)), where N is the given positive integer. 
SC : O(N)

Approach (Using Trie) : 

1) Add a additional field “COUNT” in the implementation of the node of the trie. This field will be equal to the number / occurrences of the current string in the first array. For the nodes that do not represent the end of a string, the value of count will be zero.

2) Firstly, we traverse the first array and insert the strings in a trie. While inserting a string in the trie, we increment the variable “COUNT” of the last node i.e. the node representing the last character of the string.

3) After the creation of the trie, we traverse the second array and for each string in the second array, we check if it is present in the trie. 

4) If the string exists in the trie, we add it to the answer and decrement the variable “COUNT” for the last node i.e. the node representing the last character of the string.

5) After the traversal of the second array, the answer will contain the common strings.

TC : O(K * S), where ‘K’ = max('N', ‘M’) and ‘S’ is the average length of strings.
SC : O(26 * N * S), where ‘N’ is the size of the first array and ‘S’ is the average length of the strings.

Approach : 

1) We will maintain two stacks, one for each direction i.e. leftToRight and rightToleft.

2) We will do a level order traversal of the given binary tree and push nodes of each level onto one of the stack according to the current direction of traversal.

3) After we’ve pushed all nodes of a level onto one stack, we’ll start popping those nodes. While popping the nodes we will push their children (if any) onto our other direction stack, so that the next level be traversed in reverse order.

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

Abstract class and interface both are used to achieve abstraction where we can declare the abstract methods.

Key differences b/w Abstract Class and Interface are :

1) Abstract class can have abstract and non-abstract methods.
Interface can have only abstract methods. Since Java 8, it can have default and static methods also.

2) Abstract class doesn't support multiple inheritance.
Interface supports multiple inheritance.

3) Abstract class can have final, non-final, static and non-static variables.
Interface has only static and final variables.

4) Abstract class can provide the implementation of interface.
Interface can't provide the implementation of abstract class.

5) The abstract keyword is used to declare abstract class.
The interface keyword is used to declare interface.

6) An abstract class can extend another Java class and implement multiple Java interfaces.
An interface can extend another Java interface only.

7) An abstract class can be extended using keyword "extends".
An interface can be implemented using keyword "implements".

1) The static keyword in Java is mainly used for memory management. 
2) The static keyword in Java is used to share the same variable or method of a given class. 
3) The users can apply static keywords with variables, methods, blocks, and nested classes. 
4) The static keyword belongs to the class than an instance of the class. 
5) The static keyword is used for a constant variable or a method that is the same for every instance of a class.

Constructors :
1) A Constructor is a block of code that initializes a newly created object.
2) A Constructor can be used to initialize an object.
3) A Constructor is invoked implicitly by the system
4) A Constructor is invoked when a object is created using the keyword new.
5) A Constructor doesn’t have a return type.
6) A Constructor’s name must be same as the name of the class.
7) A Constructor cannot be inherited by subclasses.


Method :
1) A Method is a collection of statements which returns a value upon its execution.
2) A Method consists of Java/C++ code to be executed.
3) A Method is invoked by the programmer.
4) A Method is invoked through method calls.
5) A Method must have a return type.
6) A Method’s name can be anything.
7) A Method can be inherited by subclasses.

This was a very standard DP problem and I had already solved it on platforms like LeetCode and CodeStudio so I was able to come up with the logic and code it preety fast.

Steps :
1) Create a two-dimensional array, ‘dp’, where ‘dp[i][j]’ will denote the total number of ways to make j value by using i coins.

2) Run 2 loops ,1st one from 1 to value and second one throught the array denominations.

3) Fill dp array by the recurrence relation as follows:
ways[i][j] = ways[i-1][j] + ways[i][j-denominations[i]] (if j-denominations[i]>=0)
Where first term represents that we have excluded that coin and,
Second term represents that we have included that coin.

4) Base Case : Fill dp[0]=0 (as we can make 0 amount by giving no coins at all) and the remaining indices with INT_MAX value

5) Finally , if dp[value]==INT_MAX , return -1 as it is not possible to make "value" using the given coins else return dp[value] itself

TC : O(N*V) where N=number of coins and V=Value to be made
SC : O(N*V)

Approach 1 :
1) Initialise a string named rev with the given string .
2) Reverse the string rev.
3) Now, if s is a palindrome then we would have rev==s , return true if rev==s and false otherwise

TC : O(N) where N=length of the string
SC : O(1)


Approach 2(Using Two Pointers) :
1) Keep pointer i=0 and j=n-1 where n=length of the string
2) Run a loop till i<=j and check if s[i]==s[j] for the condition of palindrome
3) If at any point s[i]!=s[j] then simply return false from the loop
4) Else return true after the end of the loop.

TC : O(N)
SC : O(1)