[Challenge] Uber coding challenge

Consider a city where the streets are perfectly laid out to form an infinite square grid. In this city finding the shortest path between two given points (an origin and a destination) is much easier than in other more complex cities. As a new Uber developer, you are tasked to create an algorithm that does this calculation.

Given user’s departure and destination coordinates, each of them located on some street, find the length of the shortest route between them assuming that cars can only move along the streets.

Example

For departure = [0.4, 1] and destination = [0.9, 3] the answer should be 2.7.

[input] array.float departure

An array [x, y] of x and y coordinates. It is guaranteed that at least one coordinate is integer.

[input] array.float destination

The destination is given the same way as the departure location.

[output] float

The shorted distance between two points along the streets.

This was an interesting problem to solve because I constantly wondered if there was an elegant way possible besides the obvious brute-force way to solve the problem.
You know what? I couldn’t think of any.
Lesson learned was that if it the code does the job for you, and it has a decent efficiency, there’s no point in writing something cool.

My solution is messy but it works with an efficiency of O(n).
At this point in life, I’m not overly concerned about failing coding challenges. If I do, then I certainly don’t deserve the job.

I think interview questions should truly reflect on one’s ability to perform at high efficiency at the company and fulfill the company’s vision. If I see someone wasting precious time to write “elegant” code at work, I mostly think of the person as trying to show-off (which isn’t negative but in my mind, I’m like really – was that necessary). I’d much rather see someone write quality code, quickly and correctly, with high readability so that someone that isn’t too technical like me can understand.

Anyway I wrote the solution to this problem by brute-forcing it. The question would be trivial if it were just integers but the constraint of floating points adds some complexity and makes us cover some corner cases. For some floating points, we have to think about moving backwards (floor) or move front (ceil) and find the minimum in every scenario.

Sorry in advance if it’s not an one-liner in C++.

#!/usr/bin/python
# -*- coding: utf-8 -*-
# CodeFights perfectCity

def perfectCity(departure, destination):
    import math
    (depX, depY) = departure
    (destX, destY) = destination
    distances = []

    for i in [math.floor, math.ceil]:
        x = depX
        y = depY
        distance = 0
        while 1:
            (dx, dy) = (0, 0)
            if x == destX:
                dy = destY - y
            elif y == destY:
                dx = destX - x
            elif x % 1 != 0:
                dx = i(x) - depX
            elif y % 1 != 0:
                dy = i(y) - depY
            elif destX % 1 != 0:
                dy = destY - y
            elif destY % 1 != 0:
                dx = destX - x

            distance += abs(dx + dy)
            x += dx
            y += dy

            if x == destX and y == destY:
                break

        distances.append(distance)

    return min(distances)

#!/usr/bin/python

# -*- coding: utf-8 -*-

# CodeFights perfectCity

def perfectCity(departure, destination):

import math

(depX, depY) = departure

(destX, destY) = destination

distances = []

for i in [math.floor, math.ceil]:

x = depX

y = depY

distance = 0

while 1:

(dx, dy) = (0, 0)

if x == destX:

dy = destY - y

elif y == destY:

dx = destX - x

elif x % 1 != 0:

dx = i(x) - depX

elif y % 1 != 0:

dy = i(y) - depY

elif destX % 1 != 0:

dy = destY - y

elif destY % 1 != 0:

dx = destX - x

distance += abs(dx + dy)

x += dx

y += dy

if x == destX and y == destY:

break

distances.append(distance)

return min(distances)

Not too difficult of a challenge. I heard DropBox’s challenges were difficult on CodeFlights. That’ll be my next goal!

[Challenge] Uber coding challenge

Share: