Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[gkrieg13]

My brother, during a job interview, was asked to find the best algorithm to find the looping point of a linearly linked list that loops back to some point in the middle (so it looks like a P).  The best that we can come up with is n² time, with constant space, or n time with n space.  However, the person doing the interview claimed that he had n time with constant space.  Can any of you think of the answer?  My brother and I have been trying to think of something to no avail.

Can you set the next pointer to null in each node as you go along?  That would ruin your linked list, but it would find the point for you when you get to a node with a null pointer. N time and constant space

[sudgy]

My brother, during a job interview, was asked to find the best algorithm to find the looping point of a linearly linked list that loops back to some point in the middle (so it looks like a P).  The best that we can come up with is n² time, with constant space, or n time with n space.  However, the person doing the interview claimed that he had n time with constant space.  Can any of you think of the answer?  My brother and I have been trying to think of something to no avail.

Can you set the next pointer to null in each node as you go along?  That would ruin your linked list, but it would find the point for you when you get to a node with a null pointer. N time and constant space

Forgot to mention, you can't kill the list too.

(Actually, in the interview my brother found several solutions, including this one, and each time the interviewer asked if there was another way that was better in some way.)

Keep in mind that the guy could have been stupid too and he doesn't actually have a solution.  It would be hard to prove that though.

[gkrieg13]

My brother, during a job interview, was asked to find the best algorithm to find the looping point of a linearly linked list that loops back to some point in the middle (so it looks like a P).  The best that we can come up with is n² time, with constant space, or n time with n space.  However, the person doing the interview claimed that he had n time with constant space.  Can any of you think of the answer?  My brother and I have been trying to think of something to no avail.

Can you set the next pointer to null in each node as you go along?  That would ruin your linked list, but it would find the point for you when you get to a node with a null pointer. N time and constant space

Forgot to mention, you can't kill the list too.

(Actually, in the interview my brother found several solutions, including this one, and each time the interviewer asked if there was another way that was better in some way.)

Keep in mind that the guy could have been stupid too and he doesn't actually have a solution.  It would be hard to prove that though.

Are you allowed to move the list?  Pointers are really just numbers representing memory locations, so you could maybe move them so they are in order and then you know if you get back to the loop part when your pointer doesn’t point to a node anymore because it has been moved. But then you don’t know where in the list you were supposed to be pointing.

Hmmmmm

[Donald X.]

My brother, during a job interview, was asked to find the best algorithm to find the looping point of a linearly linked list that loops back to some point in the middle (so it looks like a P).  The best that we can come up with is n² time, with constant space, or n time with n space.  However, the person doing the interview claimed that he had n time with constant space.  Can any of you think of the answer?  My brother and I have been trying to think of something to no avail.

I've heard this one before. There is an answer.

[blueblimp]

My brother, during a job interview, was asked to find the best algorithm to find the looping point of a linearly linked list that loops back to some point in the middle (so it looks like a P).  The best that we can come up with is n² time, with constant space, or n time with n space.  However, the person doing the interview claimed that he had n time with constant space.  Can any of you think of the answer?  My brother and I have been trying to think of something to no avail.

I was going to accuse that of being a bad interview question because I only knew one solution, which is a bit of a trick answer and not particularly relevant to algorithms you'd actually use. But then I looked up the problem and it turns out there are more easily discoverable algorithms, so maybe it's not so bad after all.

If you get stuck, look on Wikipedia for cycle detection.

[liopoil]

I'm not sure I understand the question. What exactly is n supposed to be? What information exactly are you given and what does each query or whatever tell you?

[sitnaltax]

I'm not sure I understand the question. What exactly is n supposed to be? What information exactly are you given and what does each query or whatever tell you?

This is a slangy way of talking about the efficiency of the algorithm. n is the size of the list. When they're referring to an "n" or "n^2", they're referring to a solution that's O(n) or O(n^2), meaning that as the list grows in size, the time or space needed by the algorithm will grow only by that factor (times some constant) of the input size.

The Wikipedia article is overly technical; CS students get the basics without the tedious mathematical underpinnings, typically in an algorithms course. https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ is a good quick intro.

[liopoil]

I know how run-time works in general, just not sure precisely what quantity n is referring to in this context. If it's the size of the list, I guess my question is exactly how the list is structured. Before I assumed that the list was infinite and it just started being periodic after some point and the period was around n or something. So now I don't have any real idea what a "linearly linked list" is. If it's like, each element points to its successor, or something, I'm not sure what stops you from just like going down the list until you get somewhere you've already been. If it's just a graph shaped like a P or something, then you're just looking for the vertex with degree three. I'm just trying to guess what this structure is at this point... I guess that's what I meant by "What information exactly are you given" - as in what's the data structure.

[sudgy]

I know how run-time works in general, just not sure precisely what quantity n is referring to in this context. If it's the size of the list, I guess my question is exactly how the list is structured. Before I assumed that the list was infinite and it just started being periodic after some point and the period was around n or something. So now I don't have any real idea what a "linearly linked list" is. If it's like, each element points to its successor, or something, I'm not sure what stops you from just like going down the list until you get somewhere you've already been. If it's just a graph shaped like a P or something, then you're just looking for the vertex with degree three. I'm just trying to guess what this structure is at this point... I guess that's what I meant by "What information exactly are you given" - as in what's the data structure.

Code: [Select]

struct Node {
    Type data;
    Node* next;
};
With this, the only operation you can do to traverse the list is go to the next element in it.  You are given the first node, and that's it.

[silverspawn]

Apropos to nothing, this is totally worth rereading

[Titandrake]

If it's like, each element points to its successor, or something, I'm not sure what stops you from just like going down the list until you get somewhere you've already been.

Sure, you can do that, but how do you know if you're visiting a place again, if you're only allowed a constant amount of space to store things?

I agree with blueblimp that this doesn't seem like a good question, I only know the trick solution and it's more like a novelty. (Like the problem of switching a and b without defining a 3rd temporary variable.)

[sudgy]

If it's like, each element points to its successor, or something, I'm not sure what stops you from just like going down the list until you get somewhere you've already been.

Sure, you can do that, but how do you know if you're visiting a place again, if you're only allowed a constant amount of space to store things?

I agree with blueblimp that this doesn't seem like a good question, I only know the trick solution and it's more like a novelty. (Like the problem of switching a and b without defining a 3rd temporary variable.)

Trick solution?  I looked up the solutions and they don't seem like tricks to me.  Complicated, yes, but tricks, no.

[Kirian]

Speaking of time constraints:

There isn't enough time to deeply learn everything I want to know about.
There isn't enough time to shallowly learn everything I want to know about.

There isn't even enough time to learn enough to make a list of the things I want to know about, even if I had started 39 years ago.  Mostly because I don't even know of the existence of many of these things.  (These thoughts are precipitated by reading an article on model-based design, which I hadn't heard of until today.)

This doesn't take into account motivation or available spoons, just actual time.

Someone try to cheer me up?

[LastFootnote]

Speaking of time constraints:

There isn't enough time to deeply learn everything I want to know about.
There isn't enough time to shallowly learn everything I want to know about.

There isn't even enough time to learn enough to make a list of the things I want to know about, even if I had started 39 years ago.  Mostly because I don't even know of the existence of many of these things.  (These thoughts are precipitated by reading an article on model-based design, which I hadn't heard of until today.)

This doesn't take into account motivation or available spoons, just actual time.

Someone try to cheer me up?

Your existence is ultimately meaningless. Any knowledge you do or do not acquire is unimportant.









Did it work?

[Seprix]

Speaking of time constraints:

There isn't enough time to deeply learn everything I want to know about.
There isn't enough time to shallowly learn everything I want to know about.

There isn't even enough time to learn enough to make a list of the things I want to know about, even if I had started 39 years ago.  Mostly because I don't even know of the existence of many of these things.  (These thoughts are precipitated by reading an article on model-based design, which I hadn't heard of until today.)

This doesn't take into account motivation or available spoons, just actual time.

Someone try to cheer me up?

If you invest really hard in life extension/immortality, you might get more time.

[Donald X.]

Your existence is ultimately meaningless. Any knowledge you do or do not acquire is unimportant.

Meaning depends on context, which you provide (and I don't mean, the meaning of words, though, that too).

Devoid of context, meaninglessness is also meaningless. Meaninglessness only gets value from you assigning it value and well I don't recommend it.

[Kirian]

Devoid of context, meaninglessness is also meaningless. Meaninglessness only gets value from you assigning it value and well I don't recommend it.

That is oddly comforting, actually.

[silverspawn]

I actually think pleasure and happiness are inherently meaningful.

[Witherweaver]

[crax]

Should I get an avatar?

[Kuildeous]

Should I get an avatar?

If you don't, then someone will yell at you to choose an avatar. That's how I got this one.

I forgot who yelled at me. Was it Silverspawn? I want to say it was Silverspawn.

[Awaclus]

The problem with people not having avatars is that it's more difficult to tell them apart. It's not as big of a problem as having the same card art as someone else or just a very similar color scheme though.

[Tables]

Having an avatar makes it look like you're a member of the community, rather than someone who just joined and is making a few quick posts. It makes you look a little more unique, rather than just a username posting.

[ThetaSigma12]

Having an avatar makes it look like you're a member of the community, rather than someone who just joined and is making a few quick posts. It makes you look a little more unique, rather than just a username posting.

The best avatars are either a painting of you or dominion art.

[Kuildeous]

Having an avatar makes it look like you're a member of the community, rather than someone who just joined and is making a few quick posts.

I think my 3500+ posts may be a dead giveaway.

I know, not everyone is going to look, but yeesh. I don't normally bother with avatars.