## Google Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

I feel like it is like a bfs problem, but I am not sure whether it satisfies interviewer? start from the origin point, and bfs search its surrounding area. Any other idea?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````# Randomly assuming that target is calculated (once reached) as target = target[x]* 7, target[y]* 7
def move(start, target):
queue = collections.deque([[start]])
seen = {start}
while queue:
path = queue.popLeft()
x, y = path[-1]
if x, y == target:
return move((x, y), (target[0] * 7, target[1] * 7))
candidates = {(x + 1, y + 1), (x - 1, y + 1), (x - 1, y - 1), (x + 1, y - 1)}
forbidden_l = get_forbidden_cells()
for can in candidates:
if can not in forbidden_l  and can not in seen:
queue.append(path + [can])

def get_forbidden_cells():
# not relevant, probably O(1)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

ID DFS + BFS

Comment hidden because of low score. Click to expand.
0
of 0 vote

to reach any row or col the minimum jumps required is row/col number/2. then need to check which is the target cell. Worst case is 3 extra jumps to reach that cell. we use this formula

Comment hidden because of low score. Click to expand.
0
of 0 vote

A* Search should accomplish this! Use the manhattan distance from ur current space to the goal (x, y) as your heuristic.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <utility>
// #include <abs>

using std::abs;
using std::make_pair;
using std::pair;
using std::queue;
using std::set;
using std::vector;

int minStepsToTarget(int x, int y, const set<pair<int, int>>& forbidden) {
// Normalizing x, y to handle symmetry; a knight's move is symmetric across axes.
x = abs(x);
y = abs(y);
if (x < y) std::swap(x, y);

// Directions a knight can move.
vector<pair<int, int>> directions = {
{2, 1}, {1, 2}, {-1, 2}, {-2, 1},
{-2, -1}, {-1, -2}, {1, -2}, {2, -1}
};

queue<pair<pair<int, int>, int>> q; // ((x, y), steps)
set<pair<int, int>> visited; // To avoid revisiting and infinite loops.

q.push(make_pair(make_pair(0, 0), 0)); // Start from the origin.
visited.insert(make_pair(0, 0));

while (!q.empty()) {
auto front = q.front();
q.pop();
auto [currentX, currentY] = front.first;
int steps = front.second;

// Normalize the current position for symmetry.
currentX = abs(currentX);
currentY = abs(currentY);

if (currentX < currentY) {
std::swap(currentX, currentY);
}

// Check if we've reached the target.
if (currentX == x && currentY == y) {
return steps;
}

// Explore all possible moves.
for (const auto& dir : directions) {
int nextX = currentX + dir.first;
int nextY = currentY + dir.second;
if (nextX < nextY) {
std::swap(nextX, nextY); // Normalize for symmetry.
}

// Check if the move is allowed and not yet visited.
if (forbidden.find(make_pair(nextX, nextY)) == forbidden.end() && visited.find(make_pair(nextX, nextY)) == visited.end()) {
q.push(make_pair(make_pair(nextX, nextY), steps + 1));
visited.insert(make_pair(nextX, nextY));
}
}
}

// In case no path exists (shouldn't happen on an infinite board without forbidden coordinates)
return -1;
}

int main() {
set<pair<int, int>> forbidden = {{2, 3}, {3, 2}}; // Example forbidden coordinates.
int x = 5, y = 5;

std::cout << "Minimum steps to reach (" << x << ", " << y << "): "
<< minStepsToTarget(x, y, forbidden) << std::endl;

return 0;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.