sharmanalin59
BAN USERI'm removing those rocks that are completely contained in bigger rocks and with remaining rocks creating a directed graph and using BFS to find the shortest route
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
/**
*
* @author Nalin.Sharma
*
*/
/*
*
* BFS implementation
*/
public class RockClimb {
static class Node{
public Node(int x, int y, int r, int n) {
super();
this.x = x;
this.y = y;
this.r = r;
num = n;
}
int x;
int y;
int r; //radius
int num;
Node parent;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
List<Node> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
String [] arr = sc.nextLine().split(" ");
list.add(new Node(Integer.parseInt(arr[0]), Integer.parseInt(arr[1]), Integer.parseInt(arr[2]), i));
}
String[] Y = sc.nextLine().split(" ");
int ylow = Integer.parseInt(Y[1]);
int yhigh = Integer.parseInt(Y[0]);
boolean [] [] adj = new boolean[n][n];
boolean [] visited = new boolean[n];
for (int i = 0; i < list.size(); i++) {
for (int j = i+1; j < list.size(); j++) {
Node INode = list.get(i);
Node JNode = list.get(j);
//added
int ix1 = INode.x - INode.r;
int ix2 = INode.x + INode.r;
int iy1 = INode.y - INode.r;
int iy2 = INode.y + INode.r;
int jx1 = JNode.x - JNode.r;
int jx2 = JNode.x + JNode.r;
int jy1 = JNode.y - JNode.r;
int jy2 = JNode.y + JNode.r;
//clean rocks being completely engulfed by other rocks
if(jx1 <= ix1 && ix1 <=jx2 && jx1 <= ix2 && ix2 <=jx2
&& jy1 <= iy1 && iy1 <=jy2 && jy1 <= iy2 && iy2 <=jy2 ){
list.remove(i);
i -= 1;
continue;
}
else if(ix1 <= jx1 && jx1 <=ix2 && ix1 <= jx2 && jx2 <=ix2
&& iy1 <= jy1 && jy1 <=iy2 && iy1 <= jy2 && jy2 <=iy2 ){
list.remove(j);
j -= 1;
continue;
}
int x = Math.abs(INode.x - JNode.x);
int y = Math.abs(INode.y - JNode.y);
long hypot = x*x + y*y;
if(hypot <= INode.r + JNode.r){
//i,j rocks touch each other
adj [i] [j] = true;
adj [j] [i] = true;
}
}
}
Queue<Node> bfs = new LinkedList<>();
bfs.add(list.get(0));
Node fNode = null;
while(!bfs.isEmpty()){
Node node = bfs.remove();
if(visited[node.num] == true){
continue;
}
if(node.y + node.r >= yhigh){
fNode = node;
break;
}
visited[node.num] = true;
for (int i = 0; i < n; i++) {
if(adj[node.num][i] == true){
//line up connected neighbors
list.get(i).parent = node;
bfs.add(list.get(i));
}
}
}
if(fNode == null){
System.out.println("-1");
}
else{
int count = 0;
while(fNode != null){
fNode = fNode.parent;
count++;
}
System.out.println(count);
}
}
}
Simple one producer binds to exchange, exchange has n queues each queue can have a consumer. I'm using three Queues one for odd one for even for for just number(both odd even).Each queue has one consumer feeding off it.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
/**
*
* @author Nalin.Sharma
*
*/
/*
* Concurrent linked Queue
* simple one producer one exchange multiple queues, one q to one consumer example
*/
class Sleep{
static void sleep(){
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
//consumer job
class Consumer implements Runnable{
//ds
Queue q;
String name;
boolean hasReceived = false;
Consumer(String n){
name = n;
(new Thread(this)).start();
}
@Override
public void run() {
hasReceived = true;
while(true){
Sleep.sleep();
if(!q.isEmpty())
System.out.println(name+" reading "+q.remove());
}
}
}
//producer job
class Producer implements Runnable{
//ds
Exchange exchange;
//Object payload;
String routingKey;
//boolean hasSent = true;
Producer(Exchange e){
exchange = e;
(new Thread(this)).start();
}
@Override
public void run() {
//hasSent = true;
int i = 0;
Sleep.sleep();
while(i < 100){
if(i%2 == 0)
exchange.addAndRoute(i,"even,number");
else
exchange.addAndRoute(i,"odd,number");
System.out.println("prod .. "+ i);
i++;
}
System.out.println("prod done ");
}
}
class MyQueue{
//ds
String routingKey;
Queue q;
Consumer c; //you can count number of consumers of a type and spawn multiple threads
public MyQueue(String routingKey, Queue q, Consumer c) {
this.routingKey = routingKey;
this.q = q;
this.c = c;
c.q = q; //one to one
}
}
class Exchange{
//ds
String name;
Producer p; //one producer
Map<String,List<MyQueue>> qs = new HashMap<>(); //routing queue and list of queues(each having one consumer)
Exchange(String n){
name = n;
}
void bindProducer(Producer p){
this.p = p;
}
void bindConsumer(MyQueue q){
if(qs.get(q.routingKey) == null)
qs.put(q.routingKey, new ArrayList<>());
qs.get(q.routingKey).add(q);
}
void addAndRoute(Object payload, String routingKeys){
String [] rKeys = routingKeys.split(",");
for(String key :rKeys){
List<MyQueue> Q = qs.get(key);
for (int i = 0; i < Q.size(); i++) {
Q.get(i).q.add(payload);
}
}
}
}
class Broker{
//ds
Exchange exchange;
Broker(Exchange e, Producer p){
this.exchange = e;
this.exchange.p = p;
}
void bindToExchange(Queue q, Consumer c, String rq){
MyQueue mq = new MyQueue(rq, q, c);
exchange.bindConsumer(mq);
}
}
public class MessageBrokerDesign {
public static void main(String[] args) {
Exchange e = new Exchange("e1");
Producer p = new Producer(e);
Broker mb = new Broker(e, p);
Queue odd = new ConcurrentLinkedQueue();
Consumer oddC1 = new Consumer("odd");
mb.bindToExchange(odd, oddC1, "odd");
Queue even = new ConcurrentLinkedQueue();
Consumer evenC1 = new Consumer("even");
mb.bindToExchange(even, evenC1, "even");
Queue number = new ConcurrentLinkedQueue();
Consumer numberC = new Consumer("number");
mb.bindToExchange(number, numberC, "number");
}
}
Here is my recursive solution hope it helps :)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
*
* @author Nalin.Sharma
*
*/
/*
* a = 1
* b = 2
* .
* .
* .
* input
* 112
* output
* aab
* kb(11 for k)
* al(12 for l)
*
*/
public class FacebookFlipkartQuestion {
public static void main(String[] args) {
String s = "112";
char a [] = s.toCharArray();
Map<Integer,Character> map = new HashMap<>();
fill(map);
List<List<Integer>> all = new ArrayList<>();
List<Integer> l = prepareList(a);
all.add(l);
rec(l, all);
print(all,map);
System.out.println();
}
private static void print(List<List<Integer>> all, Map<Integer, Character> map) {
for(List<Integer> l : all){
String out = "";
for (int i = 0; i < l.size(); i++) {
out += map.get(l.get(i));
}
System.out.println(out);
}
}
private static void rec(List<Integer> l, List<List<Integer>> all) {
for (int i = 0; i < l.size(); i++) {
if(i+1 < l.size() && l.get(i) < 9 && l.get(i+1) < 9){
int n = l.get(i) * 10 + l.get(i+1);
if(n<26){
List<Integer> lnew = new ArrayList<>(l);
lnew.remove(i+1);
lnew.set(i, n);
all.add(lnew);
rec(lnew, all);
}
}
}
}
private static List<Integer> prepareList(char[] a) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < a.length; i++) {
list.add(Character.getNumericValue(a[i]));
}
return list;
}
private static void fill(Map<Integer, Character> map) {
char c;
for(int i =0 ; i < 26; i++){
c = (char) ('a' + i);
map.put(i+1 , c);
}
}
}
Below is the working code using recursion, hope it helps :)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
*
* @author Nalin.Sharma
*
*/
/*
* a = 1
* b = 2
* .
* .
* .
* input
* 112
* output
* aab
* kb(11 for k)
* al(12 for l)
*
*/
public class FacebookFlipkartQuestion {
public static void main(String[] args) {
String s = "112";
char a [] = s.toCharArray();
Map<Integer,Character> map = new HashMap<>();
fill(map);
List<List<Integer>> all = new ArrayList<>();
List<Integer> l = prepareList(a);
all.add(l);
rec(l, all);
print(all,map);
System.out.println();
}
private static void print(List<List<Integer>> all, Map<Integer, Character> map) {
for(List<Integer> l : all){
String out = "";
for (int i = 0; i < l.size(); i++) {
out += map.get(l.get(i));
}
System.out.println(out);
}
}
private static void rec(List<Integer> l, List<List<Integer>> all) {
for (int i = 0; i < l.size(); i++) {
if(i+1 < l.size() && l.get(i) < 9 && l.get(i+1) < 9){
int n = l.get(i) * 10 + l.get(i+1);
if(n<26){
List<Integer> lnew = new ArrayList<>(l);
lnew.remove(i+1);
lnew.set(i, n);
all.add(lnew);
rec(lnew, all);
}
}
}
}
private static List<Integer> prepareList(char[] a) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < a.length; i++) {
list.add(Character.getNumericValue(a[i]));
}
return list;
}
private static void fill(Map<Integer, Character> map) {
char c;
for(int i =0 ; i < 26; i++){
c = (char) ('a' + i);
map.put(i+1 , c);
}
}
}
hashcode will not be in picture as we aren't talking about hashset or linkedhashset or any collection that uses hashing!
- sharmanalin59 November 07, 2014public class Repeat {
public static void main(String[] args) {
String str = "wwwwaaadexxxxxxfgttsgge", output = "";
char[] arr = str.toCharArray();
int count = 1;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == arr[i + 1]) {
count++;
} else {
if (count > 1)
output += arr[i] + "" + count;
else
output += arr[i] + "";
count = 1;
}
}
if (count > 1)
output += arr[arr.length - 1] + "" + count;
else
output += arr[arr.length - 1] + "";
System.out.println(output);
}
}
- sharmanalin59 August 02, 2018