I can't recall any instance where I actually needed to do so as part of my job
I guess that is true for nearly everyone here.
Which is exactly why it's a bad interview question. The more experience you have, the longer it's been since you've been in that introductory algorithm class and the less likely you are to remember the details of a sorting algorithm which you should never choose for any non-trivial task. The ability to answer that interview question has nothing to do with your practical skills as a programmer; it tests only your ability to remember useless trivia.
in an introductory Algorithms class as an example of what not to do.
That is wrong. I suggest to check Wikipedia, facepalm.
Since you refer to Wikipedia, I'll leave this quote here as further evidence that bubble sort is best relegated to the role of a bad example:
Even among simple O(n^2) sorting algorithms, algorithms like insertion sort are usually considerably more efficient.
Due to its simplicity, bubble sort is often used to introduce the concept of an algorithm, or a sorting algorithm, to introductory computer science students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught.
The Jargon File, which famously calls bogosort "the archetypical [sic] perversely awful algorithm", also calls bubble sort "the generic bad algorithm". Donald Knuth, in his famous book The Art of Computer Programming, concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems", some of which he then discusses.
Bubble sort has a few niche uses, as I already alluded to. It can be faster when the list is extremely small (like three elements or less) or when the input list is known to be very nearly sorted with only a few close elements swapped. Such cases are vanishingly rare in the real world.
Likewise, if you're an expert programmer, you should be able to write bubble sort on the whiteboard without a web search.
Who actually uses bubble sort on the job? Bubble sort is one of those algorithms that you should see roughly once in your career—in an introductory Algorithms class as an example of what not to do. As simple as a bubble sort may be, if you've been programming long enough to earn the title "expert" I think you can be forgiven for forgetting the details. For that matter, unless you've been doing bare-metal systems programming, best practice in almost every case is to use a standard library function rather than writing your own sort routine. The average expert programmer working in a high-level language has very little reason to reimplement any sort algorithm in the course of their professional work, though most should at least be aware that there are multiple reasonable sort algorithms, and that the proper choice depends on the task at hand.
A better interview task would be to compare and contrast some of the more common algorithms and give examples of situations where each would be suitable. I wouldn't expect bubble sort to make the list, but given the pseudo-code for a bubble sort I would expect the applicant to be able to reason about its time and space complexity and articulate why it would generally be a poor choice compared to the other options. (The only possible exception I can think of offhand, for bonus points, is where the array length is known to be trivial and you have a really pressing need to minimize both code and stack size, but even then it's a close call.)
Speaking as a Sr. Software Engineer with at least 15 years of professional programming experience, while I would be able to write bubble sort, merge sort, and quicksort by hand without a reference, I can't recall any instance where I actually needed to do so as part of my job. The implementation details are inconsequential trivia compared to knowing that quicksort is best for mutable data structures with fast random access, while merge sort is more suitable for immutable data structures or data too large to fit in RAM.
Also, when a commit is signed it becomes bundled with it, which means its associated SHA-1 hash will change.
Yes, but the commit only includes the SHA-1 hash of the tree object, which in turn refers to other trees and files by their SHA-1 hashes. Given the possibility of SHA-1 collisions, the commit signature guarantees that you get the right commit, but not necessarily the right file contents. Of course, for this attack to work someone would have to get their obviously artificial collision-prone file included in the signed commit in the first place, so that they could later substitute the malicious version. This is not a practical means of attack for source code repositories where commits are subject to even cursory peer review. There might be some justification for extra precautions when it comes to opaque binary files, such as firmware, which could be as simple as including the SHA-2 of the binary file as part of the commit and verifying it during the build.
If there is one thing the Wikipedia article makes perfectly clear, it is that there is considerable disagreement over the nature and limits of the "appeal to authority" logical fallacy. However, in the first and only "notable example" given in the article to illustrate "appeal to authority", the authority figure in question was an expert in the field, which leads me to seriously doubt your assertion that "[a]ppeal to authority is a logical fallacy when the person is NOT an expert in the field."
Quoting from the article, with emphasis added:
In the Western rationalistic tradition and in early modern philosophy, appealing to authority was generally considered a logical fallacy.
More recently, logic textbooks have shifted to a less blanket approach to these arguments, now often referring to the fallacy as the "Argument from Unqualified Authority" or the "Argument from Unreliable Authority".
However, these are still not the only recognized forms of appeal to authority. For example, a 2012 guidebook on philosophical logic describes appeals to authority not merely as arguments from unqualified or unreliable authority, but as arguments from authority in general. In addition to appeals lacking evidence of the authority's reliability, the book states that arguments from authority are fallacious if there is a lack of "good evidence" that the authorities appealed to possess "adequate justification for their views."
So on the whole, it would not be unreasonable to consider an argument of the form "X is true because Y said so, and Y is a recognized authority in the field of X" an example of the "appeal to authority" logical fallacy. That is not to say that X is thus untrue, or that Y's opinion should be disregarded—but there is a vast difference between the valued opinion of a qualified authority figure and a sound logical argument.
You would be perfectly correct to say that this is not an example of the "Argument from Unqualified Authority" fallacy described in the newer textbooks, but that fallacy is much more limited in scope than "appeal to authority".
you can't infringe on their right of ownership by copying the DVDs
There is no such thing as a "right of ownership" over the content of the DVDs. The poorly named legal fiction of "copyright" is not a right at all, but merely a privilege; and like all other instances of legal privilege, it can only exist by infringing on the actual ownership rights of others.
The difference is obvious even to a cursory inspection. If copyright were about ownership then it wouldn't expire after a limited duration, or be subject to exceptions for fair use or (in some cases) compulsory licensing. More importantly, if copyright were treated as a right of ownership, then the liability for infringement would be determined by the extent to which the infringement diminished the copyright holder's ability to make use of the copyrighted content—which is, of course, impossible, since the creation of a new copy does not in any way diminish the utility of any existing copy. Copyright is not a right, it's an example of misguided social engineering run amok, a legal parasite intent on strangling its host.
The thing is, unless you have seen everything you would possibly want to see in older movies available for $10, why would you pay $50 for the same home experience?
Yes, I have seen every decent older movie I care to see.
This may seem a bit obvious, but new movies turn into older movies at exactly the same rate that new movies are released. It's not as if "older movies" were a fixed set. If you make a policy of only watching movies that are at least X years old, you'll end up with the same amount of "new" (to you) content each year as if you watched every new blockbuster on opening night at several times the price.
Perhaps the government has no right to search X, for any X, but they DO have the right to say "no you can't come in", or impose any conditions they feel are proper before granting entry.
False equivalency. You have the right to exclude others from your home because you own your home. Your rights of ownership are founded, ultimately, in the homesteading of previously unowned land though the labor of an original owner, plus an unbroken chain of voluntary contracts passing the rights to that land from its original owner to you. The government, by contrast, has no such legitimate claim to ownership of the entire country, and consequently does not have the right to exclude anyone from entering.
On the other hand, it would be wrong for me to block your entry into your *own* house... Unlike people who wish to visit, peope have a right to enter their own home.
Anyone with the right to enter their own home also has the right to invite others to enter. It would be wrong for you to block the entry of my invited guests into my house.
Once you're in the US (and while your outside the US), your rights as a human being should be fully respected.
Inside, outside, or in transition, your rights as a human being should always be respected.
Bill Gates is only going to buy so many TVs, cars, and houses. Doubling his wealth is not going to change his spending habits.
It won't change his personal consumption habits, no. Instead he would spend the extra wealth on capital investments, which improve the efficiency of production and allow vast numbers of other people to buy more TVs, cars, and houses at lower prices.
Consumption is important, of course, but all economic progress comes from the part of our income which we don't immediately spend on short-lived consumer goods.
You're also conflating wealth with money. They aren't the same thing. Bill Gates has a lot of wealth, but most of it isn't in the form of money. Instead, he owns shares in various investments. Even if it were, people would simply switch to an alternate form of currency long before the symptoms you're attributing to "wealth concentration" became apparent.
There is one factor which could have the effect you're referring to, but it only occurs in non-free markets. It is not always the case that more capital investment equals lower prices; over-investment can create a situation where the prices necessary to cover the cost of the capital are above the optimal point on the supply & demand curve. Imagine, for example, that you can sell 10,000 of a certain widget per year at an optimal price point of $10 each, and that your cost per widget is $8 (for $20k profit). If you rent a machine for $50,000/year you can lower production costs (excluding the rent) to $5 each. Under normal circumstances this would be an uneconomical investment, since the rent would raise the overall cost to $10 per widget, eliminating your profit. (Raising the price is not an option since that would reduce both the quality sold and overall revenues.) However, if a regulation were introduced requiring the use of this machine it would change the parameters: now the optimal price point (for widgets produced with this machine) is perhaps 8,000 units at $18, and you only make $14,000 in profit while 2,000 potential customers do without widgets. The same argument can be applied if the machine instead comes with a tax-funded subsidy rather than a mandate. With the subsidy included, the real cost per widget is still $18, but the buyer only sees $10 at the point of sale and the remaining $8 is spread among all the taxpayers—reducing the money they have left over to spend on widgets and other goods. Any market intervention (regulation, tax, subsidy, monetary policy, etc.) which either rewards or punishes capital investment, and thus shifts the allocation of resources away from the optimal balance, reduces the efficiency of the market and the purchasing power of the average citizen.
But earning 4 times the national average is clearly not equal.
You're leaving out half the story here. If two people given similar opportunities make different choices, and as a result one of them ends up earning four times as much as the other, that isn't inequality. They each had an equal chance at earning that income; one took advantage of that opportunity and the other did not. The thing we should be striving for is equal opportunity, not equality of outcome. It is only natural that someone who takes the long view and makes difficult choices should end up better off than someone else in the same circumstances who focuses only on the present.
On the subject of inherited wealth, this applies just as much to families as it does to individuals. True, the recipient of the inheritance has been granted an unearned opportunity which others lacked. (Unearned by the recipient, that is—the parent earned the right to make that gift.) Taking the larger view, however, any family with even a small amount of discretionary income has the option of saving and investing and passing those investments down to the next generation, following a long-term strategy which will eventually result in a sizeable inheritance. This demonstrates how different choices at the family level over the course of multiple generations can produce unequal outcomes from equal opportunities.
Our choices make all the difference, not just for ourselves but for our descendents as well, and that is exactly as it should be. The inequality we should be concerned about is inequality under the law, and especially the variety of legal inequality which results in property earned by one individual or family being unjustly seized and granted instead to some other individual or group. This is an attempt to force equal outcomes by perversely punishing those who make better choices.
I hope you don't count "You can't dump toxic sludge from your factory into the local river" as "ridiculous."
The enforcement of property rights is not regulation. You have every right to use your own property as you please, but others have exactly the same right—implying that you do not have the right to use their property without their permission. If you dispose of your pollutants in such a way that they end up harming others' property, including but not limited to their bodies, then you have infringed on their property rights and owe the victims redress. This is not some arbitrary regulation regarding how you may use your own property, but rather the natural consequence of others' rights to determine the use of their property.
As a term of art in political discussions, the term "regulation" refers to a restriction above and beyond simply respecting the property rights of others. Some regulations are indeed "ridiculous", but most are simply wrong, a product of politicians making a nuisance of themselves in situations where they have no standing to interfere.
The Fourth Amendment bans only "unreasonable searches and seizures". The exception considers searches at the border to be "reasonable".
That's only half of the story. The 4th Amendment also says that no warrants shall be issued (in plain language: no permission shall be granted to perform a search or seizure) "but upon probable cause, supported by Oath or affirmation, and particularly describing the place to be searched, and the persons or things to be seized." The so-called "Border Search Exception" manufactured by the courts out of thin air is an unconstitutional warrant. There is no probable cause, no supporting Oath or affirmation, and no particular description of the place to be searched or the person or things to be seized. Ergo, there is no constitutional authority to issue a warrant, which would be the only legal basis to perform any search or to seize any property.
Probable cause—or in other words a reasonable, and evidence-based, expectation that a particular search will turn up evidence of illegal activity sufficient to retroactively justify the search—is the only thing that makes a search "reasonable". If the majority of these searches do not uncover evidence of illegal activity then there is no probable cause and they are de facto unreasonable.
Well, it isn't 'nothing.' It costs money to develop ideas and art.
And they're welcome to charge for the development and initial publication of those ideas and works of art. The part that costs "nothing" is making and distributing copies—and yet that's what they charge for now. You're not paying for an idea or work of art to be developed, you're paying for permission to make a copy of an idea or artwork which already exists. (Or you're paying someone else to make the copy for you, since they won't grant you permission to do it yourself.) What you are paying for comes at zero cost to the patent or copyright holder. If you made said copy without their permission they would not be harmed in any way—in terms of cost to the patent or copyright holder, infringement has exactly the same effect as if you never became aware of the work in the first place. Either way, they neither gain nor lose anything as a result of your actions. It is absurd to punish someone for infringement when simply ignoring the work causes exactly as much harm to the patent or copyright holder and yet goes unpunished.
Using the iterative algorithm I posted above, I think you can see that we do NOT track any data whatsoever about how we got to the current URL. All of the information about past pages, which would be on the stack in a recursive algorithm, do not exist in my program. So in fact it does *not* "track the same data"...
You're comparing apples and oranges. The iterative version of your program is not using the same algorithm as the recursive version. You replaced a depth-first search with a breadth-first search, which makes your example completely irrelevant for comparing iterative vs. recursive implementations of the same algorithm. Among other things, the order in which your web crawler visits pages is very different in the iterative version. To maintain the original order you would need to restore the depth-first search algorithm, which would imply tracking the chain of pages you came from—exactly like the recursive implementation, though you could store that information on the heap or in a database rather than on the stack. (Note that a tail-recursive implementation would also store that information on the heap or in a database... this isn't a matter of recursion vs. iteration.)
You are certainly correct that you *can* simulate iteration by using recursion.
The tail-recursive implementation is not "simulating" iteration. It is iteration. Expressing the same algorithm with a loop construct rather than an explicit function call would not make it any less recursive; the loop implies a built-in fixpoint operator. If this trivial difference of style makes any difference in how much stack space your function uses, that's a bug in your toolchain.
The key point, to me, is that at least what I mean by "recursive" is that there is a parent and a child. The parent doesn't return/exit until its child does - and its child, and its child, and its child, and its child...
That is not what "recursion" means. Moreover, how would that definition even account for something like tail-recursion, where the "parent" is replaced by the "child"? Logically, the "parent" still does not exit until the "child" does, but in the meantime it occupies no space on the stack and the return from the innermost "child" is also the return from all of the "parents". No matter how deep the tail-calls become, the stack use remains constant. Recursion only requires additional stack space when there is more for the function to do after the call, i.e. when it is not tail-recursion. Such cases cannot be converted to iteration (using the same algorithm) without shifting all the data required by the continuation from the function-call stack into some other data structure.
You' started talking about an apartment building, and in those places the residents are not the owners, and have only very restricted property rights.
In at least some of the cases in question it was the owner of the apartment building, not a renter, who was fined for using AirBnB. A renter's right to sublet, and more generally to allow others access to the apartment, is, of course, subject to the terms of their contract with the owner of the apartment building.
Zoning laws are not designed to prevent imminent threats of irreversible harm.
Yes, which is one of the many things wrong with zoning laws. Zoning laws in general are no more justifiable than the more specific restrictions on using AirBnB. However, that is a topic for another day.
The CFAA doesn't ban bona fide government investigations.
Right, but is this an bona fide investigation? IIRC that exception applies to law-enforcement agencies, whereas this is about the organization responsible for approving visas. They're not investigating any crime; it's more like a background check.
Either way, there's still the TOS issue. The applicant is not legally compelled to turn over the password; they can refuse (and allow their visa application to be denied). Ergo, if they do submit the password they are violating the TOS of their own free will, which can result in their account being terminated and perhaps other penalties.
Care to point to which step "is defined in terms of the process itself"? I don't see that anywhere.
It's part of the compiler's internal definition of the loop construct, and does not appear in the source code. In the object code it can be identified as the opcode that branches back to the beginning of the loop.
This becomes more obvious if you consider programming languages where iteration is not a built-in construct, and loops are written in terms of explicit recursion. In Haskell, for example, a simplified C "while" keyword (disregarding "break", "continue", etc.) could be implemented as the following recursive function:
while:: Monad m => m Bool -> m () -> m () while cond body = cond >>= \c -> when c (body >> while cond body)
Or using the fixpoint operator, without referencing the current definition by name:
while cond body = fix (\loop -> cond >>= \c -> when c (body >> loop))
Building on the fixpoint example above, would you call this a recursive function?
void f(void (*g)(), int c) { if (c < 10) g(g, c + 1); }
Sometimes it isn't so simple. The body of f() does not refer to f(). However, what happens if you call f(f, 0)? The function might be recursive, or it might not be, depending on the arguments. It all depends on that function pointer.
Arguments might be avoided by saying it's not a recursive FUNCTION - no function calls itself, can't run out of stack space.
It's not a recursive function, since it's not the entire function that's repeated. It would be more accurate to say that it contains a recursive function, though that inner function is hidden behind the loop construct. Barring the use of alloca() or similar it won't run out of space on the function-call stack, since alloca() / variable-length arrays and function calls are the only ways to allocate from the function-call stack, but the iterative version of the function still needs to track the same data and can still run out of memory given large enough inputs—just not stack memory. Sometimes that distinction is important, but more often it isn't, especially given the stack sizes available to programs running on most virtual memory based operating systems, ranging from several megabytes to "malloc() would fail first". (After all, some languages allocate stack frames from the heap.)
Anyway, the fact that (unoptimized) tail calls use stack space while iteration constructs ordinarily do not is nothing but an artifact of poor compiler implementation, and easily corrected through tail-call optimization. It's really no different from the way some languages with simplistic garbage-collection algorithms (e.g. Perl) fail to collect sets of objects with cyclic references. You can either take pains to avoid cyclic references (tail recursion), or just switch to one of the many modern languages which don't cause arbitrary runtime errors when you write code in the most natural style. Given a reasonable guarantee of tail-call optimization, function calls in general may allocate additional function-call stack space, but a call in tail position won't, so tail recursion is exactly the same as iteration in terms of expected stack use.
When there's such a pattern of behavior of disruption coming from apartments being rented out, isn't it okay to ban the underlying bad behavior?
No, that sort of prior restraint requires serious justification—"imminent threat of irreversible harm". The handful of minor disruptions which have actually occurred are nowhere near that level of threat; very few things are, short of direct physical attacks. While it would certainly be a simpler solution, prior restraint violates the property rights of those who rent out their apartments to considerate guests who do not cause such disruptions, while also causing harm to the guests themselves in the form of fewer choices of accommodation and correspondingly higher prices.
The Constitution says nothing about depriving one of property rights; only property.
A distinction without a difference. Property rights are property, and vice-versa. Any time your property rights are infringed you have been deprived of your property to at least some degree. To argue otherwise admits the absurd legal fiction that the property technically still belongs to you, you just don't have any actual right to use it—the property rights belong to someone else. When people talk about being deprived of their property, it's not mere physical possession that they're referring to but rather their legal rights relating to the property.
No, not with fines for renting out the apartment. Fines for disturbing the peace. The problem isn't the rental, which is no one's business but the property owner's. The problem is holding the property owner accountable for the use of the property, including use by guests. You want to rent out your apartment on AirBnB? No problem—but you are responsible to your neighbours for your guests' behavior during their stay. So you'd better make sure they're well-behaved and considerate before letting them stay at your apartment.
The persistent identification cookie on the laptop, tablet computer, or smartphone that a traveler carries allows access.
Legally speaking, it only allows access for the account owner. Barring a special exception to the Computer Fraud and Abuse Act, anyone else using that cookie (or the login & password, whether provided voluntarily in violation of the TOS or under duress) without the service provider's permission is committing a felony by hacking into the service provider's systems without authorization. The account owner may be at the border, but the account owner cannot legally delegate permission to access the account to a third party and the system being accessed is not located at the border.
The only legal option consistent with both the TOS you agreed to and CFAA is to refuse to turn over the passwords—even knowing that this means the visa request will be denied.
Some people would point out this solves a recursive and say it's therefore a recursive algorithm. The algorithm isn't recursive by definition because no function calls itself, even indirectly.
The algorithm is still recursive; the recursion is just built in to the language in the form of predefined iteration constructs like "foreach" and "while". Any time you have an iterative program of the form "first do X, and then repeat the process for the remaining input", that's recursion: one of the steps in the process (the repetition) is defined in terms of the process itself.
Some recursive algorithms can run in constant space, while others (such as most operations on trees) inherently require more space to process larger inputs—even when implemented "iteratively". The space used does not depend on whether the recursion is implemented with explicit function calls or loops, but rather on the quality of the compiler, including, but not limited to, tail-call optimization. Far from being complex wizardry, this optimization is really just the correction of a common implementation flaw wherein a function's stack frame remains allocated until the function returns, rather than being freed once it is no longer needed. This simplifies the compiler slightly at the cost of forcing the programmer to distinguish between implicit and explicit recursion, thus impairing the readability of naturally recursive algorithms and sparking endless debates over what ought to be a trivial difference of coding style with no runtime effect.
You don't like interacting with companies that try to understand you? You'd rather receive the same generic product offers as everyone else?
I just don't believe this. I believe that the more a company tries to make their communication relevant for each customer, the more value the customer gets from the company.
Yes, I would prefer to receive the same generic product offers as everyone else—the less relevant the better. That way, I am less likely to be subtly influenced against my will and contrary to my own interests. I'd prefer to avoid these ads entirely, but to the extent that is impossible, by all means, fill the ubiquitous ad spots with products I will never buy and services I will never require.
It's a different matter when I'm in "shopping mode" searching for a specific product. In that case relevance is a virtue—relevance to the explicit search parameters, that is, not passive tracking data.
If say Walmart sends you an offer that your personal assistant believes won't interest you then it will not show it to you.
That's great so long as I can be certain that the AI assistant is working for me, and not Walmart or any other advertiser. Key test: Can I make it send all "offers" to the trash, or will it insist on letting some through? Assuming I do permit some offers, will it select the ones which serve my best interests—which I will not regret buying later—or will it select the ones most likely to maximize profits for someone else?
As profitable as these insurance companies are, I have a feeling they would be just fine with a simple law that says "pre-existing conditions are not allowed as reasons for denying health insurance coverage." They'll bitch about it, but they'll cope with it and survive.
It's a bit hard to survive as a company when every single customer you have costs you more in covered medical expenses than they pay in premiums. That is the result you can expect from requiring insurance companies to cover pre-existing conditions without also requiring individuals to carry insurance.
This is an entirely different class of threat from the other regulations you referred to, which still left room for incumbents in the regulated industries to earn a profit while raising barriers to entry and inhibiting competition.
I'm not saying there wasn't good stuff in the law - the ban on pre-existing conditions and the extension of dependent insurance is awesome. I just don't understand why those couldn't have been passed as simple laws without all the other shit that nobody likes.
The ban on discrimination against pre-existing conditions is arguably the worst part of the law, and definitely the part that necessitated all the parts no one likes. You can't require insurance companies to cover pre-existing conditions without forcing everyone to buy insurance unless your intention is to bankrupt the entire insurance industry. Given the choice to delay buying insurance, if the agency must cover pre-existing conditions then the sane thing to do is to wait until you actually have a medical expense, and only then buy the insurance. Of course, at that point it isn't really "insurance" at all, because the "risk" is 100%, but the company is required to offer you coverage with the same premiums as if the risk were not already realized, which is a great deal for you.
Insurance is about mitigating unrealized future risks. Pre-existing conditions don't have any place here. If you have a pre-existing condition you can't pay for yourself, what you need is not insurance, but charity. Insurance companies make poor charitable organizations.
The flip side of this is that an insurance policy should cover the full lifetime cost of anything discovered while the policy was in effect—even if you later drop your coverage or switch to another insurance provider. The primary drive for coverage of P.E.C.s stems from the fact that current insurance policies cease to pay out the moment you are no longer a customer; the P.E.C. coverage mandate unreasonably shifts the burden from the insurer that voluntarily chose to take on the risk on equitable terms in exchange for a premium to a separate victim agency which knows up front that the premiums you will pay will never cover the expected cost of your treatment.
If you oppose a government policy, then change the law, don't handicap its enforcement.
Conversely, and arguably more importantly: If you can't get sufficient consensus in favor of the law to ensure that it will be enforced efficiently and uniformly, don't pass it in the first place!
Of course repealing the law would be the best approach, assuming it can be done. In the meantime, however, when a bad law can't be changed handicapping its enforcement is a far better option than simply giving up and letting others with no regard for your rights do whatever they please.
Slashdot Mirror
I can't recall any instance where I actually needed to do so as part of my job
I guess that is true for nearly everyone here.
Which is exactly why it's a bad interview question. The more experience you have, the longer it's been since you've been in that introductory algorithm class and the less likely you are to remember the details of a sorting algorithm which you should never choose for any non-trivial task. The ability to answer that interview question has nothing to do with your practical skills as a programmer; it tests only your ability to remember useless trivia.
in an introductory Algorithms class as an example of what not to do.
That is wrong. I suggest to check Wikipedia, facepalm.
Since you refer to Wikipedia, I'll leave this quote here as further evidence that bubble sort is best relegated to the role of a bad example:
Even among simple O(n^2) sorting algorithms, algorithms like insertion sort are usually considerably more efficient.
Due to its simplicity, bubble sort is often used to introduce the concept of an algorithm, or a sorting algorithm, to introductory computer science students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught.
The Jargon File, which famously calls bogosort "the archetypical [sic] perversely awful algorithm", also calls bubble sort "the generic bad algorithm". Donald Knuth, in his famous book The Art of Computer Programming, concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems", some of which he then discusses.
Bubble sort has a few niche uses, as I already alluded to. It can be faster when the list is extremely small (like three elements or less) or when the input list is known to be very nearly sorted with only a few close elements swapped. Such cases are vanishingly rare in the real world.
Likewise, if you're an expert programmer, you should be able to write bubble sort on the whiteboard without a web search.
Who actually uses bubble sort on the job? Bubble sort is one of those algorithms that you should see roughly once in your career—in an introductory Algorithms class as an example of what not to do. As simple as a bubble sort may be, if you've been programming long enough to earn the title "expert" I think you can be forgiven for forgetting the details. For that matter, unless you've been doing bare-metal systems programming, best practice in almost every case is to use a standard library function rather than writing your own sort routine. The average expert programmer working in a high-level language has very little reason to reimplement any sort algorithm in the course of their professional work, though most should at least be aware that there are multiple reasonable sort algorithms, and that the proper choice depends on the task at hand.
A better interview task would be to compare and contrast some of the more common algorithms and give examples of situations where each would be suitable. I wouldn't expect bubble sort to make the list, but given the pseudo-code for a bubble sort I would expect the applicant to be able to reason about its time and space complexity and articulate why it would generally be a poor choice compared to the other options. (The only possible exception I can think of offhand, for bonus points, is where the array length is known to be trivial and you have a really pressing need to minimize both code and stack size, but even then it's a close call.)
Speaking as a Sr. Software Engineer with at least 15 years of professional programming experience, while I would be able to write bubble sort, merge sort, and quicksort by hand without a reference, I can't recall any instance where I actually needed to do so as part of my job. The implementation details are inconsequential trivia compared to knowing that quicksort is best for mutable data structures with fast random access, while merge sort is more suitable for immutable data structures or data too large to fit in RAM.
Also, when a commit is signed it becomes bundled with it, which means its associated SHA-1 hash will change.
Yes, but the commit only includes the SHA-1 hash of the tree object, which in turn refers to other trees and files by their SHA-1 hashes. Given the possibility of SHA-1 collisions, the commit signature guarantees that you get the right commit, but not necessarily the right file contents. Of course, for this attack to work someone would have to get their obviously artificial collision-prone file included in the signed commit in the first place, so that they could later substitute the malicious version. This is not a practical means of attack for source code repositories where commits are subject to even cursory peer review. There might be some justification for extra precautions when it comes to opaque binary files, such as firmware, which could be as simple as including the SHA-2 of the binary file as part of the commit and verifying it during the build.
If there is one thing the Wikipedia article makes perfectly clear, it is that there is considerable disagreement over the nature and limits of the "appeal to authority" logical fallacy. However, in the first and only "notable example" given in the article to illustrate "appeal to authority", the authority figure in question was an expert in the field, which leads me to seriously doubt your assertion that "[a]ppeal to authority is a logical fallacy when the person is NOT an expert in the field."
Quoting from the article, with emphasis added:
In the Western rationalistic tradition and in early modern philosophy, appealing to authority was generally considered a logical fallacy.
More recently, logic textbooks have shifted to a less blanket approach to these arguments, now often referring to the fallacy as the "Argument from Unqualified Authority" or the "Argument from Unreliable Authority".
However, these are still not the only recognized forms of appeal to authority. For example, a 2012 guidebook on philosophical logic describes appeals to authority not merely as arguments from unqualified or unreliable authority, but as arguments from authority in general. In addition to appeals lacking evidence of the authority's reliability, the book states that arguments from authority are fallacious if there is a lack of "good evidence" that the authorities appealed to possess "adequate justification for their views."
So on the whole, it would not be unreasonable to consider an argument of the form "X is true because Y said so, and Y is a recognized authority in the field of X" an example of the "appeal to authority" logical fallacy. That is not to say that X is thus untrue, or that Y's opinion should be disregarded—but there is a vast difference between the valued opinion of a qualified authority figure and a sound logical argument.
You would be perfectly correct to say that this is not an example of the "Argument from Unqualified Authority" fallacy described in the newer textbooks, but that fallacy is much more limited in scope than "appeal to authority".
you can't infringe on their right of ownership by copying the DVDs
There is no such thing as a "right of ownership" over the content of the DVDs. The poorly named legal fiction of "copyright" is not a right at all, but merely a privilege; and like all other instances of legal privilege, it can only exist by infringing on the actual ownership rights of others.
The difference is obvious even to a cursory inspection. If copyright were about ownership then it wouldn't expire after a limited duration, or be subject to exceptions for fair use or (in some cases) compulsory licensing. More importantly, if copyright were treated as a right of ownership, then the liability for infringement would be determined by the extent to which the infringement diminished the copyright holder's ability to make use of the copyrighted content—which is, of course, impossible, since the creation of a new copy does not in any way diminish the utility of any existing copy. Copyright is not a right, it's an example of misguided social engineering run amok, a legal parasite intent on strangling its host.
The thing is, unless you have seen everything you would possibly want to see in older movies available for $10, why would you pay $50 for the same home experience?
Yes, I have seen every decent older movie I care to see.
This may seem a bit obvious, but new movies turn into older movies at exactly the same rate that new movies are released. It's not as if "older movies" were a fixed set. If you make a policy of only watching movies that are at least X years old, you'll end up with the same amount of "new" (to you) content each year as if you watched every new blockbuster on opening night at several times the price.
Perhaps the government has no right to search X, for any X, but they DO have the right to say "no you can't come in", or impose any conditions they feel are proper before granting entry.
False equivalency. You have the right to exclude others from your home because you own your home. Your rights of ownership are founded, ultimately, in the homesteading of previously unowned land though the labor of an original owner, plus an unbroken chain of voluntary contracts passing the rights to that land from its original owner to you. The government, by contrast, has no such legitimate claim to ownership of the entire country, and consequently does not have the right to exclude anyone from entering.
On the other hand, it would be wrong for me to block your entry into your *own* house... Unlike people who wish to visit, peope have a right to enter their own home.
Anyone with the right to enter their own home also has the right to invite others to enter. It would be wrong for you to block the entry of my invited guests into my house.
Once you're in the US (and while your outside the US), your rights as a human being should be fully respected.
Inside, outside, or in transition, your rights as a human being should always be respected.
Bill Gates is only going to buy so many TVs, cars, and houses. Doubling his wealth is not going to change his spending habits.
It won't change his personal consumption habits, no. Instead he would spend the extra wealth on capital investments, which improve the efficiency of production and allow vast numbers of other people to buy more TVs, cars, and houses at lower prices.
Consumption is important, of course, but all economic progress comes from the part of our income which we don't immediately spend on short-lived consumer goods.
You're also conflating wealth with money. They aren't the same thing. Bill Gates has a lot of wealth, but most of it isn't in the form of money. Instead, he owns shares in various investments. Even if it were, people would simply switch to an alternate form of currency long before the symptoms you're attributing to "wealth concentration" became apparent.
There is one factor which could have the effect you're referring to, but it only occurs in non-free markets. It is not always the case that more capital investment equals lower prices; over-investment can create a situation where the prices necessary to cover the cost of the capital are above the optimal point on the supply & demand curve. Imagine, for example, that you can sell 10,000 of a certain widget per year at an optimal price point of $10 each, and that your cost per widget is $8 (for $20k profit). If you rent a machine for $50,000/year you can lower production costs (excluding the rent) to $5 each. Under normal circumstances this would be an uneconomical investment, since the rent would raise the overall cost to $10 per widget, eliminating your profit. (Raising the price is not an option since that would reduce both the quality sold and overall revenues.) However, if a regulation were introduced requiring the use of this machine it would change the parameters: now the optimal price point (for widgets produced with this machine) is perhaps 8,000 units at $18, and you only make $14,000 in profit while 2,000 potential customers do without widgets. The same argument can be applied if the machine instead comes with a tax-funded subsidy rather than a mandate. With the subsidy included, the real cost per widget is still $18, but the buyer only sees $10 at the point of sale and the remaining $8 is spread among all the taxpayers—reducing the money they have left over to spend on widgets and other goods. Any market intervention (regulation, tax, subsidy, monetary policy, etc.) which either rewards or punishes capital investment, and thus shifts the allocation of resources away from the optimal balance, reduces the efficiency of the market and the purchasing power of the average citizen.
But earning 4 times the national average is clearly not equal.
You're leaving out half the story here. If two people given similar opportunities make different choices, and as a result one of them ends up earning four times as much as the other, that isn't inequality. They each had an equal chance at earning that income; one took advantage of that opportunity and the other did not. The thing we should be striving for is equal opportunity, not equality of outcome. It is only natural that someone who takes the long view and makes difficult choices should end up better off than someone else in the same circumstances who focuses only on the present.
On the subject of inherited wealth, this applies just as much to families as it does to individuals. True, the recipient of the inheritance has been granted an unearned opportunity which others lacked. (Unearned by the recipient, that is—the parent earned the right to make that gift.) Taking the larger view, however, any family with even a small amount of discretionary income has the option of saving and investing and passing those investments down to the next generation, following a long-term strategy which will eventually result in a sizeable inheritance. This demonstrates how different choices at the family level over the course of multiple generations can produce unequal outcomes from equal opportunities.
Our choices make all the difference, not just for ourselves but for our descendents as well, and that is exactly as it should be. The inequality we should be concerned about is inequality under the law, and especially the variety of legal inequality which results in property earned by one individual or family being unjustly seized and granted instead to some other individual or group. This is an attempt to force equal outcomes by perversely punishing those who make better choices.
I hope you don't count "You can't dump toxic sludge from your factory into the local river" as "ridiculous."
The enforcement of property rights is not regulation. You have every right to use your own property as you please, but others have exactly the same right—implying that you do not have the right to use their property without their permission. If you dispose of your pollutants in such a way that they end up harming others' property, including but not limited to their bodies, then you have infringed on their property rights and owe the victims redress. This is not some arbitrary regulation regarding how you may use your own property, but rather the natural consequence of others' rights to determine the use of their property.
As a term of art in political discussions, the term "regulation" refers to a restriction above and beyond simply respecting the property rights of others. Some regulations are indeed "ridiculous", but most are simply wrong, a product of politicians making a nuisance of themselves in situations where they have no standing to interfere.
The Fourth Amendment bans only "unreasonable searches and seizures". The exception considers searches at the border to be "reasonable".
That's only half of the story. The 4th Amendment also says that no warrants shall be issued (in plain language: no permission shall be granted to perform a search or seizure) "but upon probable cause, supported by Oath or affirmation, and particularly describing the place to be searched, and the persons or things to be seized." The so-called "Border Search Exception" manufactured by the courts out of thin air is an unconstitutional warrant. There is no probable cause, no supporting Oath or affirmation, and no particular description of the place to be searched or the person or things to be seized. Ergo, there is no constitutional authority to issue a warrant, which would be the only legal basis to perform any search or to seize any property.
Probable cause—or in other words a reasonable, and evidence-based, expectation that a particular search will turn up evidence of illegal activity sufficient to retroactively justify the search—is the only thing that makes a search "reasonable". If the majority of these searches do not uncover evidence of illegal activity then there is no probable cause and they are de facto unreasonable.
Well, it isn't 'nothing.' It costs money to develop ideas and art.
And they're welcome to charge for the development and initial publication of those ideas and works of art. The part that costs "nothing" is making and distributing copies—and yet that's what they charge for now. You're not paying for an idea or work of art to be developed, you're paying for permission to make a copy of an idea or artwork which already exists. (Or you're paying someone else to make the copy for you, since they won't grant you permission to do it yourself.) What you are paying for comes at zero cost to the patent or copyright holder. If you made said copy without their permission they would not be harmed in any way—in terms of cost to the patent or copyright holder, infringement has exactly the same effect as if you never became aware of the work in the first place. Either way, they neither gain nor lose anything as a result of your actions. It is absurd to punish someone for infringement when simply ignoring the work causes exactly as much harm to the patent or copyright holder and yet goes unpunished.
Using the iterative algorithm I posted above, I think you can see that we do NOT track any data whatsoever about how we got to the current URL. All of the information about past pages, which would be on the stack in a recursive algorithm, do not exist in my program. So in fact it does *not* "track the same data"...
You're comparing apples and oranges. The iterative version of your program is not using the same algorithm as the recursive version. You replaced a depth-first search with a breadth-first search, which makes your example completely irrelevant for comparing iterative vs. recursive implementations of the same algorithm. Among other things, the order in which your web crawler visits pages is very different in the iterative version. To maintain the original order you would need to restore the depth-first search algorithm, which would imply tracking the chain of pages you came from—exactly like the recursive implementation, though you could store that information on the heap or in a database rather than on the stack. (Note that a tail-recursive implementation would also store that information on the heap or in a database... this isn't a matter of recursion vs. iteration.)
You are certainly correct that you *can* simulate iteration by using recursion.
The tail-recursive implementation is not "simulating" iteration. It is iteration. Expressing the same algorithm with a loop construct rather than an explicit function call would not make it any less recursive; the loop implies a built-in fixpoint operator. If this trivial difference of style makes any difference in how much stack space your function uses, that's a bug in your toolchain.
The key point, to me, is that at least what I mean by "recursive" is that there is a parent and a child. The parent doesn't return/exit until its child does - and its child, and its child, and its child, and its child ...
That is not what "recursion" means. Moreover, how would that definition even account for something like tail-recursion, where the "parent" is replaced by the "child"? Logically, the "parent" still does not exit until the "child" does, but in the meantime it occupies no space on the stack and the return from the innermost "child" is also the return from all of the "parents". No matter how deep the tail-calls become, the stack use remains constant. Recursion only requires additional stack space when there is more for the function to do after the call, i.e. when it is not tail-recursion. Such cases cannot be converted to iteration (using the same algorithm) without shifting all the data required by the continuation from the function-call stack into some other data structure.
You' started talking about an apartment building, and in those places the residents are not the owners, and have only very restricted property rights.
In at least some of the cases in question it was the owner of the apartment building, not a renter, who was fined for using AirBnB. A renter's right to sublet, and more generally to allow others access to the apartment, is, of course, subject to the terms of their contract with the owner of the apartment building.
Zoning laws are not designed to prevent imminent threats of irreversible harm.
Yes, which is one of the many things wrong with zoning laws. Zoning laws in general are no more justifiable than the more specific restrictions on using AirBnB. However, that is a topic for another day.
The CFAA doesn't ban bona fide government investigations.
Right, but is this an bona fide investigation? IIRC that exception applies to law-enforcement agencies, whereas this is about the organization responsible for approving visas. They're not investigating any crime; it's more like a background check.
Either way, there's still the TOS issue. The applicant is not legally compelled to turn over the password; they can refuse (and allow their visa application to be denied). Ergo, if they do submit the password they are violating the TOS of their own free will, which can result in their account being terminated and perhaps other penalties.
Care to point to which step "is defined in terms of the process itself"? I don't see that anywhere.
It's part of the compiler's internal definition of the loop construct, and does not appear in the source code. In the object code it can be identified as the opcode that branches back to the beginning of the loop.
This becomes more obvious if you consider programming languages where iteration is not a built-in construct, and loops are written in terms of explicit recursion. In Haskell, for example, a simplified C "while" keyword (disregarding "break", "continue", etc.) could be implemented as the following recursive function:
Or using the fixpoint operator, without referencing the current definition by name:
Building on the fixpoint example above, would you call this a recursive function?
Sometimes it isn't so simple. The body of f() does not refer to f(). However, what happens if you call f(f, 0)? The function might be recursive, or it might not be, depending on the arguments. It all depends on that function pointer.
Arguments might be avoided by saying it's not a recursive FUNCTION - no function calls itself, can't run out of stack space.
It's not a recursive function, since it's not the entire function that's repeated. It would be more accurate to say that it contains a recursive function, though that inner function is hidden behind the loop construct. Barring the use of alloca() or similar it won't run out of space on the function-call stack, since alloca() / variable-length arrays and function calls are the only ways to allocate from the function-call stack, but the iterative version of the function still needs to track the same data and can still run out of memory given large enough inputs—just not stack memory. Sometimes that distinction is important, but more often it isn't, especially given the stack sizes available to programs running on most virtual memory based operating systems, ranging from several megabytes to "malloc() would fail first". (After all, some languages allocate stack frames from the heap.)
Anyway, the fact that (unoptimized) tail calls use stack space while iteration constructs ordinarily do not is nothing but an artifact of poor compiler implementation, and easily corrected through tail-call optimization. It's really no different from the way some languages with simplistic garbage-collection algorithms (e.g. Perl) fail to collect sets of objects with cyclic references. You can either take pains to avoid cyclic references (tail recursion), or just switch to one of the many modern languages which don't cause arbitrary runtime errors when you write code in the most natural style. Given a reasonable guarantee of tail-call optimization, function calls in general may allocate additional function-call stack space, but a call in tail position won't, so tail recursion is exactly the same as iteration in terms of expected stack use.
When there's such a pattern of behavior of disruption coming from apartments being rented out, isn't it okay to ban the underlying bad behavior?
No, that sort of prior restraint requires serious justification—"imminent threat of irreversible harm". The handful of minor disruptions which have actually occurred are nowhere near that level of threat; very few things are, short of direct physical attacks. While it would certainly be a simpler solution, prior restraint violates the property rights of those who rent out their apartments to considerate guests who do not cause such disruptions, while also causing harm to the guests themselves in the form of fewer choices of accommodation and correspondingly higher prices.
The Constitution says nothing about depriving one of property rights; only property.
A distinction without a difference. Property rights are property, and vice-versa. Any time your property rights are infringed you have been deprived of your property to at least some degree. To argue otherwise admits the absurd legal fiction that the property technically still belongs to you, you just don't have any actual right to use it—the property rights belong to someone else. When people talk about being deprived of their property, it's not mere physical possession that they're referring to but rather their legal rights relating to the property.
No, not with fines for renting out the apartment. Fines for disturbing the peace. The problem isn't the rental, which is no one's business but the property owner's. The problem is holding the property owner accountable for the use of the property, including use by guests. You want to rent out your apartment on AirBnB? No problem—but you are responsible to your neighbours for your guests' behavior during their stay. So you'd better make sure they're well-behaved and considerate before letting them stay at your apartment.
The persistent identification cookie on the laptop, tablet computer, or smartphone that a traveler carries allows access.
Legally speaking, it only allows access for the account owner. Barring a special exception to the Computer Fraud and Abuse Act, anyone else using that cookie (or the login & password, whether provided voluntarily in violation of the TOS or under duress) without the service provider's permission is committing a felony by hacking into the service provider's systems without authorization. The account owner may be at the border, but the account owner cannot legally delegate permission to access the account to a third party and the system being accessed is not located at the border.
The only legal option consistent with both the TOS you agreed to and CFAA is to refuse to turn over the passwords—even knowing that this means the visa request will be denied.
Some people would point out this solves a recursive and say it's therefore a recursive algorithm. The algorithm isn't recursive by definition because no function calls itself, even indirectly.
The algorithm is still recursive; the recursion is just built in to the language in the form of predefined iteration constructs like "foreach" and "while". Any time you have an iterative program of the form "first do X, and then repeat the process for the remaining input", that's recursion: one of the steps in the process (the repetition) is defined in terms of the process itself.
Some recursive algorithms can run in constant space, while others (such as most operations on trees) inherently require more space to process larger inputs—even when implemented "iteratively". The space used does not depend on whether the recursion is implemented with explicit function calls or loops, but rather on the quality of the compiler, including, but not limited to, tail-call optimization. Far from being complex wizardry, this optimization is really just the correction of a common implementation flaw wherein a function's stack frame remains allocated until the function returns, rather than being freed once it is no longer needed. This simplifies the compiler slightly at the cost of forcing the programmer to distinguish between implicit and explicit recursion, thus impairing the readability of naturally recursive algorithms and sparking endless debates over what ought to be a trivial difference of coding style with no runtime effect.
You don't like interacting with companies that try to understand you? You'd rather receive the same generic product offers as everyone else?
I just don't believe this. I believe that the more a company tries to make their communication relevant for each customer, the more value the customer gets from the company.
Yes, I would prefer to receive the same generic product offers as everyone else—the less relevant the better. That way, I am less likely to be subtly influenced against my will and contrary to my own interests. I'd prefer to avoid these ads entirely, but to the extent that is impossible, by all means, fill the ubiquitous ad spots with products I will never buy and services I will never require.
It's a different matter when I'm in "shopping mode" searching for a specific product. In that case relevance is a virtue—relevance to the explicit search parameters, that is, not passive tracking data.
If say Walmart sends you an offer that your personal assistant believes won't interest you then it will not show it to you.
That's great so long as I can be certain that the AI assistant is working for me, and not Walmart or any other advertiser. Key test: Can I make it send all "offers" to the trash, or will it insist on letting some through? Assuming I do permit some offers, will it select the ones which serve my best interests—which I will not regret buying later—or will it select the ones most likely to maximize profits for someone else?
As profitable as these insurance companies are, I have a feeling they would be just fine with a simple law that says "pre-existing conditions are not allowed as reasons for denying health insurance coverage." They'll bitch about it, but they'll cope with it and survive.
It's a bit hard to survive as a company when every single customer you have costs you more in covered medical expenses than they pay in premiums. That is the result you can expect from requiring insurance companies to cover pre-existing conditions without also requiring individuals to carry insurance.
This is an entirely different class of threat from the other regulations you referred to, which still left room for incumbents in the regulated industries to earn a profit while raising barriers to entry and inhibiting competition.
I'm not saying there wasn't good stuff in the law - the ban on pre-existing conditions and the extension of dependent insurance is awesome. I just don't understand why those couldn't have been passed as simple laws without all the other shit that nobody likes.
The ban on discrimination against pre-existing conditions is arguably the worst part of the law, and definitely the part that necessitated all the parts no one likes. You can't require insurance companies to cover pre-existing conditions without forcing everyone to buy insurance unless your intention is to bankrupt the entire insurance industry. Given the choice to delay buying insurance, if the agency must cover pre-existing conditions then the sane thing to do is to wait until you actually have a medical expense, and only then buy the insurance. Of course, at that point it isn't really "insurance" at all, because the "risk" is 100%, but the company is required to offer you coverage with the same premiums as if the risk were not already realized, which is a great deal for you.
Insurance is about mitigating unrealized future risks. Pre-existing conditions don't have any place here. If you have a pre-existing condition you can't pay for yourself, what you need is not insurance, but charity. Insurance companies make poor charitable organizations.
The flip side of this is that an insurance policy should cover the full lifetime cost of anything discovered while the policy was in effect—even if you later drop your coverage or switch to another insurance provider. The primary drive for coverage of P.E.C.s stems from the fact that current insurance policies cease to pay out the moment you are no longer a customer; the P.E.C. coverage mandate unreasonably shifts the burden from the insurer that voluntarily chose to take on the risk on equitable terms in exchange for a premium to a separate victim agency which knows up front that the premiums you will pay will never cover the expected cost of your treatment.
If you oppose a government policy, then change the law, don't handicap its enforcement.
Conversely, and arguably more importantly: If you can't get sufficient consensus in favor of the law to ensure that it will be enforced efficiently and uniformly, don't pass it in the first place!
Of course repealing the law would be the best approach, assuming it can be done. In the meantime, however, when a bad law can't be changed handicapping its enforcement is a far better option than simply giving up and letting others with no regard for your rights do whatever they please.