## 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.File;
import java.io.IOException;

import com.code.saurabh.util.UtilClass;

public class PolygonDiagonal {

public static void main(String[] args) {
try {
} 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;
}

for (int i = 0; i < totalTest; i++) {
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;
}
}

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

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

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

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.