Skip to content

Commit 234d565

Browse files
EdwardTangEdwardTang
authored
snapchat vmware (#2)
* snapchat vmware * fix formatting
1 parent 42e8582 commit 234d565

File tree

4 files changed

+299
-41
lines changed

4 files changed

+299
-41
lines changed

‎src/main/java/com/company/samsara/box/Box.java

+29-41
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11
package com.company.samsara.box;
22

3-
43
import java.util.HashMap;
54
import java.util.Map;
65
import java.util.PriorityQueue;
@@ -28,46 +27,62 @@ public class Box {
2827
private Map<Integer, Valuable> contentMap;
2928

3029
public Box(int sizeBar) {
31-
if(sizeBar <= 0) {
32-
throw new IllegalArgumentException("Size bar of a box cannot be smaller thant or equal to zero");
30+
if (sizeBar <= 0) {
31+
throw new IllegalArgumentException(
32+
"Size bar of a box cannot be smaller thant or equal to zero");
3333
}
3434
this.sizeBar = sizeBar;
3535
this.currentSize = 0;
36-
maxValuables = new PriorityQueue<>((a,b)->(b.size - a.size));
36+
maxValuables = new PriorityQueue<>((a, b) -> (b.size - a.size));
3737
contentMap = new HashMap<>();
3838
}
3939

4040
public void addValuable(Valuable valuable) {
41-
if(valuable == null) {
41+
if (valuable == null) {
4242
throw new IllegalArgumentException("added valuable cannot be null");
4343
}
4444

45-
if(contentMap.containsKey(valuable.id)) {
45+
if (contentMap.containsKey(valuable.id)) {
4646
throw new IllegalArgumentException("valuable is already in the box");
4747
}
4848

49-
if(currentSize + valuable.size > sizeBar) {
50-
throw new IllegalArgumentException(String.format("adding this valuable with size %d will exceeds the box' size bar %d", valuable.size, sizeBar));
49+
if (currentSize + valuable.size > sizeBar) {
50+
throw new IllegalArgumentException(
51+
String.format(
52+
"adding this valuable with size %d will exceeds the box' size bar %d",
53+
valuable.size, sizeBar));
5154
}
5255

5356
contentMap.put(valuable.id, valuable);
5457
maxValuables.offer(valuable);
5558
currentSize += valuable.size;
56-
System.out.println("Added " + valuable.toString() + ", current box size: " + currentSize + " maxValueSize: " + getMaxValuableSize());
59+
System.out.println(
60+
"Added "
61+
+ valuable.toString()
62+
+ ", current box size: "
63+
+ currentSize
64+
+ " maxValueSize: "
65+
+ getMaxValuableSize());
5766
}
5867

5968
public void removeValuable(int id) {
60-
if(!contentMap.containsKey(id)) {
69+
if (!contentMap.containsKey(id)) {
6170
throw new IllegalArgumentException("valuable is no in the box");
6271
}
6372
Valuable removed = contentMap.remove(id);
6473
maxValuables.remove(removed);
6574
currentSize -= removed.size;
66-
System.out.println("Removed " + removed.toString() + ", current box size: " + currentSize + " maxValueSize: " + getMaxValuableSize());
75+
System.out.println(
76+
"Removed "
77+
+ removed.toString()
78+
+ ", current box size: "
79+
+ currentSize
80+
+ " maxValueSize: "
81+
+ getMaxValuableSize());
6782
}
6883

6984
public int getMaxValuableSize() {
70-
if(maxValuables.isEmpty()) {
85+
if (maxValuables.isEmpty()) {
7186
return 0;
7287
} else {
7388
return maxValuables.peek().size;
@@ -84,10 +99,10 @@ public static void main(String[] args) {
8499
Valuable v9 = new Valuable(6, "valuable 9", 9);
85100

86101
Box aBox = new Box(30);
87-
try{
102+
try {
88103
aBox.addValuable(v1);
89104
aBox.addValuable(v10);
90-
// aBox.addValuable(v20);
105+
// aBox.addValuable(v20);
91106
aBox.removeValuable(v10.id);
92107
aBox.addValuable(v29);
93108
aBox.removeValuable(v29.id);
@@ -97,33 +112,6 @@ public static void main(String[] args) {
97112
} catch (IllegalArgumentException e) {
98113
System.out.println(e.getMessage());
99114
}
100-
101115
}
102-
103116
}
104117

105-
class Valuable {
106-
int id;
107-
String name;
108-
int size;
109-
110-
public Valuable(int id, String name, int size) {
111-
if(StringUtils.isBlank(name)) {
112-
throw new IllegalArgumentException("Valuabe cannot be blank");
113-
}
114-
if(size <= 0) {
115-
throw new IllegalArgumentException("Valuabe size cannot be smaller than or equal to 0");
116-
}
117-
this.id = id;
118-
this.name = name;
119-
this.size = size;
120-
}
121-
122-
@Override
123-
public String toString() {
124-
return "[id = " + id + ", name = " + name + ", size = " + size + "]";
125-
}
126-
127-
}
128-
129-

‎src/main/java/com/company/samsara/box/Valuable.java

+26
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.company.samsara.box;
2+
3+
import org.apache.commons.lang3.StringUtils;
4+
5+
class Valuable {
6+
int id;
7+
String name;
8+
int size;
9+
10+
public Valuable(int id, String name, int size) {
11+
if (StringUtils.isBlank(name)) {
12+
throw new IllegalArgumentException("Valuabe cannot be blank");
13+
}
14+
if (size <= 0) {
15+
throw new IllegalArgumentException("Valuabe size cannot be smaller than or equal to 0");
16+
}
17+
this.id = id;
18+
this.name = name;
19+
this.size = size;
20+
}
21+
22+
@Override
23+
public String toString() {
24+
return "[id = " + id + ", name = " + name + ", size = " + size + "]";
25+
}
26+
}

‎src/main/java/com/company/snapchat/phone/tree/BinaryTreePostOrderIterator.java

+74
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package com.company.snapchat.phone.tree;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
5+
import java.util.ArrayDeque;
6+
import java.util.ArrayList;
7+
import java.util.Arrays;
8+
import java.util.Deque;
9+
import java.util.LinkedList;
10+
import java.util.List;
11+
12+
public class BinaryTreePostOrderIterator {
13+
14+
private Deque<TreeNode> stack = new ArrayDeque<>();
15+
private LinkedList<TreeNode> out = new LinkedList<>();
16+
17+
// 1. Post-order is the reverse order of pre-order with traversing right substree before traversing
18+
// left subtree:
19+
// pre-order : root -> left-subtree -> right-subtree
20+
// pre-order-visit-right-first: root -> right-subtree -> left-subtree
21+
// reversed-(pre-order-visit-right-first): left-subtree -> right-subtree -> root
22+
// post-order: left-subtree -> right-subtree -> root
23+
//
24+
// 2. And since stack is LIFO, we should push left substree to stack, then right substree.
25+
// 3. So for next step, the top element of stack is right subtree.
26+
// 4. And we need to also reverse the order of the elements poped from stack.
27+
// 5. So we use another linkedList based stack to maintain the reverse order
28+
public BinaryTreePostOrderIterator(TreeNode root) {
29+
stack.addFirst(root);
30+
while (!stack.isEmpty()) {
31+
TreeNode node = stack.removeFirst();
32+
out.addFirst(node);
33+
if (node.left != null) {
34+
stack.addFirst(node.left);
35+
}
36+
if (node.right != null) {
37+
stack.addFirst(node.right);
38+
}
39+
}
40+
}
41+
42+
public boolean hasNext() {
43+
return !out.isEmpty();
44+
}
45+
46+
public TreeNode next() {
47+
if (!hasNext()) {
48+
return null;
49+
}
50+
return out.removeFirst();
51+
}
52+
53+
public static void main(String[] args) {
54+
55+
List<Integer> list = Arrays.asList(new Integer[] {5, 3, 6, 2, 4, null, null, 1});
56+
/**
57+
* the tree for [5, 3, 6, 2, 4, null, null, 1], i.e. looks like the following:
58+
5
59+
/ \
60+
3 6
61+
/ \ / \
62+
2 4 # #
63+
/
64+
1
65+
*/
66+
TreeNode root = TreeUtils.constructBinaryTree(list);
67+
List<Integer> result = new ArrayList<>();
68+
BinaryTreePostOrderIterator iterator = new BinaryTreePostOrderIterator(root);
69+
while (iterator.hasNext()) {
70+
result.add(iterator.next().val);
71+
}
72+
System.out.println(result.toString()); // [1, 2, 4, 3, 6, 5]
73+
}
74+
}

0 commit comments

Comments
 (0)