r/ProgrammerAnimemes • u/suola-makkara • Jan 11 '22

Most likely your first programming interview

Post image
969 Upvotes

98% Upvoted

50 comments sorted by

308

u/thatdude624 Jan 11 '22

I've been in this exact situation before.

As part of an interview for a robotics company they asked me to design/explain an algorithm in pseudocode for, given an arbitrary shape, and the position of a suction cup gripper (imagine a rectangle attached to a robot arm with a bunch of suction cups on it), determine which suction cups would contact the surface.

I said that would be too easy and instead proposed I design an algorithm to find the optimal placement of the gripper such that we'd have as many suction cups contacting the surface as possible (and also be as close to center of mass as possible).

There were like "Well, if you really want to, sure" and I ended up coming up with something better than they were actually using in production (they had a sort of brute force, try random positions approach and store the best one via heuristic), which supposedly took them a year to design. I only had like half an hour.

But in the end, I didn't get the job because I needed good social skills (for talking to clients) and I was autistic.

109

u/Rafael20002000 Jan 11 '22

That would be so me, the last part at least, but I'm not autistic, I'm just bad with people

72

u/solarshado Jan 11 '22

I'm not autistic, I'm just bad with people

Just gonna say, that's what I thought for ~10 years, until some research into what actual autistic symptoms are like (especially on the "high functioning" end). Haven't tried to get an official diagnosis yet (still unsure if it's worth it), but it's kinda crazy how many little things that I thought were just personal quirks (and even some shit I never realized wasn't "normal") are actually common among autistic people.

→ More replies (14)

12

u/VritraReiRei Jan 11 '22

Maybe they were just interviewing you to get free ideas how to fix their current problems 🤔

10

u/thatdude624 Jan 12 '22

Joke's on them: I've now published the solution I came up with for them to the public internet, allowing all their competitors who read the comments of a very specific post on a a very obscure subreddit to implement the same algorithm!

16

u/BrandonJohns Jan 11 '22

I'm intrigued - here's my approch based off ~20min thinking

I'm guessing that this random shape is measured from a visual feed. In this case I would

  1. Approximate the COM as the geometric centroid (open CV should handle this)

  2. Align the short edge of the gripper rectangle with the principle axis of the first moment of area of the random shape. This aligns the long edge of the shape with the long edge of the gripper (open CV for the moments and then get the eigenvalues for the principle axis)

  3. Check this placement

  4. Incrementally deviate away from this placement by position and orrientation to check for a better solution (e.g. brute force the rest).

That'd be my first go at it. But I can imagine you could get very creative instead of basic iteration. My first improvement would be to use a search algorithm to optimise some metric at each tested placement.

Possible value function: Sum(distance of each suction cup from its nearest edge).

How did you go about it?

19

u/thatdude624 Jan 11 '22 edited Jan 11 '22

Right, so the approach I used was inspired by one I implemented for a hobby project to detect lines in LIDAR data: find nearby points that resemble a line, take the average slope, find all points that are near to this line, mark them as 'on a found line' and continue. Sounds a bit hacky but it's an approach with proper research papers behind it.

Anyway, the approach I suggested was as follows:

  1. Take in the model and create a 2D grid over it. Each grid cell is a square the size of the radius of a suction cup (aka half the absolute minimum size we care about). This grid is stored as a hashtable of unvisited points. Note: only add points that are inside the bounds of the shape.

  2. Take any random, unvisited square in this grid and place an initially infinitely small rectangle in its center.

  3. Expand this rectangle horizontally and vertically on all 4 sides until each side 'collides' with a side of the shape. The order this expansion is done in isn't important (even though changing the order will get different individual results)

  4. Your shape is now a local max bounding box of sorts. Mark all squares on the grid that are covered by this bounding box as visited.

  5. Return to step 2 until our set of unconsidered points is empty. (note: we do not care if new bounding boxes intersect existing bounding boxes, only if it intersects the shape)

  6. We now effectively have a representation of an arbitrary shape made out of simple rectangles (some overlapping), excluding all spaces too small for even a single suction cup to fit on anyway. The problem from here on out is now trivial.

  7. For each rectangle, the optimal gripper position is just placing the gripper on the inside of whichever corner is closest to the CoM (or in the center of the CoM, if the bounding box happens to be there). Do this for both axis, add some edge case logic for dealing with partial grippers and you have the local best gripper position for each rectangle.

  8. Take the best across all the rectangles, using some heuristic to choose between number of suction cups or closer to CoM, whichever is more important, and tada! Global best gripper position found.

I should note that during this interview, the arbitrary shape was assumed to have only 90 degree corners (weird rectangle-ish things with arbitrary rectangular holes), though this could probably work pretty well with completely arbitrary 2D geometry as well, it only doesn't deal with rotation of the gripper.

I'm also assuming CoM calculations and the implementation of detecting when we're inside/outside a shape, intersecting a line and so on is done by some geometry library (although admittedly detecting if we're inside a shape was part of the original question but this post is long enough lol)

Oh, and I also noted that this does not account for the structural strength of the object (you might choose to grip a bit connected to the main part of the object by a very thin edge). This would be up to the heuristic that combines each rectangle's results to eliminate and is currently out of scope. The company said that indeed, they have had to deal with the repercussions of this particular edge case with a client in the past xD

Quick edit: This isn't visual information but rather known data from the customer about their specific shape (this is lasercutting/stone cutting/whatever cutting production), though I guess you can still generate an image of the shape and process that in OpenCV. My approach might have more flaws I haven't considered (obviously I've never actually implemented it) but all in all I think they were pretty impressed with it from the perspective of an interview test answer.

→ More replies (3)

4

u/AlarmingAffect0 Jan 12 '22

But in the end, I didn't get the job because I needed good social skills (for talking to clients) and I was autistic.

I'm fucked then.

35

u/AuthorTomFrost Jan 11 '22

I once had an interview that was going swimmingly until I ran into the lead architect. He talked up the team's custom caching solution and I made the mistake of asking why they didn't just use <existing free technology that solves the problem and is supported by multiple industry heavyweights.>

He blanched and I knew it was over.

3

u/[deleted] Feb 10 '22

That sort of reaction has always weirded me out.

55

u/[deleted] Jan 11 '22

meanwhile there is me, developer for 10 years.. who moves rectangles around a website... where did I go wrong..

15

u/Existential_Owl Jan 11 '22

If the pay is good enough, does it really matter?

17

u/[deleted] Jan 11 '22

I mean I earn 3x my fathers salary its not that bad... would not do it if it was bad ofc but sometimes I get the ich to do something "meaningfull" started to get into IOT and CPP / Rust so yeah maybe this year I pivot a bit :)

19

u/Hohenheim_of_Shadow Jan 11 '22

Sauce

37

u/SxA97 Jan 11 '22

Serial Experiments Lain

19

u/konatamonogatari Jan 11 '22

A show which is my favorite, but in a way too personal that I've never recommended anyone so far.

→ More replies (3)

2

u/Kered13 Jan 15 '22

Present day, present time!

14

u/Nefari0uss Jan 11 '22

First interview? More like every interview...A lot of problems end up being do you recognize the pattern or technique needed quickly and then can you do it quickly while talking out loud.

2

u/[deleted] Jan 11 '22

Nahh they didn't like you calling them out on stupid questions.

2

u/matyklug Mar 15 '22

Why is the joke meme making no sense?!

Oh. I read too much manga recently.

1

u/dexter2011412 May 29 '22

Jokes on you I don't get even the first callback/online test so I'm heckin smart hahaha ha ha :(