What everyone knows and what no one knows(cacm.acm.org)
cacm.acm.org
What everyone knows and what no one knows
https://cacm.acm.org/blogs/blog-cacm/248022-what-everyone-knows-and-what-no-one-knows/fulltext
65 comments
> What can we say about `not A' and `not B'?
Haha, yes. I interpreted the `and` in that sentence as the logical connective, and (A → B) says nothing about (¬A ∧ ¬B). But he meant `and` in the human language sense.
Haha, yes. I interpreted the `and` in that sentence as the logical connective, and (A → B) says nothing about (¬A ∧ ¬B). But he meant `and` in the human language sense.
The author compares it to asking about 2+2, but I think it's more closely analogous to asking "What can we say about 4 and 2+2?" Given the ambiguous wording, I wouldn't expect anyone to answer confidently, and lost of intelligent people would answer eight rather than "they're equal."
[deleted]
[deleted]
I agree this question is phrased very strangely in a way I find hard to parse. Perhaps this is a common way of speaking in academia, but "what can we say about…" was not a phrase I immediately understood. I was also unsure if he meant `not A AND not B` or, casually, `not A` and also `not B`. If it was phrased more precisely, I think I would have been able to answer better.
This whole thing reminds me of old-style, bad tech interviews where the interviewer is really selecting for someone similar to themselves, i.e., someone who understands a particular obscure phrasing of a problem, and immediately knows the correct answer.
However, he does point out that he tried explaining things, and different phrasing, so maybe there really is something here.
However, he does point out that he tried explaining things, and different phrasing, so maybe there really is something here.
Well, this is interesting but not surprising.
I have conducted hundreds of interviews and I am astonished at low level of knowledge or understanding of some things that are completely obvious to me.
I don't typically ask questions outside typical tech topics so that I don't bias against people who did not go to CS course.
Some of questions that I almost never get correct answer to but feel completely obvious to me:
- Under what conditions linked lists are faster than array lists (Java)?
- Why can't one process take a pointer, send it to another process to have it dereference to same data? When does this work?
- Is Java pass by reference or pass by value language? Why? (I ask this senior Java developers and never got correct answer)
- Can more than one processes listen on the same port on the same interface and IP address?
- What does `volatile` keyword do in Java, exactly?
- Explain what is a breakpoint and how it stops the program.
I would assume at least some of the things should be familiar to somebody who spent years programming in the given language.
I have conducted hundreds of interviews and I am astonished at low level of knowledge or understanding of some things that are completely obvious to me.
I don't typically ask questions outside typical tech topics so that I don't bias against people who did not go to CS course.
Some of questions that I almost never get correct answer to but feel completely obvious to me:
- Under what conditions linked lists are faster than array lists (Java)?
- Why can't one process take a pointer, send it to another process to have it dereference to same data? When does this work?
- Is Java pass by reference or pass by value language? Why? (I ask this senior Java developers and never got correct answer)
- Can more than one processes listen on the same port on the same interface and IP address?
- What does `volatile` keyword do in Java, exactly?
- Explain what is a breakpoint and how it stops the program.
I would assume at least some of the things should be familiar to somebody who spent years programming in the given language.
I'll try to answer these, just for fun, even though I am not doing an interview. I have not Googled anything, so if things are horribly wrong, let me know.
- I have no idea, but I could try answering this through thinking through the problem. Generally a linked list has a pointer to from one item to the other. An array list I assume uses arrays for holding the items using indexes.
What are the available operations generally for a data structure?
Search - Search would be O(1) in array list and O(N) in linked list, can't be this.
Insert - Insert in a linked list is actually quite quick if you have the node since you could just move the pointers. For an array list, you would have to shift everything over. I think this is the answer.
Remove - Same deal as Insert.
Did I get this right?
- Because processes cannot access each others memory, the OS prevents from happening. A pointer is a pointer to an address in memory so you generally cannot do this. In terms of where would this work, umm, maybe in an old OS that didn't have the protection, or perhaps dynamically linking libs?
- Neither, it's pass by copy from what I recall. Or something of the sorts. Maybe call by sharing? I would just explain how it works since that's easier, generally everything in Java is copied, so it's pass by value in the traditional sense. But when you think pass by value, are objects copied? The answer is no, objects copy their pointer instead in Java. So when you modify a passed object, it does modify the underlying data in that object, but you can never re-assign the object.
- Nope, I don't think so. From what I recall, I've always had programs fail to run if I use the same IP + Port + Interface. You can do virtual hosts in Apache/Nginx tho where you can handle multiple different domains on the same port.
- Volatile is generally used when working with threading. I cannot fully recall what it is, but it's required in thread safety. I would generally use thread safety operations and data structures instead here, but I do recall having to use volatile a few times.
- I don't know how a breakpoint works exactly, but it's a marker placed in code and when a debugger runs into it, it stops the process. I assume since the Java code gets converted to byte code for the JVM to process, it would be a byte code added between the lines where the breakpoint lives.
Note: haven't used Java in 4 years.
- I have no idea, but I could try answering this through thinking through the problem. Generally a linked list has a pointer to from one item to the other. An array list I assume uses arrays for holding the items using indexes.
What are the available operations generally for a data structure?
Search - Search would be O(1) in array list and O(N) in linked list, can't be this.
Insert - Insert in a linked list is actually quite quick if you have the node since you could just move the pointers. For an array list, you would have to shift everything over. I think this is the answer.
Remove - Same deal as Insert.
Did I get this right?
- Because processes cannot access each others memory, the OS prevents from happening. A pointer is a pointer to an address in memory so you generally cannot do this. In terms of where would this work, umm, maybe in an old OS that didn't have the protection, or perhaps dynamically linking libs?
- Neither, it's pass by copy from what I recall. Or something of the sorts. Maybe call by sharing? I would just explain how it works since that's easier, generally everything in Java is copied, so it's pass by value in the traditional sense. But when you think pass by value, are objects copied? The answer is no, objects copy their pointer instead in Java. So when you modify a passed object, it does modify the underlying data in that object, but you can never re-assign the object.
- Nope, I don't think so. From what I recall, I've always had programs fail to run if I use the same IP + Port + Interface. You can do virtual hosts in Apache/Nginx tho where you can handle multiple different domains on the same port.
- Volatile is generally used when working with threading. I cannot fully recall what it is, but it's required in thread safety. I would generally use thread safety operations and data structures instead here, but I do recall having to use volatile a few times.
- I don't know how a breakpoint works exactly, but it's a marker placed in code and when a debugger runs into it, it stops the process. I assume since the Java code gets converted to byte code for the JVM to process, it would be a byte code added between the lines where the breakpoint lives.
Note: haven't used Java in 4 years.
1.
So, Linked Lists vs Arrays is tough and situation specific. What I look from candidate is general understanding of the problem instead of just blindly saying "linked lists are faster for insertions and deletions".
Believe or not, ArrayList are faster for most real life examples (or can be made much faster).
Basically (not very precisely but describes it pretty well), for Linked List to be faster than Array List you need an index (or some other way to locate an entry like when you iterate over the list and already have the reference) or perform most operations at both ends.
Against popular knowledge, ArrayList is faster in any random access (read, insert or delete) requiring first linear search to locate the entry or insertion place. Why writes is faster even if you have to move heaps of memory to insert something in the middle of array is because searches are so much more expensive for Linked List.
Linear search through unindexed Linked List is horribly inefficient compared to ArrayList for many reasons. First, the data is less dense due to references. Then to access next element you need to read pointer from memory and dereference it and this is rather expensive compared to incrementing a pointer which is what you get to get to next element in array list. Then if you have large data structure that was result of random writes it will have rather random layout in memory in case of linked list meaning you will be jumping all over memory and not making good use of prefetching or sharing cache lines. Having CPU prefetch next pages as you iterate through the ArrayList is incredible speedup (but you can get linked list arranged roughly the same way in memory but it can be complex). Then the fact that it is easy to parallellize linear search on array list but not possible on linked list. If the array list can be kept sorted you can do other search strategies (like binary search) but that doesn't work with linked list. The list is long.
Linked list will be faster if you require insertions and deletions to be fast AT BOTH ends. If you need to insert at the beginning of the ArrayList but not at the end, just reverse the order.
It is possible that you can iterate over the list and do operations on elements (for example, delete it). You use the fact that you already have the reference to the location in in that case Linked List may be much faster than Array List.
2.
Virtual Memory. Because each process has their own memory translations. Basically, userspace pointer does not point to physical memory directly. Instead, every process has their own namespace and same pointer values have different meaning in different namespaces. Those namespaces are then dynamically mapped to physical memory and the Operating System is responsible for keeping the mapping and constantly feeding it to CPU whenever CPU executes userspace code and finds a pointer for which it does not have mapping.
CPU keeps Page Table and a buffer of mappings (it is called TLB -- translation lookaside buffer, you may have heard the name). When it gets a pointer to map to physical memory it looks at the page table, when it can't find in page table it refers to lookaside buffer and if it can't find the information necessary it momentarily interrupts to the operating system. This is normally completely invisible to the program unless somebody is doing some microbenchmarking and then can see it as unexplained artifacts and cause some chuckles from people who really know the stuff.
It is possible to map region of same physical memory or file to the same userspace range of addresses (for example using mmap or when using shared libraries). In this case it is possible to make multiple processes have pointers with same values to dereference to same physical memory address.
Old operating systems that did not have concept of virtual memory were basically open world where a process could access everything. Then the concept of Virtual Memory was introduced but the separation was not enforced in other way because just the fact that single page of physical memory was only mapped from single memory space made it pretty good enforcement (at the time).
3.
Java is exclusively pass by value. The values are primitives or references. It is pass by value because the variable in Java holds either a primitive or a reference and when a function is invoked, instead of passing reference to the variable, the value of the variable is copied. Meaning if you have Object a = x; function_call(a); then you are sure than nothing that happened in function_call(a) could modify the variable a. In pass by reference language the the function_call(a) would pass reference to a and this could allow function_call(a) to modify the variable a.
4.
You can have multiple programs listening on different protocols. For example, you can have one program listening on TCP port and another on UDP. There is I think some new facility in Linux that allow even more functionality but I am not up to date with it.
5.
Volatile ensures ordering of operations around reads writes to the volatile variable is not changed by VM or CPU and also ensures that any writes and reads are directed to main memory (at least on systems with more than one L3 cache, ie. with more than one CPU).
On most CPUs this happens by a special fence instruction. I am not very familiar with JVM internals so I don't know how this is exactly done (but I expect special instruction, too).
6.
Breakpoint is an instruction that is inserted by the debugger directly into machine code of the running program (bytecode in case of Java program). In case of native program this instruction causes an interrupt that causes CPU to stop the program and wake up Operating System. The operating system then passes control to the debugger (which had to first make appropriate setup for this to happen) and then debugger decides what to do depending on the action debugger user wanted to execute.
The way the instruction is inserted is usually interesting by itself. Depending on environment, either some space is kept in the function so that it can grow to accommodate the new instruction or the code of the function is copied somewher else with the new instruction and all references to the function are mapped to point to the new copy of the function machine code. I don't know how this is exactly achieved in Java.
So, Linked Lists vs Arrays is tough and situation specific. What I look from candidate is general understanding of the problem instead of just blindly saying "linked lists are faster for insertions and deletions".
Believe or not, ArrayList are faster for most real life examples (or can be made much faster).
Basically (not very precisely but describes it pretty well), for Linked List to be faster than Array List you need an index (or some other way to locate an entry like when you iterate over the list and already have the reference) or perform most operations at both ends.
Against popular knowledge, ArrayList is faster in any random access (read, insert or delete) requiring first linear search to locate the entry or insertion place. Why writes is faster even if you have to move heaps of memory to insert something in the middle of array is because searches are so much more expensive for Linked List.
Linear search through unindexed Linked List is horribly inefficient compared to ArrayList for many reasons. First, the data is less dense due to references. Then to access next element you need to read pointer from memory and dereference it and this is rather expensive compared to incrementing a pointer which is what you get to get to next element in array list. Then if you have large data structure that was result of random writes it will have rather random layout in memory in case of linked list meaning you will be jumping all over memory and not making good use of prefetching or sharing cache lines. Having CPU prefetch next pages as you iterate through the ArrayList is incredible speedup (but you can get linked list arranged roughly the same way in memory but it can be complex). Then the fact that it is easy to parallellize linear search on array list but not possible on linked list. If the array list can be kept sorted you can do other search strategies (like binary search) but that doesn't work with linked list. The list is long.
Linked list will be faster if you require insertions and deletions to be fast AT BOTH ends. If you need to insert at the beginning of the ArrayList but not at the end, just reverse the order.
It is possible that you can iterate over the list and do operations on elements (for example, delete it). You use the fact that you already have the reference to the location in in that case Linked List may be much faster than Array List.
2.
Virtual Memory. Because each process has their own memory translations. Basically, userspace pointer does not point to physical memory directly. Instead, every process has their own namespace and same pointer values have different meaning in different namespaces. Those namespaces are then dynamically mapped to physical memory and the Operating System is responsible for keeping the mapping and constantly feeding it to CPU whenever CPU executes userspace code and finds a pointer for which it does not have mapping.
CPU keeps Page Table and a buffer of mappings (it is called TLB -- translation lookaside buffer, you may have heard the name). When it gets a pointer to map to physical memory it looks at the page table, when it can't find in page table it refers to lookaside buffer and if it can't find the information necessary it momentarily interrupts to the operating system. This is normally completely invisible to the program unless somebody is doing some microbenchmarking and then can see it as unexplained artifacts and cause some chuckles from people who really know the stuff.
It is possible to map region of same physical memory or file to the same userspace range of addresses (for example using mmap or when using shared libraries). In this case it is possible to make multiple processes have pointers with same values to dereference to same physical memory address.
Old operating systems that did not have concept of virtual memory were basically open world where a process could access everything. Then the concept of Virtual Memory was introduced but the separation was not enforced in other way because just the fact that single page of physical memory was only mapped from single memory space made it pretty good enforcement (at the time).
3.
Java is exclusively pass by value. The values are primitives or references. It is pass by value because the variable in Java holds either a primitive or a reference and when a function is invoked, instead of passing reference to the variable, the value of the variable is copied. Meaning if you have Object a = x; function_call(a); then you are sure than nothing that happened in function_call(a) could modify the variable a. In pass by reference language the the function_call(a) would pass reference to a and this could allow function_call(a) to modify the variable a.
4.
You can have multiple programs listening on different protocols. For example, you can have one program listening on TCP port and another on UDP. There is I think some new facility in Linux that allow even more functionality but I am not up to date with it.
5.
Volatile ensures ordering of operations around reads writes to the volatile variable is not changed by VM or CPU and also ensures that any writes and reads are directed to main memory (at least on systems with more than one L3 cache, ie. with more than one CPU).
On most CPUs this happens by a special fence instruction. I am not very familiar with JVM internals so I don't know how this is exactly done (but I expect special instruction, too).
6.
Breakpoint is an instruction that is inserted by the debugger directly into machine code of the running program (bytecode in case of Java program). In case of native program this instruction causes an interrupt that causes CPU to stop the program and wake up Operating System. The operating system then passes control to the debugger (which had to first make appropriate setup for this to happen) and then debugger decides what to do depending on the action debugger user wanted to execute.
The way the instruction is inserted is usually interesting by itself. Depending on environment, either some space is kept in the function so that it can grow to accommodate the new instruction or the code of the function is copied somewher else with the new instruction and all references to the function are mapped to point to the new copy of the function machine code. I don't know how this is exactly achieved in Java.
> Old operating systems that did not have concept of virtual memory
And modern OSes for microcontrollers. When you've got only a few kB of RAM and no swap there's not much point to virtual memory. "Library OSes" are common, where the OS is statically linked with all of its tasks, and everything shares an address space.
And modern OSes for microcontrollers. When you've got only a few kB of RAM and no swap there's not much point to virtual memory. "Library OSes" are common, where the OS is statically linked with all of its tasks, and everything shares an address space.
I don’t know if this is true for linked-lists/arrays: but it is sometimes true that an O(1) algorithm is slower than an O(n) one, for small ns (hash-table vs. a linear search of a list of pairs is one example of this).
For almost all of these questions I’d be concerned about unusual edge cases: like, I believe it’s possible for two processes to share the same IP/Port on Linux, if you set the right socket options.
For almost all of these questions I’d be concerned about unusual edge cases: like, I believe it’s possible for two processes to share the same IP/Port on Linux, if you set the right socket options.
Yeah, I think SO_REUSEPORT allows that: https://superuser.com/a/1267230
Thanks for this one, I forgot about it. This is relatively new addition, in times past the only way was to listen on separate protocols (one process on TCP and one on UDP, for example).
It's also OS (well, network stack) dependent. The most general answer is that it's possible, but you might need a custom network stack to do it.
> In terms of where would this work, umm, maybe in an old OS that didn't have the protection, or perhaps dynamically linking libs?
Modern OSes all have shared memory functionality. And dynamically linked libs are a complicated thing, so it's both yes and no there, at least on some OSes, while on others it's a clear no :)
> Neither, it's pass by copy from what I recall.
Pass by copy is the same thing as pass by value.
In C and Pascal the definitions are pretty clear, but people insist on using them on other languages where they don't make sense. Let's extend it a bit: is Haskell a pass by value or pass by reference language? What about Prolog?
About breakpoints, they usually have hardware support. But since Java runs on a virtual machine, I have no idea it the buck stops at the JVM or if they use the hardware interface.
Modern OSes all have shared memory functionality. And dynamically linked libs are a complicated thing, so it's both yes and no there, at least on some OSes, while on others it's a clear no :)
> Neither, it's pass by copy from what I recall.
Pass by copy is the same thing as pass by value.
In C and Pascal the definitions are pretty clear, but people insist on using them on other languages where they don't make sense. Let's extend it a bit: is Haskell a pass by value or pass by reference language? What about Prolog?
About breakpoints, they usually have hardware support. But since Java runs on a virtual machine, I have no idea it the buck stops at the JVM or if they use the hardware interface.
Yes, the value can either be copied or a reference to it can be passed and this determines whether it is pass by value or by reference.
It is clear that Java is pass by value but a little bit confusing since everybody is used to thinking about objects as references and this people confuse that these are different references than the ones in "pass by reference".
As to breakpoints this is more complicated and will depend on whether the code is interpreted or it has already been compiled.
In an interpreted bytecode (before JIT comes and compiles it) the buck stops at JVM as it is the one responsible for actually executing the bytecode.
Once JIT comes and compiles the code, the JVM looses ability to stop at a given physical instruction. In this case I think one of two things happen:
1. The function reverts to interpreted (bytecode) version.
or, 2. The JVM inserts instruction into the generated bytecode.
But I don't know JVM that well to tell which one is used, actually.
It is clear that Java is pass by value but a little bit confusing since everybody is used to thinking about objects as references and this people confuse that these are different references than the ones in "pass by reference".
As to breakpoints this is more complicated and will depend on whether the code is interpreted or it has already been compiled.
In an interpreted bytecode (before JIT comes and compiles it) the buck stops at JVM as it is the one responsible for actually executing the bytecode.
Once JIT comes and compiles the code, the JVM looses ability to stop at a given physical instruction. In this case I think one of two things happen:
1. The function reverts to interpreted (bytecode) version.
or, 2. The JVM inserts instruction into the generated bytecode.
But I don't know JVM that well to tell which one is used, actually.
1) When adding the 2^n'th element. Linked List would just append to the tail O(1) time where as ArrayList would double the size copy half the array and then add it doing O(N) amount of work. Still though amortized analysis of insertions in array list is O(1) because rarely do we double the size of array.
(30 times required to double the array for insertion of a billion elements).
(30 times required to double the array for insertion of a billion elements).
I can't help but think that this is due to a combination of selection bias via the applicant pool and interviewer bias.
It's kind of ironic that his logic is flawed here - "I interviewed 120 master's program applicants and none of them knew about contrapositive equivalence - therefore students are no longer learning basic logic rules in undergrad."
I'm making a big assumption here, but the way this reads, the author sounds like the kind of interviewer who would get frustrated if a candidate wouldn't immediately know the answer to a question or if a candidate asked for clarification, and subsequently write off a candidate before the interview's over. If that's the case, it's not entirely surprising that 100% of his interviewees would fail this question.
It's kind of ironic that his logic is flawed here - "I interviewed 120 master's program applicants and none of them knew about contrapositive equivalence - therefore students are no longer learning basic logic rules in undergrad."
I'm making a big assumption here, but the way this reads, the author sounds like the kind of interviewer who would get frustrated if a candidate wouldn't immediately know the answer to a question or if a candidate asked for clarification, and subsequently write off a candidate before the interview's over. If that's the case, it's not entirely surprising that 100% of his interviewees would fail this question.
I think it's more that people are not familiar with the formal presentation of the problem. I doubt many people would have difficulty understanding a less abstract statement:
dog => mammal (dog implies mammal )
What can we say about not a dog ? (can be a cat, or a chair... ) What can we say about not a mammal ? (can be a chair, building... )
It's more intuitive because we as human understand the groups.
dog => mammal (dog implies mammal )
What can we say about not a dog ? (can be a cat, or a chair... ) What can we say about not a mammal ? (can be a chair, building... )
It's more intuitive because we as human understand the groups.
It surprises me that more of the folks he interviewed didn't try to figure out the contours of the formal presentation of the problem by plugging in concrete examples; isn't that the default "brute force" attempt you'd expect from someone trying to work out problems like this? It's the same thing you'd expect from someone solving Leetcode problems; you don't attack the general case immediately unless you've memorized the problem before, you usually try to play around with concrete examples until you've got enough of a handle on it to try and code up something a little more general.
> I got a few vague and wordy excursions into things that are true and things that are false, but never the clear, straightforward answer. Not once.
Sounds like he made a point to shut down that line of reasoning.
Sounds like he made a point to shut down that line of reasoning.
What part of this quote gives you that impression?
I don't think I've ever used the word 'implies' in that context, which may be the problem with the question. It still doesn't quite make sense in my thought process. Does a dog 'imply' a mammal? I wouldn't think so, a dog guarantees a mammal.
'Implies' to me suggests a possible underlying interpretation. If someone tells me he wants to eat, it implies that he is hungry. However he might not be hungry, he might be strict about eating at 8pm for other reasons. An 'implication' is perhaps the most likely association, but not necessarily the correct one.
'Implies' to me suggests a possible underlying interpretation. If someone tells me he wants to eat, it implies that he is hungry. However he might not be hungry, he might be strict about eating at 8pm for other reasons. An 'implication' is perhaps the most likely association, but not necessarily the correct one.
'Implies' is a term with a formal meaning in logic. You don't get to question a domain simply because one of its pieces of jargon has other interpretations in the vernacular.
From the title
> What Everyone Knows
I don't believe everyone knows of the formal meaning in logic, even among candidates for a Master's program. He doesn't seem to want to consider that there's a flaw in his question, rather than a failure on our academic institutions.
> What Everyone Knows
I don't believe everyone knows of the formal meaning in logic, even among candidates for a Master's program. He doesn't seem to want to consider that there's a flaw in his question, rather than a failure on our academic institutions.
> and What No One Knows
The question certainly has some flaws in phrasing (discussed elsewhere in this thread). Its use of the word "implies" is not a flaw. If intro-level formal logic is a valid requirement, then there is no problem using "implies" in that context. If intro-level formal logic is not a valid requirement, then the whole question is bunk, but not the use of "implies".
The question certainly has some flaws in phrasing (discussed elsewhere in this thread). Its use of the word "implies" is not a flaw. If intro-level formal logic is a valid requirement, then there is no problem using "implies" in that context. If intro-level formal logic is not a valid requirement, then the whole question is bunk, but not the use of "implies".
It's perhaps plausible that someone might assume the colloquial definition, but if a candidate for a master's program doesn't know of the formal logic definition in the first place, that is a failure of our academic institutions.
Except that it also depends on the definition you're using for "implies," so the normal use of English breaks things if you're really asking about logic. For example, dog implies "likes dogfood" is a reasonable thing to say, but "doesn't like dogfood" certainly includes dog outliers who only eat, say, kitchen scraps, and refuse dogfood. So no, a implies b doesn't let you say not a implies not b, given the normal definition of "implies."
I suspect though that this is the kind of quibbling that will quickly pass the interview test; you say something about dogfood and colloquial use of _implies_, the interviewer says "oh no, we're talking about formal logic where implies means..." and you go on from there. And frankly, that's the kind of interview question that's useful, since if you assume that marketing people use the logic definition of "implies" you're going to be in all sorts of pain in real-world meetings about developing software.
I suspect though that this is the kind of quibbling that will quickly pass the interview test; you say something about dogfood and colloquial use of _implies_, the interviewer says "oh no, we're talking about formal logic where implies means..." and you go on from there. And frankly, that's the kind of interview question that's useful, since if you assume that marketing people use the logic definition of "implies" you're going to be in all sorts of pain in real-world meetings about developing software.
I don't understand.
If A implies B, then not B implies not A, and I'm pretty sure when I was in CS school in France (5 years ago) we learned this.
And I'm also pretty sure that I knew this before, though I can't exactly remember when I first learned it.
If A implies B, then not B implies not A, and I'm pretty sure when I was in CS school in France (5 years ago) we learned this.
And I'm also pretty sure that I knew this before, though I can't exactly remember when I first learned it.
Modus tollens. It was also covered in both CS (explicitly in Discrete Math) and Philosophy (explicitly in Intro to Logic, and implicitly in many others) at my school in the US.
It seems like the question in the article doesn't really make it clear that you're supposed to answer about the relation between the two. It could easily be interpreted as a question about the truth value of each.
It's definitely true that some people don't think in terms of formal logic and wouldn't know this anyway (this is why we have affirming the consequent and denying the antecedent as common examples of bad logic), but I don't think the question as stated demonstrates that of them.
EDIT: Just remembered it being explicitly explained in Intro to Philosophy and/or Professional Ethics as well.
It seems like the question in the article doesn't really make it clear that you're supposed to answer about the relation between the two. It could easily be interpreted as a question about the truth value of each.
It's definitely true that some people don't think in terms of formal logic and wouldn't know this anyway (this is why we have affirming the consequent and denying the antecedent as common examples of bad logic), but I don't think the question as stated demonstrates that of them.
EDIT: Just remembered it being explicitly explained in Intro to Philosophy and/or Professional Ethics as well.
One amusing thing I saw in the two courses I mentioned is that in Intro to Logic, we spent something like a month learning each of the eighteen rules of inference, gradually adding a couple each day until we were familiar with all of them.
In Discrete Math, the professor wrote out the eighteen rules in as part of a single lecture and then we had homework due that same week wherein we were expected to know and use all of them. (He may have introduced predicate logic in that same lecture.)
Intro to Logic was a philosophy course, but some majors allowed students to take it instead of their one required College Algebra course. The result was it was a lot of very non-technical people who struggled with intro algebra, and consequently struggled with formal logic. (Predicate logic was the focus of the third section of the course later on.)
Discrete Mathematical Structures was a math/cs course, where almost every student was a CS major, so it was predominantly technically-minded people for whom formal logic was at least very familiar, if not natural.
In Discrete Math, the professor wrote out the eighteen rules in as part of a single lecture and then we had homework due that same week wherein we were expected to know and use all of them. (He may have introduced predicate logic in that same lecture.)
Intro to Logic was a philosophy course, but some majors allowed students to take it instead of their one required College Algebra course. The result was it was a lot of very non-technical people who struggled with intro algebra, and consequently struggled with formal logic. (Predicate logic was the focus of the third section of the course later on.)
Discrete Mathematical Structures was a math/cs course, where almost every student was a CS major, so it was predominantly technically-minded people for whom formal logic was at least very familiar, if not natural.
I think it's a trick question, in the way he phrases it. If A implies B, then not B implies not A. But he doesn't say that. He says, "If A implies B, does not A imply not B," for which the answer is no.
Well, no, he asks "What can we say about `not A' and `not B'?"
The way he phrases it is "What can we say about !A and !B," according to the article. The only time he talks about "If A implies B, does not A imply not B," is when describing close answers he got to his question. I don't think it's a trick question the way he asks it, and it also seems like the sort of thing you should be able to work out with concrete examples if you aren't sure.
God I feel like an idiot for questioning this, but is it really true not B implies not A in that situation? It seems like it depends on what you mean by "implies."
E.g., you could have A -> B, and A -> C, and B != C. Then C is not B, but implies A just as much as B might (in the very least it doesn't imply not A per se, as A might be true). It seems like there's some implicit assumptions going on.
E.g., you could have A -> B, and A -> C, and B != C. Then C is not B, but implies A just as much as B might (in the very least it doesn't imply not A per se, as A might be true). It seems like there's some implicit assumptions going on.
"not B" doesn't mean "something else which is not identically B", it means "the negation of B". Also, the statement "A->B" has absolutely no bearing on the statement "B->A". Hope this helps.
> I recently conducted a large number of remote one-on-one interviews of candidates to a new master program in software engineering.
> Assume that A implies B. What can we say about `not A' and `not B'?
Maybe I'm missing something but there's no "implies" operator in programming languages and it isn't used this way in casual language so why would you expect software engineers to understand a very precise definition of an operator they don't use?
I've taught formal logic classes and people new to it including programmers always have problems with "implies". Formal logic isn't intuitive and needs to be taught.
> Assume that A implies B. What can we say about `not A' and `not B'?
Maybe I'm missing something but there's no "implies" operator in programming languages and it isn't used this way in casual language so why would you expect software engineers to understand a very precise definition of an operator they don't use?
I've taught formal logic classes and people new to it including programmers always have problems with "implies". Formal logic isn't intuitive and needs to be taught.
it's also underspecified if the desired answer is "not A implies not B". there are an infinitude of examples of that particular conclusion being false in the real world.
I think you're demonstrating my point. It sounds like you're going with what you intuitively think "implies" must mean like you would if you saw it written in a news article, when instead the article is using a formal logic definition that would appear appears often in logic/math proofs.
You really need to look at the truth table the implies operator and read off the answer from there. There'd be no confusion if the operator didn't have a name that roughly matched something we say in casual language.
You really need to look at the truth table the implies operator and read off the answer from there. There'd be no confusion if the operator didn't have a name that roughly matched something we say in casual language.
and that's exactly my point. you need to specify 'formal logic', otherwise, it's underspecified.
Ah, okay. Yes, it's ambiguous to the point of being a trick question to me.
yah, if the author wants to assert a (perhaps deceptive) pedantic logical conclusion about others, then they should be particularly keen to avoid making pedantic logical errors themselves.
It does exist. You know it as the assignment operator.
Not quite - logical implication maps to function types in programming via the Curry-Howard isomorphism:
https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
i.e. knowing "A implies B" is like having a function that accepts a value of type A and outputs a value of type B.
https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
i.e. knowing "A implies B" is like having a function that accepts a value of type A and outputs a value of type B.
> so why would you expect software engineers to understand a very precise definition of an operator they don't use
I wasn't in grad school for a CS program, but one of my friends was. One thing I noticed is how often the papers he read, as well as the course material, used formal logic symbols.[0] His research area was very much applied - not theoretical.
Not knowing "basic" things like what implies means formally is likely going to hurt you in a MS program.
[0]: http://www.philosophypages.com/lg/e10a.htm
I wasn't in grad school for a CS program, but one of my friends was. One thing I noticed is how often the papers he read, as well as the course material, used formal logic symbols.[0] His research area was very much applied - not theoretical.
Not knowing "basic" things like what implies means formally is likely going to hurt you in a MS program.
[0]: http://www.philosophypages.com/lg/e10a.htm
For me, the shocker is the penultimate paragraph, stating that many computing programmes at many institutions no longer teach logic. I could see that for a fourth-rate community college (maybe) but if we are talking about universities here, then it's time to close down those departments.
A course in logic is often offered in a Phil Dept, perhaps as a way to meet liberal studies requirements (that's where I took it, and where the course is at the school where I now teach).
The equivalence of A => B and ~B => ~A is taught in every college and university CS program I've ever seen, as part of a standard course that may be called something like Discrete Math. I teach this course out of a book by Rosen and another popular author is Epp. This equivalence is also, as many other posters noted, perfectly natural to a person with a technical bent.
But I understood the piece's author's point to be that they are looking for a certain maturity. When we teach, we see that there are stages of competence through which students pass. First they are able to ape the required work on a sentence-by-sentence basis, but not whole problems from start to finish. Next they are able to reliably work entire problems, but only in a context (for instance, they can do induction in the Induction section but outside of it they are easily confused). Finally, with enough practice, they have a larger view and can select the appropriate tool for the job when there are a lot of tools lying around, as well as apply that tool. (FWIW, I take the posters here saying that the author didn't prompt well enough to be recognizing those stages, implicitly.)
The equivalence of A => B and ~B => ~A is taught in every college and university CS program I've ever seen, as part of a standard course that may be called something like Discrete Math. I teach this course out of a book by Rosen and another popular author is Epp. This equivalence is also, as many other posters noted, perfectly natural to a person with a technical bent.
But I understood the piece's author's point to be that they are looking for a certain maturity. When we teach, we see that there are stages of competence through which students pass. First they are able to ape the required work on a sentence-by-sentence basis, but not whole problems from start to finish. Next they are able to reliably work entire problems, but only in a context (for instance, they can do induction in the Induction section but outside of it they are easily confused). Finally, with enough practice, they have a larger view and can select the appropriate tool for the job when there are a lot of tools lying around, as well as apply that tool. (FWIW, I take the posters here saying that the author didn't prompt well enough to be recognizing those stages, implicitly.)
I honestly, don't think this is a fair assessment. For years, there has been a huge argument about what they should teach as far as CS goes. Logic is definitely important, but do you really fault a degree program and a kid's (young adult) ability on something that is never stated that way in the real world? Most people just want to graduate and get on with life. They learn what they need to pass and then move on, and there is nothing wrong with that. I put this in the same boat as all those logic puzzles they asked in the mid 90's early 00's. Ok maybe someone given enough time should be able to figure it out, but there are a lot of people out there that will do just fine at a job without being able to answer it on the spot.
Bertrand is definitely in a league of his own as far as skill and intelligence, but he comes from a different era than today. I'm not insulting his age, but I do think that we need to take into account what has changed over the last 35-40 years. Things seem so much more complex than before. Even source control is complex. I feel for people just starting out these days. It's a give and take. You have to gloss over some things to make time to teach about others.
Bertrand is definitely in a league of his own as far as skill and intelligence, but he comes from a different era than today. I'm not insulting his age, but I do think that we need to take into account what has changed over the last 35-40 years. Things seem so much more complex than before. Even source control is complex. I feel for people just starting out these days. It's a give and take. You have to gloss over some things to make time to teach about others.
> Logic is definitely important, but do you really fault a degree program and a kid's (young adult) ability on something that is never stated that way in the real world? Most people just want to graduate and get on with life.
He is not interviewing people who want to "get on with life". He's interviewing people who are entering a Master's program. In most areas of engineering, and especially in CS/SW, one can get pretty good pay and make a living without an MS. So for MS and beyond, universities care more about academic rigor, etc, and whether what they learn is useful in industry is given a much lower weight (rightly so).
A lot of universities really don't want MS/PhD students who are using it to get a promotion or bump in pay. Some do compromise for MS students assuming they're paying full tuition.
Chances are quite high that when they take a grad level course, the professor will expect you to know this. I did grad studies in a different engineering discipline, and professors generally had low tolerance for students who did not know something this basic.
Finally:
> on something that is never stated that way in the real world?
I'm probably biased, but I often state this in the real world :-) It has not been a problem in professional settings.
He is not interviewing people who want to "get on with life". He's interviewing people who are entering a Master's program. In most areas of engineering, and especially in CS/SW, one can get pretty good pay and make a living without an MS. So for MS and beyond, universities care more about academic rigor, etc, and whether what they learn is useful in industry is given a much lower weight (rightly so).
A lot of universities really don't want MS/PhD students who are using it to get a promotion or bump in pay. Some do compromise for MS students assuming they're paying full tuition.
Chances are quite high that when they take a grad level course, the professor will expect you to know this. I did grad studies in a different engineering discipline, and professors generally had low tolerance for students who did not know something this basic.
Finally:
> on something that is never stated that way in the real world?
I'm probably biased, but I often state this in the real world :-) It has not been a problem in professional settings.
>He's interviewing people who are entering a Master's program.
You're right I missed that. Fair point.
>I'm probably biased, but I often state this in the real world :-) It has not been a problem in professional settings.
The concept does come up, but I normally don't hear it this way. It comes up in different forms sure. Maybe it has, and I just gloss over not thinking about the language.
You're right I missed that. Fair point.
>I'm probably biased, but I often state this in the real world :-) It has not been a problem in professional settings.
The concept does come up, but I normally don't hear it this way. It comes up in different forms sure. Maybe it has, and I just gloss over not thinking about the language.
Programming is, in many ways, applied logic. Understanding logic leads to much cleaner code. People who don't understand logic make the code I've had to clean up. Things like taking a > 500 line function with a complex set of nested conditionals, pulling them all out, and realizing that it could be < 100 lines with no nesting or only one level below the top by properly placing guards at the top of the function.
I have worked with programmers who have no understanding of logic, I never want to work on their code again. It's a remarkably simple skill to develop and should be part of every CS students' curriculum.
I have worked with programmers who have no understanding of logic, I never want to work on their code again. It's a remarkably simple skill to develop and should be part of every CS students' curriculum.
Not sure if it helps someone, but I like to use the following intermediate formula to explain it:
"A implies B" is equivalent to "B or (not A)" (either B is true and then A can be true or false, or B is false but then A cannot be true since it would entail that B is true as well).
"B or (not A)" is equivalent to "(not A) or B" and to "(not A) or (not (not B))", you can then apply the previous reasoning to realize it's also equivalent to "(not B) implies (not A)".
Not sure if my twisted way of thinking about it helps anyone though... furthermore it requires to have clearly in mind the distinction between "or" and "xor", the later being sadly closer to the vernacular use of "or"...
"B or (not A)" is equivalent to "(not A) or B" and to "(not A) or (not (not B))", you can then apply the previous reasoning to realize it's also equivalent to "(not B) implies (not A)".
Not sure if my twisted way of thinking about it helps anyone though... furthermore it requires to have clearly in mind the distinction between "or" and "xor", the later being sadly closer to the vernacular use of "or"...
Another exemple that I like:
"When it rains I carry my umbrella."
does not prevent me from carrying said umbrella when the weather is nice.
However it is the same as saying that "when I don't have my umbrella with me then the weather is good".
Do you think the results would be different if people were asked "If A implies B then does not B imply not A"?
This could just be about using the right prompt - I do not know how information is stored in the brain and whether most people would be able to access the correct answer: "not B implies not A" if the prompt were just "what can we say about not A and not B".
Assuming that most people would actually know the answer if prompted the right way, one reason the prompt given in the article may not lead them to the answer could be that most people do not need to apply Modus Tollens outside of a class on Logic. And thus, since the concept has never been widely applied, at least in their heads, it is not accessible?
This is all conjecture of course.
This could just be about using the right prompt - I do not know how information is stored in the brain and whether most people would be able to access the correct answer: "not B implies not A" if the prompt were just "what can we say about not A and not B".
Assuming that most people would actually know the answer if prompted the right way, one reason the prompt given in the article may not lead them to the answer could be that most people do not need to apply Modus Tollens outside of a class on Logic. And thus, since the concept has never been widely applied, at least in their heads, it is not accessible?
This is all conjecture of course.
I think this is applied all the time, but we might not always realize when we're using it. Also, while your version of the prompt may be more likely to elicit the correct response, this does not mean the original prompt was somehow wrong.
One thing that stuck with me about these kinds of questions was that logical "implies" can be translated to set theory as "is a subset of." Then I draw a Venn diagram and the lightbulb goes on instantly for me.
Now I read the thread here and still don't know the answer. I too am a bit stuck with the word "implied". Is it if A is true, B must be true?.
I answered the question without reading further and wrote this:
not A:
- obvious: can not be A;
- and maybe relevant in the context but no true insight: could be B, could imply A, could imply B
Exactly the same for B (can not be B, etc.)
Hope I'm hired now.
I answered the question without reading further and wrote this:
not A:
- obvious: can not be A;
- and maybe relevant in the context but no true insight: could be B, could imply A, could imply B
Exactly the same for B (can not be B, etc.)
Hope I'm hired now.
Quicksort isn't O(n), as far as I know, the best you can do is O(n log(n))
Implies isn't something I've ever had to program... and it took me a moment to figure out that NOT B implies NOT A, which is interesting... but I don't see how it's useful.
Implies is probably something you've used in a program's logic, it's probably not something you've directly programmed (in the sense that few people, outside of exercises, are going to code up logical operators). You'll see it in some conditionals. Think of the logical expression: If the radiation emitter is on then the safety door is closed.
This is not causal, we don't say that we will close the door, we are saying something that should just be true about the system (like in an assert). Perhaps if this assert fails we want the whole thing to shutdown.
Since languages like C don't have an implies operator, you'd write this assert as something like:
This is not causal, we don't say that we will close the door, we are saying something that should just be true about the system (like in an assert). Perhaps if this assert fails we want the whole thing to shutdown.
Since languages like C don't have an implies operator, you'd write this assert as something like:
ASSERT(!RADIATION_EMITTER_ON || DOOR_IS_SHUT,
"Well, we irradiated something, but probably not what we wanted.")
A B | A => B ~A || B
F F | T T
F T | T T
T F | F F
T T | T TI have also found that most people don’t know how to think. There is nothing tricky or unclear about the way he asks the question. I certainly wouldn’t hire somebody to write computer programs who couldn’t answer this question right away. I don’t think that’s harsh or elitist; I just don’t see how someone who doesn’t know this basic rule of thought can be a decent programmer.
Not that I would qualify. I’m not sure what the complexity of quicksort is. But I know how to think. I think.
ADDED: I’m also fuzzy on MVC. I think I know what they’re supposed to mean, but, in practice, the ideas seem to overlap so much that I’m unsure. In Django, for example, that calls itself an MVC framework, there is a certain lack of agreement about what is what.
So I would be able to answer the question that “nobody” can, and not do too well on the other one.
Not that I would qualify. I’m not sure what the complexity of quicksort is. But I know how to think. I think.
ADDED: I’m also fuzzy on MVC. I think I know what they’re supposed to mean, but, in practice, the ideas seem to overlap so much that I’m unsure. In Django, for example, that calls itself an MVC framework, there is a certain lack of agreement about what is what.
So I would be able to answer the question that “nobody” can, and not do too well on the other one.
before reading the article my initial answer was 'nothing'
However, there's something about the way this guy asked the question that makes me unsure whether I would have correctly answered it on the spot. It's somehow detached from both application, and the logic that underlies it.
If the question had been asked as: "Is there any relationship between Not A and Not B" I would have instantly gotten the correct answer.
...But the way he asked it, it comes across as a question about whether Not A implies Not B which of course does not follow the given. I realize none of those words are in actually in there, yet the phrasing of the question somehow leads my brain into filling in the gaps in that way. My suspicion is that this is actually a common thought pattern and perhaps those being interviewed may have fallen into a similar trap.