Round 1

You are trapped in a grid where some cells contain walls, some are occupied by zombies, and others are open paths. Your goal is to find the shortest path from the start point to the gate (exit), while staying as far away from the zombies as possible.

Grid Details:

The grid is represented as a 2D matrix.
Each cell in the matrix can be one of the following:
'S': Start position (You begin at this location).
'G': Gate (Your goal is to reach this location).
'Z': Zombie (You should avoid these cells as much as possible).
'W': Wall (These cells are impassable).
'0': Open cell (You can move through these cells).
Movement:

You can move up, down, left, or right, but cannot move diagonally.
You cannot move through walls.
Your priority is to stay as far away from zombies as possible while still finding the shortest path to the gate.
Task:
Write a function that takes this matrix as input and returns the path so you stay as far as possible from zombie.

Round 2

Interview Question: Efficient Search Engine with Recent Query Management
Problem Statement:

You are tasked with designing a search engine component that keeps track of the most recent search queries performed by users. The system should store a maximum of n unique search queries, ensuring that the most recent searches are easily accessible.

When a search query is performed:

If the query is already stored, it should be moved to the front of the list, marking it as the most recent query.
If the query is new and the list is full (containing n queries), the oldest query should be removed to make room for the new one.
The system should allow retrieval of the top n most recent queries, with the most recent queries appearing first.

Requirements:

Implement a class called SearchEngine that supports the following methods:

search(query: string): void - Adds a search query to the system.
topSearch(n: number): string[] - Returns the top n most recent unique search queries.
Optimize the implementation for:
Searching better than O(n)