SDE - 1

You have been given a graph consisting of ‘N’ vertices numbered from 1 to ‘N’. The graph has ‘M’ edges. In an operation, you can shift an edge between two directly connected vertices to between pair of disconnected vertices to make them directly connected. Return the minimum number of operations to make the graph connected. If it is not possible to make graph connected return -1.

Example:

Let’s say ‘N’ is 4 and ‘M' is 3. The 3 edges are (1,2), (2,3) and (1,3). Then our graph will look as follows:-

To make the graph connected we can shift the edge between (1,3) to (1,4). This operation will make the graph connected. There are multiple ways in which we can make graph connected. So, in this case, we can make graph connected in just one operation.

Note:

1. A connected graph is a graph that is connected in the sense of a topological space, i.e., there is a path from any vertex to any other vertex in the graph.

2. There are no repeated edges and self-loops in the graph.

3. You do not need to print anything; it has already been taken care of. Just implement the function.

A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are N items and the ith item weighs wi and is of value vi. Considering the constraints of the maximum weight that a knapsack can carry, you have to find and return the maximum value that a thief can generate by stealing items.

Abhishek, a blind man has N distinct binary strings all of the equal lengths. A binary string only contains '0's and '1's. The strings are numbered from 1 to N and all are distinct strings. Abhishek can only differentiate between these strings by touching them. In one touch Abhishek can identify one character at a position of any particular string from the set. Your task is to find the minimum number of touches Abhishek has to make so that he finds that all strings are different.

You are given a linked list of 'n' nodes and an integer 'k', where 'k' is less than or equal to 'n'.

Your task is to reverse the order of each group of 'k' consecutive nodes, if 'n' is not divisible by 'k', then the last group of nodes should remain unchanged.

For example, if the linked list is 1->2->3->4->5, and 'k' is 3, we have to reverse the first three elements, and leave the last two elements unchanged. Thus, the final linked list being 3->2->1->4->5.

Implement a function that performs this reversal, and returns the head of the modified linked list.

Example:

Input: 'list' = [1, 2, 3, 4], 'k' = 2

Output: 2 1 4 3

Explanation:
We have to reverse the given list 'k' at a time, which is 2 in this case. So we reverse the first 2 elements then the next 2 elements, giving us 2->1->4->3.

Note:

All the node values will be distinct.

The ninja visits an amusement park but finds himself confused because he wants to ride the rides such that he gets maximum fun. The amusement park has only one entrance that is root.

Each ride has a fun number assigned to it and ninja wants to maximize this fun but there is a rule in the park that no one is allowed to ride two directly connected rides.

As the ninja is smart and good in programming because he did a course from coding ninja, he found immediately that park rides are connected like binary tree where the root is the root of the binary tree. Help the ninja to get the maximum fun this time.

Design an Uber booking system where Uber drivers constantly update their location and app users can make a booking and get the closest drivers.
I was given around 25 minutes to identify the various entities involved in the system, establish the relationships between these entities and also identify the primary key - foreign key constraints. After 25 minutes, we had a good discussion on my findings and corrections with respect to certain attributes I may have missed out on in my design. 
A few complex SQL queries were also asked related to the above schemas.
Unfortunately After this round i did not a get follow up from HR. so i assume that i was rejected.