I failed the Google phone interview. Not happy about it at all, but of all the interviews I’ve encountered this is the first that has seriously stretched my limits.
I’m not sure what the limitations are, but the problem starts easily enough.
Find all the planets in a list that can be visited .
We simply need to determine if a path is reachable or not.
Given the following structure, determine whether or not we can find a path to the destination planet (dp)
struct planet {
int x;
int y;
char *name;
}
A function signature is given as well…
int doesPathExist( planet \*op, planet \*dp, planet \*\*planets ) {
}
I caught that this was a graph pretty quickly, but for some stupid reason got tripped up when determining the bounds for the breadth-first search.
Unfortunately, I knew I had blown this problem by 30 minutes in simply because I didn’t think in-depth enough.
What this problem should have looked like in the first 10 minutes should have been something like:
// We can discard decimals
int get_distance ( planet \*a, planet \*b ) {
int x = a.x - b.x;
int y = a.y - b.y;
x *= x, y *= y;
// Probably should take the ceiling of this number...
return sqrt( x + y );
}
const int fuel = 20;
int doesPathExist( planet \*op, planet \*dp, planet \*\*planets ) {
int distance = sqrt ( ( dp.x - op.x ) ( dp.y - op.y ) );
if ( get_distance( op, dp ) <= fuel ) {
return 1;
}
for ( planet **p = planets; *p; p++ ) {
}
return 0;
}
Our C code is making some assumptions for the sake of brevity. The first is that planets contains a terminating NULL, which assumes that this is a dynamically allocated list. If this were static, we could either initialize one of the struct values with a symbolic value (e.g. name could point to NULL meaning that there is no name for a planet that does not exist).
We are also doing away with any floating point calculations (hence the reason for rounding up our distance).
Calculating each of the paths will be a pretty long process, but it’s really the only way to go about solving a problem like this.
Let’s skip to the for loop.
int doesPathExist( planet \*op, planet \*dp, planet \*\*planets ) {
...
// In essence, we don't have a solid way to sort these
for ( planet *cp = op, **p = planets; *p; p++ ) {
if ( strcmp( p->name, op->name ) == 0 ) {
continue;
}
for ( ;; ) {
}
}
...
}
Can you guess what should be in the second inner-most for loop?
It’s not obvious if you haven’t been brushing up on implementing BFS.
Our code needs to mark each planet we’ve visited and simply determine if there is a reachable path.
int doesPathExist( planet \*op, planet \*dp, planet \*\*planets ) {
...
planet **set = NULL;
for ( planet **ip = planets; *ip; ip++ ) {
//Consider neither the origin planet nor the current planet
if ( !p->visited || strcmp( p->name, op->name ) == 0 || strcmp( p->name, cp->name ) == 0 ) {
continue;
}
else {
int distNext = get_distance( cp, ip );
int distEnd = get_distance( ip, dp );
if ( distEnd <= fuel && distNext <= fuel ) {
return 1;
}
ip->visited = 1;
if ( distNext <= fuel ) {
append( &set, ip );
}
}
}
...
}
A good grasp on algorithms and practice applying them will probably get you further than any other exercise. Typical interviews usually ask about things like reversing strings or linked lists or finding cycles. Obviously knowing these in and out is good practice and good for being able to explain the what and why behind many of our choices when coming up with a solution. But remember, we’re not consultants. At the end of the day, programmers write code that solves a problem and delivers a solution. Being able to map these relationships early on is one of the most useful ways to approach a problem.
Second, chill. I still find myself getting nervous in interview situations because there is a time crunch and someone I’m not familiar with on the other side of the table.
Perhaps I’ll have better news in the future.