-
Notifications
You must be signed in to change notification settings - Fork 11
/
Decode string
113 lines (84 loc) · 2.92 KB
/
Decode string
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
Airbnb: Decode string
Often, we want to encode raw IDs in our database by hiding them behind some
2-way decodeable hash. So, a URL which would have at one time been:
https://www.airbnb.com/rooms/848662
becomes
https://www.airbnb.com/rooms/kljJJ324hjkS_
We decode the ID kljJJ324hjkS_ to 848662 on our backend and serve the
relevant content. at some point, we start getting 404 errors from clients
requesting a certain URL of the form
https://www.airbnb.com/rooms/kljjj324hjks_
This can happen if certain clients, email services, or url shorteners "
sanitize" the url. Unfortunately, this change breaks decoding and the
resource cannot be found.
To assess how big of a deal this is, we may want to recover the IDs of the
targets that were 404ing.
Your task:
Given a method decode(testEncStr) which will return the decoded int id if
testEncStr is decodeable or will throw an exception or return null (
depending on the language) if not, implement a new method decodeFind(String
badEncStr) which takes a string and returns the decoded int id.
Solution:
import java.io.*;
import java.util.*;
public class Solution {
public Integer decodeFind(String badEncString) {
if (badEncString == null || badEncString.length() == 0) {
return -1;
}
StringBuffer sb = new StringBuffer();
return decodeFindHelper(0, sb, badEncString);
}
private Integer decodeFindHelper(int start, StringBuffer curr, String badEncString) {
if (start == badEncString.length()) {
String testEncStr = curr.toString();
Integer result = decode(testEncStr);
if (result != null) {
return result;
} else {
return null;
}
}
char c = badEncString.charAt(start);
if (!Character.isLetter(c)) {
curr.append(c);
Integer result = decodeFindHelper(start + 1, curr, badEncString);
if (result != null) {
return result;
}
curr.deleteCharAt(curr.length() - 1);
} else {
// To lower case
char lower = Character.toLowerCase(c);
curr.append(lower);
Integer result = decodeFindHelper(start + 1, curr, badEncString);
if (result != null) {
return result;
}
curr.deleteCharAt(curr.length() - 1);
// To upper case
char upper = Character.toUpperCase(c);
curr.append(upper);
result = decodeFindHelper(start + 1, curr, badEncString);
if (result != null) {
return result;
}
curr.deleteCharAt(curr.length() - 1);
}
return null;
}
public Integer decode(String testEncStr) {
String truth = "kljJJ324hijkS_";
if (testEncStr.equals(truth)) {
return 848662;
} else {
return null;
}
}
public static void main(String[] args) {
Solution solution = new Solution();
String badEncStr = "kLjjj324hijks_";
Integer result = solution.decodeFind(badEncStr);
System.out.println(result);
}
}