We’re rewarding the question askers & reputations are being recalculated! Read more.

# Tag Info

23

Wikipedia has an extensive list of languages that use the off-side rule1: ABC Boo BuddyScript Cobra CoffeeScript Converge Curry Elixir (, do: blocks) Elm F# (if #light "off" is not specified) Genie Haskell (only for where, let, do, or case ... of clauses when braces are omitted) Inform 7 ISWIM, the abstract language that ...

10

There are: Elm, Haskell, its predecessor Miranda and its predecessor ISWIM, YAML where spaces are crucial for syntax and tabs are forbidden, OCCAM, Coffee script and Cokescript both are language to language compilers with JavaScript as target and esoteric Whitespaces. There is also Agda - interactive theorem prover, which is probably not what you had in ...

6

It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the size of input in bits. In this assumption, the sum of the input can be represented with 1 word, so the space complexity is $O(1)$ words. Measured in bits, the ...

4

Make fits your description, even though it probably isn't quite what you have in mind, with its limited syntax and power. It infamously indicates its code blocks (recipes) with a particular form of whitespace: one tab character. Alternative ways are available (e.g. GNU Make supports using an alternative character), but rarely used in practice. Another ...

4

Unfortunately, this has no name—because it doesn't work. Pontus provided a good test case. lst = [2, 1, 3, 4, 5] sort_algo(lst) print(lst) [2, 1, 3, 4, 5] It's been mathematically proven that comparison-based sorting algorithms (that is, sorting algorithms based on comparing elements against each other, rather than exploiting certain clever tricks) can ...

3

Resource usage always depends on your model of computation. If you're in a situation where integers can grow arbitrarily large then, yes, you need to take that into account. One way of doing this is by assuming that integer variables take an amount of space that depends on the value stored. Another way is to use something like the word RAM model, which more ...

3

You haven't extracted the 14 most significant bits. First, you have to write $r$ as a $w$-bit number: $$00000001000011001100000001000000$$ Now you extract the 14 most significant bits: $$00000001000011$$ Converting to decimal, this is 67.

2

So you have the right logic, if you have a loop of $O(n)$ iterations, the complexity of the entire loop will be $O(n*\text{complexity of loop operations})$. In this case, you again are correct that your loop's complexity is $O(n)$ for each iteration. Your last bullet point shows that you understand this as well, as the total loop complexity is then $O(n^2)$...

2

Think carefully about the flow. Your innermost While loop runs through b = 1, 2, each time it hits. It does this for EACH value of a in the outermost loop. So when a == 2, we progress inward and run through that loop twice. a == 2 both times.

2

The length of the binary representation of a natural number $n$ is roughly $\log_2 n$. As an example, the number represented by the binary string $10^{n-1}$ of length $n$ is $2^n$. Your sources are misleading. Usually $n$ is reserved for the input length or a related quantity, not the input value. If the input to a function is an integer $m$, then the input ...

1

No, breaking the algorithm by increasing n (the amount of numbers) makes this 100% not working in constant space. To the question nobody asked: You could easily modify the algorithm to get the space to be constant. (Only the solution given in the interview has this problem. The "best" solution does not have this problem.) Basically the size of the sum ...

1

This would fall under something called black box optimization. In general, there are several methods you could try in practice such as (stochastic) hill climbing or say a genetic algorithm. Such methods might seem "random", but they take some care in moving in a smart way but also use some "randomness" to escape local optimums.

1

There seems to be something wrong in the first result you obtained - your case (a) - irrespective of questions to do with floating-point precision and cancellations. $$x=\frac{-b-\sqrt{b^2-4ac}}{2a}$$ should not cause any problems at all, since there is no cancellation. This value is very nearly $\frac{-2b}{2a}$. The fact that you did not get 1E+06 or ...

1

You can understand which, if either, solution is correct by substituting it back into the quadratic and seeing which one works. As to why you get different answers, it's to do with the accuracy of floating point representations. Roughly speaking, numbers are represented to some number of significant figures and this can cause problems when you add numbers ...

1

Your question appears to be a very long version of "Could we add some sort of punctuation to Polish notation so that it's unambiguous where each numerical operand ends?" Yes, of course you could. Normally, we use a space and write the numbers most-significant digit first but, sure, if you want to use the symbol ∅ and write the digits in the opposite order, ...

1

To answer your question literally, yes, the code does just return a string of length $n$ where $n$ is the length of the integer that we pass. And this is the right way to think about it. Your source, though, is using $n$ to denote the value of the integer, not its length. This is an unusual thing to do and it is, in my opinion, a very bad idea when ...

1

Your problem is no harder and no easier than the approximate subset-sum problem. There is a natural approach for your problem: Find any subset that sums to something close to zero, and output it. Remove those numbers from the set $A$. Go back to step 1 and repeat, until the set $A$ is empty. This requires a way to find a subset that sums to approximately ...

Only top voted, non community-wiki answers of a minimum length are eligible