Amazon Interview Question for SDE-2s
- 0of 0 votes
You are given a set of N horizontal lines which are connected by equal number of vertical lines to form squares of size 1x1. Now some segments are removed. You need to count the number of squares of all sizes (1x1, 2x2, ..., NxN) with all sides present.- imunique August 30, 2017 in India
Image : https://he-s3.s3.amazonaws.com/media/uploads/1ce3516.png
In the above example you see four horizontal and vertical lines and few missing segments. Now you need to count the number of squares of all sizes with all sides.
First line is a positive integer N, number of horizontal and vertical lines.
Second line is positive integer M, number of segments removed.
Then there are m lines, each containing V,i,j or H,i,j where i and j are positive integers. H,i,j indicates a horizontal missing segment in the ith horizontal line between the jth and (j+1)th point on the line. V,i,j represents a gap in ith vertical line between the jth and (j+1)th point on the line.
Is the total number of squares in the figure with all sides along the remaining lines in the figure.
Sample Input :
Explanation : Here in this figure we have 4 squares of size 1x1 and 1 square of size 3x3, hence total is 5.
| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm Data Structures Dynamic Programming Online Test Problem Solving
Interview Type: Written Test