HackerRank ‘Service Lane’ Solution

Short Problem Definition:

Calvin is driving his favorite vehicle on the 101 freeway. He notices that the check engine light of his vehicle is on, and he wants to service it immediately to avoid any risks. Luckily, a service lane runs parallel to the highway. The length of the highway and the service lane is N units. The service lane consists of N segments of equal length and different width.

Link

Service Lane

Complexity:

time complexity is O(n)

space complexity is O(n)

Execution:

This challenge can be solved in a brute force manner. You just check for every entry/exit combination the biggest possible vehicle by min(arr[entry:exit+1]). Here, I will present a prefix sum solution with better runtime.

I create a prefix array, that saves the last entry point (or -1 if not possible) for this type of vehicle that comes before the current index (the exit point). Therefore, I can check for every entry/exit point the biggest possible type in constant time.

Solution:
#read
n,t = raw_input().split()
n = int(n)
t = int(t)
arr = map(int, raw_input().split())

#preprocess
last_possible_entry = []
for i, lane_width in enumerate(arr):
    last_car_entry = -1
    last_truck_entry = -1
    if lane_width > 1:
        last_car_entry = i
        if len(last_possible_entry) > 0 and last_possible_entry[-1][0] >= 0:
            last_car_entry = last_possible_entry[-1][0]
    
    if lane_width > 2:
        last_truck_entry = i
        if len(last_possible_entry) > 0 and last_possible_entry[-1][1] >= 0:
            last_truck_entry = last_possible_entry[-1][1]
       
    last_possible_entry.append([last_car_entry, last_truck_entry])

#get test cases    
for _ in xrange(t):
    i, j = map(int, raw_input().split())
    
    access_pattern = last_possible_entry[j]
    if access_pattern[1] != -1 and access_pattern[1] <= i:
        print "3"
    elif access_pattern[0] != -1 and access_pattern[0] <= i:
        print "2"
    else:
        print "1"
    
    

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Robert Kuska

    You know you could simply took the array of widths and print the minimum from given range?

    if input was 0,3 you would print min(arr[0:3+1])

    • Yeah, I wrote that such a solution exists in the description. It even passes all the HackerRank tests :). I chose to post a more time-effective variant.

      • Robert Kuska

        Oh, I was looking only at the solution, in that case I am sorry 🙂

  • Yeah, I wrote that such a solution exists in the description. It even passes all the HackerRank tests :). I chose to post a more time-effective variant.

  • Vishal Doshi

    Hello there, if you post a diagram or an solved example, it will be easy to understand. Pseudocode might also help. Thanks!

    • Hi Vishal,

      I won’t be able to do that in May. But I might do that afterwards, if the interest persists.

  • anirudh goel

    hello, can you please share the pseudocode?

    • X <- for each service width remember last entry for all width types before this point

      for q(begin,end) in Query read biggest possible width from X where X[end] has to be before begin

  • Сварожічъ Х’Арійскі

    This is an ugly pseudo-code for a such easy and stupid problem!

    Here it is C++ one line solution:
    int largest = 3;
    for_each(widths.begin() + enter, widths.begin() + exit + 1, [&](int n){ largest = min(n, largest); });

    Where:
    widths – is a vector of all highway widths;
    enter, exit – are int’s