SDE - Intern Freecharge interview experience | Anonymous

Interview rounds

Round

Medium

Video Call

Duration60 minutes

Interview date9 Sep 2021

Coding problem2

The interview was conducted over Google Meet and the interviewer worked as a Lead Software at freecharge. The interview started with a brief introduction and then a discussion on my projects happened followed by 2 DSA Problems.

1. Delete Node In BST

Moderate

10m average time

90% success

0/80

Asked in companies

You have been given a Binary Search Tree of integers with ‘N’ nodes. You are also given data of a node of this tree. Your task is to delete the given node from the BST.

A binary search tree (BST) is a binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with data less than the node’s data.

• The right subtree of a node contains only nodes with data greater than the node’s data.

• Both the left and right subtrees must also be binary search trees.

Example:

For the given BST, if we want to delete the node with data 5 :

The modified BST will be:

Please notice that another valid answer is:

Note :

1. The node which we want to delete will always be present in the given tree.

2. If after deletion the tree becomes empty, print -1.

Problem approach

Use the BST property to search the node and then delete if found the required node.

So if the traget node has value less than root then we will surely get it in the left subtree...so just call ur recursive function for the left subtree.
If the traget node has value greater than root then we will surely get it in the right subtree...so just call ur recursive function for the right subtree.
And now comes the case when u have to do your work that is root itself is the required node to be deleted. Here again comes three cases:
If left of root is null and u also have to delete the root node...then just simply return the right subtree.

If right of root is null and u also have to delete the root node...then just simply return the left subtree.

Both are not null then you have to not just delete the node but also maintain the BST structure.
So now you have to think if you delete the root node then which node can optimally replace it so that all the nodes on left are still small and on right are larger.
So that node will be the node just greater than the largest node in the left subtree which is the smallest node in the right subtree
So point your pointer on the right subtree and then move it to the left most node of this subtree that will be your required node and so now replace the value of your root with this node value which will ensure that the key which u wanted to delete is deleted and the value there is the right value.
Now you have to delete that node whose value is already present in the root...so now that work will be done by the recursion so now just pass that right subtree in which the value is present with that nodes value which will be now the target

Try solving now

2. Linked List Cycle II

Moderate

10m average time

90% success

0/80

Asked in companies

You are given a singly linked list that may or may not contain a cycle. You are supposed to return the node where the cycle begins, if a cycle exists, else return 'NULL'.

A cycle occurs when a node's next pointer returns to a previous node in the list.

Example:

In the given linked list, there is a cycle starting at position 0, hence we return 0.

Problem approach

A temporary node is created. The next pointer of each node that is traversed is made to point to this temporary node. This way we are using the next pointer of a node as a flag to indicate whether the node has been traversed or not. Every node is checked to see if the next is pointing to a temporary node or not. In the case of the first node of the loop, the second time we traverse it this condition will be true, hence we return that node.

Try solving now

Round

Easy

Video Call

Duration60 minutes

Interview date13 Sep 2021

Coding problem2

This round revolved around technical concepts, Project Discussion, past experiences, and 1 DSA problem

1. DBMS Questions

What are clustered and non-clustered indexes?
What are the ACID properties of transactions?
I was asked to write some SQL queries.

Problem approach

Tip 1 : Be clear with the explanation
Tip 2 : If any question requires explanation use the resource that is provided for explaining
Tip 3 : Study the most important questions. you can use the internet for that