Skip to content

Commit 42a1556

Browse files
anitshanitsh
committed
Hackerrank contd..
Assertion fail hasFourCitiesTwoStationsAtFirstAndLast.
1 parent 60f44d7 commit 42a1556

File tree

1 file changed

+178
-41
lines changed

1 file changed

+178
-41
lines changed

‎src/hackerrank/FlatlandSpaceStations.java

Lines changed: 178 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -93,81 +93,218 @@
9393
* number of cities-1.
9494
*/
9595
public class FlatlandSpaceStations {
96-
public static int flatlandSpaceStations(int n, int[] c){
97-
int spaceStations = c.length;
96+
public static int flatlandSpaceStations(int noOfCities, int[] spaceStations){
97+
int noSpaceStations = spaceStations.length;
9898

99-
if ( n == 1 && spaceStations == 1 ) return 0;
100-
else if ( n == 2 && spaceStations == 1 ) return 1;
101-
else if ( n == 2 && spaceStations == 2 ) return 0;
102-
else if ( n == 3 && spaceStations == 2 ) return 1;
99+
if ( noOfCities == 1 && noSpaceStations == 1 ) return 0;
100+
else if ( noOfCities == 2 && noSpaceStations == 1 ) return 1;
101+
else if ( noOfCities == 2 && noSpaceStations == 2 ) return 0;
102+
else if ( noOfCities == 3 && noSpaceStations == 2 ) return 1;
103103

104-
if ( spaceStations == 1 ) {
105-
int firstSpaceStation = c[0];
104+
if ( noSpaceStations == 1 ) {
105+
int firstSpaceStation = spaceStations[0];
106106

107-
if ( n == 3 )
108-
return Math.max(firstSpaceStation, n-firstSpaceStation-1);
107+
if ( noOfCities == 3 )
108+
return Math.max(firstSpaceStation, noOfCities-firstSpaceStation-1);
109109

110-
else if ( firstSpaceStation == c.length-1 || c.length == 3 )
111-
return Math.max(firstSpaceStation-1, n-firstSpaceStation-1);
110+
else if ( firstSpaceStation == noSpaceStations-1 || noSpaceStations == 3 )
111+
return Math.max(firstSpaceStation-1, noOfCities-firstSpaceStation-1);
112112

113113
else
114-
return Math.max(Math.abs(firstSpaceStation-1), n-firstSpaceStation);
114+
return Math.max(Math.abs(firstSpaceStation-1), noOfCities-firstSpaceStation);
115115
}
116116

117-
Arrays.sort(c);
118117
int maxDistance = 0;
118+
Arrays.sort(spaceStations);
119+
int i=0;
119120

120-
int[] withLastCity = new int[spaceStations+1];
121-
withLastCity[spaceStations] = n-1;
122-
123-
System.arraycopy(c, 0, withLastCity, 0, spaceStations);
124-
// maximum distance between space stations
125-
126-
for(int i=0; i<spaceStations-1; i++){
127-
int distanceDiff = Math.abs(withLastCity[i]-withLastCity[i+1]);
121+
for(; i<noSpaceStations-1; i++){
122+
int distanceDiff = Math.abs(spaceStations[i]-spaceStations[i+1]);
128123

129124
if ( maxDistance < distanceDiff)
130125
maxDistance = distanceDiff;
131126
}
132127

128+
if (spaceStations[i] < noSpaceStations) {
129+
int distanceFromLast = noOfCities-1-spaceStations[i];
130+
131+
if (maxDistance < distanceFromLast)
132+
return distanceFromLast;
133+
}
134+
133135
return maxDistance;
134136
}
137+
135138
}
136139

137140

138141
class FlatlandSpaceStationsTest {
139142

143+
// @Test
144+
// @Disabled
145+
// void hasFourCitiesThreeStationsAtFirstSecondLast() {
146+
// int n=4, expected=1; // Distance from city four to city 2
147+
// int[] c={0,1,3};
148+
// Assertions.assertEquals(expected,
149+
// FlatlandSpaceStations.flatlandSpaceStations(n, c));
150+
//
151+
// /**
152+
// * The current implementation fails.
153+
// * Expected :1
154+
// * Actual :2
155+
// *
156+
// * The maximum distance being calculated
157+
// */
158+
// }
159+
140160
@Test
141-
@Disabled
142-
void hasFourCitiesThreeStationsAtFirstSecondLast() {
143-
int n=4, expected=1; // Distance from city four to city 2
144-
int[] c={0,1,3};
145-
Assertions.assertEquals(expected,
146-
FlatlandSpaceStations.flatlandSpaceStations(n, c));
161+
void hasFourCitiesTwoStationsAtFirstAndLast() {
162+
int noOfCities = 4, expectedMaxDistance=1; // Distance from city four to city 2
163+
int[] spaceStaions = {3, 0};
164+
int spaceStationsLen = spaceStaions.length;
165+
166+
Assertions.assertEquals(expectedMaxDistance,
167+
FlatlandSpaceStations.flatlandSpaceStations(noOfCities, spaceStaions));
147168

148169
/**
149-
* The current implementation fails.
170+
* Test fails
150171
* Expected :1
151-
* Actual :2
172+
* Actual :3
173+
*
174+
* int maxDistance = 0;
175+
* Arrays.sort(spaceStations);
176+
* int i=0;
177+
*
178+
* for(; i<noSpaceStations-1; i++){
179+
* int distanceDiff = Math.abs(spaceStations[i]-spaceStations[i+1]);
180+
*
181+
* if ( maxDistance < distanceDiff)
182+
* maxDistance = distanceDiff;
183+
* }
184+
*
185+
* if (spaceStations[i] < noSpaceStations) {
186+
* int distanceFromLast = noOfCities-1-spaceStations[i];
187+
*
188+
* if (maxDistance < distanceFromLast)
189+
* return distanceFromLast;
190+
* }
191+
*
192+
* return maxDistance;
193+
*
194+
* Logic fail
195+
* int distanceDiff = Math.abs(spaceStations[i]-spaceStations[i+1]);
196+
* distanceDiff is 3, spaceStation[1](3) - spaceStation[0](3)
197+
*
198+
* We failed to consider the cities and distance
199+
* from space stations to cities.
200+
*
201+
* The distance between two space stations should
202+
* be (spaceStation[1](3) - spaceStation[0](3))/2
203+
*
204+
* Let's just consider first and last to be a
205+
* special case.
152206
*
153-
* The maximum distance being calculated
154207
*/
208+
209+
210+
}
211+
212+
@Test
213+
void hasFourCitiesTwoStationsAtFirstAndThird() {
214+
int noOfCities = 4, expectedMaxDistance=2; // Distance from city four to city 2
215+
int[] spaceStaions = {2, 0};
216+
int spaceStationsLen = spaceStaions.length;
217+
218+
Assertions.assertEquals(expectedMaxDistance,
219+
FlatlandSpaceStations.flatlandSpaceStations(noOfCities, spaceStaions));
155220
}
156221

157222
@Test
158-
@Disabled
159223
void hasFourCitiesTwoStationsAtFirstAndSecond() {
160-
int n=4, expected=2; // Distance from city four to city 2
161-
int[] c={0,1};
162-
Assertions.assertEquals(expected,
163-
FlatlandSpaceStations.flatlandSpaceStations(n, c));
224+
int noOfCities = 4, expectedMaxDistance=2; // Distance from city four to city 2
225+
int[] spaceStaions = {1, 0};
226+
int spaceStationsLen = spaceStaions.length;
164227

228+
Assertions.assertEquals(expectedMaxDistance,
229+
FlatlandSpaceStations.flatlandSpaceStations(noOfCities, spaceStaions));
230+
231+
// int maxDistance = 0;
232+
// Arrays.sort(spaceStaions);
233+
//
234+
//// int[] withLastCity = new int[noOfCities+1];
235+
//// withLastCity[noOfCities] = noOfCities-1;
236+
//// System.arraycopy(spaceStaions, 0, withLastCity, 0, spaceStationsLen);
237+
//
238+
// for(int i=0; i<spaceStationsLen-1; i++){
239+
// int distanceDiff = Math.abs(spaceStaions[i]-spaceStaions[i+1]);
240+
//
241+
// if ( maxDistance < distanceDiff)
242+
// maxDistance = distanceDiff;
243+
// }
244+
//
245+
// maxDistance++;
246+
//
247+
// Assertions.assertEquals(expectedMaxDistance, maxDistance);
248+
249+
/**
250+
* Get the distance from the space station to city.
251+
*
252+
* 0 is a space station, check if the next city has
253+
* space station or not.
254+
*
255+
* If it has then start counting the cities from next.
256+
*
257+
* Pseudocode:
258+
* Sort space stations
259+
* Loop in cities
260+
* Check if space station or not
261+
* If not increase distance
262+
*
263+
*
264+
*/
265+
// Arrays.sort(spaceStaions);
266+
// int maxDistance=0;
267+
// for (int city=0; city<noOfCities; city++) {
268+
// int distance=0;
269+
//
270+
// for (int spaceStation=city+1; spaceStation < spaceStaions.length; spaceStation++){
271+
//
272+
// if ( city != spaceStaions[spaceStation] )
273+
// distance++;
274+
// else break;
275+
// }
276+
//
277+
// if (distance > maxDistance) maxDistance = distance;
278+
//
279+
// }
165280
/**
166-
* Get the maximum distance in space stations.
167-
* Here, 0 and 1 has 0 distance but there
168-
* 0 is the starting so no other cities and
169-
* there are cities after one as total cities
170-
* is 4.
281+
* This above idea becomes complicated.
282+
* We are trying to keep track of distance from
283+
* city to space station.
284+
*
285+
* for (int spaceStation=city+1;
286+
* if ( city != spaceStaions[spaceStation] )
287+
*
288+
* This logic fails.
289+
*
290+
* Loop space stations.
291+
* Get the distance from the last city.
292+
*
293+
* Original/First logic implemented which failed
294+
* for the test case.
295+
*
296+
* The idea is to get the distance from max index
297+
* to the space station. Looks a bit like Sub-Array
298+
* Sum kind of problem.
299+
*
300+
* Factored in last city which is not a space station.
301+
*
302+
* The solution should be straight forward.
303+
* Get the distance from city to space station or
304+
* space station to city. The only problem being
305+
* created is solving by considering which comes
306+
* first.
307+
*
171308
*/
172309
}
173310

0 commit comments

Comments
 (0)