#What did they ask?

1 messages · Page 1 of 1 (latest)

barren karma
#

Title

valid cape
#

say the problem

void siren
#

https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/description/

LeetCode
Minimum Distance to Type a Word Using Two Fingers - LeetCode

Can you solve this real interview question? Minimum Distance to Type a Word Using Two Fingers - [https://assets.leetcode.com/uploads/2020/01/02/leetcode_keyboard.png]

You have a keyboard layout as shown above in the X-Y plane, where each English uppercase letter is located at some coordinate.

  • For example, the letter 'A' is located at coordi...
#

however instead of typing a word you wanted to find the min distance between restaurants

#

and the 2d matrix could be filled with any amount of restaurants upto n^2

#

restriction was to O(n^2) for time complexity

static root
#

đź’€

void siren
#

at the end you want to return the starting point with that min dist

static root
#

horrible interviewer to ask that

void siren
#

and apparently you can have more than 1 starting point with a min dist, which i didn't fully understand but 🤷‍♂️

void siren
gentle horizon
#

it's weird that interns they ask that...

#

when did u interview

exotic copper
#

Wouldn’t that be mst on the weighted graph with only those restaurants being nodes

void siren
void siren
void siren
gentle horizon
void siren
#

I TA DSA at my school and prev @ google

#

it was still a hard question for me though

exotic copper
#

Yeah you’d have to precompute the graph first with some math bs

#

But I think ignoring the non restaurants probably doesn’t change stuff right

void siren
#

yeah, i don’t exactly recall but I believe if there were no restaurants then you’d do the min dist between all those non restaurants

#

that wasn’t included in the prompt though, it was an edge case that he gave me

void siren
exotic copper
#

Right so if u have all the restaurant coordinates you could find the edge weight between each pair

#

And then stick this on it

#

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_kruskals_minimal_spanning_tree.htm#:~:text=A minimum spanning tree is,weights assigned to each edge).

Kruskal’s Minimal Spanning Tree

Kruskal’s Minimal Spanning Tree - Kruskal’s minimal spanning tree algorithm is one of the efficient methods to find the minimum spanning tree of a graph. A minimum spanning tree is a subgraph that connects all the vertices present in the main graph with the least possible edges and minimum cost (sum of the weights assigned to each

#

It would be n^2 bc you have to get all the edge weights

void siren
#

yeah i was not thinking of kruskal’s during the interview 💀

#

i should’ve asked if I could look stuff up

exotic copper
#

That’s wild tho Idt I’ve gotten anything like this in an interview

static root
void siren
static root
# void siren .

lmao i TA dsa and prev at amazon. got fucking kokobananas and binary search a sorted list

near pebble
#

Probably no hc so instead of cancelling just gave an impossible interview

void siren
void siren
dreamy kernel
neat hemlock
neat hemlock
#

sounds like this one