This page is still under construction.

Parts of this page are still being built. What you see may change.

SMH

Interview

Time limit1sMemory limit512 MB

Summary
Given heights of up to 11 students in a line, find the maximum number of other students any single student can see, where sight is blocked by any head on the segment.
Level

Medium4 of 10

Topics
Brute force, Geometry, Array, Implementation
Solved
No attempts yet

Problem

Write a function P5:

  • Samin High School has N students in the class of '20. The principal has bad memories involving students whose heights are similar to his own, so he admitted every student with a distinct height (student IDs are not sorted by height).
  • One day, the students lined up in a single straight line on the school field for a health checkup. The spacing between adjacent students is 1 m.
  • The teacher wants to secretly watch the students and picks one of them to act as a lookout. Since the students stand in a straight line, a student cannot see anyone blocked by their line of sight. For example, if the students in order have heights 1 m, 3 m, and 2 m, the 1 m student cannot see the 2 m student.
  • It is not true that a student can always see a taller student or can never see a shorter one. Draw the students on a plane and connect the heads of two different students: one can see the other if there is no obstacle on the line segment. If a head lies on the line segment, they cannot see each other.
  • The teacher wants to select the student who can watch as many students as possible.
  • input parameter: a list A stores each student's height in meters as an integer, ordered by student ID. A[ii] represents student 20-(i+1)(i+1) (e.g.: A[0] → 20-001). Heights range from 1 m to 100 m. The size of list A is at most 11.
  • return value: return the maximum number of students that can be watched.

Examples1

  1. Example 1

    Input
    5
    
    Expected output
    0