SDE - 1

28 MCQs based on core CS – trees, BFS, DFS, C++ outputs, stacks, queues. If you’ve prepared for placements, you’ll get through them pretty easily. If unprepared, it will be challenging to go through them within the allotted time.

A doubly-linked list is a data structure that consists of sequentially linked nodes, and the nodes have reference to both the previous and the next nodes in the sequence of nodes.

You are given a sorted doubly linked list of size 'n'.

Remove all the duplicate nodes present in the linked list.

Example :

Input: Linked List: 1 <-> 2 <-> 2 <-> 2 <-> 3

Output: Modified Linked List: 1 <-> 2 <-> 3

Explanation: We will delete the duplicate values ‘2’ present in the linked list.

You are a student of Netaji Subhas Institute of Technology. You have to take ‘N’ number of courses labelled from 1 to N to complete your B.Tech Degree.

Some courses may have prerequisites, for example, to take course 1 you have to first take course 2, which is expressed as a pair: [1, 2]. Now, your task is to find is it possible for you to finish all courses.

Note: There are no duplicate pairs in the prerequisites array.

For example-

If N = 2 and prerequisite = [[1, 2]]. Then, there are a total of 2 courses you need to take. To take course 1 you need to finish course 2. So, it is possible to complete all courses. 

You have been given a Binary Tree of distinct integers and two nodes ‘X’ and ‘Y’. You are supposed to return the LCA (Lowest Common Ancestor) of ‘X’ and ‘Y’.

The LCA of ‘X’ and ‘Y’ in the binary tree is the shared ancestor of ‘X’ and ‘Y’ that is located farthest from the root.

Note :

You may assume that given ‘X’ and ‘Y’ definitely exist in the given binary tree.

For example :

For the given binary tree

LCA of ‘X’ and ‘Y’ is highlighted in yellow colour.

You are given a class named as BSTIterator that represents an iterator over inorder traversal of a binary search tree. You need to implement the following things as follows:

1. BSTIterator(Node root) - It is a parameterized constructor in which you are given the root of the Binary search tree. It will be called whenever an object of BSTIterator is created.

2. next() - This member function will return the next smallest element in the in-order traversal of the binary search tree. You need to implement this function.

3. hasNext() - This function will return true if there exists the next smallest element in the traversal else it will return false. You need to implement this function

The binary search tree has ‘N’ nodes you need to print the inorder traversal of the tree using the iterator.

Given a binary array 'ARR' of size 'N', your task is to find the longest sequence of continuous 1’s that can be formed by replacing at-most 'K' zeroes by ones. Return the length of this longest sequence of continuous 1’s.

Given an adjacency list representation of a directed graph with ‘n’ vertices and ‘m’ edges. Your task is to return a list consisting of Breadth-First Traversal (BFS) starting from vertex 0.

In this traversal, one can move from vertex 'u' to vertex 'v' only if there is an edge from 'u' to 'v'. The BFS traversal should include all nodes directly or indirectly connected to vertex 0.

Note:

The traversal should proceed from left to right according to the input adjacency list.

Example:

Adjacency list: { {1,2,3},{4}, {5}, {},{},{}}

The interpretation of this adjacency list is as follows:
Vertex 0 has directed edges towards vertices 1, 2, and 3.
Vertex 1 has a directed edge towards vertex 4.
Vertex 2 has a directed edge towards vertex 5.
Vertices 3, 4, and 5 have no outgoing edges.

We can also see this in the diagram below.

BFS traversal: 0 1 2 3 4 5

You have been given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges. Each edge connecting two nodes (‘X’,’Y’) will have a weight denoting the distance between node ‘X’ and node ‘Y’.

Your task is to find the shortest path distance from the source node, which is the node labeled as 0, to all vertices given in the graph.

Example:

Input:
4 5
0 1 5
0 2 8
1 2 9
1 3 2
2 3 6

In the given input, the number of vertices is 4, and the number of edges is 5.

In the input, following the number of vertices and edges, three numbers are given. The first number denotes node ‘X’, the second number denotes node ‘Y’ and the third number denotes the distance between node ‘X’ and ‘Y’.

As per the input, there is an edge between node 0 and node 1 and the distance between them is 5.

The vertices 0 and 2 have an edge between them and the distance between them is 8.
The vertices 1 and 2 have an edge between them and the distance between them is 9.
The vertices 1 and 3 have an edge between them and the distance between them is 2.
The vertices 2 and 3 have an edge between them and the distance between them is 6.

Note:

1. There are no self-loops(an edge connecting the vertex to itself) in the given graph.

2. There can be parallel edges i.e. two vertices can be directly connected by more than 1 edge.

A couple of DBMS questions - 

- What database have you worked on.
- Can you tell me what normal forms are?
- Can you explain me a few normal forms 
- Diff between sql and nosql
- Example of nosql databases? Example of nosql databases of amazon

The interviewer’s style was very different from others. Discussion started as follows -

- Tell me about yourself
- Tell me your best project from resume
- What did you do in this
- How is it different from any other similar project
- How did you assure code quality in your project
- How do you define code quality
- How did you test your code
- Did you write test cases for your code
- Write down test case for this code ( he gave a code )

He took each point very seriously, and did counter arguments for some of these.

- Then he asked me which app do I use for music.
- Lets design a database for an app.
- So I wrote a basic schema. He then picked up on the details. A bit of discussion.
- Then we moved to a specific table.
- Why is this table like this
- Do you think that app uses it like this
- Do you think its scalable
- What can you do to make it scalable
- What should you do to make it scalable
- Think about more use cases, develop a generic db structure which can accommodate some of future changes.
- A little discussion about development methodologies - ( plan a lot of use cases and then make database schema ) or ( deliver fast and re-iterate ).

Ninja is now bored with numbers and is now playing with characters but hates when he gets repeated characters. Ninja is provided a string, and he wants to return the first unique character in the string.The string will contain characters only from the English alphabet set, i.e., ('A' - 'Z') and ('a' - 'z'). If there is no non-repeating character, print the first character of the string. If there is no non-repeating character, return the first character of the string.