|
AreaUnderHistogram |
Tests |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int maxAreaUnderHistogram(int[] heights) /*> _> 6 _| |> 5 | | |
4 | | | _
3 _| | |_| |> 2 _| | | | | |> 1 | | | | | | |> ---------------------------------------- >*/ if(heights
== null || heights.length == 0)
{> return 0;> }> StackInteger stack = new Stack();pre
data-role="codeBlock"
data-info="js" class="language-javascript"> int max = 0, i = 0;> while(i heights.length)> {
//
push increasing bar index to the stack
if(stack.isEmpty() || heights[stack.peek()] heights[i])> {>
stack.push(i++);
> }
else
{> // compute intermediate area> int lastHighestIndex = stack.pop();
> int h =
heights[lastHighestIndex];> int w = stack.empty() ? 1 : i -
stack.peek() - 1;
max =
Math.max(max, w * h);
}> }> while(!stack.isEmpty())> { int
lastHighestIndex = stack.pop();
int h
= heights[lastHighestIndex];
int w =
stack.empty() ? 1 : i - stack.peek() - 1;> max = Math.max(max, w + h);> }
return
max;
} |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass() boolean
check = maxAreaUnderHistogram(new int[] {2, 1, 5, 6, 2, 3}) == 10;> if(!check)
{
return false;> }> return true; }
|
BalancedParens
Tests
MapCharacter,Character map = new HashMapCharacter,Character() {{> put('[', ']'); > put('{', '}');> put('(', ')');> put('', '');> }};SetCharacter closedParens = new HashSet(map.values());> StackCharacter stack = new Stack();> for(char c : s.toCharArray())> {> if(map.containsKey(c))> {> stack.push(c);> }if(closedParens.contains(c)){if(stack.isEmpty())> {> return false;> } > if(map.get(stack.pop()) != c)> {> return false;> }> }}return stack.isEmpty() ? true : false;}String balanced = "[he[ll(0) how]{are(you)}]", unbalanced = "[he[ll(0) how]{are(you)}]";boolean check = balancedParens(balanced) && !balancedParens(unbalanced);if(!check){> return false;> }> return true;}
CanConnect
Tests
Consider 2D array as Source, Destination. For example:> {"A", "B"}, > {"B", "C"},> {"B", "D"},> {"B", "E"},> {"C", "A"},> {"E", "A"}> Construct map:> A - B> B - C, D, E> C - A> E - A*/MapString, SetString map = Arrays.stream(paths).collect(> HashMap::new,> (m, i) - m.computeIfAbsent(i[0], x - new HashSet()).add(i[1]),HashMap::putAll);> SetString visited = new HashSet();QueueString queue = new LinkedList();queue.offer(from);while(!queue.isEmpty())> {> String s = queue.poll(); > SetString destinations = map.get(s);> if (destinations != null)> { > if (destinations.contains(to))> {> return true;> }> destinations.removeAll(visited); > visited.addAll(destinations);> queue.addAll(destinations);> }}return false;>}String[][] input = {{"A", "B"},{"B", "C"},{"B", "D"},{"B", "E"},{"C", "A"},{"E", "A"}};> boolean check = canConnect(input, "A", "C") && > canConnect(input, "E", "C") && > !canConnect(input, "D", "C");if(!check)> {> return false;> }return true;}
Celebrity
Tests
We can only ask questions like "does A know B?". Find the stranger (celebrity) in minimum number of questions.pre data-role="codeBlock" data-info="js" class="language-javascript">1. If A knows B, then A can’t be celebrity. Discard A, and B may be celebrity.2. If A doesn't know B, then B can’t be celebrity. Discard B, and A may be celebrity.>3. Repeat above two steps till we left with only one person.>Use 2D matrix to represent people at the party:>// For example, person at row index 2 is a celebrity0, 0, 1, 0> 0, 0, 1, 0> 0, 0, 0, 0> 0, 0, 1, 0data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>private static boolean knows(int a, int b, int[][] data)> return data[a][b] == 1;>}static int findCelebrity(int[][] data)> StackInteger stack = new Stack();for(int i = 0; i data.length; ++i){> stack.push(i);> }while(stack.size() 1){> int a = stack.pop();> int b = stack.pop();> if(knows(a, b, data)) // a can't be a celerity{> stack.push(b);> }else // b can't be a celebrity{stack.push(a);> }> }int lastPerson = stack.pop();for(int i = 0; i data.length; ++i){> if(i != lastPerson && (knows(lastPerson, i, data) || !knows(i, lastPerson, data)))> {> return -1;> }}return lastPerson;>}int[][] data = {{0, 0, 1, 0},> {0, 0, 1, 0},> {0, 0, 0, 0},> {0, 0, 1, 0}> };> boolean check = findCelebrity(data) == 2;> if(!check){return false;> }> return true;}
KnightShortestWalk
Tests
private static int[] X_MOVES = {2, 1, 1, 2, -2, -1, -1, -2};> private static int[] Y_MOVES = {1, 2, -2, -1, 1, 2, -2, -1};> private static int SIZE = 8;> > private static boolean isValid(int x, int y)> {> return x = 0 && x SIZE && y = 0 && y SIZE;}> > private static boolean isValid(int[] pt)> {return isValid(pt[0], pt[1]);}> > static int shortestWalk(int[] start, int[] target)> {> boolean[][] visited = new boolean[SIZE][SIZE];pre data-role="codeBlock" data-info="js" class="language-javascript"> QueueDistancePoint queue = new LinkedList(); > if(isValid(start))> {> visited[start[0]][start[1]] = true;> }> else> {> return -1; > }queue.offer(new DistancePoint(start[0], start[1], 0));while(!queue.isEmpty()){> DistancePoint lastPoint = queue.poll();if(lastPoint.x == target[0] && lastPoint.y == target[1])> {> return lastPoint.distance; > }>for(int i = 0; i SIZE; ++i){int nextX = lastPoint.x + X_MOVES[i];int nextY = lastPoint.y + Y_MOVES[i];if(isValid(nextX, nextY) && !visited[nextX][nextY])> { > visited[nextX][nextX] = true;> queue.offer(new DistancePoint(nextX, nextY, lastPoint.distance + 1));}}> }> return -1;> }> int x, y, distance;> DistancePoint(int x, int y, int distance)> {> this.x = x;> this.y = y; > this.distance = distance;> }static class DistancePoint> {}}boolean check = shortestWalk(new int[] {0, 0}, new int[] {4, 5}) == 3;> if(!check){return false;> }> return true;}
Maze
Tests
}> >static private boolean isValid(int[] pt, int[][] maze)pre data-role="codeBlock" data-info="js" class="language-javascript"> return isValid(pt[0], pt[1], maze);>}> >static boolean solve(int[][] maze)Queueint[] queue = new LinkedList();> queue.offer(maze[0]);> while(!queue.isEmpty())> {int[] pt = queue.poll();if(pt[0] == maze.length - 1 && pt[1] == maze[0].length - 1)> {> return true; > }int[] newPt1 = new int[] {pt[0] + 1, pt[1]};int[] newPt2 = new int[] {pt[0], pt[1] + 1};> if(isValid(newPt1, maze)) > { > queue.offer(newPt1);> }if(isValid(newPt2, maze)){> queue.offer(newPt2);> }> }return false;}int[][] data1 = new int [][] {{1, 1, 0, 1},{0, 1, 0, 0},> {0, 1, 1, 0},> {0, 0, 1, 1},> {0, 0, 0, 1}> };> boolean check = solve(data1);> if(!check){return false;> }> int[][] data2 = new int [][] { > {1, 1, 0, 1},> {0, 1, 0, 0},> {0, 1, 0, 0},> {0, 0, 1, 1},> {0, 0, 0, 1}> };check = !solve(data2);if(!check)> {> return false;> }return true;}
MergeIntervals
Tests
{> // If start time of current interval is = to end time of prior interval - mergeif(intervals[i][0] = stack.peek()[1]){> // If end time of current interval is than end time of the prior interval,> // modify prior interval> if(intervals[i][1] stack.peek()[1])> {> int[] item = stack.pop(); > item[1] = intervals[i][1];> stack.push(item);> }> }else{> stack.push(intervals[i]);> }> }return stack.stream().collect(Collectors.toList());}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int areaOfOverlappingRectangle(int[][] r1, int[][] r2)> int[][] xIntervals = new int[][] {> {r1[0][0], r1[1][0]},> {r2[0][0], r2[1][0]}> };int[][] yIntervals = new int[][] {{r1[0][1], r1[1][1]},{r2[0][1], r2[1][1]}};> Arrays.sort(xIntervals, Comparator.comparingInt((int[] a) - a[0])> .thenComparing((int[] a) - a[1]));pre data-role="codeBlock" data-info="js" class="language-javascript"> // Both intervals must overlap> if(!(xIntervals[0][0] xIntervals[1][0] || yIntervals[0][1] yIntervals[1][1])){> return 0;> }> int w = xIntervals[0][1] - xIntervals[1][0];pre data-role="codeBlock" data-info="js" class="language-javascript"> int h = yIntervals[0][1] - yIntervals[1][0];> return w * h; >}int [][] intervals = {{8,10},> {1,3},> {15,18},> {7,8},> {4,5}, > {2,6}> };Listint[] result = mergeIntervals(intervals);> boolean check = Arrays.equals(new int[] {1,6}, result.get(0)) &&> Arrays.equals(new int[] {7,10}, result.get(1)) &&Arrays.equals(new int[] {15,18}, result.get(2));> if(!check){return false;> }> int[][] r1 = {> {1, 1},> {4, 4},> };int [][] r2 = {{3, 3},> {6, 5},> };> check = areaOfOverlappingRectangle(r1, r2) == 1;pre data-role="codeBlock" data-info="js" class="language-javascript"> if(!check)> {return false;}> return true;>}
MinStack
Tests
private StackInteger minStack = new Stack();>@Overridepublic Integer push(Integer item){> if(item min())> {> minStack.push(item);> }return super.push(item);}> > @Overridepublic synchronized Integer pop(){int val = super.pop();> if(val == minStack.peek())> {> minStack.pop(); > }return val;}> > public int min()> {if(minStack.isEmpty()){> return Integer.MAX_VALUE;> }> return minStack.peek(); > }}MinStack minStack = new MinStack();minStack.push(3); minStack.push(5); minStack.push(2);> boolean check = minStack.min() == 2; > if(!check){return false;> }> minStack.pop();> check = minStack.min() == 3;> if(!check){return false;> }> return true;}
MouseAndCheese
Tests
// 1 denotes valid move, 0 denotes invalid move, 9 denotes cheese>private static int[] X_MOVES = {-1, 0, 0, 1};private static int[] Y_MOVES = { 0, 1, -1, 0};> private static int[][] maze;>private static boolean isValid(int x, int y){return x = 0 && x maze.length && y = 0 && y maze[0].length && (maze[x][y] == 1 || maze[x][y] == 9);}>static int distance(int[][] maze, int[] start){MouseAndCheese.maze = maze;> > boolean[][] visited = new boolean[maze.length][maze[0].length];> visited[start[0]][start[1]] = true;> > QueueDistancePoint queue = new LinkedList();> queue.offer(new DistancePoint(start[0], start[1], 0));while(!queue.isEmpty()){> DistancePoint lastPoint = queue.poll();> if(maze[lastPoint.x][lastPoint.y] == 9){> return lastPoint.distance;> }>for(int i = 0; i X_MOVES.length; ++i)> {> int nextX = lastPoint.x + X_MOVES[i];> int nextY = lastPoint.y + Y_MOVES[i];> > if(isValid(nextX, nextY) && !visited[nextX][nextY])> {> visited[nextX][nextY] = true; > queue.offer(new DistancePoint(nextX, nextY, lastPoint.distance + 1));> }> }> }return -1;}> > static class DistancePoint> {int x, y, distance;DistancePoint(int x, int y, int distance){> this.x = x;> this.y = y;> this.distance = distance; > }}}int maze[][] = {{1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },{1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },{1, 1, 1, 0, 1, 1, 0, 1, 1, 1 },{0, 0, 0, 0, 9, 0, 0, 1, 0, 1 },{1, 1, 1, 0, 1, 1, 1, 1, 1, 0 },{1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },{1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },{1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },{1, 1, 1, 0, 0, 1, 1, 1, 0, 1 }};boolean check = distance(maze, new int[] {0, 0}) == 11;if(!check)> {> return false;> }return true;}
Palindrome
Tests
StackCharacter stack = new Stack();> int len = s.length();> int idx = 0; > while(idx len / 2)> {stack.push(s.charAt(idx++));}> if(len % 2 == 1)> {> idx++;}while(idx len)> {> if(stack.empty())> { > return false;> }if(stack.pop() != s.charAt(idx++)){return false;> }> }return true;}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>staticT boolean isPalindromeList(ListT list)> StackT stack = new Stack();pre data-role="codeBlock" data-info="js" class="language-javascript"> List.NodeT slow = list.head, fast = list.head;> while(fast != null && fast.next != null){> stack.push(slow.data);> slow = slow.next;> fast = fast.next.next;> }if(fast != null){> // odd number of items> slow = slow.next;> }while(slow != null){> if(slow.data != stack.pop())> {> return false;> }slow = slow.next;}> return true;>}String s1 = "abcddcba", s2 = "abcdcba", s3 = "abcdba";pre data-role="codeBlock" data-info="js" class="language-javascript"> boolean check = isPalindromeString(s1);> if(!check){return false;> }> check = isPalindromeString(s2); > if(!check){return false;> }> check = isPalindromeString(s3); > if(check){return false;> }> ListInteger l1 = new List();> l1.add(1, 2, 3, 4, 3, 2, 1);> check = isPalindromeList(l1) == true;> if(!check)> {return false;}> ListInteger l2 = new List();l2.add(1, 2, 3, 4, 5, 2, 1);> check = isPalindromeList(l2) == true;> if(check)pre data-role="codeBlock" data-info="js" class="language-javascript"> {> return false;> }return true;}
PhoneNumberAlpha
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>private static String[] TABLE = {> "",> "", > "abc",> "def",> "ghi",> "jkl", > "mno",> "pqrs",> "tuv",> "wxyz">};> >static ListString generateCombinations(int[] n)> int len = n.length;> ListString result = new ArrayList();> QueueString queue = new LinkedList();> queue.offer("");> while(!queue.isEmpty())> {> String s = queue.poll(); > if(s.length() == len)> {> result.add(s);> }else{> String letters = TABLE[n[s.length()]];> for(int i = 0; i letters.length(); ++i){> queue.offer(s + letters.charAt(i));}> }> }return result;}ListString list = generateCombinations(new int[] {4, 9, 8, 9, 6, 3, 7});> boolean check = list.size() == 5184;> if(!check)> {return false;}> return true;>}
ProductOfDigits
Tests
// 455 is a result of 100// 100 = 4 * 5 * 5> StackInteger stack = new Stack();for(int factor = 9; factor 1; factor--){> while(n % factor == 0)> {> stack.push(factor);> n /= factor;> }}int num = 0;> while(!stack.isEmpty())> {> num = num * 10 + stack.pop(); > }return n == 1 ? num : -1;}boolean check = productOfDigits(100) == 455;if(!check){> return false;> }> return true;}
SimplifyDirPath
Tests
String[] parts = path.split("/");if(parts.length == 0){> return path;> }> QueueString queue = new LinkedList(); > for(String token : parts)> {if(!StringUtils.isBlank(token) && !token.equals("."))> {if(token.equals("..") && !queue.isEmpty())> { > queue.poll();> }> else> {> queue.offer(token); > }> }}StringBuilder sb = new StringBuilder();while(!queue.isEmpty())> {> sb.append("/"); > sb.append(queue.poll());> }return sb.toString();}boolean check = simplifyDirPath("/a/./b/../../c/").equals("/c") &&pre data-role="codeBlock" data-info="js" class="language-javascript"> simplifyDirPath("/home//foo/").equals("/home/foo"); > if(!check)> {> return false;> }return true;}
SortAscending
Tests
int val = stack.pop();if(sortedStack.isEmpty()){> sortedStack.push(val);> }> else> { > while(!sortedStack.isEmpty() && sortedStack.peek() val)> {pre data-role="codeBlock" data-info="js" class="language-javascript"> stack.push(sortedStack.pop());> } > sortedStack.push(val);> }}return sortedStack;>}StackInteger stack = new Stack();> stack.push(3); > stack.push(1); > stack.push(4); > stack.push(5); > stack.push(2);> stack = sortAscending(stack); > int[] a = stack.stream().mapToInt(x - x).toArray();> boolean check = Arrays.equals(new int[] {1, 2, 3, 4, 5}, a);> if(!check)> {> return false;> }return true;}
StructuredOutline
Tests
// Create structured outline from input/*> Heading(1, "h1_1");> Heading(2, "h2_11");> Heading(3, "h3_111");> Heading(3, "h3_112");> Heading(3, "h3_113");> Heading(2, "h2_12");> Heading(3, "h3_121");> Heading(1, "h1_2"); > Heading(2, "h2_21");> Heading(2, "h2_22");> Heading(2, "h2_23"); > Heading(3, "h3_231");> Heading(3, "h3_232");> Heading(3, "h3_233");> Heading(1, "h1_3");> */>static class Heading{> int weight;> String text;>Heading(int weight, String text){this.weight = weight;> this.text = text;> }> }> Heading heading;> ListNode children = new ArrayList();> > Node(Heading heading)> { > this.heading = heading;> }static class Node> {>int getWeight() { return heading.weight; }}> > private ListHeading headings;StructuredOutline(ListHeading headings)> {this.headings = headings;}> > Node createStructuredOutline() > {Node root = new Node( new Heading(0, "root"));>StackNode stack = new Stack();> stack.push(root);>for(Heading heading : headings){Node node = new Node(heading);> if(stack.peek().getWeight() heading.weight)> {> stack.peek().children.add(node);> stack.push(node);> }> else if(stack.peek().getWeight() == heading.weight) > {> stack.pop();> stack.peek().children.add(node);> stack.push(node);> }> else > { > // Walk down the stack to find a parent for this node> while(stack.peek().getWeight() heading.weight){> stack.pop();> }> > StackNode temp = new Stack(); > while(node.getWeight() == stack.peek().getWeight()) > {> temp.push(stack.pop());> }> stack.peek().children.add(node); > while(!temp.isEmpty())> {> stack.push(temp.pop()); > }> stack.push(node);> }> }>}ListHeading data = Arrays.asList(> new Heading(1, "h1_1"), > new Heading(2, "h2_11"),> new Heading(3, "h3_111"),> new Heading(3, "h3_112"),> new Heading(3, "h3_113"),new Heading(2, "h2_12"),new Heading(3, "h3_121"),new Heading(1, "h1_2"),new Heading(2, "h2_21"),new Heading(2, "h2_22"),new Heading(2, "h2_23"),new Heading(3, "h3_231"),new Heading(3, "h3_232"),> new Heading(3, "h3_233"),pre data-role="codeBlock" data-info="js" class="language-javascript"> new Heading(1, "h1_3")> );> StructuredOutline structuredOutline = new StructuredOutline(data);> Node root = structuredOutline.createStructuredOutline();> boolean check = root.children.size() == 3;> if(!check){return false;> }> check = root.children.get(0).heading.text.equals("h1_1") &&> root.children.get(1).heading.text.equals("h1_2") && > root.children.get(2).heading.text.equals("h1_3");> if(!check)pre data-role="codeBlock" data-info="js" class="language-javascript"> {> return false;> }check = root.children.get(0).children.size() == 2;if(!check){> return false;> }> check = root.children.get(0).children.get(0).heading.text.equals("h2_11") &&root.children.get(0).children.get(1).heading.text.equals("h2_12");> if(!check) > {return false;}> return true;>}