Python interview with an Apple engineer: Count islands



Book a mock interview or coaching session with an Apple engineer as early as tomorrow on interviewing.io! Sign up here: https://interviewing.io/signup?utm_source=youtube.com&utm_medium=referral&utm_campaign=video_link

Check out the feedback by the Apple interviewer and the full transcript on https://interviewing.io/recordings/Python-Apple-1/

Or view other Python interviews: https://interviewing.io/python-interview-questions

Disclaimer: All interviews are shared with explicit permission from the interviewer and the interviewee, and all interviews are anonymous. interviewing.io has the sole right to distribute this content.

source

9 thoughts on “Python interview with an Apple engineer: Count islands”
  1. Hi, what position where you interviewing for? I’m applying to test engineer position and have a coding exercise. Just wonder what the complexity is going to look like.

  2. One approach for this could be:
    1) maintain a list of coordinates already processed
    1.1) maintain a count of total islands
    2) traverse matrix standard for loop way
    3) for each coordinate determine if it is a piece of land
    4) if it is a piece of land, DFS(right negihbour, bottom neighbour)
    5) in the DFS function, base case is if current coordinate == 0
    6) if not 0, then add coordinate to processed set and DFS on right and bottom neighbour
    7) once original DFS call returns, add a delimiter to processed coordinate list (this seperates one island from one another) and update island count
    8) continue traversing the matrix and only DFS'ing on coordinaate if non 0 and not in processed

  3. Basic dfs question where you visit all the neighbors of 1 and mark them all -1. You repeat dfs until you got no 1s in the matrix and the no of times dfs runs would be the no of islands I guess.

  4. error is on line number 39.
    it should be" 0 <= future_x < row_len and 0 <= future_y < col_len …….."

  5. My instinct with this would be to implement a flood-fill algorithm (as a helper function). Then, pick a random 1 coordinate, flood-fill from that point to get all the other 1's on its island, yield that island's coordinates, then set all those coordinates to 0 and repeat. I guess DFS ends up being equivalent to BFS though.

Leave a Reply

Your email address will not be published.

Captcha loading...