Amazon Interview Question
SDE-2sCountry: India
Interview Type: Written Test
import b.k.P;
import java.util.*;
public class Main {
public static void main(String[] args) {
int N=4;
int M=4;
List<Edge> edges = new ArrayList<Edge>();
edges.add(new Edge('H',2,1));
edges.add(new Edge('H',3,1));
edges.add(new Edge('V',2,2));
edges.add(new Edge('V',2,3));
HashSet<String> hor = new HashSet();
HashSet<String> ver = new HashSet();
StringBuilder sb = new StringBuilder();
for(Edge e: edges){
sb.setLength(0);
HashSet ref ;
if(e.type=='H'){
ref = hor;
}else{
ref = ver;
}
sb.append(e.s);
sb.append(e.e);
sb.append(e.e+1);
ref.add(sb.toString());
int r = e.e+2;
while(r<=N){
sb.delete(2,3);
sb.append(r);
ref.add(sb.toString());
r++;
}
int l = e.e-1;
while(l>=1){
sb.delete(1,3);
sb.append(l);
sb.append(e.e+1);
ref.add(sb.toString());
l--;
}
}
int total =0;
for(int l=1;l<N;l++){
for(int i=1;i<=N-l;i++){
for(int j=1;j<=N-l;j++){
String h1 = String.valueOf(i)+String.valueOf(j)+String.valueOf(j+l);
String h2 = String.valueOf(i+l)+String.valueOf(j)+String.valueOf(j+l);
String v1 = String.valueOf(j)+String.valueOf(i)+String.valueOf(i+l);
String v2 = String.valueOf(j+l)+String.valueOf(i)+String.valueOf(i+l);
if(!hor.contains(h1)&&!hor.contains(h2)&&
!ver.contains(v1)&&!ver.contains(v2)){
total++;
}
}
}
}
System.out.println(total);
}
static class Edge{
char type;
int s;
int e;
public Edge(char t, int start, int end){
type = t;
s = start;
e = end;
}
}
}
import Cocoa
// get input
let argv = ["4","4","H,2,1","H,3,1", "V,2,2", "V,2,3"]
let argc = argv.count
let sizeh:Int! = Int(argv[0])
let sizev:Int! = Int(argv[1])
let missingsegs = argv[2..<argc]
// use a 2d array of origin points, one for horizontal, one for vertical
// 0 indicates no line at that orgin
// 1 indicates a line at the origin
// Assumption: horizontal lines are left to right from origin
// Assumption: vertical lines are top to bottom from origin
//
// initiate the 2d arrays with 1 assuming all segments are present
var hmap = Array(repeating: Array(repeating: 1, count: sizev), count: sizeh)
var vmap = Array(repeating: Array(repeating: 1, count: sizev), count: sizeh)
// Now remove segments using the coded values provided
// set the vertical or horizontal segment value to zero
// at the origin where that segment is missing.
var x:Int = 0
var y:Int = 0
var temp:String = ""
for item in missingsegs {
if item.hasPrefix("H") {
temp = item.components(separatedBy:",")[1]
x = (Int(temp))!
temp = item.components(separatedBy:",")[2]
y = (Int(temp))!
hmap[x - 1][y - 1] = 0
} else if item.hasPrefix("V") {
temp = item.components(separatedBy:",")[1]
x = (Int(temp))!
temp = item.components(separatedBy:",")[2]
y = (Int(temp))!
vmap[x - 1][y - 1] = 0
}
}
// Now search for squares of each size at every origin point
var maxsz = 0
var sqcount = 0
var exists = true
if sizeh > sizev {
maxsz = sizeh
} else {
maxsz = sizev
}
// for each xy origin point
for x in 1...sizeh - 1 {
for y in 1...sizev - 1 {
// for each possible square size
for sz in 1...maxsz {
exists = true
// validate square could exist based on origin
// and square size desired
if x + sz > sizeh || y + sz > sizev {
exists = false
} else {
// check left and right sides exist
for xx in x...(x + sz - 1) {
if vmap[xx - 1][y - 1] == 0 { exists = false }
if vmap[xx - 1][y + sz - 1] == 0 { exists = false }
}
// check top and bottom sides exist
for yy in y...(y + sz - 1) {
if hmap[x - 1][yy - 1] == 0 { exists = false }
if hmap[x + sz - 1][yy - 1] == 0 { exists = false }
}
}
if exists {
sqcount += 1
print("\(sqcount). \(sz) x \(sz) found at coordinates \(x),\(y)")
}
}
}
}
print("\(sqcount) squares found in total")
package progs.sample.squarecounter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Optional;
import java.util.Scanner;
import progs.sample.squarecounter.vo.Segment;
import progs.sample.squarecounter.vo.Square;
public class SquareCounter {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
System.out.println("Enter the number of lines: ");
int noOfLines = reader.nextInt();
System.out.println("Enter the number of segments to be removed: ");
int noOfRemovedLines = reader.nextInt();
List<Segment> removedSegments = new ArrayList<Segment>();
System.out.println("Enter details of the segments to be removed:");
for(int i=0; i<noOfRemovedLines; i++)
{
String removedSegDetails = reader.next();
String[] details = removedSegDetails.split(",");
Segment removedSeg = new Segment(details[0], new Integer(details[1]).intValue(), new Integer(details[2]).intValue(),false);
removedSegments.add(removedSeg);
}
reader.close();
List<Segment> finalStructure = new ArrayList<Segment>();
buildStructure(noOfLines,finalStructure,removedSegments);
System.out.println("Final structure is:");
finalStructure.forEach(seg -> System.out.println(seg));
int squareCounter = 0;
//Traverse each possible horizontal segment that can form a unique square
for(int row=1;row<noOfLines;row++)
{
int jCount=1;
while(jCount < noOfLines)
{
int segCount = jCount;
while(segCount < noOfLines)
{
List<Segment> startingSide = new ArrayList<Segment>();
for(int i=jCount; i<=segCount;i++)
{
Segment segment = new Segment("H",row,i,false);
startingSide.add(segment);
}
if(doesCompleteSquareExist(startingSide, finalStructure))
{
System.out.println("Square complete for side: ");
startingSide.forEach(segment -> System.out.println(segment));
squareCounter++;
}
segCount++;
}
jCount++;
}
}
System.out.println("The number of squares left are: "+squareCounter);
}
private static void buildStructure(int noOfLines,
List<Segment> startingStructure,List<Segment> removedLines) {
String[] orientations = {"H","V"};
String currentOrientation = null;
for(int k=0;k<orientations.length; k++)
{
currentOrientation = orientations[k];
for(int i=1;i<=noOfLines;i++)
{
for(int j=1; j<=noOfLines-1;j++)
{
Segment currentSegment = new Segment(currentOrientation,i,j,false);
Optional<Segment> matchingRemovedSegment = removedLines.stream().filter(segment -> segment.getOrientation().equals(currentSegment.getOrientation())
&& segment.getFirstDimension() == currentSegment.getFirstDimension() &&
segment.getSecondDimension() == currentSegment.getSecondDimension()).findFirst();
if(!matchingRemovedSegment.isPresent())
{
startingStructure.add(currentSegment);
}
}
}
}
}
private static boolean doesCompleteSquareExist(List<Segment> startingSegment, List<Segment> finalStructure)
{
boolean doesCompleteSquareExist = true;
Square square = new Square();
//Proceed only if all startingSegment parts exist
for(Segment seg : startingSegment)
{
Optional<Segment> foundSeg = findSegmentInStructure(seg, finalStructure);
if(!foundSeg.isPresent())
{
return false;
}
}
Collections.sort(startingSegment,Comparator.comparing(Segment::getSecondDimension));
square.setFirstHorizontalSide(startingSegment);
int sideLength = (startingSegment.get(startingSegment.size()-1).getSecondDimension()
- startingSegment.get(0).getSecondDimension()) +1;
List<Segment> firstVerticalSide = new ArrayList<Segment>();
int verticalLine = startingSegment.get(startingSegment.size()-1).getSecondDimension() + 1;
for(int i=0;i<sideLength;i++)
{
Segment sidePart = new Segment("V",verticalLine,startingSegment.get(0).getFirstDimension()+i,false);
Optional<Segment> foundSeg = findSegmentInStructure(sidePart, finalStructure);
if(foundSeg.isPresent() && !foundSeg.get().isRemoved())
{
firstVerticalSide.add(sidePart);
}
else
{
return false;
}
}
square.setFirstVerticalSide(firstVerticalSide);
List<Segment> secondHorizontalSide = new ArrayList<Segment>();
for(int i=0;i<startingSegment.size();i++)
{
Segment sidePart = new Segment("H",startingSegment.
get(i).getFirstDimension()+sideLength,startingSegment.get(i).getSecondDimension(),false);
Optional<Segment> foundSeg = findSegmentInStructure(sidePart, finalStructure);
if(foundSeg.isPresent() && !foundSeg.get().isRemoved())
{
secondHorizontalSide.add(sidePart);
}
else
{
return false;
}
}
square.setSecondHorizontalSide(secondHorizontalSide);
List<Segment> secondVerticalSide = new ArrayList<Segment>();
int secverticalLine = startingSegment.get(0).getSecondDimension();
for(int i=0;i<firstVerticalSide.size();i++)
{
Segment sidePart = new Segment("V",secverticalLine,firstVerticalSide.get(i).getSecondDimension(),false);
Optional<Segment> foundSeg = findSegmentInStructure(sidePart, finalStructure);
if(foundSeg.isPresent())
{
secondVerticalSide.add(sidePart);
}
else
{
return false;
}
}
square.setSecondVerticalSide(secondVerticalSide);
return doesCompleteSquareExist;
}
private static Optional<Segment> findSegmentInStructure(Segment segmentToFind, List<Segment> structure)
{
return structure.stream().filter(segment -> segment.getOrientation().equals(segmentToFind.getOrientation()) &&
segment.getFirstDimension()==segmentToFind.getFirstDimension() &&
segment.getSecondDimension() == segmentToFind.getSecondDimension()).findFirst();
}
}
package progs.sample.squarecounter.vo;
public class Segment {
private String orientation;
private int firstDimension;
private int secondDimension;
boolean removed;
public Segment(String orientation, int firstDimension, int secondDimension,
boolean removed) {
super();
this.orientation = orientation;
this.firstDimension = firstDimension;
this.secondDimension = secondDimension;
this.removed = removed;
}
public int getFirstDimension() {
return firstDimension;
}
public void setFirstDimension(int firstDimension) {
this.firstDimension = firstDimension;
}
public int getSecondDimension() {
return secondDimension;
}
public void setSecondDimension(int secondDimension) {
this.secondDimension = secondDimension;
}
public String getOrientation() {
return orientation;
}
public void setOrientation(String orientation) {
this.orientation = orientation;
}
public boolean isRemoved() {
return removed;
}
public void setRemoved(boolean removed) {
this.removed = removed;
}
@Override
public String toString() {
return "Segment [orientation=" + orientation + ", firstDimension="
+ firstDimension + ", secondDimension=" + secondDimension + ", removed="
+ removed + "]";
}
}
public static int getNumberOfSquareBySize(int size, int noHLine, List<Segment> brokenSegment, int count) {
for (int i = 1; i < noHLine; i++) {
for (int j = 1; j < noHLine; j++) {
boolean isUnbrokenSquare = false;
if (j + size-1 < noHLine && i + size-1 < noHLine) {
for (int k = 0; k < size; k++) {
// check for 1st horizontal line for length k
if (brokenSegment.contains(new Segment('H', i, j + k))) {
isUnbrokenSquare = true;
break;
}
if (brokenSegment.contains(new Segment('V', j, i + k))) {
isUnbrokenSquare = true;
break;
}
}
if (!isUnbrokenSquare) {
for (int k = 0; k < size; k++) {
if (brokenSegment.contains(new Segment('H', size + i, j + k))) {
isUnbrokenSquare = true;
break;
}
if (brokenSegment.contains(new Segment('V', j + size, i + k))) {
isUnbrokenSquare = true;
break;
}
}
}
if (!isUnbrokenSquare) {
count++;
}
}
}
}
return count;
}
static class Segment {
char segmentType;
int hLength;
int vLength;
public Segment(char segmentType, int hLength, int vLength) {
super();
this.segmentType = segmentType;
this.hLength = hLength;
this.vLength = vLength;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj instanceof Segment) {
Segment s = (Segment) obj;
if (this.segmentType == s.segmentType && this.hLength == s.hLength && this.vLength == s.vLength) {
return true;
}
}
return false;
}
}
- Makarand September 02, 2017