Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Hot answers tagged

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 ...
user avatar
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 ...
user avatar
  • 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 -...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 $\...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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: ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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,...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
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$....
user avatar
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 ...
user avatar
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'...
user avatar
  • 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 ...
user avatar
  • 33.2k

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