Cleartrip.com Interview Question for Software Developers

Country: India

Comment hidden because of low score. Click to expand.
0
of 0 vote

Build a graph with rocks as vertices, with edges representing overlaps between rocks.To find overlap between rocks use this code

``````bool Overlap(float x1,float y1,float r1,float x2,float y2, float r2)
{
if((pow((x2-x1),2)+pow((y2-y1),2))<(r1+r2))
return true;
else
return false;``````

}

Add source and destination vertices.Source vertex is connected to the "shore rocks" of
one shore. Destination vertex is connected to the "shore rocks" of other shore. Use this code to find shore rocks

``````bool ShoreRock( float rockX,float rockY, float rockR, float yIntercept)
{
if(((rockY-yIntercept)-rockR)>0)
return true;
else
return false;``````

}

Now we got a graph, we have to find shortest path from source to destination. We can use djikstra algorithm for this.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.*;

public class RockProblem{
public static void main(String[] args){
int shore_b = 3;
int shore_a = 0;
List<Rock> rockList = new ArrayList<Rock>();
rockList.add(new Rock(1, 1, 1, 1, shore_a, shore_b));
rockList.add(new Rock(2, 1, 2, 1, shore_a, shore_b));
rockList.add(new Rock(3, 3, 4, 1, shore_a, shore_b));
solve(rockList, shore_a, shore_b);
}
public static void solve(List<Rock> rockList, int shore_a, int shore_b){
Path path = null;
for(Rock r: rockList){
if(r.touchShoreA && r.touchShoreB){
path = new Path(r);
break;
}
if(r.touchShoreA){
path = findPath(r, rockList);
if(path != null){
break;
}
}
}
if(path != null ){
System.out.println(path);
}
}
public static Path findPath(Rock rock, List<Rock> rockList){
if(rock.neighbers != null){
return null;
}
for(Rock r: rockList){
if(rock.index != r.index
&& rock.r + r.r - Math.sqrt(Math.pow(rock.y - r.y, 2) + Math.pow(rock.x - r.x, 2))>0 ){
if(r.touchShoreB){
//found path
Path p = new Path(rock);
p.next = new Path(r);
return p;
}
List<Rock> neighbers = rock.neighbers;
if(neighbers == null){
neighbers = new ArrayList<Rock>();
}
rock.neighbers = neighbers;
}
}
for(Rock r: rock.neighbers){
Path next = findPath(r, rockList);
if(next != null){
Path p = new Path(rock);
p.next = next;
return p;
}
}
return null;
}
}

class Path{
Rock r;
Path next;
Path(Rock r){
this.r = r;
}
@Override
public String toString(){
return r.index + (next == null ? "" : ("->" + next.toString()));
}
}
class Rock{
int index;
int x;
int y;
int r;
boolean touchShoreA = false;
boolean touchShoreB = false;
// neighbersClosertoShore, y + r bigger or equals this
List<Rock> neighbers;
Rock(int index, int x, int y, int r, int shore_a, int shore_b){
this.x = x;
this.y = y;
this.r = r;
this.index = index;
this.touchShoreA = (Math.abs(y - r) <= r) ;
this.touchShoreB = (Math.abs(shore_b - y)<= r);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Cutting to the cheese - dropping all useless information the problem is succinctly summarised by :
=======================================
Given a list of circles of various radii and centre:
1. Would it be possible to move from one starting point to another
2. What would be the min path and the circles
=======================================
Thus we end up having a directed graph, where :
======
1. Nodes are the circles
2. Edges between nodes exist, if and only if the circles overlap
3. Circles having centre with y larger than the North bank y are north bank stones
4. Circles having centre with y smaller than the South bank y are south bank stones
=========
Now, we need to find out all paths from one bank to another, and the minimum path.
This is doable by iterating over all source nodes - and rejecting paths.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I'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.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 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(" ");
}
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);

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
}
}
}
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++) {
//line up connected neighbors
list.get(i).parent = node;
}
}
}
if(fNode == null){
System.out.println("-1");
}
else{
int count = 0;
while(fNode != null){
fNode = fNode.parent;
count++;
}
System.out.println(count);
}

}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.