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++)
                    result.add(Square.of(new int[]{x, y}, s));
        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";
        }
    }
}

- Makarand September 02, 2017 | Flag Reply
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>();
        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;
        }
    }
}

- alex.climov September 10, 2017 | Flag Reply
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")

- unblendme September 13, 2017 | Flag Reply
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) {
		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 + "]";
	}

	
}

- Suruchi November 01, 2017 | Flag Reply
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;
		}
	}

- lokesh.kmr.mishra December 17, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More