Amazon Interview Question for SDE-2s

Country: India
Interview Type: Written Test

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

``````package com.home.careercup;

import java.util.*;

/**
* N lines ( vertically and horizontally) can form a N -1  x N -1 grid.
* <p>
* Also, using combinatorics  we know how many squares are there in a
* M-1 x N-1 grid.
* it is sum ( M-1 x N-1 + M-2 x N-2 + .. +1 x1 )
* But, I did not find any way (formula) to determine number of squares destroyed
* (of various sizes) when sides/segments in (inside) the grid are destroyed
* <p>
* Edges are stored using a flyweight pattern
*
* @version 1.0
*/

public class MatchStickProblemSolver {
public static void main(String[] args) {
final int N = 4, M = 4;
MatchStickProblemSolver solver = new MatchStickProblemSolver();
List<Square> squares = solver.gridFill(new int[]{0, 0}, M, N);
System.out.println(squares);
int totalSquares = squares.size();
int totalSides /*edges*/ = Edge.edgeCount();
System.out.println("total edges created=" + totalSides);
System.out.println("total squares created=" + totalSquares);

Edge[] remove = new Edge[]{
Edge.of(new int[]{1, 0}, new int[]{1, 1}), // h 2,1
Edge.of(new int[]{2, 0}, new int[]{2, 1}), // h 3,1
Edge.of(new int[]{1, 1}, new int[]{2, 1}), // v 2,2
Edge.of(new int[]{2, 1}, new int[]{3, 1}), // v 2,3
};
int squaresDestroyed = 0;
for (Square s : squares) {
for (Edge e : remove) {
if (s.containsEdge(e)) {
squaresDestroyed++;
System.out.printf("Removal of Edge %s dissolves %s%n", e, s);
break; // important
}
}

}
System.out.println("destroyed squares " + squaresDestroyed);
int remainingSquares = totalSquares - squaresDestroyed;
System.out.println("Squares remaining " + remainingSquares);

/*
** sample output ** for input grid 3x3 ( M=N=4)
total edges created=24
total squares created=14
destroyed squares 9
Squares retained 5
*/

}

/**
* @param left co-ordinates of left top corner
* @param M    number of vertical lines
* @param N    number of horizontal lines
* @return all squares of all possible sizes
*/
List<Square> gridFill(int[] left, int M, int N) {
List<Square> result = new ArrayList<>();
for (int s = 1; s <= Math.min(M - 1, N - 1); s++)
for (int x = left[0]; x + s <= M - 1; x++)
for (int y = left[1]; y + s <= N - 1; y++)
return result;
}

static class Edge {
int[] e1;
int[] e2;

static Edge of(int[] a, int[] b) {
Edge e = new Edge();
e.e1 = a;
e.e2 = b;
cache.putIfAbsent(e, e);
return cache.get(e);
}

static int edgeCount() {
return cache.size();
}

;
private static Map<Edge, Edge> cache = new HashMap<>();

@Override  /* auto generated */
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Edge)) return false;
Edge edge = (Edge) o;
if (!Arrays.equals(e1, edge.e1)) return false;
return Arrays.equals(e2, edge.e2);
}

@Override /* auto generated */
public int hashCode() {
int result = Arrays.hashCode(e1);
result = 31 * result + Arrays.hashCode(e2);
return result;
}

@Override
public String toString() {
return "E{" +
"" + Arrays.toString(e1) +
"," + Arrays.toString(e2) +
'}';
}
}

static class Square {
int[] left;
int[] right;
List<Edge> edges = new ArrayList<>();
int size;

static Square of(int[] left, int[] right) {
Square q = new Square();
q.left = left;
q.right = right;
q.size = Math.abs(left[0] - right[0]);
q.populateEdges();

return q;
}

static Square of(int left[], int size) {
return Square.of(left, new int[]{left[0] + size, left[1] + size});
}

/**
* adds all the edges that form the sides of this square shape
*/
private void populateEdges() {
if (edges.size() > 0) return; /* safety check */
int[] left = this.left;
int size = this.size;

// add horizontal segments for sides
for (int row : new int[]{left[0], left[0] + size})
for (int j = left[1]; j < left[1] + size; j++)
edges.add(Edge.of(new int[]{row, j}, new int[]{row, j + 1}));

// add vertical segments for sides
for (int col : new int[]{left[1], left[1] + size})
for (int j = left[0]; j < left[0] + size; j++)
edges.add(Edge.of(new int[]{j, col}, new int[]{j + 1, col}));

}

boolean containsEdge(Edge e) {
for (Edge f : this.edges) {
if (f.equals(e)) return true;
}
return false;
}

@Override
public String toString() {
return "Square{" +
"left=" + Arrays.toString(left) +
", right=" + Arrays.toString(right) +
", size=" + size +
", edge count=" + edges.size() +
", edges=" + edges +

"}\n";
}
}
}``````

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

``````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>();

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);

int r = e.e+2;
while(r<=N){
sb.delete(2,3);
sb.append(r);
r++;
}
int l = e.e-1;
while(l>=1){
sb.delete(1,3);
sb.append(l);
sb.append(e.e+1);
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;
}
}
}``````

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

``````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")``````

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

``````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) {
System.out.println("Enter the number of lines: ");

System.out.println("Enter the number of segments to be removed: ");
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[] details = removedSegDetails.split(",");
Segment removedSeg = new Segment(details[0], new Integer(details[1]).intValue(), new Integer(details[2]).intValue(),false);
}

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);
}
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())
{
}
}
}
}

}

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())
{
}
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())
{
}
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())
{
}
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 + "]";
}

}``````

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

``````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;
}
}``````

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.