[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.
departure = [0.4, 1]and
destination = [0.9, 3]the answer should be
- [input] array.float departure
- An array
ycoordinates. 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++.
# -*- coding: utf-8 -*-
# CodeFights perfectCity
def perfectCity(departure, destination):
(depX, depY) = departure
(destX, destY) = destination
distances = 
for i in [math.floor, math.ceil]:
x = depX
y = depY
distance = 0
(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:
Not too difficult of a challenge. I heard DropBox’s challenges were difficult on CodeFlights. That’ll be my next goal!