21 votes

The fastest way to find one unique value when all other values are the same

Benchmarks! Benchmarks for lists with a thousand or a million elements, with the unique element in the middle of the array to reflect the "typical"/"average" case. The results are ...
  • 2,983
20 votes
Accepted

Calculate square of a number without multiplication

A more efficient way to do this is to keep doubling the product while you can.... So, for example, \$5^2\$ is: $$\begin{eqnarray*} 5 +& 5 &\longrightarrow 10 \\ 10 +& 10 &\...
  • 97k
18 votes
Accepted

Check if one string is a permutation of another using Python

Yes, len(str) should be O(1) in Python. (Good question!) Each of your for loops is O(n), so your whole function is O(n). Your ...
18 votes
Accepted

Finding the most popular element with C# given O(1) space complexity requirement

You don't have \$O(1)\$ space complexity at the moment, OrderBy and OrderByDescending (used wrong as pointed out in the other ...
16 votes

"Algorithmic Crush" problem hitting timeout errors

Constraints \$3 ≤ N ≤ 10^7\$ \$1 ≤ M ≤ 2 \cdot 10^5\$ \$1 ≤ a ≤ b ≤ N\$ \$0 ≤ k ≤ 10^9\$ You should verify that every value you read from the user is a valid value in your program. ...
  • 6,118
14 votes
Accepted

Find the total number of ways W, in which a sum S can be reached in N throws of a dice

1. Review The sum \$s=0\$ can be reached in \$n=0\$ throws in exactly one way, but: ...
  • 49.4k
13 votes

The fastest way to find one unique value when all other values are the same

No matter how the array is traversed, the distinguished element can occur at the end of the traversal. Therefore, it is necessary to go through the entire array in the worst case and there does not ...
  • 2,301
12 votes
Accepted

Finding Pythagorean triplet in array

A couple of notes on your code before going into alternative solutions. In your findTriplet method, you are doing: ...
  • 9,203
11 votes
Accepted

Finding whether there exists a pair of numbers in a set having a given product

The algorithm description is good, but the implementation of find is \$ O(n) \$, so the overall runtime is actually \$ O(n^2) \$. Detailed review follows: There ...
  • 49.4k
11 votes
Accepted

Does my Linklist implementation have memory leaks?

It does not appear to be leaking memory (except on exit). However, there are a number of things you can do to improve this code. Fix the formatting Code that has poor formatting is hard to read, ...
  • 64.9k
11 votes

Binary Search written in python with O(n)

It's not really a binary search if it is not O(log(n)). Binary search only works on sorted inputs and it takes advantage of the fact that it is sorted to achieve ...
  • 5,015
10 votes
Accepted

Sum the exponents of the prime factors of a number

In addition to the other answer: There is no need to generate all primes up to n. You can generate them up to sqrt(n). If ...
  • 5,580
10 votes
Accepted

Solving 'decent numbers' that follow specific division rules

At the heart of your problem you are trying to solve a single linear Diophantine equation. Because 3 and 5 are coprime, their greatest common divisor is 1, and hence your equation, \$3a + 5b = n\$, ...
  • 6,562
10 votes
Accepted

Google's Python exercise about lists very different from the given solution

In a nutshell, yours is better, for two reasons. First, Python isn't designed for speed. It's decently fast, but the goal is code like yours: so clear, concise, obvious, and readable that anyone can ...
10 votes
Accepted

Finding number of number pairs with given difference

Current complexity is \$O(n^2)\$, you can accomplish this with \$O(n \space log \space n)\$ instead by sorting the array first and then loop through the elements. Let's say that you know that the ...
10 votes

Finding a max element in an array in Java

Yes, this is O(n), because you visit every element once. You can't possibly do better than O(n), because there is no way to be sure that you have found the maximum value without inspecting every ...
10 votes
Accepted

Find the number of K-Complementary pairs in an array

Current algorithm The time complexity of the current solution is O(N²): for a given array of length N, it needs to loop through its elements from 0 to its length, ...
  • 9,203
10 votes
Accepted

Sort an array of 0s, 1s and 2s in Java

Descriptive names private static void printSortedArr (int[] arr) { I don't like these names. I would rather write out array if that's what's being said. E....
  • 21.4k
10 votes
Accepted

Regular Expression Evaluator

Bug There is a case that requires NFA instead of simple DFA to recognize string (of course it is possible to convert NFA to DFA): eval("aaab", "a*ab"); Gives ...
  • 9,249
10 votes
Accepted

Time and Space Complexity of Prime factorization

isPrime() Complexity This function contains a simple loop that iterates up to Math.sqrt(number) times, so assuming ...
  • 32.9k
9 votes
Accepted

Codility MaxCounters peformance in Python capping out at 77% performance

What hurts your performance is filling the array with max_count. So don't do it. Imply it. The trick is all there, and it makes this slightly different from trying ...
  • 2,671
9 votes

Find maximum difference between values in an array

What does this algorithm do? It finds the smallest and greatest number in an array and creates the difference of them. Nope. Consider {5, 2, 1}. The pseudo code returns 5 - 1 = 4 which happens to be ...
  • 1,010
9 votes
Accepted

URLify a string using Python

Your complexity analyses look correct to me. I would just say, in short, that this function works in O(n2) time. Note that this is an awkward exercise to do in Python, or any language in which ...
9 votes

Finding the most popular element with C# given O(1) space complexity requirement

...
  • 44.1k
9 votes
Accepted

Find the smallest positive integer that is absent from a given array

I then tried putting the array into an arraylist, which reduces big-O since each object is "touched" only once, and I can use .Contains which is more efficient than iteration (not sure if that's true; ...
  • 2,889
8 votes
Accepted

Finding overlapping time intervals

You could make the Meeting class generic with the T : IComparable<T> constraint. Thus you'll be able to use any type as a ...
  • 4,579
8 votes
Accepted

Sufficient implementation of subset sum for 45 min interview

Bug I ran your program, replacing 100 with 6. This should have found the subset {2,4} as a ...
  • 28.5k
8 votes
Accepted

Finding the most common character in a string with a hash map

Normally operations on a hashmap should be pretty much constant (O(n)=1), so it's something like O(n) = n + 2*m (number of characters in the String plus twice the amount of different characters in the ...
8 votes
Accepted

Function to check truth value of a specific statement

Make the function return True or False. You can use all and a generator comprehension ...
  • 41.8k

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