SDE - 1

You are given an infinite chessboard (ie: the x-coordinates and y-coordinates can be anything between -infinity to +infinity).

You have a knight placed at coordinates ‘(0, 0)’. Find the minimum number of steps needed to move the knight to ‘(X, Y)’.

The knight has 8 possible moves, each move is two units in a cardinal direction, then one unit in an orthogonal direction.

For example :

As depicted in the photo below, the knight currently at (0, 0) can move to any of the 8 positions: (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2).

Example :

If X = 1 and Y = -1, then we need to find out the minimum number of steps to move the knight from (0, 0) to (1, -1).

We need at least 2 steps to move the knight to the desired position.

First move: (0, 0) -> (2, 1) 

Second move: (2,1) -> (1, -1)

Here we can see that there are many ways, but we need at least 2 steps. Therefore we will return the value 2.

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. Write what data structure you will use to store the friends' information of all users.

1. Why do you want to choose a startup?
2. You are from a non-cs background, Why do you want to be a developer?
3. Why Rupeek?