## Amazon Interview Question for SDE1s

Country: India
Interview Type: Phone Interview

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

``````package com.code.saurabh.misc;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

import com.code.saurabh.util.UtilClass;

public class PolygonDiagonal {

public static void main(String[] args) {
try {
readInput ("Inputs/polygon.txt");
} catch (NumberFormatException | IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}

private static void readInput(String filename) throws NumberFormatException, IOException {
File file = new File (filename);
if (!file.exists()) {
return;
}

FileReader fr = new FileReader (filename);
BufferedReader br = new BufferedReader (fr);
int totalTest = Integer.parseInt(br.readLine());
for (int i = 0; i < totalTest; i++) {
String[] NK = br.readLine().split("\\s+");
int N = Integer.parseInt(NK[0]);
int K = Integer.parseInt(NK[1]);
System.out.println("N: " + N + ", K: " + K + " -> " + calculateDiag (N, K));
}
}

static int calculateDiag (int N, int K) {
/*It can create a diagonal with all other vertexes than immediate neighbors and its own vertex (count 3) */
int maxDiagonal = N-3; //Maximum number of diagonals from a vertex
int totalDiagonal = 0;
if (maxDiagonal <= 0) {
return 0;
}

if (K > maxDiagonal) {
return 0;
}

/*This method calculate how many diagonal can be created from a single vertex given constraint*/
int pointDiagonal = singleVertexDiagonal (K, maxDiagonal);

totalDiagonal = pointDiagonal * N;
if (K == 1) {
totalDiagonal = totalDiagonal/2;
}
return totalDiagonal;
}

private static int singleVertexDiagonal(int k, int maxDiagonal) {
return factorial (maxDiagonal) / (factorial (maxDiagonal-k) * factorial (k));
}

public static int factorial (int N) {
if (N == 0 || N == 1) {
return 1;
}
return N * factorial (N-1);
}
}``````

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

run following file:
8
3 1
4 1
5 2
5 3
6 1
6 2
6 3
6 4

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

I see one problem with your solution. You don't consider combinations where not all diagonals start from one vertex. For example, if you hava a polygon with six vertexes (1,2..6) and you ned to put two diagonals your code will ignore the pair of diagonals (1,5) and (2,4).

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

This is a classic combinatorial problem. Google "PolygonDiagonal".

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

Can You please tell how did u arrive at the logic for singleVertexDiagonal ?

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

``calculate: (N*(N-3Ck)) / ((N-3)/k)``

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

My idea is to draw a diagonal and divide the polygon

``````NonIntersectingDiagonals(N, K)
{
totalSolutions=0;
if(K==1) return N*(N-3)/2;
if(N<4) return 0;

for(int i=3;i<=N-1;i++)
{
for(int j=0;j<=K;j++)
{
totalSolutions += NonIntersectingDiagonals(i,j)*NonIntersectingDiagonals(N-i+2, K-j);
}
}
return totalSolutions*N;
}``````

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