## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

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

This is one of the latest Google Foobar questions. It's unlikely to come up in an interview setting. The answer involves a fair amount of graph theory and a fast implementation.

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

Here is a brute-ish solution. Traverse the graph, and maintain a "bunny state", consisting of the bunnies rescued, and the time remaining. At each node, store the state in a hash table. Or, if the same state was previously encountered with an equal or better time remaining, terminate that branch of the search.

With a maximum of 5 bunnies, I don't know why "a fair amount of graph theory and a fast implementation" is necessary.

``````const int cMaxBunnies = 5;

union bunnyState
{
struct
{
int8_t bRescued[cMaxBunnies];
int8_t location;
};
int64_t hashVal;
};

typedef std::vector<int> rowType;

void Rescue_Recurse(const std::vector<rowType>& mtx, rowType& result, const bunnyState& state, std::unordered_map<int64_t, int>& bestStates,
int loc, int tm)
{
bunnyState newState = state;
newState.location = loc;
if (loc == mtx.size() - 1)
{
int rescued = std::count(state.bRescued, state.bRescued + cMaxBunnies, 1);
if ((tm >= 0) && (rescued > (int)result.size()))
{
result.clear();
for (int i = 0; i < cMaxBunnies; i++)
if (state.bRescued[i])
result.push_back(i);
}
}
else if (loc > 0)
newState.bRescued[loc-1] = 1;
auto curVal = bestStates.find(newState.hashVal);
if ((curVal == bestStates.end()) || curVal->second < tm)
{
bestStates[newState.hashVal] = tm;
for (int i = 0; i < (int)mtx[loc].size(); i++)
Rescue_Recurse(mtx, result, newState, bestStates, i, tm - mtx[loc][i]);
}
}

rowType Do_Rescue(const std::vector<rowType>& mtx, int tm)
{
std::vector<int> result;
std::unordered_map<int64_t, int> bestStates;
Rescue_Recurse(mtx, result, {0}, bestStates, 0, tm);
printf("{");
for (int i: result)
printf("%d,", i);
printf("}\n");
return result;
}

int main()
{
Do_Rescue({ {0, 1, 1, 1, 1}, {1, 0, 1, 1, 1}, {1, 1, 0, 1, 1}, {1, 1, 1, 0, 1}, {1, 1, 1, 1, 0} }, 3); //output: {0,1,}
Do_Rescue({ {0, 2, 2, 2, -1}, {9, 0, 2, 2, -1}, {9, 3, 0, 2, -1}, {9, 3, 2, 0, -1}, {9, 3, 2, 2, 0} }, 1); //output: {1,2}
}``````

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

I got this question in the foobar challenge, I solved it using Edmonds' blossom-contraction algorithm for maximum carnality matching in general graphs , it was not easy ...

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

hey can you elaborate it more like how the blossom-contraction algorithm can be used for this problem.

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

What is the importance of time_limit in this question

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.