SDE - 1 Times Internet interview experience | Anonymous

Interview rounds

Round

Easy

Face to Face

Duration60 minutes

Interview date11 Mar 2015

Coding problem5

I had one interview for approx. an hour, it includes both Technical and HR round, well mostly technical. Interview starts with tell me something about yourself. Asked in detailed about algorithms/web based projects mentioned in CV, make sure that whatever you have written you have complete knowledge about it. Asked to code few basic algorithms questions. Do mention about small project if you have done related to web development.
If interviewer says if you want to ask any question, its always better to ask one or two question.

1. General Question

Introduce yourself.

Problem approach

Prepare tell me something about yourself way before your placement starts, a month or so. Write it down on a piece of paper, keep it to less than 120 sec, 90-100 sec is good.
A basic format would be like, your introduction, schooling (doesn't matter but if you have something good to say about), give an overview of your project/work experience mentioned in your CV.
You should cover all the necessary and important parts written in your cv in this question. If something interest the interviewer your interview can start from those topic you mentioned.
Just make sure whatever you have written in your CV, you have full knowledge of it.

2. DS Question

What is a BST?

Problem approach

Binary Search Tree is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.

3. Insert Into A Binary Search Tree

Easy

20m average time

80% success

0/40

Asked in companies

You have been given a root node of the binary search tree and a positive integer value. You need to perform an insertion operation i.e. inserting a new node with the given value in the given binary search tree such that the resultant tree is also a binary search tree.

If there can be more than one possible tree, then you can return any.

Note :

A binary search tree is a binary tree data structure, with the following properties :

    a. The left subtree of any node contains nodes with a value less than the node’s value.

    b. The right subtree of any node contains nodes with a value equal to or greater than the node’s value.

    c. Right, and left subtrees are also binary search trees.
It is guaranteed that,

    d. All nodes in the given tree are distinct positive integers.

    e. The given BST does not contain any node with a given integer value.

Example, below the tree, is a binary search tree.

Below the tree is not a BST as node ‘2’ is less than node ‘3’ but ‘2’ is the right child of ‘3’, and node ‘6’ is greater than node ‘5’ but it is in the left subtree of node ‘5’.

Problem approach

A new key is always inserted at the leaf. We start searching a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
Pseudocode:
1. If tree is empty (no root), create a node with key k as root; return .
2. Set CurrNode = RootNode.
3. If k == CurrNode.key, return since the node is already present.
4. If k< CurrNode.key ... /* key must go in left subtree */
If CurrNode.left == NULL, create a node holding k as left child of CurrNode; return.
else set CurrNode = CurrNode.left, and go to 3.
5. else ... /* key must go in right subtree */
If CurrNode.right == NULL, create a node holding k as left child of CurrNode; return.
else set CurrNode = CurrNode.right, and go to 3.

Try solving now

4. 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

Three cases arise in deleting a node :
1.Node to be deleted is the leaf: Simply remove it from the tree.
2. Node to be deleted has only one child: Copy the child to the node and delete the child node.
3.Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor.

Pseudocode :
if node is null ->
return the node (either we were given an empty tree or we've iterated through the tree and didn't find the value, in which case we return the original tree)

if current node is less than the value we're looking for ->
recursively call function on right side

if current node is great than the value ->
recursively call function on left side

otherwise, we've found the node we want to delete
-> if the node has no children, return null
-> if the node has one child, return the non-null subtree
-> otherwise:
-> find the min value in the right subtree
-> set the current node's value to the found min value
-> delete the now duplicated node
-> return the current node

Try solving now

5. Clone Linked List with Random Pointer

Easy

10m average time

90% success

0/40

Asked in companies

Given a linked list having two pointers in each node. The first one points to the next node of the list, however, the other pointer is random and can point to any node of the list or null. The task is to create a deep copy of the given linked list and return its head. We will validate whether the linked list is a copy of the original linked list or not.

A deep copy of a Linked List means we do not copy the references of the nodes of the original Linked List rather for each node in the original Linked List, a new node is created.

For example,

Random pointers are shown in red and next pointers in black.

Problem approach

Algorithm :
1. Consider l1 as a node on the 1st list and l2 as the corresponding node on 2nd list.
2. Build the 2nd list by creating a new node for each node in 1st list. While doing so, insert each new node after it's corresponding node in the 1st list.
3. The new head is the 2nd node as that was the first inserted node.
4. Fix the random pointers in the 2nd list: (Remember that l1->next is actually l2) l2->random will be the node in 2nd list that corresponds l1->random, which is next node of l1->random.
5. Separate the combined list into 2: Splice out nodes that are part of second list.
6. Return the new head that we saved in step 2.
Time Complexity : O(N)
Auxiliary Space : O(1)

Try solving now