87
votes
Accepted
Keeping a String Secret in (Open) Source Code
You have at least two options, depending on what problem you want to solve.
If you want innocent readers of your code to not get the answers inadvertently, or you at least want to make it a bit ...
- 269k
44
votes
Accepted
Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted?
Fixed-size queues are often implemented using what some people call circular buffers. If you remove the protection against it being full, you get the desired behaviour.
Of course, no actual pushing ...
- 70.8k
37
votes
Accepted
Time complexity $O(m+n)$ Vs $O(n)$
Yes:
$n+m \le n+n=2n$ which is $O(n)$, and thus $O(n+m)=O(n)$
For clarity, this is true only under the assumption that $m\le n$. Without this assumption, $O(n)$ and $O(n+m)$ are two different things -...
- 10.7k
31
votes
Accepted
One element that differs in two arrays. How to find it efficiently?
I see four main ways to solve this problem, with different running times:
$O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes ...
- 3,394
29
votes
Keeping a String Secret in (Open) Source Code
You have two three options:
Keep the answers separate from the rest of the source code
If you want your code to be open source, however don't want the answers to be open source, then you open source ...
- 391
26
votes
Accepted
What is the advantage of heaps over sorted arrays?
$\small \texttt{find-min}$ (resp. $\small \texttt{find-max}$), $\small \texttt{delete-min}$ (resp. $\small \texttt{delete-max}$) and $\small \texttt{insert}$ are the three most important operations of ...
- 726
25
votes
How to find 5 repeated values in O(n) time?
The solution in fade2black's answer is the standard one, but it uses $O(n)$ space. You can improve this to $O(1)$ space as follows:
Let the array be $A[1],\ldots,A[n]$. For $d=1,\ldots,5$, compute $\...
- 269k
22
votes
Accepted
How to find 5 repeated values in O(n) time?
You could create an additional array $B$ of size $n$. Initially set all elements of the array to $0$. Then loop through the input array $A$ and increase $B[A[i]]$ by 1 for each $i$. After that you ...
- 9,592
16
votes
One element that differs in two arrays. How to find it efficiently?
The $\Theta(n)$ difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is:
...
- 1,915
15
votes
Accepted
Matrix Max in less than O(n)
If you don't know anything about the contents of the matrix (such as some kind of monotonicity property), linear time is the best you can do for a one-off search with a deterministic algorithm by a ...
- 1,999
15
votes
One element that differs in two arrays. How to find it efficiently?
I'd post this as a comment on Tobi's answer, but I don't have the reputation yet.
As an alternative to calculating the sum of each list (especially if they are large lists or contain very large ...
- 411
14
votes
One element that differs in two arrays. How to find it efficiently?
Element = Sum(Array2) - Sum(Array1)
I sincerely doubt this is the most optimum algorithm. But it's another way to solve the problem, and is the simplest way to solve it. Hope it helps.
If the number ...
- 1,587
12
votes
What is the best solution to find whether the sum of an array is even or odd
By a simple "adversary argument", you have to check each element (in some way): Suppose you have missed some element $x$ and get an answer "The sum is even": the adversary can modify $x$ (if it's odd, ...
- 9,179
12
votes
What is “Oracle Access”?
An oracle is basically a magic black box that does something (e.g. query the entries of an array), usually in constant time. How the oracle does this is abstracted away from (and sometimes an oracle ...
12
votes
Accepted
Applicative-order languages don't support constant time array writes? If not, why not?
Skiena didn't say "applicative order", just "applicative". This is sometimes used as meaning something like "purely functional", or a language that evaluates via the application of functions as ...
- 11.8k
12
votes
Accepted
How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?
What is meant by "lower bound" in this case is a lower bound on the worst-case number of comparisons. In this case, it happens to also be an upper bound.
The lower bound has to be something that is ...
11
votes
Accepted
Find a point shared by maximum segments
Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:
...
- 3,162
11
votes
Time complexity $O(m+n)$ Vs $O(n)$
Yes, since $n + m \leq 2n$ the algorithm is $O(n)$. However, you may wish to write $O(m + n)$ because it clearly shows which variables the algorithm depends on, and what each variable does to the ...
- 211
10
votes
How to measure "sortedness"
Mannila [1] axiomatizes presortedness (with a focus on comparison-based algorithms) as follows (paraphrasing).
Let $\Sigma$ a totally ordered set. Then a mapping $m$ from $\Sigma^{\star}$ (the ...
- 70.8k
9
votes
Accepted
Time complexity of Dynamic Array via repeated doubling
Both are correct but you're using $n$ to mean two different things:
when you say that $1 + 2^1 + 2^2 + \dots + 2^n = (2^{(n-1)} - 1) \sim O(2^n)$, you're using $n$ to mean the number of times you ...
- 80.1k
9
votes
Accepted
k-ordered array problem
Take your example
$$ A = [1,4,2,6,3,7,5,8]. $$
An array is 1-ordered if it is ordered, and the 1-ordered array corresponding to $A$ is $1,2,3,4,5,6,7,8$. Let's write both arrays together:
$$
1,4,2,6,3,...
- 269k
9
votes
Accepted
the convention for declaring arrays in pseudocode
Pseudocode is not a formal language. Declare your arrays however you want, as long as it's obvious what you mean. Including the full limits (as you have in both your array examples) is good, since it ...
- 80.1k
9
votes
What is a contiguous subarray?
This is just the ordinary dictionary definition of "contiguous": all adjacent in space. A subarray is defined by any subset of the indices of the original array; a contiguous subarray is defined by an ...
- 80.1k
9
votes
Accepted
From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?
Let's assume that adding two strings of lengths $a,b$ takes time $a+b$. Consider the following strategy to convert a list of $n$ characters into a list:
Read the list in chunks of $k$, convert them ...
- 269k
9
votes
Accepted
Find a weighted median for unsorted array in linear time
Let $A$ be an input array containing $n$ elements, $a_i$ the $i$-th element and $w_i$ its corresponding weight. You can determine the weighted median in worst case linear time as follows. If the array ...
- 3,959
9
votes
Accepted
Why does merging two sorted arrays take 2N - 1 comparisons?
The question asks to show the lower bound on the number of comparisons in merging two sorted arrays of length $N$. Therefore, you need to argue that no matter what comparison-based algorithm you use, ...
- 1,453
9
votes
Why shuffling by picking random position in all array instead of a part is not correct
Suppose that the array has length $n$. Since you are making $n$ random choices of numbers from 1 to $n$, the probability to obtain any specific permutation is of the form $A/n^n$, for some integer $A$....
- 269k
8
votes
Complexity of algorithm to find number of elements > element index i in an array
Your problem is very related to that of computing the number of inversions in a permutation, or (equivalently) the Kendall tau distance between two permutations; this is the sum of your vector. In ...
- 269k
8
votes
How to find 5 repeated values in O(n) time?
There's also a linear time and constant space algorithm based on partitioning, which may be more flexible if you're trying to apply this to variants of the problem that the mathematical approach doesn'...
- 902
8
votes
Accepted
Sorting a large list of test scores
This is a very easy question, assuming all scores are integers.
Here is the simplest algorithm in plain words. We will initiate count, an integer array of 100 ...
- 33.2k
Only top scored, non community-wiki answers of a minimum length are eligible