Member of Technical Staff

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)

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)

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 : A stack can be implemented using two queues. Let stack to be implemented be ‘s’ and queues used to implement be ‘q1’ and ‘q2’. Stack ‘s’ can be implemented in two ways : 

Method 1 (push - O(1) , pop - O(n) ) :

1) push(s, x) operation : 
i) Enqueue x to q1 (assuming size of q1 is unlimited).

2) pop(s) operation : 
i) One by one dequeue everything except the last element from q1 and enqueue to q2.
ii) Dequeue the last item of q1, the dequeued item is result, store it.
iii) Swap the names of q1 and q2
iv) Return the item stored in step 2.

TC : push(s,x) -> O(1)
pop() -> O(n)



Method 2 (push - O(n) , pop - O(1) ) :

1) push(s, x) operation : 
i) Enqueue x to q2
ii) One by one dequeue everything from q1 and enqueue to q2.
iii) Swap the names of q1 and q2

2) pop(s) operation : 
i) Dequeue an item from q1 and return it.


TC : push(s,x) -> O(n)
pop() -> O(1)

Answer :

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.

Answer : 

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.

6) Friend functions have objects as arguments.

7) It cannot access the member names directly and has to use dot membership operator and use an object name with the member name.

8) We can declare it either in the ‘public’ or the ‘private’ part.

Approach (Using Inorder Traversal) :

1) Maintain two variables ‘PRE’ and ‘SUC’ which point to the predecessor and successor respectively.
2) We use a helper function ‘FIND_PRE_SUC_HELP’, which take the following as parameter :
‘ROOT’ , ‘PRE’ , ‘SUC’ , ‘KEY’ i.e. ‘X’.
3) If the current node's data is equal to ‘KEY’ then :
3.1) The maximum value in the left subtree is the predecessor.
3.2) The minimum value in the right subtree is the successor.
4) If after exiting ‘FIND_PRE_SUC_HELP’ any of ‘PRE’ or ‘SUC’ are NULL then that value was not found 
then add -1 to the vector.
5) Else add the value pointed by ‘PRE’ and then ‘SUC’.

TC : O(N), where ‘N’ is the number of nodes in the given tree.
SC : O(N)

Approach (Using DP) :

1) We reach “currStep” step in taking one step or two steps:
1.1) We can take the one-step from (currStep-1)th step or,
1.2) 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.

3) Let dp[currStep] define the total number of ways to reach “currStep” from the 0th. So,
dp[ currStep ] = dp[ currStep-1 ] + dp[ currStep-2 ]

4) 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)

Algorithm : 

1) Create a variable ‘res’ =0, which will store the number of good arrays that can be formed.
2) Create four variables ‘oddRightSum’ = 0, ‘evenRightSum’ = 0, ‘oddLeftSum’ = 0, ‘evenLeftSum’ = 0;
3) Iterate over all index ‘i’ in array ‘A:
3.1) If ‘i’ is even, then add the current element to ‘evenRightSum’
3.2) If ‘i’ is odd, then add the current element to ‘oddRightSum’
4) Iterate over all index ‘i’ in array ‘A:
4.1) If ‘i’ is odd, then decrease ‘oddRightSum’ by the current element.
4.2) If ‘i’ is even, then decrease ‘evenRightSum’ by the current element.
4.3) If ‘leftEvenSum’ + ’rightOddSum’ == ‘leftOddSum’ + ‘rightEvenSum’., then increment ‘res’, as we 
have found one good array.
4.4) If ‘i’ is odd, then increase ‘oddRightSum’ by the current element.
4.5) If ‘i’ is even, then increase ‘evenRightSum’ by the current element.
5) Return ‘res’ variable.

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

Answer : 

1) Memory protection is a strategy that makes it possible to manage the amount of access rights that are granted to the memory found on a computer hard drive. 

2) The main purpose of this type of protection is to minimize the potential for some type of storage violation that would harm the data contained in the memory, or damage a portion of the memory capacity of the hard drive.

3) One of the main functions of memory protection is the prevention of any application from making use of memory that the operating system has not specifically allocated to that application. 

4) This prevents applications from seizing control of an inordinate amount of memory and possibly causing damage that negatively impacts other applications that are currently in use, or even creating a loss of data that is saved on the hard drive. 

5) In many operating systems, this is managed by segmenting the memory for use by all open applications, ensuring that each has enough to operate properly without creating issues with the other running applications.