SDE - 1

You are given a chessboard consisting of ‘N’ rows and ’M’ columns. Rows are numbered from 0 to ‘N-1’ and columns are numbered from 0 to ‘M-1’. Cell(i, j) is the cell at the intersection of the ith row and the jth column.

A knight is a chess piece that can move from cell (x1, y1) to the cell (x2, y2) if one of the following conditions is met:

|x1−x2| = 2 and |y1−y2| = 1, or

|x1−x2| = 1 and |y1−y2| = 2.

A knight cannot move outside the chessboard.

Initially a knight is placed at the cell(0, 0) of this chessboard, Moving according to the rules of chess, the knight must visit each cell exactly once. Find out the order of each cell in which they are visited.

Note :

1. There are multiple possible orders in which a knight can visit each cell of the chessboard exactly once. You can find any valid order.
2. It may be possible that there is no possible order to visit each cell exactly once. In that case, return a matrix having all the values equal to -1. 

Example :

Consider an 8*8 chessboard, one possible order for visiting each cell exactly once is shown in the image below. Numbers in cells indicate the move number of the Knight. 

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

Write an optimal algorithm for Facebook friend suggestions.Choose write data structure to store the friends information of all users.

Why do you want to choose a startup?

You are from non cs background, Why do you want to be a developer?

Why Rupeek?