A robot cleaner interview question I was stuck on, how would you guys approach it?

New / Eng AirCoinHub
Dec 31, 2017 22 Comments

Design a robot cleaner algorithm with 4 given APIs and a starting position in an unknown space (with obstacles in random locations)

The 4 APIs are:
clean(): clean the current location.
turnleft(k): turn left k*90 degrees.
turnrigt(k): turn right k*90 degrees.
move(): move forward for 1 position, return False if that’s not possible.

How do you clean the entire space?

comments

Want to comment? LOG IN or SIGN UP
TOP 22 Comments
  • Airbnb / Eng
    Cppjavapy

    Airbnb Eng

    PRE
    Facebook
    Cppjavapymore
    Isn’t this just exploring every node in a graph?
    Dec 31, 2017 0
  • New / Eng
    RhoSigma

    New Eng

    PRE
    Amazon
    RhoSigmamore
    Simple DFS with recursive implementation (DFS is better than BFS in this scenario as less tiles are covered multiple times on average). Also didn't you sign an NDA for this company's interviews?
    Dec 31, 2017 3
    • Microsoft vishnu
      Lol NDA
      Dec 31, 2017
    • Apple StYE24
      How do you ensure that you don’t get in a cycle, you need to create the graph as you go
      Jan 1, 2018
    • New / Eng
      RhoSigma

      New Eng

      PRE
      Amazon
      RhoSigmamore
      I mean of course the visited coordinates set
      Jan 1, 2018
  • Amazon / Other Honk
    Place phone call to local human cleaning service.
    Dec 31, 2017 0
  • Apple StYE24
    Breath first search on a graph. Each node needs a marker if it was cleaned or not and what it’s world frame coordinates would be. When new nodes have been created see if that node already exists if not add it to a kd tree. To deal with multiple paths to the same place

    I don’t think A* can help much here unless you have more information or the robot has probabilistic completion of actions
    Dec 31, 2017 2
    • Google Noogler69
      Breadth-first? The robot is going to teleport?
      Dec 31, 2017
    • Apple StYE24
      Oops good catch I meant to say depth first, breath is wrong for this problem due to the cost of as you say “teleporting” being non zero. The cost of compute is insignificant compared to travel time
      Dec 31, 2017
  • Intel / Eng Litecoin
    iRobot is hiring, huh?
    Dec 31, 2017 0
  • Apple / Eng
    BoseDK

    Apple Eng

    PRE
    Apple
    BoseDKmore
    I’d divert their attention to the security of this algo. What if hackers replace the call to clean with an implementation for fart ?
    Dec 31, 2017 1
    • Amazon / Eng
      Hooliganss

      Amazon Eng

      BIO
      Engineer at AWS
      Hooliganssmore
      Indeed, this issue raises serious problems.
      Dec 31, 2017
  • Microsoft / Eng
    Sugardaddy

    Microsoft Eng

    PRE
    Amazon
    Sugardaddymore
    Didn’t you sign NDA?
    Jan 3, 2018 0
  • Amazon Vacuum
    What level were you interviewing for?
    Dec 31, 2017 3
    • New / Eng AirCoinHub
      OP
      Entry level big N
      Jan 1, 2018
    • Amazon / Eng party-n-bs
      Wait, N as in Netflix? Since when does Netflix have entry level eng positions?
      Jan 1, 2018
    • Airbnb / Eng
      UserFy

      Airbnb Eng

      PRE
      500 Startups
      UserFymore
      Big N just means one of the top tech companies, usually a mix of Google/Facebook/Microsoft/Amazon
      Jan 1, 2018
  • Amazon / Eng party-n-bs
    Agree with others. DFS, maintain a set of visited "nodes" to prevent going in a cycle, backtracking to ensure you navigate around obstacles
    Jan 1, 2018 0
  • Zillow Group ghoop
    1.Left-forward until false-right-forward(break if false)
    2.left forward until false-left forward (break if false)
    Do steps 1 and 2 alternatively
    Dec 31, 2017 0
  • Apple / Eng SgtTickles
    This is literally a graph traversal problem.

    Simplest way is probably DFS.
    Jan 5, 2018 0
  • Netflix / Eng
    Rj@4r

    Netflix Eng

    PRE
    500 Startups
    Rj@4rmore
    This is painting algorithm, classic
    Jan 2, 2018 0
  • Amazon AyYD45
    Check graph section on hackerrank
    Jan 1, 2018 0

Salary
Comparison

    Real time salary information from verified employees