Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2cc9015

Browse files
committed
Refactor find route solution
Use HashMap to redue time and space complexities.
1 parent2c1114a commit2cc9015

File tree

3 files changed

+146
-8
lines changed

3 files changed

+146
-8
lines changed

‎src/talabat/route/README.MD‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,3 +37,68 @@ Output: “Halifax, Montreal, Toronto, Chicago, Winnipeg, Seattle”
3737
1. Find the starting point
3838
2. Create route
3939

40+
##Refactor
41+
Let's review the input again
42+
[“USA”, “BRA”],[“JPN”, “CAI”],[“BRA”, “UAE”],[“UAE”, “JPN”]
43+
44+
The path is acyclic - there is one start and destination.
45+
46+
[“USA”, “BRA”],
47+
[“JPN”, “CAI”],
48+
[“BRA”, “UAE”],
49+
[“UAE”, “JPN”]
50+
51+
It looks like a key value pair.
52+
First solutions time complexity is O(n^2).
53+
Can storing the values in a hashmap improve
54+
time complexity? Or simplify our solution?
55+
56+
Let's store the input in the hashmap.
57+
58+
[“USA” => “BRA”],
59+
[“JPN” => “CAI”],
60+
[“BRA” => “UAE”],
61+
[“UAE” => “JPN”]
62+
63+
The basic solution remains the same.
64+
1. Find starting point
65+
2. Make route
66+
67+
###Find starting point
68+
The starting point is such a key that
69+
would not appear as a value.
70+
71+
We need to find the key such that it
72+
does not appear as the value of other
73+
pairs.
74+
75+
Hashmap has a functionality to check
76+
value exists.
77+
78+
**boolean containsValue(Object value)**
79+
80+
This method returns true if some value
81+
equals to the value exists within the map,
82+
else return false.
83+
84+
So we iterate through all the pairs until
85+
containsValue returns false.
86+
87+
###Make route
88+
We have the starting point as the key
89+
from one of the pairs.
90+
91+
Route is created such a way that value
92+
of a pair (destination) must be the key
93+
of other (source).
94+
95+
The final destination does not have another
96+
source.
97+
98+
So to create a route, first we need to
99+
find the key of another pair which is
100+
the value of the current key.
101+
102+
This is our simple solution to make a
103+
route.
104+

‎src/talabat/route/Solution.java‎

Lines changed: 64 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -4,28 +4,85 @@
44

55
classSolution {
66

7+
publicStringtrackRoute(String[][]itineraries) {
8+
Stringroute ="";
9+
intitineraryLen =itineraries.length;
10+
11+
if(itineraryLen ==1 ) {
12+
returnitineraries[0][0] +", " +itineraries[0][1];
13+
}
14+
15+
// 1. Transform to hashmap
16+
// 2. Find starting point
17+
// 3. Make route
18+
19+
20+
// Transform to hashmap
21+
HashMap<String,String>itinerariesMap =newHashMap<>();
22+
23+
for (inti=0;i<itineraryLen;i++) {
24+
itinerariesMap.put(itineraries[i][0],itineraries[i][1]);
25+
}
26+
27+
// Find starting point
28+
booleanfoundStart =false;
29+
Stringstart ="";
30+
for (inti=0;i <itineraryLen &&foundStart ==false;i++ ) {
31+
start =itineraries[i][0];
32+
33+
if ( !itinerariesMap.containsValue(start) )
34+
foundStart =true;
35+
}
36+
37+
// Make route
38+
Stringend =itinerariesMap.get(start);
39+
route +=start +", " +end;
40+
41+
// As we can take start and end at once,
42+
// find the number of iterations to make
43+
intloop =itineraryLen/2 +itineraryLen%2 -1;
44+
45+
for (inti=0;i<loop;i++ ) {
46+
start =itinerariesMap.get(end);
47+
end =itinerariesMap.get(start);
48+
route +=", " +start +", " +end;
49+
50+
}
51+
52+
// Last destination is missed when itineraries
53+
// length is even
54+
if (itineraryLen %2 ==0 )
55+
route +=", " +itinerariesMap.get(end);
56+
57+
returnroute;
58+
}
59+
}
60+
61+
classSolutionLegacy {
62+
763
publicStringtrackRoute(String[][]itineraries) {
864
intstartIndex =this.findStartingIndex(itineraries);
965
returnthis.createPath(startIndex,itineraries);
1066
}
1167

1268
publicintfindStartingIndex(String[][]itineraries) {
69+
intitineraryLen =itineraries.length;
1370
Stringstart ="";
1471
booleanstartFound =false;
1572
inti =0;
1673

17-
for (;i <itineraries.length &&startFound ==false;i++) {
74+
for (;i <itineraryLen &&startFound ==false;i++) {
1875
start =itineraries[i][0];
1976
intj =0;
2077

21-
for (;j <itineraries.length;j++) {
78+
for (;j <itineraryLen;j++) {
2279

2380
if (i !=j &&start ==itineraries[j][1]) {
24-
j =itineraries.length +1;
81+
j =itineraryLen +1;
2582
}
2683
}
2784

28-
if (j ==itineraries.length) {
85+
if (j ==itineraryLen) {
2986
startFound =true;
3087
}
3188
}
@@ -34,16 +91,17 @@ public int findStartingIndex(String[][] itineraries) {
3491
}
3592

3693
publicStringcreatePath(intstartIndex,String[][]itineraries) {
94+
intitineraryLen =itineraries.length;
3795
Stringroute =itineraries[startIndex][0] +", " +itineraries[startIndex][1];
3896
StringnextStart =itineraries[startIndex][1];
3997
HashMap<Integer,Boolean>traversedIndex =newHashMap<Integer,Boolean>();
4098
traversedIndex.put(startIndex,true);
4199

42-
for (intl =0;l <itineraries.length+1;l++) {
100+
for (intl =0;l <itineraryLen+1;l++) {
43101

44102
if (traversedIndex.containsKey(l) ==false ) {
45103
intm =0;
46-
for (;m <itineraries.length;m++) {
104+
for (;m <itineraryLen;m++) {
47105

48106
if (traversedIndex.containsKey(m) ==false
49107
&&nextStart ==itineraries[m][0]) {

‎src/talabat/route/SolutionTest.java‎

Lines changed: 17 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@ void shouldPassWithExample2() {
4545
{"Winnipeg","Seattle"}
4646
};
4747
Stringexpected ="Halifax, Montreal, Toronto, Chicago, Winnipeg, Seattle";
48-
Assertions.assertEquals(solution.trackRoute(itineraries),expected);
48+
Assertions.assertEquals(expected,solution.trackRoute(itineraries));
4949
}
5050

5151
@Test
@@ -60,7 +60,7 @@ void shouldPassWithExample2Suffled() {
6060
{"Winnipeg","Seattle"}
6161
};
6262
Stringexpected ="Halifax, Montreal, Toronto, Chicago, Winnipeg, Seattle";
63-
Assertions.assertEquals(solution.trackRoute(itineraries),expected);
63+
Assertions.assertEquals(expected,solution.trackRoute(itineraries));
6464
}
6565

6666
@Test
@@ -73,4 +73,19 @@ void shouldPassWithASingleInput() {
7373
Assertions.assertEquals(expected,solution.trackRoute(itineraries));
7474
}
7575

76+
@Test
77+
voidshouldPassWithExample2AddOne() {
78+
79+
Solutionsolution =newSolution();
80+
String[][]itineraries = {
81+
{"Montreal","Toronto"},
82+
{"Toronto","Chicago"},
83+
{"Chicago","Winnipeg"},
84+
{"Halifax","Montreal"},
85+
{"Winnipeg","Seattle"},
86+
{"Seattle","Boston"}
87+
};
88+
Stringexpected ="Halifax, Montreal, Toronto, Chicago, Winnipeg, Seattle, Boston";
89+
Assertions.assertEquals(expected,solution.trackRoute(itineraries));
90+
}
7691
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp