Paras
BAN USERO(nlogn) Solution.
1. consider the given view point as center of axis and calculate the angle of each point.
2. sort the angles
3. find the maximum window in the sorted list with max difference of given viewing angle.
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
/**
* Created by paras.mal on 14/11/16.
*/
public class A2 {
static class Point{
int x, y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
public static double getAngle(int x, int y, int x1, int y1){
x = x1-x;
y = y1-y;
if(x > 0 && y >= 0){
return Math.toDegrees(Math.asin(Math.abs(y) / Math.sqrt(x * x + y * y)));
}
if(x<=0 && y>0){
return Math.toDegrees(Math.asin(Math.abs(x)/Math.sqrt(x*x + y*y))) + 90;
}
if( x < 0 && y<=0){
return Math.toDegrees(Math.asin(Math.abs(y)/Math.sqrt(x*x + y*y))) + 180;
}
if( x >= 0 && y<0){
return Math.toDegrees(Math.asin(Math.abs(x)/Math.sqrt(x*x + y*y))) + 270;
}
throw new RuntimeException();
}
public static void main(String s[]){
List<Point> points = new LinkedList<>();
points.add(new Point(2,1));
points.add(new Point(2,2));
points.add(new Point(1,2));
points.add(new Point(0,2));
points.add(new Point(0,1));
points.add(new Point(0,0));
points.add(new Point(1,0));
points.add(new Point(2,0));
List<Double> d= new LinkedList<>();
int x1 = 1,y1 = 1;
points.stream().forEach((x) -> d.add(getAngle(x1, y1, x.x, x.y)));
Collections.sort(d);
int i = 0, j = 0;
int diff = 0;
int check = 90;
int i1 =0, j1 =0;
while(j<d.size() && i<d.size()){
while(j<d.size() && d.get(j)-d.get(i) <= check){
if(j1-i1 < j-i && d.get(j)-d.get(i) <= check){
j1 = j;
i1 = i;
}
j++;
}
while( i <= j && j < d.size() && d.get(j)-d.get(i) > check){
i++;
}
}
}
}
1. Generate a random number between 0 & 2^64
2. Check if random number exists in db.
3, if exists go to step 1. if does't exist. go to step 4.
4. a. Take write lock
4. b. again check if random number exist in db.
4. c. if exists unlock db and go to step 2. if doesn't exist. insert the random number in db.
5. d. return the random number.
Now to scale this service we can use sharding to divide our data source.
Big problem : if number of retry for random number is directly proportional to current number of keys in db.
Second solution: generate keys sequencially.
1. take lock on db. increment the counter unlock the lock and return the count.
problem its hard to scale because now we need to create many many shards to handle the concurrent requests.
Since the diagonal moves are not allowed so to reach (a1,b1,c1) to (a2,b2,c2) we need |a1-a2| + |b1-b2|+|c1-c2| moves. If point(A,B,C) is point which minimizes distance then total distance is sum(|A-ai|) + sum(|B-bi|)+ sum(|C-ci|) . We can find A , B, C independently by binary search over the axis. So total complexity will be O(K(log(m) +log(n) + log(o))).
- Paras November 07, 2016public class Main {
static Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
static int k = 4, n = 10;
static Set<Integer> list = new HashSet<Integer>();
static List<Integer> list2 = new ArrayList<Integer>();
public static void main(String s[]){
Random random = new Random(System.currentTimeMillis());
//random.nextInt(1>>k);
for(int i = 0;i<n;i++){
list.add(random.nextInt(1<<k));
}
list2.addAll(list);
Collections.sort(list2);
for(Integer v : list2){
for(int i = 0;i<k;i++){
if((v & (1<<i)) > 0){
Set<Integer> l = map.get(i);
if(l == null){
l = new HashSet<Integer>();
}
l.add(v);
map.put(i, l);
}
}
}
int sum = 0;
for(Integer v : list2){
Set<Integer> set = new HashSet<Integer>();
set.addAll(list2);
for(int i = 0;i<k;i++){
if((v & (1<<i)) > 0){
Set<Integer> l = map.get(i);
set.retainAll(l);
}
}
if(set.size() >= 1){
sum += set.size()-1;
}
}
System.out.println(sum);
}
}
Observation : 2 lines(x1,y1), (x2,y2) intersect iff on the circle x2 comes between x1 and y1 or wise verse. Assume all the lines are maked as (x1,y1), (x2,y2).....(xn,yn)
1. start from any point on the circle and move along the circle(circumfrance) to come back to same point, along the path keep the sequence of xi's as they come in the path.
2. Now again do the same process in the opposite direction but this time keep track of sequence of yi's along the path.
now you name 2 sequances one of xi's and other yi's
now find the maximum matching sequence for (xi's ,yi's ) which will give you subset of maximum lines without overlap.
Repmarkhmitchell6, Analyst at ASAPInfosystemsPvtLtd
At first, tattooing was a hobby kind of thing for me. I didn’t spend too much time in tattoo ...
this can be solved in O(M.N^2) using dynamic programming.
equation would be
recurr(n,sum) = for(i in 1 to m) {max( recurr(n + 1, sum(i)+1) + stacks[i].get(sum[i]))};
- Paras November 28, 2016