Shops and Houses

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
3 upvotes
Asked in company
Google inc

Problem statement

You have an ‘H’ number of friends who live in different ‘H’ houses. You are going shopping with them. To reduce the shopping time, you have to choose the shop closest to your friend’s house. You have two integer arrays, ‘SHOPS’ and ‘HOUSES’, representing the location of a shop and house in a city. For each house, you have to find the nearest shop location. If many shops are equidistant from a house, choose the shop with the smallest numerical location.

Example :

Give houses location, ‘HOUSES’ : {2, 4, 2}
Given shops location, ‘SHOPS’ : {5, 1, 2, 3}

The shops closest to each houses are : {2, 3, 2}
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, the number of test cases.

The first line of each test case contains a single integer ‘H’ representing the number of the houses.

The second line of each test case contains ‘H’ single space-separated integers representing the location of the houses.

The third line of each test case contains a single integer ‘S’ representing the number of the shops.

The fourth line of each test case contains ‘S’ single space-separated integers representing the location of the shops.
Output Format : 
For each test case, print ‘H’ space separated integers denoting the closest shop to the ith house.

Output for each test case will be printed in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= H <= 10^2
1 <= S <= 10^2
0 <= HOUSE[i], SHOP[i] <= 10^5

Where HOUSE[i], SHOP[i] represent the ith house and ith shop respectively.

Time Limit : 1 sec
Sample Input 1 :
2
3
2 4 2
4
5 1 2 3
3
5 10 17
5
1 5 20 11 16
Sample Output 1 :
2 3 2
5 11 16
Explanation For Sample Input 1 :
For first test :

The shop closest to house 2 is : 2
The shop closest to house 4 is : 3 ( 3 and 5 are at the same distance from 4. Since 3 is smaller than 5, therefore, we choose 3)
The shop closest to house 2 is : 2


For second test case the graph will be :

The shop closest to house 5 is : 5
The shop closest to house 10 is : 11 
The shop closest to house 17 is : 16
Hint

Think of traversing each shop for each house.

Approaches (2)
Brute Force

The basic idea is to traverse the ‘SHOP’ array for each house to find the shop nearest to a house.

 

Here is the algorithm :

 

  1. Create an array (say, ‘RES’) that will store the location of each shop and initialize it with a large number.
  2. Run a loop from 0 to ‘H’ (say, iterator ‘i’) to traverse the houses.
    • Create a variable (say, ‘DIST’) that will store the distance between house and shop and initialize it with a large number.
    • Run a loop from 0 to ‘S’ (say, iterator ‘j’) to traverse the shops.
      • Check if ‘ABS(HOUSE[i] - SHOP[j])’ is smaller than ‘DIST’
        • Update ‘DIST’ to ‘ABS(HOUSE[i] - SHOP[j])’.
        • Update ‘RES[i]’ to ‘SHOP[j]’.
      • Check if ‘ABS(HOUSE[i] - SHOP[j])’ is equal to ‘DIST’
        • Update ‘DIST’ to ‘ABS(HOUSE[i] - SHOP[j])’.
        • Update ‘RES[i]’ to a minimum of ‘RES[i]’ and ‘SHOP[j]’.
  3. Finally, return ‘RES’.
Time Complexity

O(H*S),  where ‘H’ is the number of houses and ‘S’ is the number of shops.

 

We traverse the ‘SHOP’ array for each house, i.e., for ‘H’ number of times. Therefore, the overall time complexity will be O(H*S).

Space Complexity

O(1)

 

We are not using any extra space. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Shops and Houses
Full screen
Console