dfrnascimento
BAN USERSince we do not know the location of 3 and there is no weight on route, I used Breath Search First. Otherwise, Dijkstra or Bellman-Ford as we learned on communication networks...
I used a matrix to track the parent of each node. I thought on using a list associated with each pendent to visit node and mark the visited in the same matrix (e.g. 4). Actually I think it use less memory with the "parent" list instead of matrix....
import java.util.LinkedList;
public class Snake{
static int N = 6;
static int M = 6;
int[][] matrix = new int[N][M];
Pair[][] mark = new Pair[N][M];
class Pair{
public int x;
public int y;
public Pair(int xVal,int yVal){
x = xVal;
y = yVal;
}
}
public static void main(String[] args){
Snake sn = new Snake();
sn.matrix[0] = new int[]{1,1,1,1,1,1};
sn.matrix[1] = new int[]{1,0,0,0,0,1};
sn.matrix[2] = new int[]{1,0,1,1,1,1};
sn.matrix[3] = new int[]{1,0,1,0,0,0};
sn.matrix[4] = new int[]{1,0,1,1,3,0};
sn.matrix[5] = new int[]{1,0,0,0,0,0};
sn.findRoute();
}
public void findRoute(){
LinkedList<Pair> visitList = new LinkedList<Pair>();
visitList.addFirst(new Pair(0,0));
mark[0][0] = new Pair(0,0);
Pair found;
while(!visitList.isEmpty()){
Pair pair = visitList.removeLast();
found = getNeighbords(pair.x,pair.y,pair,visitList);
if(found != null){
trace(found);
break;
}
}
}
public void trace(Pair dest){
int x = dest.x;
int y = dest.y;
Pair parent;
while(!(x == 0 && y == 0)){
System.out.println(x+" : "+y);
parent = (mark[x][y]);
x = parent.x;
y = parent.y;
}
}
public Pair getNeighbords(int x,int y,Pair parent,LinkedList<Pair> queue ){
//Horizontal range
int xMin = Math.max(x-1, 0);
int xMax = Math.min(x+1,M-1);
int yMin = Math.max(y-1,0);
int yMax = Math.min(y+1,N-1);
for(int xp = xMin; xp <= xMax; xp++){
for(int yp = yMin; yp <= yMax; yp++){
//visited?
if(mark[xp][yp] != null)
continue;
mark[xp][yp] = parent;
//passable?
if(matrix[xp][yp] == 1){
queue.addFirst(new Pair(xp,yp));
}
//goal?
if(matrix[xp][yp] == 3){
System.out.println("found: "+x+":"+y);
return new Pair(xp,yp);
}
}
}
return null;
}
}
public class Test{
public static void main(String[] args){
int n = 2;
int m = 5;
int[][] matrix = new int[n][m];
fillMatrix(matrix,n,m);
printDiagonal(matrix,n,m);
}
public static void fillMatrix(int[][] matrix,int n,int m){
int i = 1;
for(int l = 0; l < n; l++){
for(int k = 0; k < m; k++){
matrix[l][k] = i++;
}
}
}
public static void printDiagonal(int[][] matrix,int n,int m){
StringBuilder sb = new StringBuilder();
int dMax = n+m-1;
int d = 0;
for(d = 0; d < m; d++){
for(int l = 0; l <= d && l < n; l++){
sb.append(matrix[l][d-l]);
sb.append(" ");
}
sb.append("\n");
}
//pos diagonal
while(d <= dMax){
for(int l = d-m+1; l <= d && l < n ; l++){
sb.append(matrix[l][d-l]);
sb.append(" ");
}
sb.append("\n");
d++;
}
System.out.println(sb.toString());
}
}
My approach is quiet the same and dump maybe... but billion is ~ 2^30 (GB). Since these numbers are integers, you have a range: 2^32 possibilities. If each possibility is a counter of 32bit (which gives you a massive support, despite hotspots, for the endless stream) you could use a int array to count the integers. Since this counter is indexed, the counting process is O(n) and scales with the stream.
- dfrnascimento March 02, 2014More, you can use a double to count the TOTAL number of entires (or BigInteger), then to find the median, just /2 the Total and use a pointer to sum and reach that value.
Issues: The median is not real-time and the stream would need to stop
I would say the heap or bst options and not mine... but it was just a new idea...