Skip to content

Commit aebacda

Browse files
EdwardTangEdwardTang
authored
solution without supporting numbers (#3)
* solution without supporting numbers * vmware mock interview questions solution * vmware-phone-2020-02 Solved find duplicates in file system * code clean up * add comments on problems
1 parent 234d565 commit aebacda

File tree

7 files changed

+430
-1
lines changed

7 files changed

+430
-1
lines changed

‎src/main/java/com/company/vmware/decodestr/DecodeAsciiString.java

+89
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
package com.company.vmware.decodestr;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* We encode a string, s, by performing the following sequence of actions:
8+
*
9+
* <p>Replace each character with its ASCII value representation. Reverse the string. For example,
10+
* the table below shows the conversion from the string "Go VMWare" to the ASCII string
11+
* "711113286778797114101":
12+
*
13+
* <p>Character G o V M W a r e ASCII Value 71 111 32 86 77 87 97 114 101
14+
*
15+
* <p>We then reverse the ASCII string to get the encoded string 101411797877682311117. For
16+
* reference, the characters in s are ASCII characters within the range 10 - 126 which include
17+
* special characters. The function must decode the encoded string and return the list of ways in
18+
* which s can be decoded.
19+
*
20+
* <p>// encoded - A reversed ASCII string denoting an encoded string s static Collection<String>
21+
* decode(String encoded) {
22+
*
23+
* <p>return Collection<String> }
24+
*/
25+
public class DecodeAsciiString {
26+
public static List decode(String encoded) {
27+
List<String> ans = new ArrayList<>();
28+
29+
StringBuilder input1 = new StringBuilder();
30+
31+
// append a string into StringBuilder input1
32+
input1.append(encoded);
33+
34+
// reverse StringBuilder input1
35+
input1 = input1.reverse();
36+
37+
// print reversed String
38+
// System.out.println(input1);
39+
40+
char[] encodedArr = encoded.toCharArray();
41+
42+
decodeHelper(0, encodedArr.length, new StringBuilder(), ans, input1.toString());
43+
44+
for (String s : ans) {
45+
System.out.println(s);
46+
}
47+
return ans;
48+
}
49+
50+
public static void decodeHelper(
51+
int start, int length, StringBuilder sb, List<String> ans, String encoded) {
52+
53+
if (start >= length - 1) {
54+
ans.add(sb.toString());
55+
return;
56+
}
57+
List<String> splitList = new ArrayList<>();
58+
if (start + 2 <= length) {
59+
// get the first 2 chars of the string
60+
splitList.add(encoded.substring(start, start + 2));
61+
}
62+
if (start + 3 <= length) {
63+
// get the first 3 chars of the string
64+
splitList.add(encoded.substring(start, start + 3));
65+
}
66+
// For each substring in splitList, check if it is valid ASCII value,
67+
for (String each : splitList) {
68+
if (isValid(each)) {
69+
// System.out.println(each);
70+
sb.append((char) (Integer.parseInt(each)));
71+
decodeHelper(start + each.length(), length, sb, ans, encoded);
72+
sb.setLength(sb.length() - 1); // back tracking
73+
}
74+
}
75+
}
76+
77+
public static boolean isValid(String s) {
78+
int val = Integer.parseInt(s);
79+
return (val >= 10 && val <= 126);
80+
}
81+
82+
public static void main(String[] args) {
83+
System.out.println("Hello World!");
84+
// String ss = "0018014111117811180180110127";
85+
// decode(ss);
86+
// decode("64101301011794019923111611236112117900179231116112312161150180150189792310140161123511501231019901110130150180180110161101137");
87+
decode("101411797877682311117");
88+
}
89+
}

‎src/main/java/com/company/vmware/finddup/FindDupInFileSystem.java

+47
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.company.vmware.finddup;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashMap;
5+
import java.util.List;
6+
import java.util.Map;
7+
8+
/** Leetcode 609. Find Duplicate File in System */
9+
class FindDupInFileSystem {
10+
// High level:
11+
// 1. split the string into: pair of <content : dir + fileName>
12+
// 2. use content as key, group all the pair into a hashmap: Map<content, List <dir + fileName>>
13+
// 3. add the values of above hash map entries to a List<List<String>> result
14+
public List<List<String>> findDuplicate(String[] paths) {
15+
List<List<String>> result = new ArrayList<>();
16+
if (paths == null | paths.length == 0) {
17+
return result;
18+
}
19+
Map<String, List<String>> map = new HashMap<>();
20+
21+
for (String folder : paths) {
22+
String[] folderSubstr = folder.split(" ");
23+
mapAndGroup(map, folderSubstr);
24+
}
25+
map.entrySet().stream()
26+
.filter(e -> (e.getValue() != null && e.getValue().size() > 1))
27+
.forEach(
28+
e -> {
29+
result.add(e.getValue());
30+
});
31+
return result;
32+
}
33+
34+
private void mapAndGroup(Map<String, List<String>> map, String[] s) {
35+
String dir = s[0];
36+
for (int i = 1; i < s.length; i++) {
37+
String[] metaData = s[i].split("\\(");
38+
String fileName = metaData[0];
39+
String content = metaData[1].substring(0, metaData[1].length() - 1);
40+
String file = dir + "/" + fileName;
41+
if (!map.containsKey(content)) {
42+
map.put(content, new ArrayList<>());
43+
}
44+
map.get(content).add(file);
45+
}
46+
}
47+
}

‎src/main/java/com/company/vmware/hangman/HangmanSolver.java

+75
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package com.company.vmware.hangman;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
/**
8+
* Design data structure for HangMan solver game. We are given array of lexocographically sorted
9+
* strings 'dict[]' as input and a pattern 'puzzle', return list of all the words matching pattern
10+
* 'puzzle'. 'puzzle' is a pattern containing underscore character "_".
11+
*
12+
* <p>class HangmanSolver {
13+
*
14+
* <p>public HangmanSolver(String[] dict) { // todo }
15+
*
16+
* <p>public List<String> solve(String puzzle) { // todo } } Here solve method could be called
17+
* multiple times however HangManSolver() will be called only once. So the problem is to process
18+
* strings in the input array and store in a data structure efficient for searching strings matching
19+
* given pattern.
20+
*
21+
* <p>Example:
22+
*
23+
* <p>HangmanSolver solver = new HangmanSolver(["ant", "feet", "meet", "zebra"]);
24+
* solver.solve("_e_t"); // ["feet", "meet"]
25+
*/
26+
public class HangmanSolver {
27+
28+
private HangmanTrieNode root;
29+
30+
public HangmanSolver(List<String> dict) {
31+
root = new HangmanTrieNode(' ');
32+
for (String word : dict) {
33+
HangmanTrieNode ref = root;
34+
for (char c : word.toCharArray()) {
35+
ref.next[c - 'a'] = new HangmanTrieNode(c);
36+
ref = ref.next[c - 'a'];
37+
}
38+
ref.word = word;
39+
}
40+
}
41+
42+
public List<String> solve(String puzzle) {
43+
List<String> result = new ArrayList<>();
44+
dfs(root, result, puzzle, 0);
45+
return result;
46+
}
47+
48+
private void dfs(HangmanTrieNode root, List<String> result, String puzzle, int cur) {
49+
// base case: no such char root in the dictionary
50+
if (root == null || cur > puzzle.length()) {
51+
return;
52+
}
53+
if (cur == puzzle.length()) {
54+
if (root.word != null) {
55+
result.add(root.word);
56+
}
57+
return;
58+
}
59+
60+
char pChar = puzzle.charAt(cur);
61+
if (pChar == '_') {
62+
for (HangmanTrieNode next : root.next) {
63+
dfs(next, result, puzzle, cur + 1);
64+
}
65+
} else {
66+
dfs(root.next[pChar - 'a'], result, puzzle, cur + 1);
67+
}
68+
}
69+
70+
public static void main(String[] args) {
71+
List<String> dict1 = Arrays.asList(new String[] {"ant", "feet", "meet", "zebra"});
72+
HangmanSolver solver1 = new HangmanSolver(dict1);
73+
System.out.println(solver1.solve("_e_t").toString());
74+
}
75+
}

‎src/main/java/com/company/vmware/hangman/HangmanTrieNode.java

+12
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
package com.company.vmware.hangman;
2+
3+
public class HangmanTrieNode {
4+
char val;
5+
HangmanTrieNode[] next;
6+
String word;
7+
8+
public HangmanTrieNode(char val) {
9+
this.val = val;
10+
this.next = new HangmanTrieNode[26];
11+
}
12+
}

‎src/main/java/com/company/vmware/json/JsonValidator.java

+160
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
package com.company.vmware.json;
2+
3+
import static org.junit.Assert.assertFalse;
4+
import static org.junit.Assert.assertTrue;
5+
6+
import java.util.ArrayDeque;
7+
import java.util.Deque;
8+
9+
/**
10+
* Validate a json and return true or false.
11+
*/
12+
public class JsonValidator {
13+
14+
public static void main(String[] args) {
15+
String test1 = "{}"; // true
16+
String test2 = "{"; // false
17+
String test3 = "{\"x\" : { \"y\" : \"z\"}}"; // true
18+
String test4 =
19+
"{ \n"
20+
+ " \"glossary\":{ \n"
21+
+ " \"title\":\"exampleglossary\",\n"
22+
+ " \"GlossDiv\":{ \n"
23+
+ " \"title\":\"S\",\n"
24+
+ " \"GlossList\":{ \n"
25+
+ " \"GlossEntry\":{ \n"
26+
+ " \"ID\":\"SGML\",\n"
27+
+ " \"SortAs\":\"SGML\",\n"
28+
+ " \"GlossTerm\":\"StandardGeneralizedMarkupLanguage\",\n"
29+
+ " \"Acronym\":\"SGML\",\n"
30+
+ " \"Abbrev\":\"ISO8879:1986\",\n"
31+
+ " \"GlossDef\":{ \n"
32+
+ " \"para\":\"Ameta-markuplanguage,usedtocreatemarkuplanguagessuchasDocBook.\",\n"
33+
+ " \"GlossSeeAlso\":[ \n"
34+
+ " \"GML\",\n"
35+
+ " \"XML\"\n"
36+
+ " ]\n"
37+
+ " },\n"
38+
+ " \"GlossSee\":\"markup\"\n"
39+
+ " }\n"
40+
+ " }\n"
41+
+ " }\n"
42+
+ " }\n"
43+
+ "}";
44+
String test5 = "[{\n" + "\t\"\": \"\"\n" + "}]";
45+
String test6 = "[\n" + "\t[]";
46+
// assertTrue(isValid(test1));
47+
// assertFalse(isValid(test2));
48+
// assertTrue(isValid(test3));
49+
assertTrue(isValid(test4));
50+
assertTrue(isValid(test5));
51+
assertFalse(isValid(test6));
52+
}
53+
54+
public static boolean isValid(String s) {
55+
Deque<Character> stack = new ArrayDeque<>();
56+
char[] chars = s.toCharArray();
57+
for (int i = 0; i < chars.length; i++) {
58+
// TODO handle numeric values in json
59+
60+
// if(!stack.isEmpty() && stack.peekLast() == ':') {
61+
// if(chars[i] == '"' || chars[i] == '{' || chars[i] == '[' ||
62+
// Character.isDigit(chars[i])) {
63+
// if(chars[i] == '"' || chars[i] == '{' || chars[i] == '['){
64+
// stack.addLast(chars[i]);
65+
// } else if (Character.isDigit(chars[i])) {
66+
// if(chars[i] == '0'){
67+
// stack.addLast(chars[i]);
68+
// }
69+
// }
70+
// } else {
71+
// // {"x" : a }
72+
// System.out.println("processed: " + s.substring(0, i));
73+
// System.out.println("chars[i]: " + chars[i]);
74+
// return false;
75+
// }
76+
// } else if(!stack.isEmpty() && stack.peekLast() == '0') {
77+
// if(chars[i] != '.') {
78+
// System.out.println("processed: " + s.substring(0, i));
79+
// System.out.println("chars[i]: " + chars[i]);
80+
// return false;
81+
// } else {
82+
// stack.addLast(chars[i]);
83+
// }
84+
// } else if(!stack.isEmpty() && stack.peekLast() == '.') {
85+
// if(!Character.isDigit(chars[i])) {
86+
// return false;
87+
// }
88+
// } else if(isFocusSymbol(chars[i])) {
89+
90+
// Handle non-numeric values
91+
if (isFocusSymbol(chars[i])) {
92+
if (stack.isEmpty()) {
93+
stack.addLast(chars[i]);
94+
} else {
95+
// stack is not empty
96+
char top = stack.peekLast();
97+
if (!isValidTop(top)) {
98+
System.out.println("processed: " + s.substring(0, i));
99+
System.out.println("chars[i]: " + chars[i]);
100+
return false;
101+
} else {
102+
// top can be , { [ " :
103+
if (top == '{') {
104+
if (chars[i] == ']') {
105+
System.out.println("processed: " + s.substring(0, i));
106+
System.out.println("chars[i]: " + chars[i]);
107+
return false;
108+
} else if (chars[i] == '}') {
109+
stack.removeLast();
110+
} else {
111+
stack.addLast(chars[i]);
112+
}
113+
} else if (top == '[') {
114+
if (chars[i] == ':' || chars[i] == '}') {
115+
System.out.println("processed: " + s.substring(0, i));
116+
System.out.println("chars[i]: " + chars[i]);
117+
return false;
118+
} else if (chars[i] == ']') {
119+
stack.removeLast();
120+
} else {
121+
stack.addLast(chars[i]);
122+
}
123+
} else if (top == ':' || top == ',') {
124+
if (chars[i] == ']' || chars[i] == '}' || chars[i] == ',' || chars[i] == ':') {
125+
System.out.println("processed: " + s.substring(0, i));
126+
System.out.println("chars[i]: " + chars[i]);
127+
return false;
128+
} else {
129+
// if (chars[i] == '{' || chars[i] == '[' || chars[i] == '"')
130+
stack.removeLast();
131+
stack.addLast(chars[i]);
132+
}
133+
} else {
134+
// if (top == '"')
135+
if (chars[i] == '"') {
136+
stack.removeLast();
137+
} else {
138+
// skip any character inside the quotation mark
139+
continue;
140+
}
141+
}
142+
}
143+
}
144+
} else {
145+
// skip literals
146+
continue;
147+
}
148+
}
149+
return stack.isEmpty();
150+
}
151+
152+
private static boolean isFocusSymbol(char ch) {
153+
return (ch == '{' || ch == '}' || ch == '[' || ch == ']' || ch == ':' || ch == ','
154+
|| ch == '"');
155+
}
156+
157+
private static boolean isValidTop(char ch) {
158+
return (ch == '{' || ch == '[' || ch == ':' || ch == ',' || ch == '"');
159+
}
160+
}

0 commit comments

Comments
 (0)