Find Straight City | Goldman Sachs

Question :

There are a number of cities arranged on a plane which has been divided up like an ordinary Cartesian plane. Each is located at an integral (x, y) intersection.
City names and locations are given in the form of three arrays: c, x, and y, aligned by index to provide the city name (c[i]), and its coordinates, (x[i], y[i]).

For each city queried, determine the name of the nearest other city that shares either an x or a y coordinate with the queried city. If there are no other cities sharing an x or y coordinate, return NONE. If two cities have the same distance to the queried city, q[i], we consider the one with philological smaller name as the closer one.

The distance here denotes the euclidean distance on the plane. For example, there are n = 3 cities, c =

[c1, c2, c3] at locations x = [ 1, 2, 3] and y = [3, 2, 3], so points (1,3), (2,2) and (3,3). Our queries are q = [c1, c2, c3]. The nearest city to c1 is c3 which shares a y value. City c2 does not have a nearest city as none shares an x or y with c2, so this query would return NONE. A query of c3 would return c1. The return array after all queries is [c3, NONE, c1].

Function Description :

Complete the function closestStraightCity in the editor below. The function must return an array of m strings, where the i element of this array denotes the answer to the i query.

 closestStraightCity has the following parameter(s):

c 

,...c[n-1]]: an array of strings
x[x[0],...x[n-1]]: an array of integers
y[y[0],...y[n-1]]: an array of integers
q[q[0],...q[m-1]]: an array of strings

Constraints :

  • 1 ≤ x[i], y[i] ≤ 10
  • 1 ≤ | q[i] |, | c[i] | ≤ 10
  • Each character of all c[i] and q[i] ∈ ASCII[a-z]
  • All city name values, c[i], are unique
  • All cities have unique coordinates
Test Link : HackerRank

Program :

#include<iostream>
#include<string>
#include<cstdlib>
#include<vector>
using namespace std;
vector<string> closestStraightCity(vector<string> c, vector<int> x, vector<int> y, vector<string> q)
{
    int xMin,yMin,i,j,k,index;
    for(i=0;i<q.size();i++)
    {
        xMin=INT_MAX;
        yMin=INT_MAX;
        index=-1;
        for(j=0;j<c.size();j++)
            if(c[j]==q[i])
                break;
        for(k=0;k<c.size();k++)
        {
            if(j==k)
                continue;
            if(x[j]==x[k])
            {
               int d=abs((y[j]-y[k]));
               if(d<yMin)
               {
                 yMin=d;
                 index=k;
               }
            }
            else if(y[j]==y[k])
             {
               int d=abs((x[j]-x[k]));
               if(d<xMin)
               {
                 xMin=d;
                 index=k;
               }
             }
        }
        if(index==-1)q[i]="NONE";
        else q[i]=c[index];
    }
    return q;
}
int main()
{
    vector<string> c;
    string city;
    int n,a;
    cout<<"Total No of Cities : ";
    cin>>n;//Get Total No of cities
    cout<<"Enter City names below...\n ";
    for(int i=0;i<n;i++)
    {
        cin>>city;//Get City Nsme
        c.push_back(city);// Store City Names into vector c;
    }
    vector<int> x;
    cout<<"\nTotal X Coords : ";
    cin>>n;//Get Total no of X Coordinates
    cout<<"Enter X Coords Below ...\n";
    for(int i=0;i<n;i++)
    {
        cin>>a;//Get X coordinate of city
        x.push_back(a);// Store X coordinate into vector x;
    }
    vector<int> y;
    cout<<"\nTotal Y Coords : ";
    cin>>n;//Get Total no of Y Coordinates
    cout<<"Enter Y Coords Below ...\n";
    for(int i=0;i<n;i++)
    {
        cin>>a;//Get Y coordinate of city
        y.push_back(a);// Store Y coordinate into vector x;
    }
    vector<string> q;//For Query City
    cout<<"\nTotal Query Cities : ";
    cin>>n;//Get Total No of Query cities
    cout<<"Enter Query City Names Below... \n";
    for(int i=0;i<n;i++)
    {
        cin>>city;//Get Query City Nsme
        q.push_back(city);// Store Query City Names into vector q;
    }
    vector<string> res=closestStraightCity(c,x,y,q);
    cout<<"\nOUTPUT\n";
    for(int i=0;i<res.size();i++)
        cout<<res[i]<<"\n";
    return 0;
}

Input 1 :

Output 1 :

Input 2 :

Output 2 :

 

 

Hari Prasath R

You know who I am :)