SDE - 2

You have a binary tree of 'N' unique nodes and a Start node from where the tree will start to burn. Given that the Start node will always exist in the tree, your task is to print the time (in minutes) that it will take to burn the whole tree.

It is given that it takes 1 minute for the fire to travel from the burning node to its adjacent node and burn down the adjacent node.

For Example :

For the given binary tree: [1, 2, 3, -1, -1, 4, 5, -1, -1, -1, -1]
Start Node: 3

    1
   / \
  2   3
     / \
    4   5

Output: 2

Explanation :
In the zeroth minute, Node 3 will start to burn.

After one minute, Nodes (1, 4, 5) that are adjacent to 3 will burn completely.

After two minutes, the only remaining Node 2 will be burnt and there will be no nodes remaining in the binary tree. 

So, the whole tree will burn in 2 minutes.

Given a binary tree, convert this binary tree into its mirror tree.

A binary tree is a tree in which each parent node has at most two children.

Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.

Note:

1. Make in-place changes, that is, modify the nodes given a binary tree to get the required mirror tree.

You have been given a Binary Tree of 'N' nodes, where the nodes have integer values. Your task is to print the zigzag traversal of the given tree.

Note:

In zigzag order, level 1 is printed from left to right fashion, level 2 is printed from right to left. and level 3 is printed from left to right again, and so on…..

For example:

For the given binary tree

The zigzag  traversal is [1, 4, 3, 5, 2, 7, 6]

A Directed Acyclic Graph (DAG) is a directed graph that contains no cycles.

Topological Sorting of DAG is a linear ordering of vertices such that for every directed edge from vertex ‘u’ to vertex ‘v’, vertex ‘u’ comes before ‘v’ in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

Given a DAG consisting of ‘V’ vertices and ‘E’ edges, you need to find out any topological sorting of this DAG. Return an array of size ‘V’ representing the topological sort of the vertices of the given DAG.

For example, Consider the DAG shown in the picture.

In this graph, there are directed edges from 0 to 1 and 0 to 3, so 0 should come before 1 and 3. Also, there are directed edges from 1 to 2 and 3 to 2 so 1 and 3 should come before 2.

So, The topological sorting of this DAG is {0 1 3 2}.

Note that there are multiple topological sortings possible for a DAG. For the graph given above one another topological sorting is: {0, 3, 1, 2}

Note:

1. It is guaranteed that the given graph is DAG.
2. There will be no multiple edges and self-loops in the given DAG.
3. There can be multiple correct solutions, you can find any one of them. 
4. Don’t print anything, just return an array representing the topological sort of the vertices of the given DAG.

Started off by asking Java Fundamentals, OOPS , Design Patters (Singleton, Factory, Cascade), HashMap Internals, Collections, Fail Fast-Fail Safe Iterators
Then jumped off to Problem Solving - Egg Dropping Problem(Learn)
 

You are given an integer N, you need to find the number of trailing zeroes in N! (N factorial).

Note:

1. Trailing zeros in a number can be defined as the number of continuous suffix zeros starting from the zeroth place of a number.
2. For example, if a number X = 1009000, then the number of trailing zeros = 3 where the zeroth place is 0, the tenth place is 0, the hundredth place is 0.
3. ! means “FACTORIAL”. Factorial of a number is calculated by the product of the integer and all integers below it till 1.
4. Value of 0! is 1.

He took a deep dive into my resume and asked a lot of questions around my projects asking my roles and responsibilities in each project/product/team. Asked about Kadane's Algorithm.
After that he started with Spark Theory based questions: 

MapReduce Concepts in deep, Shuffle internals, Questions on Hive , re-partition, MSCK repair tables, RDDs, Catalyst optimizer, Lineage Graph, SparkDrive, Spark Submit, Implementation of Split in Reduce Stage, Narrow and Wide Dependancy, Internal and External Tables, Caching a Query in Internal Table, Optimization of SQL query.

Every question was asked in a rapid fire manner

SQL query Using Dense Rank 

Question 1 : A scenario/story where Bitonic Sequence was to be implemented.
Question 2 : Design a Scheduler for scheduling n jobs with input give at the runtime , input can be the also generic service to be called.
Question 3 : Assuming you are dumping data in-memory via a data-pipeline , Design a garbage collector that will remove unsed data.(I gave and explained Mark and sweep Algorithm).
Follow-up Questions - What are memory Leaks,how will you calculate free-unused memory, how will you evict used memory, Optimal DS used in this.

A thief wants to loot houses. He knows the amount of money in each house. He cannot loot two consecutive houses. Find the maximum amount of money he can loot.

Deep-Discussion on my projects. 

My Approach on there use cases /or the problem they were facing. 

Questions on Spark(Broadcast Join Scenario), Questions on Map-reduce (Scenario Based)
Question on String Pool, String Buffer internals, Multi-threading, Concurrency

What are my Aspirations? 

How do I motivate myself? 

What sort of disappointment I faced in life? 

Situations where your solution was accepted other than your peers and How did you convince the management for this. 

What was the hardest situation overcomed in Life? (I gave My weight transformation from 110 to 60 kg, he did not believe it so showed Facebook Picture)

How is your relationships with your seniors? 

What is the most difficult problem you ever faced and how you solved it? 

What is your Normal day routine?

How do I manage a stressful situation? 

What role have you played which involved your Leadership skills?

Why I want to join there company, 

What will happen If I get rejected from this stage? 

What are my Life Aspirations?

Discussion on my resume, Work exp, Team Size, Duration of Projects

Why did you switch 2 companies with your experience and why do you want to switch and come here(Despite my answer he advised me to be patient and wait for opportunities).
Discussion on OS, Semaphores,Mutexes,Case Scenarios, Locks 
Locking In Distributed Env(1 Phase Vs 2 Phase VS 3 Phase Commits), SpinLocks
Implement a SpinLock(Low level Design)

Data Base Optimization