This article contains my solutions to Booking.com‘s Coding assignment for the Software Developer position. I am sharing this for educational-purposes only.
Question 1
Description:
Scheduling meetings is a very common task and finding the ideal time for it is normally a tedious process. Given a schedule containing existing meetings, develop a function to help find the earliest available time for a new meeting to be scheduled.
• Important: All times are provided as number of minutes from the start of the day – i.e. 600 => 10:00 (10:00am); 1080 => 18:00 (6:00pm)
• If multiple time slots are available, your function should return the first
• If it is not possible to suggest a time for a given input, your function should output No time available
Input description:
The input contains the start and end time of the work day, followed by a list of meetings already scheduled, and finally the current time of day and how long the meeting should be – for example:
480 1080
4
600 660
720 780
780 825
900 940
780
45
Output
825-870
Question 2
Description
At Booking.com we have a search feature to find a travel destination. For this feature we have an input field where a user can enter their desired destination name. Sometimes our users make typos, so we try to help them by suggesting the closest match we have found. This question relates to that problem. Given an input string and a list of destinations, return all destinations that have the same length as the input, and that are equally different from that input amongst the list of destinations.
Example If two destinations have the same score due to having an equal number of differences from the input (e.g. they both differ by 2 characters) and a third destination has a lower score due to having more differences from the input (e.g. it differs by 4 characters), then only the first two destinations should be returned.
Input string:
“nalga”
Input dictionary:
“bali” (different length)
“malta” (2 characters different)
“palma” (2 characters different)
“paris” (4 characters different)
Expected output:
“malta”
“palma”
(all words have 2 characters different)
Constraints
0 <= dictionary.length <32,767
0 <= input.length < 127
Run time complexity
We expect a solution that has a runtime complexity of O(n*m) where n is the length of the input string, and mis the size of the dictionary.
Solution
import java.util.ArrayList;
import java.util.List;
public class DestinationMatcher {
public static void main(String[] args) {
String input = "nalga";
List dictionary = new ArrayList<>();
dictionary.add("bali");
dictionary.add("malta");
dictionary.add("palma");
dictionary.add("paris");
List result = findClosestDestinations(input, dictionary);
for (String destination : result) {
System.out.println(destination);
}
}
public static List findClosestDestinations(String input, List dictionary) {
List closestDestinations = new ArrayList<>();
int minDifference = Integer.MAX_VALUE;
for (String destination : dictionary) {
if (destination.length() == input.length()) {
int difference = calculateDifference(input, destination);
if (difference < minDifference) {
closestDestinations.clear();
closestDestinations.add(destination);
minDifference = difference;
} else if (difference == minDifference) {
closestDestinations.add(destination);
}
}
}
return closestDestinations;
}
public static int calculateDifference(String s1, String s2) {
int difference = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
difference++;
}
}
return difference;
}
}
def main():
input_str = "nalga"
dictionary = ["bali", "malta", "palma", "paris"]
result = find_closest_destinations(input_str, dictionary)
for destination in result:
print(destination)
def find_closest_destinations(input_str, dictionary):
closest_destinations = []
min_difference = float('inf')
for destination in dictionary:
if len(destination) == len(input_str):
difference = calculate_difference(input_str, destination)
if difference < min_difference:
closest_destinations.clear()
closest_destinations.append(destination)
min_difference = difference
elif difference == min_difference:
closest_destinations.append(destination)
return closest_destinations
def calculate_difference(s1, s2):
difference = 0
for c1, c2 in zip(s1, s2):
if c1 != c2:
difference += 1
return difference
if __name__ == "__main__":
main()
#include <iostream>
#include <vector>
#include <string>
#include <limits>
int calculateDifference(const std::string& s1, const std::string& s2) {
int difference = 0;
for (size_t i = 0; i < s1.length(); ++i) {
if (s1[i] != s2[i]) {
difference++;
}
}
return difference;
}
std::vector findClosestDestinations(const std::string& input, const std::vector& dictionary) {
std::vector closestDestinations;
int minDifference = std::numeric_limits::max();
for (const std::string& destination : dictionary) {
if (destination.length() == input.length()) {
int difference = calculateDifference(input, destination);
if (difference < minDifference) {
closestDestinations.clear();
closestDestinations.push_back(destination);
minDifference = difference;
} else if (difference == minDifference) {
closestDestinations.push_back(destination);
}
}
}
return closestDestinations;
}
int main() {
std::string input = "nalga";
std::vector dictionary = {"bali", "malta", "palma", "paris"};
std::vector result = findClosestDestinations(input, dictionary);
for (const std::string& destination : result) {
std::cout << destination << std::endl;
}
return 0;
}
