SDE - 1

We break the problem in 3 parts: 

1. Print the left boundary in top-down manner. 
2. Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts: 
…..2.1 Print all leaf nodes of left sub-tree from left to right. 
…..2.2 Print all leaf nodes of right subtree from left to right. 
3. Print the right boundary in bottom-up manner.
We need to take care of one thing that nodes are not printed again. e.g. The left most node is also the leaf node of the tree.
Based on the above cases, below is the implementation:


/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node {
int data;
struct Node *left, *right;
};

// Utility function to create a new tree node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = nullptr;
return temp;
}

// A simple function to print leaf nodes of a binary tree
void printLeaves(Node* root)
{
if (root == nullptr)
return;

printLeaves(root->left);

// Print it if it is a leaf node
if (!(root->left) && !(root->right))
cout << root->data << " ";

printLeaves(root->right);
}

// A function to print all left boundary nodes, except a
// leaf node. Print the nodes in TOP DOWN manner
void printBoundaryLeft(Node* root)
{
if (root == nullptr)
return;

if (root->left) {

// to ensure top down order, print the node
// before calling itself for left subtree
cout << root->data << " ";
printBoundaryLeft(root->left);
}
else if (root->right) {
cout << root->data << " ";
printBoundaryLeft(root->right);
}
// do nothing if it is a leaf node, this way we avoid
// duplicates in output
}

// A function to print all right boundary nodes, except a
// leaf node Print the nodes in BOTTOM UP manner
void printBoundaryRight(Node* root)
{
if (root == nullptr)
return;

if (root->right) {
// to ensure bottom up order, first call for right
// subtree, then print this node
printBoundaryRight(root->right);
cout << root->data << " ";
}
else if (root->left) {
printBoundaryRight(root->left);
cout << root->data << " ";
}
// do nothing if it is a leaf node, this way we avoid
// duplicates in output
}

// A function to do boundary traversal of a given binary
// tree
void printBoundary(Node* root)
{
if (root == nullptr)
return;

cout << root->data << " ";

// Print the left boundary in top-down manner.
printBoundaryLeft(root->left);

// Print all leaf nodes
printLeaves(root->left);
printLeaves(root->right);

// Print the right boundary in bottom-up manner
printBoundaryRight(root->right);
}

Tip 1: Do explain what you are thinking.
Tip 2: Explain what each attribute does like sum, where etc.
Tip 3: Interviewer is more interested in what you are thinking rather what you wrote.

Tip 1: Revise recently asked interview questions.
Tip 2: These were experience specific. I had MERN stack experience so was asked about these questions.

Tip 1: Read about common systems design problems.
Tip 2: Make sure you are communicating well throughout.

Tip 1: Explain how data is passed through the URL while get querry and in post how data is passed through the body secretly.
Tip 2: Read about common networking problems.

Tip 1: These were just brainstorming problems where the interviewer was trying to check what you do in an unclear problem.
Tip 2: Do communicate well with your interviewer.

Follow the steps below to solve the problem:

Traverse linked list using two pointers.
Move one pointer(slow_p) by one and another pointer(fast_p) by two.
If these pointers meet at the same node then there is a loop. If pointers do not meet then the linked list doesn’t have a loop.

class Node {
public:
int data;
Node* next;
};

void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = new Node();

/* put in the data */
new_node->data = new_data;

/* link the old list of the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

int detectLoop(Node* list)
{
Node *slow_p = list, *fast_p = list;

while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p) {
return 1;
}
}
return 0;
}

Tip 1: Be honest, in the start they only want to understand your tech background.
Tip 2: Answer all questions with confidence.

Approach : 
First search the target node in a binary tree recursively. After finding the target node print it and save its left child(if exist) and right child(if exist) in a queue. and return. Now, get the size of the queue and run while loop. Print elements in the queue.

// Utility function to print the sequence of burning nodes
int burnTreeUtil(Node* root, int target, queue& q)
{
// Base condition
if (root == NULL) {
return 0;
}

// Condition to check whether target
// node is found or not in a tree
if (root->key == target) {
cout << root->key << endl;
if (root->left != NULL) {
q.push(root->left);
}
if (root->right != NULL) {

q.push(root->right);
}

// Return statements to prevent
// further function calls
return 1;
}

int a = burnTreeUtil(root->left, target, q);

if (a == 1) {
int qsize = q.size();

// Run while loop until size of queue
// becomes zero
while (qsize--) {
Node* temp = q.front();

// Printing of burning nodes
cout << temp->key << " , ";
q.pop();

// Check if condition for left subtree
if (temp->left != NULL)
q.push(temp->left);

// Check if condition for right subtree
if (temp->right != NULL)
q.push(temp->right);
}

if (root->right != NULL)
q.push(root->right);

cout << root->key << endl;

// Return statement it prevents further
// further function call
return 1;
}

int b = burnTreeUtil(root->right, target, q);

if (b == 1) {
int qsize = q.size();
// Run while loop until size of queue
// becomes zero

while (qsize--) {
Node* temp = q.front();

// Printing of burning nodes
cout << temp->key << " , ";
q.pop();

// Check if condition for left subtree
if (temp->left != NULL)
q.push(temp->left);

// Check if condition for left subtree
if (temp->right != NULL)
q.push(temp->right);
}

if (root->left != NULL)
q.push(root->left);

cout << root->key << endl;

// Return statement it prevents further
// further function call
return 1;
}
}

// Function will print the sequence of burning nodes
void burnTree(Node* root, int target)
{
queue q;

// Function call
burnTreeUtil(root, target, q);

// While loop runs unless queue becomes empty
while (!q.empty()) {
int qSize = q.size();
while (qSize > 0) {
Node* temp = q.front();

// Printing of burning nodes
cout << temp->key;
// Insert left child in a queue, if exist
if (temp->left != NULL) {
q.push(temp->left);
}
// Insert right child in a queue, if exist
if (temp->right != NULL) {
q.push(temp->right);
}

if (q.size() != 1)
cout << " , ";

q.pop();
qSize--;
}
cout << endl;
}
}

Tip 1: Make sure whatever is written on your resume you can explain in detail about that.
Tip 2: All these questions were related to my resume thus my interviewer was trying to check whether I have expertise in this area or not.

Printing a matrix in spiral form is the same as peeling an onion layer by layer. Because we are printing the elements layer by layer starting from the outer layers.
In this approach, we will be using four loops to print all four sides of the matrix.

1st loop: This will print the elements from left to right.

2nd loop: This will print the elements from top to bottom.

3rd loop: This will print the elements from right to left.

4th loop: This will print the elements from bottom to top.

vector printSpiral(vector> mat) {

// Define ans array to store the result.
vector ans;

int n = mat.size(); // no. of nows
int m = mat[0].size(); // no. of columns

// Initialize the pointers reqd for traversal.
int top = 0, left = 0, bottom = n - 1, right = m - 1;

// Loop until all elements are not traversed.
while (top <= bottom && left <= right) {

// For moving left to right
for (int i = left; i <= right; i++)
ans.push_back(mat[top][i]);

top++;

// For moving top to bottom.
for (int i = top; i <= bottom; i++)
ans.push_back(mat[i][right]);

right--;

// For moving right to left.
if (top <= bottom) {
for (int i = right; i >= left; i--)
ans.push_back(mat[bottom][i]);

bottom--;
}

// For moving bottom to top.
if (left <= right) {
for (int i = bottom; i >= top; i--)
ans.push_back(mat[i][left]);

left++;
}
}
return ans;
}

Tip 1: Do not sign the contract at that spot without reading the entire document.
Tip 2: Ask for all necessary details like notice period, probation period, joining or reallocation bonus and everything.