Skip to content

Commit

Permalink
Merge branch 'master' of https://github.com/sherxon/AlgoDS
Browse files Browse the repository at this point in the history
  • Loading branch information
@rajatsharma23
rajatsharma23 committed Aug 31, 2018
2 parents bbd0ef1 + c6370c7 commit aeb3caf
Show file tree
Hide file tree
Showing 15 changed files with 1,010 additions and 127 deletions.
82 changes: 82 additions & 0 deletions src/AmazonDemo/Sample.java
View file
Original file line number Diff line number Diff line change
@@ -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);
}
}
253 changes: 126 additions & 127 deletions src/google/PrepareBunnyEscape.java
View file
Original file line number Diff line number Diff line change
@@ -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;
}

}
Loading

0 comments on commit aeb3caf

Please sign in to comment.