« first day (2000 days earlier)      last day (2963 days later) » 

@sbi U. was kinda optimistic today, he said "Everything might be okay". No specific good news, though.
 
He wanted to have a chat about my future but couldn't make the time.
 
sbi
@melak47 Oh. Really. I thought he had an appointment with some company next week? (I think he told me it's on Apr, 10th, but that's on Sunday.)
@R.MartinhoFernandes Mhmm. Shall I try to talk to him about you tomorrow?
 
Ugh, I need to go to the Burgeramt tomorrow.
 
@R.MartinhoFernandes enjoy your burger :)
 
sbi
7:09 PM
Hamburger?
(SCNR)
 
@sbi nah, he said we'll talk next week.
 
sbi
 
Oooh, Iron & Wine in Berlin again.
 
sbi
When?
 
@sbi Theres a joke here, but I don't see it =/
 
7:14 PM
the interviewer expects the interviewee to be more familiar with the terms than he actually is
 
@Borgleader The real joke for me is asking him to produce an O(n) list in O(1) space.
 
sbi
One of my colleagues just RT'ed this job ad.
 
@Puppy it doesn't actually say this
 
well it basically does.
 
> ☐ Do you have testers?
oops :P
 
sbi
7:23 PM
@Borgleader Same thought. But then, we do not have dedicated testers here either.
 
not to mention, lazy lists are a thing
 
@sbi We have testers, but they all go home too early--not very dedicated at all.
 
sbi
@JerryCoffin LOL!
 
@milleniumbug That are not lists.
they are lazy lists.
 
sbi
Nah, we have lots of unit tests and integration tests, run by the developers. But then, we don't have a product used by end users. It mostly runs on itself.
 
7:26 PM
oh, are we gonna argue about terminology? yay, oppa lounge style
@Puppy Liskov substitution principle would say a different thing
 
@Puppy I must be missing something, because I don't see it asking for that either.
 
@milleniumbug Lazy lists do not support all of the operations of non-lazy lists.
 
also O(1) space means O(1) additional space
what is a list
> a constructor for creating an empty list
check
> an operation for testing whether or not a list is empty;
check
> an operation for prepending an entity to a list
check
 
that is woefully underspecified.
I said all of the operations, not just the really vague stuff.
like I dunno, O(1) size, for example.
 
@Puppy std::list
 
7:31 PM
is not lazy in the slightest.
 
@Puppy This is the minimal set of operations that you need to call a list a list
 
sbi
What is a binary search tree? I know what a binary tree is, and I have implemented binary searches before the STL came along, but I currently have no idea what a binary search tree is supposed to be.
 
@milleniumbug Those are not all of the operations that non-lazy lists support.
 
@sbi A binary tree with specific relations on the nodes so that a search is efficient to perform
 
@sbi a binary tree with an invariant: left child is less than the node, right child is more than the node
 
sbi
7:33 PM
Ah, a sorted, balanced binary tree?
 
not necessarily balanced
 
needs to be balanced to maintain the invariant, roughly
 
although unbalanced trees are rarely useful
 
I'm not sure what sorted means wrt to binary trees, but yes, the children of a parent are sorted
 
7:34 PM
because they degenerate to lists
 
It's kind of ambiguous how they degenerate to lists
There are many different ways to traverse a tree in order to generate a list
 
@Puppy find me where in the comic it's mentioned that the interviewee is supposed to produce std::list or a non-lazy list
 
@Shoe All nodes have a right (or left) child but no left (or right) child
 
well, the requirement clearly states that he should produce a list and not a function that can be evaluated to produce individual items of a list.
 
7:36 PM
@Borgleader That's not the definition of unbalanced I remember
 
@Puppy implementations are irrelevant
 
An unbalanced tree could also not have that structure
 
lazy or not is not an implementation detail.
 
sbi
@Shoe No, but a possible instance.
 
it affects the complexity of the operations
 
sbi
7:37 PM
When you're a parent of boys, you get to say things like, "Your balls don't belong on the roof!" & then try to keep a straight face.
 
if not otherwise specified, I think it's abstract data type "list"
 
and for example what happens when an exception is thrown during evaluation
 
Also "given a binary search tree" is ambiguous
 
@Puppy actually it is if we're talking about abstract data type "list"
 
and not to mention "without stack"
 
7:38 PM
yup, process stack or data structure stack
 
@milleniumbug Well, there's the assumption right there.
 
If the binary search tree is in the classic form (nodes + references to children), then I have no idea how to do that exercise
 
@Puppy actually you make one too
 
@Shoe I thought the defn of balanced for a BST was |height(left) - height(right)| <= 1
 
you have to assume that you are talking about a language that cannot, for example, throw exceptions.
 
7:39 PM
If it's in the form of an array, for example, then it's trivial
If it means without the stack data structure, then we are done
 
in the general case, you can't assume that a lazy list and a non-lazy list are equivalent.
 
If it means without process stack, then I would like to see his program that does that
That's all I've got
@sbi What's the solution?
 
kinda pointless allocating O(n) space for all the keys but then not having any process stack available.
 
@Puppy they both meet the interface they're supposed to
 
well, not really.
lists don't throw exceptions when you start accessing elements.
the elements already exist.
they don't perform I/O or start blocking threads
unlike lazy lists which can do all of those things.
 
user1804599
7:42 PM
A set of dice is nontransitive if it contains three dice, A, B, and C, with the property that A rolls higher than B more than half the time, and B rolls higher than C more than half the time, but it is not true that A rolls higher than C more than half the time. In other words, a set of dice is nontransitive if the binary relation – X rolls a higher number than Y more than half the time – on its elements is not transitive. It is possible to find sets of dice with the even stronger property that, for each die in the set, there is another die that rolls a higher number than it more than half the...
 
user1804599
TIL
 
sbi
@Shoe Why would I know? Maybe there isn't one.
A professor of mine once gave us the task to write the LISP code to traverse a list without using recursion. We all failed. When we approached him at his next lecture he said: "But of course, this is impossible without recursion or iteration!"
 
Oh wait
It doesn't say without iteration
Then it's easy
 
nah
you can't do the iteration without a data structure occupying log(n) size.
which, amazingly enough, is also the space requirement for the recursion.
 
I guess now it's time to disambiguate "without stack"
 
7:44 PM
making it pointless to require iteration instead of recursion really.
 
@Puppy What?
Why not?
 
well
 
I could spawn 2 threads per node
 
sbi
Alfred Kinsey,an American biologist had a collection of over 5 million wasps and could insert a toothbrush, bristle-end first,into his penis
 
sure, but each thread consumes stack, so log(n) at least again.
 
7:46 PM
Actually
I have an idea
 
you can't write it without consuming log(n) stack because you need to keep track of both the left child and the right child.
 
@Puppy throwing exceptions doesn't influence the space complexity
 
so even if you iterate always the left child first, you must keep all the right children in the structure.
 
@sbi lol, TMI!
 
also you haven't specified why do you need O(n) space
 
7:47 PM
@sbi there are things in life I rather not know
 
you don't
 
@milleniumbug It's a substantial semantic difference which means that the lazy list doesn't meet the eager list interface. So whether or not it offers better complexity is irrelevant.
 
the same way you assert that "they could have used a non-lazy list", I assert "they could have used a lazy one"
> produce a list
> a list
> A LIST
any list
 
lazy lists aren't lists; they're functions.
7
 
> Fun trivia, in C (not C++), the function call operator is not even defined for functions. It is defined for pointers to functions and there is an implicit function-to-pointer conversion.
 
7:52 PM
not often a useful distinction but it does exist.
 
Interesting.
 
@Puppy non-lazy lists aren't lists; they're struct instances
^ this sentence is just as retarded as yours
 
you can make that argument if you wish.
but since functions and structs are obviously not the same thing, then that's that.
 
Lazy lists are generators
 
actually I haven't used any data List T = None | Cons T List function there
 
sbi
7:56 PM
> Victims of tit attacks.That's a very interesting article about Great Tits attacking Redpolls and Yelowhammers.
 
@Shoe The basic idea is pretty simple (though the details get pretty tedious). Let's start with a somewhat simpler version: print a singly-linked list in reverse without using extra storage (stack or otherwise). It can be done with constant extra space (basically one extra pointer). When you reach a node, you save its next pointer, then overwrite it with the address of the previous node. When you reach the end of the list, you've reversed the list, so you traverse it again backwards.
 
if I make a non-lazy list using functions, it's still irrelevant to the issue at hand (O(n) space required to produce a list)
 
> Even better, Howard Saunders (1899) wrote that “The Great Titmouse will attack small and weakly birds, splitting their skulls with its powerful beak in order to get at their brains; and it has even been known to serve a Bat in this manner”.
Zomebies!
 
sbi
@wilx Deadly Zombie Tits!
 
user1804599
I want to be a sex toy designer but I can't find universities that teach sex toy design.
 
7:59 PM
@sbi Damn!
 
With a tree, it's more complex, because each node has (in essence) two descendant linked lists instead of one. That makes the job more complex, but the same basic idea can be applied here as well (essentially, as you descend, you reverse a pointer to point back at the parent, and as you ascend, you point it back at the child).
 
sbi
 
@Zoidberg I'm sure there will be at least one uni somewhere that teaches that
 
@JerryCoffin That's not equivalent, though, since you've not printed the list, you've reversed the list and then also printed it, so you have a side effect.
 
...which is irrelevant if you don't have threads or signals in your denotational semantics
 
8:01 PM
@Puppy As you traverse in reverse, you (obviously) reverse it again, so it ends up exactly as it started. It is different in one respect though: it's not reentrant, so the whole process has to be treated as a single, atomic operation.
 
well, any aliases to any nodes of the list can observe the mutation.
 
sbi
> "Give someone a program, you frustrate them for a day; teach them how to program, you frustrate them for a lifetime." - David Leinweber
19
 
@Zoidberg try Just design?
 
user1804599
Nah, screw university. I don't like those places.
 
user1804599
Too much circlejerk.
 
sbi
8:08 PM
What would you have to study at Screw University?
 
Give someone a program, you frustrate them for a day; teach them how to program, they frustrate you every day with shitty pointer questions
 
sbi
I did another 150 slides today, and I am totally exhausted again. I now have one more day, and have to produce another ~150 slides. Then I have a day spent with flying and stuff, in which I need to review and polish 600 slides and think of two dozen exercises to pick from for practice. Sigh. And then I'll stand in front of a bunch of people and will find all the errors in those slides...
 
Xeo
@sbi I officialy start in July, and in HH. That's the DD team of ex-Funatics.
 
sbi
@Xeo DD? As in Dresden?
 
user1804599
HH? Heil Hitler? Oh wait, Hamburg Harbor.
 
Xeo
8:13 PM
Duesseldorf
 
sbi
@Zoidberg Hansestadt Hamburg.
 
Xeo
Isn't Dresden just D?
 
sbi
@Xeo That's D!
 
Xeo
welp, that's backwards!
 
sbi
@Xeo Yep. Dresden came late to the party, and has to wear Double D now.
 
8:15 PM
Double Ds are fun.
4
Wait, you're not talking about women, are you?
 
Xeo
too big
 
sbi
@R.MartinhoFernandes License plates, but here, have a star.
Anyway, I am very tired. I need to go to bed.
 
Requiescat In Pace
 
Xeo
g'night and hf on your trip
RequisCat++
 
There you go
Iterative version "without stack" (with O(1) addition space)
 
8:20 PM
hmm
you've consumed O(N) extra space with parent pointers.
not really an improvement
 
The parent pointers are clearly in the binary search tree
Is a doubly linked list a list? Yes. Is a doubly linked binary search tree a BST? Yes.
 
the fact that you've put the extra space inside the tree doesn't really change anything.
 
I haven't put anything. The interviewer gave it to me like that
 
except that you could argue that the problem is under-specified since it does not specify that the tree does not contain parent pointers.
 
@VeronikaPrüssels turns out I’m rubbish at dodge jumping from a standstill huh
 
8:25 PM
but that would simply render it a rather dumb question.
"How can you not consume space when we pre-allocated all the space needed?" "Well, gee, by using the pre-allocated space!".
 
lol
Most of the BST (which are usually balanced) have a parent pointer.
 
57 mins ago, by milleniumbug
also O(1) space means O(1) additional space
 
A BST with parent pointers satisfy the definition of "binary search tree" in the problem
The question is dumb regardless
 
not denying that
 
I thought we established that from the very start
 
8:28 PM
pretty under-specified really.
 
If I were to probabilistically assume what BST and "without stack" means in the question, I would guess "BST, variant with parent pointers" and "without addition space".
 
@Puppy It's not under-specified, unless you also consider it does not specify that the tree does not contain sibling pointers or a thousand other possible thing.
 
The combination "BST without parent pointers" and "without addition space" is clearly the worst one, and the answer, if there is, would require hours to get even remotely right; which is probably not the intent of the interviewer.
 
@R.MartinhoFernandes Those possible things have a pretty big impact on the outcome in this case.
 
Actually, no, not even that.
"Tree" by itself implies that.
It's not a tree if it has cycles.
 
8:32 PM
How it's represented in memory != definition of the structure
 
personally I'd consider it not using parent pointers unless otherwise specified
 
@Shoe How it is represented in memory is not relevant for the problem.
 
@R.MartinhoFernandes Weren't you arguing that parent pointers would create cycles which would make it not a tree?
 
@Shoe He says, having changed the representation for his own benefit ;p
 
@Shoe A tree has directed relations between nodes in a specific manner, and that manner excludes cyclic relations.
@Shoe If you're given a tree, by definition it does not have parent pointers.
 
8:34 PM
That's why I tell you that what pointers it has in the implementation is irrelevant
 
@Shoe Yes, it is irrelevant because you cannot use them.
 
then why don't you produce an iterative example without parent pointers or O(log(n)) space?
 
They're not there for all purposes, because you're given a tree.
 
No, that would be "it's not irrelevant, you can't use them". What I mean is "it's irrelevant".
 
@Shoe No, it's not. A tree does not have the relation you need for your cheat.
"BST without parent pointers" is pleonastic.
 
8:36 PM
> In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.
lol
 
"BST with parent pointers" is "almost but not quite a BST".
 
the whole need for log(n) space is to store the parent pointers of the current evaluation.
 
inb4 wikipedia is dumb I'm the true source
 
that's what the log(n) space is used for in recursive contexts
and in iterative contexts where the tree doesn't already contain them.
 
@Shoe You're misinterpreting that.
Because the nodes also have siblings, and nephews and grandparents.
None of that implies that such arcs exist in it.
Those are emergent properties.
 
8:38 PM
IIRC your definition is from graph theory
 
Also, read the whole thing if you want.
> For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general as a data structure a given node only contains the list of its children, but does not contain a reference to its parent (if any).
> A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.
There's a ton of sentences in there that back me up.
> A tree is a (possibly non-linear) data structure made up of nodes or vertices and edges without having any cycle.
 
That's assuming that pointers have a 1:1 relationship with arcs
Which they don't
The parent pointer, per the invariant of the class/function, can only have a reference to the true parent, therefore it's just redundant information that acts as a sort of a cache. In other words (children->parent == parent->left) || (children->parent == parent-right) must always hold.
 
"Pointer" is just a C++ synonym of "reference".
 
Ok, I feel like I'm an idiot here (and sorry to interrupt), but I can't come up with the syntax to declare "a pointer to an array of pointers". I want to have an MyObject *MyObjectPointerList[5]={....}; and be able to pass & assign &MyObjectPointerList to an member variable of another object, but I can't figure anything that compiles that isn't MyObject **ptr=reinterpret_cast<MyObject**>&MyObjectPointerList, and that seems mildly offensive. Any suggestions?
 
Which is not a synonym of arc
 
8:42 PM
@Shoe No, it cannot. Jesus, I can keep quoting shit from your source.
 
> There are many different ways to represent trees; common representations represent the nodes as dynamically allocated records with pointers to their children, their parents, or both, or as items in an array, with relationships between them determined by their positions in the array (e.g., binary heap).
 
> As a data structure, a linked tree is a group of nodes, where each node has a value and a list of references to other nodes (its children). (...) Thus there is also the requirement that no two references point to the same node (that each node has at most a single parent, and in fact exactly one parent, except for the root), and a tree that violates this is "corrupt".
 
Me too, let's see who is the quickest
Woops, I won already
@R.MartinhoFernandes How does the tree with parent pointers violate that?
 
@Shoe "no two references point to the same node"
 
Within the node, no two reference point to the same node
 
8:43 PM
the quote says nothing about within the node.
 
it's within the tree as a whole.
 
@Shoe Now you're just making shit up. I'm going to just file this as trolling and move on.
 
Ok
 
robot I missed you
 
8:47 PM
@milleniumbug thank you!
 
@R.MartinhoFernandes are they trying to define the difference between a graph and a tree?
 
@doug65536 A tree is a particular kind of graph.
 
exactly
 
Ell
@Puppy emotion from pupp? This is new ;)
 
In any case, the point is that a BST does not provide a O(1) parent operation.
@Puppy :)
 
8:49 PM
@Ell I have emotions.
 
Ell
TIL
 
> In general a node in a tree will not have pointers to its parents, but this information can be included (expanding the data structure to also include a pointer to the parent) or stored separately. Alternatively, upward links can be included in the child node data, as in a threaded binary tree.
 
Ell
Is there a name for a tree which also possesses parent nodes?
 
@Shoe And so can information about siblings be included, and, why not, the exact information you are looking for.
 
And that would still be a BST
Because the data structure represented != representation
There's no 1:1 mapping between the two, which is what you are arguing
 
8:51 PM
But you're given any BST, not one specific one.
 
It's underspecified
 
No, it is not.
 
A BST can be represented an array as well
 
Being general is not the same as being underspecified.
 
With no reference
And it would still be a BST
Even though there are no references/pointers, which is what you want to map to arcs
 
8:52 PM
@Shoe You mean like in a heap?
 
@Shoe That's not true.
 
A heap array representation has extra requirements. (the tree must be full)
 
sorted arrays cannot offer log(N) insertion time.
 
Gonna plonk puppy for a while, max 1 person at a time
@R.MartinhoFernandes Nope
It can be filled with std::optional
Or pointers, which can be null
Or any nullable thing
 
Look, it's like someone asking you to write a function to calculate the area of a rectangle and you write one that calculates the area of a square.
You cannot call it underspecified.
 
8:54 PM
@R.MartinhoFernandes That's not like that at all, lol
 
It's just a problem more general than your solution, so your solution is not enough.
 
@R.MartinhoFernandes A BST can be represented in many different ways and each operation has different complexities and meets different requirements.
 
@Shoe It is. There are BSTs for which your solution does not work.
 
If you don't specify how you are giving me the BST then it's underspecified
 
It's general.
 
8:55 PM
@R.MartinhoFernandes Tell me your solution and I'll tell you at least one BST representation which does not work with it
 
Just because you made assumptions not given doesn't mean it is underspecified.
 
user1804599
Superior phone problems: recipients don't see the newer emojis.
 
@Shoe That does not make the problem underspecified; it makes it unsolvable, which is what I said it was.
 
I've explained why I made the assumptions I made
Which has nothing to do with the fact that the problem is underspecified
It's underspecified even if I don't give a solution or an interpretation
Me making assumptions has nothing to do with it being underspecified
 
An underspecified problem is one which admits too many distinct solutions that solve specific instances of it, but none solves the whole.
@Shoe So how is assuming the rectangle has equal sides not the same here?
 
8:58 PM
Also are you claiming that a RBBST is not a tree as well because most implementations (or at least what's considered the common implementation) also involves a parent pointer?
@R.MartinhoFernandes You are bad at metaphors, leave them aside, trust me
 
@Shoe Those implementations indeed do not implement an RBBST.
 
@Shoe No, I don't trust you, because you haven't shown me reason to.
 
Answer my last question
 
If you mean a red-black tree, no, it doesn't involve extra pointers.
 

« first day (2000 days earlier)      last day (2963 days later) »