SDE - 1

Approach (Using DP) : 

Our intuition is:
How can we reach “currStep” step in taking one step or two steps:

1) We can take the one-step from (currStep-1)th step or,
We can take the two steps from (currStep-2)th step.

2) So the total number of ways to reach “currStep” will be the sum of the total number of ways to reach at (currStep-1)th and the total number of ways to reach (currStep-2)th step.

Let dp[currStep] define the total number of ways to reach “currStep” from the 0th. So,

dp[ currStep ] = dp[ currStep-1 ] + dp[ currStep-2 ]

3) The base case will be, If we have 0 stairs to climb then the number of distinct ways to climb will be one (we are already at Nth stair that’s the way) and if we have only one stair to climb then the number of distinct ways to climb will be one, i.e. one step from the beginning.

TC : O(N), where ‘N’ is the number of stairs.
SC : O(N)

Approach : 

1) Let prefSum[] be the array which stores the prefix sum, where prefSum[i] will be the sum of elements of the array up to the index i i.e prefSum[i] = arr[0] + arr[1] + …. + arr[i]

2) So if we are at index i, the sum of elements to the left of index i is stored at leftSum = prefSum[i - 1], given that i-1 is a valid array index.

3) Let arraySum denote the sum of the complete array.

4) Now to find the sum of elements to the right of the index i, rightSum = total sum - (sum of elements to the left of i )+ arr[i](because we need to exclude the element at index i)

5) The above statement can be simplified to rightSum = arraySum - prefSum[i - 1] + arr[i]. Thus we can say that rightSum = arraySum - prefSum[i] (since prefSum[i - 1] + arr[i] = prefSum[i]).

6) If we get leftSum = rightSum at any index, return that index.

7) After for loop ends return -1, since there is no valid index.

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

Approach : 

1) Declare a variable ‘X’ of type int to store the square root of ‘N’.
2) Compare the Distance between the square of ‘X’ and ‘N’ and the square of ‘X + 1’ and ‘N’.
3) If the distance of ‘N’ from the square of ‘X’ is less than the distance of ‘N’ from the square of ‘X + 1’ then return X and abs(N - (X * X)).
4) Otherwise return ‘X+1’and abs( N - (X+1) * (X + 1)).

TC : O(sqrt(N)), where N=given integer
SC : O(1)

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 and initilialise a variable ans=1 which will store the final answer.

2) Base Case : For every i from 0 to n-1 fill dp[i][i]=1 ( as a single character is always a palindrome ).

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 update the answer as ans=max(ans , j-i+1).

6) Finally return the ans

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

Approach : 

1) Take a stack of TreeNodes and a TreeNode prev with its initial value as NULL.
2) Run a loop till stack is not empty or root != NULL.
3) While pushing a root to the stack, push all its left descendants into the stack untill root != NULL.
4) Take current = stack.top() and pop it from the stack
5) Check if prev is NOT NULL and if prev->val >= curr->val , if this cond. is met simply return false.
6) Update prev with current.
7) Update root with root->right.

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

Approach :

When we observe the binary sequence from 0 to 2n – 1 (n is no. of bits), right most bits (least significant) vary rapidly than left most bits. The idea is to find right most string of 1’s in x, and shift the pattern to right extreme, except the left most bit in the pattern. Shift the left most bit in the pattern (omitted bit) to left part of x by one position.

//Pseudo Code :

int findNextGreaterNum(int n)
{
int ct=0 , subt=0, idx=0;
for(int i=0; i<32; i++)
{
while(n&(1<0)
{
idx=i; //idx-1 will hold the position of the leftmost one in the rightmost 1's pattern
break;
}
}
int add=(1< int ans=n-subt+add;
cout< return ans; 
}

Approach :

1) There is another mathematical approach by which we can solve this problem in linear time and constant space.
2) For every element ARR[i], increment the ARR[i]%N’th element by n i.e. ARR[ARR[i] % N] += N.
3) Now again traverse the array and print the indices where ARR[i]/N is greater than 1. It guarantees that the number N has been added to that index.
4) All these indices will be the repetitive elements because all the elements in the array are in the range 0 to N - 1 and ARR[i] will be greater than N if and only if ‘i’ has occurred more than once in the array.

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

The advantages of using a view in the table are :
1) It is a subset of the data in table.
2) It store complex queries.
3) It can simplify multiple tables into one.
4) It occupies very little space.
5) It presents the data from different perspectives.

Constraints are used to specify the rules concerning data in the table. It can be applied for single or multiple fields in an SQL table during the creation of the table or after creating using the ALTER TABLE command. The constraints are:

1) NOT NULL - Restricts NULL value from being inserted into a column.
2) CHECK - Verifies that all values in a field satisfy a condition.
3) DEFAULT - Automatically assigns a default value if no value has been specified for the field.
4) UNIQUE - Ensures unique values to be inserted into the field.
5) INDEX - Indexes a field providing faster retrieval of records.
6) PRIMARY KEY - Uniquely identifies each record in a table.
7) FOREIGN KEY - Ensures referential integrity for a record in another table.