Associate Software Engineer

This problem is a simple recursive problem. But time complexity of simple recursive calls is exponential. In O(log(n)) this problem can be solved using a simple trick.

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

This method will solve this question in O(log(n)).

The idea is simple: along the path, record all prefix sums in a hash table. For current prefix sum x, check if (x - target) appears in the hash table.

Steps :
1) We will be using a unordered map which will be filled with various path sum.
2) For every node we will check if current sum and root’s value equal to k or not. If the sum equals to k then increment the required answer by one.
3) Then we will add all those path sum in map which differs from current sum+root->data value by a constant integer k.
4) Then we will be inserting the current sum + root->data value in the map.
5) We will recursively check for left and right subtrees of current root
6) After the right subtree is also traversed we will remove the current sum + root->data value from the map so that it is not taken into consideration in further traversals of other nodes other than the current root’s.

Algorithm :

1) ReverseStack(stack)
i) If the stack is empty, then return
ii) Pop the top element from the stack as top
iii) Reverse the remaining elements in the stack, call reverseStack(stack) method
iv) Insert the top element to the bottom of the stack, call InsertAtBottom(stack, top) method
2) InsertAtBottom(stack, ele)
i) If the stack is empty, push ele to stack, return
ii) Pop the top element from the stack as top
iii) Insert the ele to the bottom of the stack, call InsertAtBottom(stack, ele) method
iv) Push top to the stack.

TC : O(N^2) , where N=total number of elements in the given stack
SC : O(N)

Steps : 

1) Make group of 5 horses and run 5 races. 

2) Suppose five groups are a,b,c,d,e and next alphabet is its individual rank in tis group(of 5 horses).For eg. d3 means horse in group d and has rank 3rd in his group. [ 5 RACES DONE ]
a1 b1 c1 d1 e1
a2 b2 c2 d2 e2
a3 b3 c3 d3 e3
a4 b4 c4 d4 e4
a5 b5 c5 d5 e5

3) Now make a race of (a1,b1,c1,d1,e1).[RACE 6 DONE] suppose result is a1>b1>c1>d1>e1
which implies a1 must be FIRST.
b1 and c1 MAY BE(but not must be) 2nd and 3rd.
FOR II position, horse will be either b1 or a2
(we have to find top 3 horse therefore we choose horses b1,b2,a2,a3,c1 do racing among them [RACE 7 DONE].

The only possibilities are :
c1 may be third
b1 may be second or third
b2 may be third
a2 may be second or third
a3 may be third

The final result will give ANSWER. suppose result is a2>a3>b1>c1>b2
then answer is a1,a2,a3,b1,c1.

HENCE ANSWER is 7 RACES

Steps :
Let's call 5L jar as X and 3L jar as Y.

1) We'll take the first jar, i.e, X. Fill X completely.
2) Then empty the X content in Y. We are left with 2 L in the X.
3) Now we will empty the Y jar and then Fill 2L from X into Y. We are left with 0L in X and 2L in Y.
4) Now again we will fill X with 5L and then empty till Y gets full.
5) As Y is already full with 2L from previous operation so it can only accomodate 1L now from X. So when
Y jar is full automatically we will have 4L left in X. This is how we will calculate 4L

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.

Answer :

Primary Key : Used to serve as a unique identifier for each row in a table.
Unique Key : Uniquely determines a row which isn’t primary key.

Key Differences Between Primary key and Unique key: 

1) Primary key will not accept NULL values whereas Unique key can accept NULL values.

2) A table can have only one primary key whereas there can be multiple unique key on a table.

3) A Clustered index automatically created when a primary key is defined whereas Unique key generates the non-clustered index.

Answer : 

LEFT JOIN : 
The LEFT JOIN or the LEFT OUTER JOIN returns all the records from the left table and also those records which satisfy a condition from the right table. Also, for the records having no matching values in the right table, the output or the result-set will contain the NULL values.

Syntax:
SELECT Table1.Column1,Table1.Column2,Table2.Column1,....
FROM Table1
LEFT JOIN Table2
ON Table1.MatchingColumnName = Table2.MatchingColumnName;

RIGHT JOIN : 
The RIGHT JOIN or the RIGHT OUTER JOIN returns all the records from the right table and also those records which satisfy a condition from the left table. Also, for the records having no matching values in the left table, the output or the result-set will contain the NULL values.

Syntax:
SELECT Table1.Column1,Table1.Column2,Table2.Column1,....
FROM Table1
RIGHT JOIN Table2
ON Table1.MatchingColumnName = Table2.MatchingColumnName;

Approach : 
Sort the distinct salary in descend order and then utilize the LIMIT clause to get the second highest salary.


SQL Query :

SELECT DISTINCT Salary
FROM Employee
ORDER BY Salary DESC
LIMIT 1 OFFSET 1;

If you get this question, it's an opportunity to choose the most compelling information to share that is not obvious from your resume.

Example :
Strength -> I believe that my greatest strength is the ability to solve problems quickly and efficiently, which makes me unique from others.

Handle Pressure -> I enjoy working under pressure because I believe it helps me grow and become more efficient .

Tip : Emphasize why you were inspired to apply for the job. You can also explain that you are willing to invest a great deal of energy if hired.

These are generally very open ended questions and are asked to test how quick wit a candidate is. So there is nothing to worry about if you have a good cammand over your communication skills and you are able to propagate your thoughts well to the interviewer