today's contribution, medium problem, sample questions

sherxon · Aug 23, 2018 · ea58888 · ea58888
1 parent 59f628b
commit ea58888
Show file tree

Hide file tree

Showing 3 changed files with 208 additions and 128 deletions.
diff --git a/src/AmazonDemo/Sample.java b/src/AmazonDemo/Sample.java
@@ -0,0 +1,82 @@
+package AmazonDemo;
+
+import java.util.*;
+
+/**
+ * Why Did you create this class? what does it do?
+ */
+public class Sample {
+
+    List<List<Integer>> nearestXsteakHouses(int totalSteakhouses, List<List<Integer>> allLocations, int numSteakhouses) {
+        if (numSteakhouses <= 0) {
+            return new ArrayList<>();
+        }
+        if (totalSteakhouses <= numSteakhouses) {
+            return allLocations;
+        }
+        List<List<Integer>> result = new ArrayList<>();
+        dijkstra(allLocations, numSteakhouses, result);
+        return result;
+    }
+
+    private void dijkstra(List<List<Integer>> allLocations, int numSteakhouses, List<List<Integer>> result) {
+        int x = 0;
+        int y = 0;
+        List<Integer> customer = new ArrayList<>();
+        customer.add(x);
+        customer.add(y);
+        Map<Double, List<List<Integer>>> dis = new TreeMap<>();
+        for (List<Integer> location : allLocations) {
+            double distance = calculateDist(location, customer);
+            List<List<Integer>> value = dis.getOrDefault(distance, new ArrayList<>());
+            value.add(location);
+            dis.put(distance, value);
+        }
+        for (Double key : dis.keySet()) {
+            if (numSteakhouses >= dis.get(key).size()) {
+                result.addAll(dis.get(key));
+                numSteakhouses -= dis.get(key).size();
+            } else {
+                for (int i = 0; i < numSteakhouses; i++) {
+                    result.add(dis.get(key).get(i));
+                }
+                return;
+            }
+            if (numSteakhouses <= 0)
+                return;
+        }
+
+    }
+
+    private Double calculateDist(List<Integer> location, List<Integer> customer) {
+        return Math.hypot(customer.get(0) - location.get(0), customer.get(1) - location.get(1));
+    }
+
+    int minimumDistance(int numRows, int numColumns, List<List<Integer>> area) {
+        if (area == null || area.size() == 0)
+            return 0;
+        int[] min = new int[] { Integer.MAX_VALUE };
+        route(area, 0, 0, min, 0);
+        return min[0] == Integer.MAX_VALUE ? -1 : min[0];
+    }
+
+    private void route(List<List<Integer>> area, int i, int j, int[] min, int distance) {
+        if (i < 0 || j < 0 || i >= area.size() || j >= area.get(i).size())
+            return;
+        if (area.get(i).get(j) == 9) {
+            min[0] = Math.min(min[0], distance);
+            return;
+        }
+        if (area.get(i).get(j) == 0)
+            return;
+        if (area.get(i).get(j) == -1)
+            return;
+
+        int val = area.get(i).get(j);
+        route(area, i + 1, j, min, distance + 1);
+        route(area, i - 1, j, min, distance + 1);
+        route(area, i, j + 1, min, distance + 1);
+        route(area, i, j - 1, min, distance + 1);
+        area.get(i).set(j, val);
+    }
+}
diff --git a/src/google/PrepareBunnyEscape.java b/src/google/PrepareBunnyEscape.java
@@ -1,155 +1,154 @@
 package google;
 
-
 import java.util.*;
 
 /**
  * Created by sherxon on 6/24/17.
  */
 public class PrepareBunnyEscape {
 
-  public static void main(String[] args) {
-    System.out.println(answer(new int[][]{
-        {0, 0, 0, 0, 0, 0},
-        {1, 1, 1, 1, 1, 0},
-        {0, 0, 0, 0, 0, 0},
-        {0, 1, 1, 1, 1, 1},
-        {0, 1, 1, 1, 1, 1},
-        {1, 0, 0, 0, 0, 0},
-    }));
-    System.out.println(answer(new int[][]{
-        {0, 1, 1, 0},
-        {0, 0, 0, 1},
-        {1, 1, 0, 0},
-        {1, 1, 1, 0},
-    }));
-    System.out.println(answer(new int[][]{
-        {0, 1, 1, 0},
-        {0, 0, 0, 0},
-    }));
-    System.out.println(answer(new int[][]{
-        {0, 1},
-        {0, 0},
-        {1, 1},
-        {1, 0},
-    }));
-  }
-
-  public static int answer(int[][] a) {
-
-    int n = a.length;
-    int m = a[0].length;
-
-    Map<Integer, Set<Integer>> map = new HashMap<>(m * n);
-    Queue<Integer> walls = new LinkedList<>();
-    for (int i = 0; i < n; i++) {
-      for (int j = 0; j < m; j++) {
-        if (a[i][j] == 0) {
-          map.put(i * m + j, getNei(a, i, j));
-        } else {
-          walls.add(i * m + j);
-        }
-      }
-    }
-    Map<Integer, Integer> fromSource = new HashMap<>();
-    Map<Integer, Integer> fromDest = new HashMap<>();
-    bfs(map, 0, fromSource);
-    bfs(map, n * m - 1, fromDest);
-
-    int min = Integer.MAX_VALUE;
-    if (fromSource.get(n * m - 1) != null) {
-      min = fromSource.get(n * m - 1);
+    public static void main(String[] args) {
+        System.out.println(answer(new int[][] {
+                { 0, 0, 0, 0, 0, 0 },
+                { 1, 1, 1, 1, 1, 0 },
+                { 0, 0, 0, 0, 0, 0 },
+                { 0, 1, 1, 1, 1, 1 },
+                { 0, 1, 1, 1, 1, 1 },
+                { 1, 0, 0, 0, 0, 0 },
+                }));
+        System.out.println(answer(new int[][] {
+                { 0, 1, 1, 0 },
+                { 0, 0, 0, 1 },
+                { 1, 1, 0, 0 },
+                { 1, 1, 1, 0 },
+                }));
+        System.out.println(answer(new int[][] {
+                { 0, 1, 1, 0 },
+                { 0, 0, 0, 0 },
+                }));
+        System.out.println(answer(new int[][] {
+                { 0, 1 },
+                { 0, 0 },
+                { 1, 1 },
+                { 1, 0 },
+                }));
     }
 
-    while (!walls.isEmpty()) {
-      Integer cw = walls.remove();
-      int ii = cw / m;
-      int jj = cw - ii * m;
-      Set<Integer> neis = getNei(a, ii, jj);
-      int minFromSource = Integer.MAX_VALUE;
-      int minFromDest = Integer.MAX_VALUE;
-      for (Integer nei : neis) {
-        if (fromSource.get(nei) != null) {
-          minFromSource = Math.min(minFromSource, fromSource.get(nei));
+    public static int answer(int[][] a) {
+
+        int n = a.length;
+        int m = a[0].length;
+
+        Map<Integer, Set<Integer>> map = new HashMap<>(m * n);
+        Queue<Integer> walls = new LinkedList<>();
+        for (int i = 0; i < n; i++) {
+            for (int j = 0; j < m; j++) {
+                if (a[i][j] == 0) {
+                    map.put(i * m + j, getNei(a, i, j));
+                } else {
+                    walls.add(i * m + j);
+                }
+            }
         }
-        if (fromDest.get(nei) != null) {
-          minFromDest = Math.min(minFromDest, fromDest.get(nei));
+        Map<Integer, Integer> fromSource = new HashMap<>();
+        Map<Integer, Integer> fromDest = new HashMap<>();
+        bfs(map, 0, fromSource);
+        bfs(map, n * m - 1, fromDest);
+
+        int min = Integer.MAX_VALUE;
+        if (fromSource.get(n * m - 1) != null) {
+            min = fromSource.get(n * m - 1);
         }
-      }
-      if (minFromDest != Integer.MAX_VALUE && minFromSource != Integer.MAX_VALUE) {
-        min = Math.min(min, minFromDest + minFromSource + 1);
-      }
-    }
-    return min;
-  }
 
-  private static void bfs(Map<Integer, Set<Integer>> map, int source,
-      Map<Integer, Integer> fromSource) {
-    if (!map.containsKey(source)) {
-      return;
-    }
-    fromSource.put(source, 1);
-    Queue<Integer> q = new LinkedList<>();
-    q.add(source);
-    Set<Integer> visited = new HashSet<>();
-    visited.add(source);
-    while (!q.isEmpty()) {
-      Integer current = q.remove();
-      if (map.containsKey(current)) {
-        for (Integer nei : map.get(current)) {
-          if (!visited.contains(nei)) {
-            visited.add(nei);
-            fromSource.put(nei, fromSource.get(current) + 1);
-            q.add(nei);
-          }
+        while (!walls.isEmpty()) {
+            Integer cw = walls.remove();
+            int ii = cw / m;
+            int jj = cw - ii * m;
+            Set<Integer> neis = getNei(a, ii, jj);
+            int minFromSource = Integer.MAX_VALUE;
+            int minFromDest = Integer.MAX_VALUE;
+            for (Integer nei : neis) {
+                if (fromSource.get(nei) != null) {
+                    minFromSource = Math.min(minFromSource, fromSource.get(nei));
+                }
+                if (fromDest.get(nei) != null) {
+                    minFromDest = Math.min(minFromDest, fromDest.get(nei));
+                }
+            }
+            if (minFromDest != Integer.MAX_VALUE && minFromSource != Integer.MAX_VALUE) {
+                min = Math.min(min, minFromDest + minFromSource + 1);
+            }
         }
-      }
-    }
-  }
-
-  private static Set<Integer> getNei(int[][] a, int i, int j) {
-    Set<Integer> set = new HashSet<>();
-    int n = a.length;
-    int m = a[i].length;
-    if (i + 1 < n && a[i + 1][j] == 0) {
-      set.add((i + 1) * m + j);
+        return min;
     }
-    if (j + 1 < m && a[i][j + 1] == 0) {
-      set.add((i) * m + j + 1);
-    }
-    if (j - 1 >= 0 && a[i][j - 1] == 0) {
-      set.add((i) * m + j - 1);
-    }
-    if (i - 1 >= 0 && a[i - 1][j] == 0) {
-      set.add((i - 1) * m + j);
+
+    private static void bfs(Map<Integer, Set<Integer>> map, int source,
+            Map<Integer, Integer> fromSource) {
+        if (!map.containsKey(source)) {
+            return;
+        }
+        fromSource.put(source, 1);
+        Queue<Integer> q = new LinkedList<>();
+        q.add(source);
+        Set<Integer> visited = new HashSet<>();
+        visited.add(source);
+        while (!q.isEmpty()) {
+            Integer current = q.remove();
+            if (map.containsKey(current)) {
+                for (Integer nei : map.get(current)) {
+                    if (!visited.contains(nei)) {
+                        visited.add(nei);
+                        fromSource.put(nei, fromSource.get(current) + 1);
+                        q.add(nei);
+                    }
+                }
+            }
+        }
     }
 
-    return set;
-  }
+    private static Set<Integer> getNei(int[][] a, int i, int j) {
+        Set<Integer> set = new HashSet<>();
+        int n = a.length;
+        int m = a[i].length;
+        if (i + 1 < n && a[i + 1][j] == 0) {
+            set.add((i + 1) * m + j);
+        }
+        if (j + 1 < m && a[i][j + 1] == 0) {
+            set.add((i) * m + j + 1);
+        }
+        if (j - 1 >= 0 && a[i][j - 1] == 0) {
+            set.add((i) * m + j - 1);
+        }
+        if (i - 1 >= 0 && a[i - 1][j] == 0) {
+            set.add((i - 1) * m + j);
+        }
 
-  private static void go(int[][] a, int[][] aa, int i, int j, int step, int ii, int jj) {
-    if (i < 0 || j < 0 || i >= a.length || j >= a[i].length) {
-      return;
+        return set;
     }
+
+    private static void go(int[][] a, int[][] aa, int i, int j, int step, int ii, int jj) {
+        if (i < 0 || j < 0 || i >= a.length || j >= a[i].length) {
+            return;
+        }
    /* if(i==5 && j==5){
       System.out.println(a[i][j]);
     }*/
-    if (a[i][j] == 1) {
-      return;
-    }
-    if (i != 0 && j != 0 && aa[i][j] <= step) {
-      return;
-    }
+        if (a[i][j] == 1) {
+            return;
+        }
+        if (i != 0 && j != 0 && aa[i][j] <= step) {
+            return;
+        }
 
-    aa[i][j] = step;
+        aa[i][j] = step;
 
-    a[i][j] = 1;
-    go(a, aa, i, j + 1, step + 1, ii, jj);
-    go(a, aa, i, j - 1, step + 1, ii, jj);
-    go(a, aa, i + 1, j, step + 1, ii, jj);
-    go(a, aa, i - 1, j, step + 1, ii, jj);
+        a[i][j] = 1;
+        go(a, aa, i, j + 1, step + 1, ii, jj);
+        go(a, aa, i, j - 1, step + 1, ii, jj);
+        go(a, aa, i + 1, j, step + 1, ii, jj);
+        go(a, aa, i - 1, j, step + 1, ii, jj);
 
-    a[i][j] = 0;
-  }
+        a[i][j] = 0;
+    }
 
 }
diff --git a/src/problems/medium/InsertIntoBST.java b/src/problems/medium/InsertIntoBST.java
@@ -14,7 +14,6 @@ public TreeNode insertIntoBST(TreeNode root, int val) {
             root.right = insertIntoBST(root.right, val);
         else
             root.left = insertIntoBST(root.left, val);
-
         return root;
     }
 }