SDE - 1

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.

Given a singly linked list of integers. Your task is to return the head of the reversed linked list.

For example:

The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse linked list is 4 -> 3 -> 2 -> 1 -> NULL and the head of the reversed linked list will be 4.

Follow Up :

Can you solve this problem in O(N) time and O(1) space complexity?

Which data structure would you use to create a dictionary?

I suggested maps, discussion on why maps, and how they would work. Some discussion around hashing.

Discussion on whether can we use Linked lists.

Alice and Bob always loved to play with arrays. Alice took a sorted array and rotated it clockwise for a certain number of times.

For example:

Alice took a sorted array = [4,6,8,10,11] and if she rotates it by 3, then the array becomes: [8, 10, 11, 4, 6]. 

After rotating a sorted array, Alice gave a number ‘K’ to Bob and asked him to search for a pair in an array whose sum is equal to K. Since Bob was busy preparing for his semester exams, he asked you to help him.

You are given an array of integers ARR and a number K. Your task is to find out whether there exists a pair in the array ARR with sum K or not. If there exists a pair then you can return TRUE else return FALSE;