Data structures test

>data structures test
>"Traverse a singly linked list backwards in O(n) or quicker"

STANDING
ON THE EDGE

Attached: serveimage.png (640x360, 26K)

Other urls found in this thread:

drive.google.com/file/d/0B234tvgKwGJnb1RNakx1QnZuR3c
npr.org/2017/07/19/538092649/say-goodbye-to-x-y-should-community-colleges-abolish-algebra?utm_campaign=storyshare&utm_source=twitter.com&utm_medium=social
twitter.com/SFWRedditImages

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?

Attached: 1541017016700.png (199x226, 3K)

>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

Attached: 1524726796698.jpg (600x532, 40K)

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/file/d/0B234tvgKwGJnb1RNakx1QnZuR3c

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

Attached: 1468679527909.jpg (488x472, 26K)

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

Attached: konata12.jpg (317x311, 28K)

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.

Attached: 1521025300400.png (645x729, 56K)

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.

npr.org/2017/07/19/538092649/say-goodbye-to-x-y-should-community-colleges-abolish-algebra?utm_campaign=storyshare&utm_source=twitter.com&utm_medium=social

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.

Attached: zz3xmu6.jpg (2140x1605, 92K)

its time we move beyond meritocracy. being qualified on paper for something doesn't mean you should actually belong there. its almost 2019 sweeties

Attached: based_firefox.png (994x805, 95K)

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

Attached: scrot.png (1133x573, 87K)

>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

Attached: Screen Shot 2018-11-04 at 2.32.46 PM.png (220x49, 11K)

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.