So this happens to us as well. One ticket someone is working on is required for the ticket you are doing. For our team we would had moved that ticket to “blocked” and then picked up the next ticket. If there was no next ticket, I would reach out to the ticket owner and offered help. If nothing, that’s when I would pull the next ticket in the backlog.

Yea DFS would had worked as well.

Not speaking of how to handle this particular situation, but speaking to the optimal handling of this common scenario.

A slack message "Hey x, I'm working on TICKET#(link to ticket) and it is blocked by your TICKET#(link to ticket)".

Quickly discuss civilly the status of the blocking ticket.

If after convo you are still blocked, work on something else.


The civil discussion from the other persons side should basically always be 1) I'm working on it and want to continue, time is X or 2) I haven't got to it yet, have at it.

None of this really makes sense to me, because I visualize trees as being very different from grids. Like, for this:

1,0 and 0,1 both have 1,1 as children, so that becomes weird in the context of traversal algorithms.

Going back to the potential solution I described earlier:

Would you describe this as BFS, DFS, or neither? (I think it's O(n) for some multiple of n but I'm not positive)

How is it like 1/2 of the people ITT work at terrible places with awful people? Weird. My place isn't amazing but its certainly not a ****show. We just have people that do their jobs. IDK.

Ok, so it sounds like she is busy with whatever she thinks is important and is pissed that you don't understand the pecking order, which is that if your issue is being blocked by her issue, you stfu and remain silent until she submits her code and unblocks your issue because she is more senior and already knows that your issue is being blocked by her issue and has prioritized better uses of her time. And on top of that, she disagrees with the code you wrote to unblock the issue yourself.

I would find some outside mentors and have them review the code that you wrote and then the changes that she requested (for this issue and other issues) and try to determine if they agree with you or her and maybe they can have some insight into what you might be doing wrong or if she is just OCD.

Also breaking down tasks to the level of "you write a switch statement that calls templates" and "you write the template html" feels like it could be a little over-agile. If they're really that intertwined maybe just have one person handle it.

It's really a graph rather than a tree

Whether this is BFS or DFS sort of depends on the nature of your recursion. You can reorder recursive visiting functions to turn them from BFS to DFS and back.

I honestly go back and forth a bit on whether it's O(n^2) or maybe it's better. Naively it's O(n^2) because you have to visit n cells and for each cell you have to find all connected pieces which is coupled to the size of n also. For a signifcant number of searches, you'll get to quit early - a lot of the ones you quit early, you get to quit in constant time (if the cell is already covered, or if all it's neighbors are covered). So the question is, are the constant-time cell visits proportional to n? So the real answer might be O(nlogn) or O(n sqrtn) or something. I don't think it can be O(n) though

On the ****ty job front: I mostly think of myself as having a "good job" and I sort of think of that of a lot of my past jobs too. But also, I have quit almost all the jobs I had because I didn't want to work there any more, so at least at some times, I've thought almost every job I had sucked. For me I guess I go through cycles, if other people are the same then I guess at some point a percentage of us will describe our jobs as ****ty.

Lol, yeah this part seems pretty crazy to me.

My interviewer didn't steer me towards implementing any recursive logic for this grid problem fwiw.

I don't necessarily mean "recursive" literally, though it could be implemented that way - just that once you find an island, you check all neighbors (and their neighbors, and their neighbors) until you exhaust that island. You could do it iteratively with a queue of points to check also.

Thinking about it a little more, you could split the solution into two parts where the first part is straight O(n) - iterate over the whole grid, tag land squares with an ID from a rising counter you keep track of, if neighboring land tiles are already marked you can use the same ID as the neighbors - but, instead of exhausting an island when you hit it, just keep iterating linearly. Then have a second map that tracks the relationships between separate IDs, such that if you tag one peninsula of an island and then hit another peninsula that you tag with a different ID, eventually you run into a point where those IDs neighbor each other and you mark that they're part of the same island.

Then, when you finish iterating, you collapse the different IDs you've tagged into the number of islands, based on which ones border each other. I'm not sure exactly what that algorithm looks like without thinking more but it's probably not very complex.

Getting O(n log n) looks reasonably straightforward to me with the approach goofy mentioned, idk if it's possible to do better than that.

Rough idea for O(n log n): Assign an id to every land tile and keep track of connections to direct neighbors. Then iteratively merge connected tiles into blobs, keeping track of connections with other blobs. The minimum size of connected-but-not-yet-merged blobs doubles in each iteration, so we need O(log n) iterations to ensure we merge everything possible. Keeping an iteration at O(n) overall seems straightforward as both # tiles and # connections are clearly O(n).

Yes this is the genesis of the issue. But you can guess who's idea that is and where I stand on it.

re: the island problem.

What about something like this:

1. Pick a random unvisited point on the grid
2. If it is water, mark it as visited and goto 1
3. If it is land, mark it as visited then:
3.1 walk north and mark each land point as visited until you reach the water
3.2 walk south and mark each land point as visited until you reach the water
3.3 move east one square and repeat 3.1 and 3.2, repeat until you reach the eastern "shore"
3.4 move west and repeat 3.1 and 3.2, repeat until you reach the western "shore"
4. When you've exhausted that current island of visited land, increment the island counter by 1

Not sure of the O-complexity. You're only visiting each square on the grid once and marking them, but I don't know how fast the "visit a random unvisited square" part is.

The following is O(n log n):
Maximum # of merge calls is O(n) as it's linear with the # of tiles, the merge itself consists of a constant time merge of the linked lists, and the update of the island pointer.

Complexity: Since only the tiles of the smaller merged island are updated, the size of the merged island is always at least twice as big as the number of updated tiles. This means any given tile can be updated at most log2(n) times, as the resulting island for the next merge would be larger than the # of total tiles. So we have at most O(n log n) tile updates total.

gl victor.

Nice!

The island problem wouldve been one of the more trivial problems in my computational geometry class but I can’t think of a solution that isn’t trivially much better than O(n)

Not sure what you mean here. The problem has a trivial lower bound at O(n), it's obvious that you can't possibly do any better than that because you already get there by merely processing the input definition for your n grid tiles.

I don’t think it’s obvious at all that you can’t do better than that.

You propose that there may be an algorithmic solution where the worse case is better than O(n), meaning you can find the # of islands without at least reading a constant fraction of the input grid?

Counter example: If your input grid is a chessboard pattern, you clearly need to read every single tile, because flipping any given tile would change the # of islands. This already limits your worst case to be at least O(n).

I'm fascinated by these kinds of problems that a kid can do with their eyes in a few seconds but telling a computer how do it is hard. It feels like there be some easier way to simulate what our brains can do. The bar graph holding water thing I posted is similar.

I guess the main issue is that when a kid starts the board already exists and land vs. sea is known to the kid. Whereas a computer has to ask about each square individually.

Well maybe not. If you assume the grid is created and the program already knows which is land and sea - why can't it find some way to "eyeball" it, like a kid would?

I said trivial better than O(n) – meaning by a constant factor. Lol. I wasn’t implying or saying there is a log n solution even though there may be, I haven’t thought about the ****ing problem enough clearly.

I think you're underestimating how much went into teaching the kid how to do it. The billions of years of evolution for our eyes and brains to create the pattern recognition and reasoning ability to recognize distinct shapes and count them. And then the hundreds/thousands of days where the kid is constantly exposed to an environment that reinforces those evolutionary traits.

If you had a computer with a built in neural network, then it would figure it out for itself pretty quickly given the input/output parameters of the problem and a tester that would judge the output.

A constant factor times n is O(n), regardless of what the constant is.

What's the O(n) solution for this?

The only thing I can think is if there is somehow some trick as to knowing the width and height that you could create some type of key to determine how many islands there are based on the number of land spaces. Like "this is a 5x5 island with 11 land spaces, check these 10 spaces to see if they are land or island and you'll know how many islands total there are"

But I'm sure that's a terrible idea.