SDE - 1

Optimize Suggestions

Search nearest  X restaurants in the city relative to the customer's location. 

Input -

1.  Pair of x & y coordinates representing the location of restaurants.

2. Number of restaurants returned to customer X

Note - Customer begins at (0,0)

You want to visit your friend’s house who lives at some location in an infinite grid. You are initially at the origin of the infinite grid and can move only in four directions (i.e East, West, North, South).

For Example, If you are at cell (X, Y) then you can move to East i.e at cell (X+1, Y), or West i.e at cell (X-1, Y), or North i.e at cell (X, Y+1), or South i.e at cell (X, Y-1).

Your friend gives you a string ‘STR’ of length ‘N’ that represents the route to his house from the origin. The string ‘STR’ has only four different characters, i.e ‘E’, ‘W’, ‘N’, ‘S’. which represent direction East, West, North, South, respectively.

You find out that the route given by your friend is very long, and a shorter route is also possible. Your task is to find the smallest route to reach your friend’s house. See the example for better clarity.

Note:

1. There can be more than one shortest route, you should return the one which is lexicographically smallest among them.

Example:

Consider that your friend’s house is in the cell (2, 1) in the grid. And the route given by your friend is represented by the string ‘STR’= “NNSEWEE”.

One of the smallest route to reach cell (2, 1) from origin i.e cell (0, 0) is given by string  “EEN”  i.e you start from the cell (0, 0), then move East, i.e at cell (1, 0), then again move East, i.e at cell (2, 0), and then finally move North i.e at cell (2, 1).

Note, there are some other smallest routes such as “NEE”,  “ENE” etc, but “EEN” is the lexicographically smallest among them, so you should return it.  

You are given a non-empty binary tree where each node has a non-negative integer value. Return the maximum possible sum of path between any two leaves of the given tree.

The path is also inclusive of the leaf nodes and the maximum path sum may or may not go through the root of the given tree.

If there is only one leaf node in the tree, then return -1.

You have been given a grid containing some oranges. Each cell of this grid has one of the three integers values:

Value 0 - representing an empty cell.

Value 1 - representing a fresh orange.

Value 2 - representing a rotten orange.

Every second, any fresh orange that is adjacent(4-directionally) to a rotten orange becomes rotten.

Your task is to find out the minimum time after which no cell has a fresh orange. If it's impossible to rot all the fresh oranges then print -1.

Note:

1. The grid has 0-based indexing.
2. A rotten orange can affect the adjacent oranges 4 directionally i.e. Up, Down, Left, Right.

Different types of graph traversals, which one should be used for shortest distance/time & why? Time complexities.

You have been given a Binary Tree of integers. You are supposed to return the level order traversal of the given tree.

For example:

For the given binary tree

The level order traversal will be {1,2,3,4,5,6,7}.

You have been given a Binary Tree of 'N' nodes, where the nodes have integer values. Your task is to print the zigzag traversal of the given tree.

Note:

In zigzag order, level 1 is printed from left to right fashion, level 2 is printed from right to left. and level 3 is printed from left to right again, and so on…..

For example:

For the given binary tree

The zigzag  traversal is [1, 4, 3, 5, 2, 7, 6]

Aahad and Harshit always have fun by solving problems. Harshit took a sorted array consisting of distinct integers and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4, 5] and if he rotates it by 2, then the array becomes: [4, 5, 1, 2, 3].

After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i]. which Harshit wanted him to search in the array. For each query, if he found it, he had to shout the index of the number, otherwise, he had to shout -1.

For each query, you have to complete the given method where 'key' denotes Q[i]. If the key exists in the array, return the index of the 'key', otherwise, return -1.

Note:

Can you solve each query in O(logN) ?

You are given an array 'A' of length 'N' consisting only of integers. You are also given three integers 'X', 'Y' and 'SUM'. Count the number of pairs ('i', 'j') where 'i' < 'j' such that ('A[i]' * 'X' + 'A[j]' * 'Y') = 'SUM'.

Example :

'N' = 3, 'A' = {3, 1, 2, 3}, 'X' = 4, 'Y'= 2, 'SUM' = 14

For 'i' = 1, 'j' = 2, Value of the expression = 4 * 3 + 2 * 1 = 14.
For 'i' = 1, 'j' = 3, Value of the expression = 4 * 3 + 2 * 2 = 16.
For 'i' = 1, 'j' = 4, Value of the expression = 4 * 3 + 2 * 3 = 18.
For 'i' = 2, 'j' = 3, Value of the expression = 4 * 1 + 2 * 2 = 8.
For 'i' = 2, 'j' = 4, Value of the expression = 4 * 1 + 2 * 3 = 10.
For 'i' = 3, 'j' = 4, Value of the expression = 4 * 2 + 2 * 3 = 14.

The possible pairs are :
(1, 3), (3,4)

What is a hashmap? When is it used. What is the time complexity while retrieving data, inserting data?
Explain the internal working of maps in Java.

Explain about the project you're currently working on. What are the challenges faced?

You have been given an array/list 'ARR' consisting of 'N' integers. Your task is to find the majority element in the array. If there is no majority element present, print -1.

Note:

A majority element is an element that occurs more than floor('N' / 2) times in the array.

Questions based on the projects mentioned in the Resume