>data structures test
>"Traverse a singly linked list backwards in O(n) or quicker"
STANDING
ON THE EDGE
>data structures test
>"Traverse a singly linked list backwards in O(n) or quicker"
STANDING
ON THE EDGE
Well, what's the problem here?
You CANT do that. The problem was actually to find and remove elements AND traverse it backwards, all in O(n).
It's theoretically IMPOSSIBLE
You mean removing EVERY element?
No, just ones on a predicate.
What if the single link was backwards instead of forwards :^)
that wasn’t the fucking question though
NO FUCK YOU THAT DOESNT COUNT
(define (reverse-traverse f l)
(if (not (null? l))
(begin
(reverse-traverse f (cdr l))
(f (car l)))))
What are you, retarded?
traverse while creating a new reversed singly linked list
O(n) time
O(n) space
>count the elements in O(n)
>create array of size n
>dump the list into the array - O(n)
>traverse that backwards
>O(n) time and space
>3n
That's like 2n so it don't count
They're the same thing. Don't you understand big O notation?
>That's like 2n so it don't count
Do you think this is a motherfucking game?
>That's like 2n so it don't count
lol
user has clearly failed their test
Oh no, poor OP is retarded ;-;
It's possible, idiot.
hahahahaha im an electrical engineer and even i know this lol, good luck with your test noob
Use recursion faggot.
>doing OP's homework for free
who is the retard now?
It took 20 seconds to write.
Wtf that's literally moving the goalpost.
Also, is a possible solution. Probably not the most efficient solution, but it clearly achieves O(n) complexity.
>look at me, i can write in a useless language the kool kids on Jow Forums hype!!!
>2n
Just drop out already
How the fuck are you supposed to know this crap they didn't show it on the lectures. do they actually expect us to make shit up on the spot like geniniouses? the FUCK
Klossie taught me :)
Not that I am using it now, since I code frontend, but it helped me get through the interview!
if you need to cram
drive.google.com
You either go to a good university or just start reading SICP.
t. self taught CS and doing math at university
This is actually fairly useful and concise, despite me already having gone through my data struct classes. Thanks, user.
>40 fucking pages
ooooooooooooooooooooooooooooooooffffff
are you having a stroke?
Two types of people.
Do you find that hard to understand or something?
Thank you. Can't wait for retards who don't know how to program to be shoveling horse shit in the industry more than they are now.
You have done the world a service.
It could be a quintillion*n but the complexity is O(n).
No, you're the problem. Stop blaming the teachers for your mental condition.
Try again next life.
>the absolute state of CS majors
Yeah it's cryptic high-level shit. You can't even tell if what complexity it is.
Put elements on a stack and pop it you mong.
std::list
lol
You're clinically retarded. First of all you can create a second list reversed from the first one in O(n) and then follow that in O(n) which is total time O(n). Secondly you can use a recursive algorithm (post-order improper binary tree traversal where all nodes are connected on the same side). That is also O(n).
I seriously hope you're the only one who failed to understand this.
Otherwise tell your classmates to fuck off elsewhere.
We already have enough crappy devs out there.
You should probably reverse the list in O(n), print it or w/e the question required, reverse again.
This also has a space complexity of O(1).
But that's CS101 level stuff and I'm assuming "data structure test" means a test in a data structure course, in which this question would be way too easy for a test.
>all these people acting superior
>first day on Jow Forums
I'm sorry you're angry user.
They very likely did explain that, but you were unable to understand it because it's in math notation and you slept through those lectures.
Nigga
Ok i actually feel bad for you. Do you have vr chat? I will literally tutor you analysis of algorithms from back to front
They are acting that way because they actually are superior in this case.
list is the linked list and e is the first element
function backwardsTrasverse(element e, linkedList list)
if (e.hasNext())
backwardsTrasverse(e.getNext(), list)
else
visit(e)
I meant to write traverse
Forgot a step
function backwardsTraverse(element e, linkedList list)
if (e.hasNext())
backwardsTraverse(e.getNext(), list)
visit(e)
else
visit(e)
>3n
>2n
It's over, drop out already. You can still blame "muh calculus" for your failure.
I actually laughed at this one
I have google +
i want to do things for you in return user
Well. At least I'm not this stupid. thank you for making my day better op.
>still no faster than O(n) solution
How's intro to java treating you freshmen?
It is impossible to traverse a linked list faster than O(n).
Sure it is, just pull out any loophole like the last 60 posts did
>his linked list isn't actually a hash map under the hood
Jeepers creepers
>she doesn't know
Never gonna get past the interview
Hashmap traversal is also O(n). It's indexing which is O(1).
ok can someone explain to me why i had to suffer through calc 3 and linear algebra to do this sh!t? how is that math helping me here understand big O notation
It's not, Big O is calc 1. Literally the definition is
F(x) / G(x) -> N
x ->oo
>suffer
>basic math
good job, you're retarded
calc 3 and linear algebra should be minimum requirements to vote
Why what's that got to to do with voting?
effective bait
it would eliminate retards on all sides, the liberal arts degrees sjws and trash fighting Trump Hicks
because math is racist and it shouldnt even be forced upon people of color.
I don't want to live in the hellscape where all policy is decided by 1st year engineering dropouts
No, it would leave behind an infinitesimal minority of angsty spergs who enjoy calc 3 and LA.
A singly linked list cannot be reversed in place. By definition, it contains no back pointers. To access a previous node without scanning the entire list again from the start, you must either keep a reference to it explicitly, or you must use the call stack with non-tail recursion. Either way, you use O(n) space to make all previous nodes accessible.
>
I was expecting some unintelligible scribbles, ended up saving.
its time we move beyond meritocracy. being qualified on paper for something doesn't mean you should actually belong there. its almost 2019 sweeties
Neat, thanks and saved.
>A singly linked list cannot be reversed in place.
struct Node
{
Node *next;
Elem elem;
};
void reverse(Node *cur)
{
Node *prev = nullptr;
while (cur)
{
Node *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
}
Danke very mucho
Brainlet here. How is it possible to go backwards in a singly linked list, when each node only points forwards?
Use recursion or an explicit stack.
I think I'm just mistaking which direction is which. It doesn't seem possible to go backwards when a node only has a pointer to the next node, but not the node behind it. I don't think any trickery can get around that.
If you only have a pointer to a node halfway through the list then you can't start going backward, sure. But that's not what traversing means - it means calling a function on every element in the list, or something like that. You can easily make sure that the functions are called in reverse order even if you start at the beginning of the list.
Are there any lists you can reverse in sub O(n) besides XOR lists?
Oh, that makes sense. Thanks.
Calc 3 and LA aren't even qualifications on paper, unless you're looking to enroll in 2nd year courses
show(){
if(next != null) next.show();
print(name);
}
Get it now? It's basic recursion. Or you could just reverse the list or use a stack.
It's called "thinking." A properly designed curriculum teaches you the fundamentals of a topic such that when you go into the real world, you can solve problems that haven't already been solved before. College shouldn't be about regurgitating the same problems the professors solve during the lectures.
are you sure you arent moddifying order of elements in List?
CUT MY LIFE INTO PIECES
>doesn't understand asymptotic runtime
Iterate over the list in normal order, adding entries to a linked stack. When you're done iterate over the stack and print.
>ITT brainlets who unironically believe that O(n) is equivalent to O(2n)
You undergradfags are hilarious...
(mutex lock)
reverse links
print and reverse links
2n time
Are you retarded or just baiting?
>hurr
if you actually have a degree, you should give it back
O(n) is unequivocally equal to O(x*n +c)
>google search for std list
>aids, chlamydia, herpes...
>pretending to be a graduate student
More stuff like this? I love cheatsheets. Concise and practical. Only the last few pages are decently useful but it's still nice overall.