SDE - 2

You are given a 2-dimensional array/list having N rows and M columns, which is filled with ones(1) and zeroes(0). 1 signifies land, and 0 signifies water.

A cell is said to be connected to another cell, if one cell lies immediately next to the other cell, in any of the eight directions (two vertical, two horizontal, and four diagonals).

A group of connected cells having value 1 is called an island. Your task is to find the number of such islands present in the matrix.

You are given a Singly Linked List of N nodes such that each node represents a single digit.

Your task is to return a node 'X', where 'X' represents the head of the Linked List storing the digits of the sum(most significant digit at the head) formed by adding the 1st half and 2nd half of the given Linked List.

Note:

1. When N is odd consider the middle element to be part of 1st half.

2. The sum should not contain any leading zero, except the number 0 itself.

For Example:

Given Linked List: 1-2-3-4-5-5-6

First half: 1-2-3-4    
Second half: 5-5-6

Output Linked List: 1-7-9-0 = (1234 + 556 = 1790)

Follow Up:

Can you add both halves without finding the length of Linked List and in O(1) space?

You are given an array arr of length N. You have to return a list of integers containing the NGE(next greater element) of each element of the given array. The NGE for an element X is the first greater element on the right side of X in the array. Elements for which no greater element exists, consider the NGE as -1.

For Example :

If the given array is [1, 3, 2], then you need to return [3, -1, -1]. Because for 1, 3 is the next greater element, for 3 it does not have any greater number to its right, and similarly for 2.

You are given a string 's', and a dictionary of words 'dict' containing 'n' words. Your task is to add spaces in 's' to form valid sentences, where each word is a word from the dictionary.

You need to return all possible sentences that can be formed using the given dictionary.

Note :

The same word from a dictionary can be used as many times as possible to make sentences.

You're given a string 'S' consisting of "{", "}", "(", ")", "[" and "]" .

Return true if the given string 'S' is balanced, else return false.

For example:

'S' = "{}()".

There is always an opening brace before a closing brace i.e. '{' before '}', '(' before ').
So the 'S' is Balanced.

Design a local transport system like BMTC.

It was mix of HLD, LLD design discussion of your project. Make sure you know enough about your projects. Questions asked were based on Amazon leadership principles. Amazon mainly focuses on those principles.