SDE - 1

Approach 1(Brute Force) : 
1) Run a for loop from 1 to ‘N’.
2) Sum up the squares of each number from 1 to ‘N’.
3) Finally, return this sum.

TC : O(N), where N is the given number
SC : O(1)


Approach 2 (Using Mathemical Formula) :
The sum of squares of first N natural numbers is given by: 1^2 + 2^2 + … N^2 = N*(N+1)*(2*N+1)/6

TC : O(1)
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 : 

The boundary traversal of a binary tree can be broken down into 4 parts. These parts are given in the same order as they are present in the traversal-

1) The root node - The root node will always be our first node in the whole boundary traversal.

2) The left boundary - Process them next except for the leaf node as it will be processed in our next part. We can use recursion for this and traverse for only left child until a leaf node is encountered. If the left child is not present we recurse for the right child.

3) The leaf Nodes - The leaf nodes of the binary tree will be processed next. We can use a simple inorder traversal for that. Inorder traversal will make sure that we process leaf nodes from left to right.

4) The right boundary - The right most nodes of the right subtree will be processed at last in reverse order except for the leaf node as it is already processed in the previous part. For this, we can use recursion in a postorder manner and traverse for the right child only until we encounter a leaf node. If the right child is not present we will recurse for the left child. 

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

Inorder Traversal : 

void inorder(TreeNode*root)
{
if(root)
{
inorder(root->left);
cout inorder(root->right);
}
}

Preorder Traversal : 

void preorder(TreeNode*root)
{
if(root)
{
preorder(root->left);
preorder(root->right);
cout }
}

Deadlock : Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
Consider an example when two trains are coming toward each other on the same track and there is only one track, none of the trains can move once they are in front of each other. A similar situation occurs in operating systems when there are two or more processes that hold some resources and wait for resources held by other(s).

Deadlock can arise if the following four conditions hold simultaneously (Necessary Conditions) :
1) Mutual Exclusion : One or more than one resource are non-shareable (Only one process can use at a time)
2) Hold and Wait : A process is holding at least one resource and waiting for resources.
3) No Preemption : A resource cannot be taken from a process unless the process releases the resource.
4) Circular Wait : A set of processes are waiting for each other in circular form.



Methods for handling deadlock :
There are three ways to handle deadlock
1) Deadlock prevention or avoidance : The idea is to not let the system into a deadlock state.
One can zoom into each category individually, Prevention is done by negating one of above mentioned necessary conditions for deadlock.
Avoidance is kind of futuristic in nature. By using strategy of “Avoidance”, we have to make an assumption. We need to ensure that all information about resources which process will need are known to us prior to execution of the process. We use Banker’s algorithm in order to avoid deadlock.
2) Deadlock detection and recovery : Let deadlock occur, then do preemption to handle it once occurred.
3) Ignore the problem altogether : If deadlock is very rare, then let it happen and reboot the system. This is the approach that both Windows and UNIX take.

The term “inheritance” means “receiving some quality or behavior from a parent to an offspring.” In object-oriented programming, inheritance is the mechanism by which an object or class (referred to as a child) is created using the definition of another object or class (referred to as a parent). Inheritance not only helps to keep the implementation simpler but also helps to facilitate code reuse. 

The various types of inheritance include:

1) Single inheritance
2) Multiple inheritances
3) Multi-level inheritance
4) Hierarchical inheritance
5) Hybrid inheritance

If you are a user, and you have a problem statement, you don't want to know how the components of the software work, or how it's made. You only want to know how the software solves your problem. Abstraction is the method of hiding unnecessary details from the necessary ones. It is one of the main features of OOPs. 
For example, consider a car. You only need to know how to run a car, and not how the wires are connected inside it. This is obtained using Abstraction.

C++ is an Object-oriented programming language and it supports Polymorphism as well:

Compile Time Polymorphism : C++ supports compile-time polymorphism with the help of features like templates, function overloading, and default arguments.

Runtime Polymorphism : C++ supports Runtime polymorphism with the help of features like virtual functions. Virtual functions take the shape of the functions based on the type of object in reference and are resolved at runtime.

Normalization is the process of minimizing redundancy from a relation or set of relations. Redundancy in relation may cause insertion, deletion, and update anomalies. So, it helps to minimize the redundancy in relations. Normal forms are used to eliminate or reduce redundancy in database tables.

Types of Normal Form :
1) 1NF : It is known as the first normal form and is the simplest type of normalization that you can implement in a database. A table to be in its first normal form should satisfy the following conditions:
i) Every column must have a single value and should be atomic.
ii) Duplicate columns from the same table should be removed.
iii) Separate tables should be created for each group of related data and each row should be identified with a unique column.


2) 2NF : It is known as the second normal form. A table to be in its second normal form should satisfy the following conditions :
i )The table should be in its 1NF i.e. satisfy all the conditions of 1NF.
ii) Every non-prime attribute of the table should be fully functionally dependent on the primary key i.e. every non-key attribute should be dependent on the primary key in such a way that if any key element is deleted then even the non_key element will be saved in the database.


3) 3NF : It is known as the third normal form. A table to be in its second normal form should satisfy the following conditions :
i) The table should be in its 2NF i.e. satisfy all the conditions of 2NF.
ii) There is no transitive functional dependency of one attribute on any attribute in the same table.


4) BCNF : BCNF stands for Boyce-Codd Normal Form and is an advanced form of 3NF. It is also referred to as 3.5NF for the same reason. A table to be in its BCNF normal form should satisfy the following conditions :
i) The table should be in its 3NF i.e. satisfy all the conditions of 3NF.
ii) For every functional dependency of any attribute A on B
(A->B), A should be the super key of the table. It simply implies that A can’t be a non-prime attribute if B is a prime attribute.

SELECT A.ID_Name, B.ID_Name
FROM A
INNER JOIN B ON A.ID=B.ID;

Tip 1 : The cross questioning can go intense some time, think before you speak.
Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.
Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round, like what are the projects currently the company is investing, which team you are mentoring. How all is the work environment etc.
Tip 4 : Since everybody in the interview panel is from tech background, here too you can expect some technical questions. No coding in most of the cases but some discussions over the design can surely happen.