Questions tagged [complexity]
Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input. Use this tag for reviews where the "Big O" is a concern.
343
questions
49
votes
12answers
21k views
Searching in an array in less than O(n) time
I have an array where each element is either one less or one greater than the preceding element \$\{x_i = x_{i-1} \pm 1\}\$. I wish to find an element in it in less than \$O(n)\$ time. I've ...
22
votes
3answers
30k views
Find all paths from source to destination
Given a directed connected graphs, find all paths from source to destination.
Looking for code review, optimizations and best practices. Also need help figuring out complexity, which in my best ...
15
votes
2answers
787 views
'Team Split' problem
Below is my solution for this 'Team Split' problem.
In summary, the problem is to find relative strength of 2 teams by finding the difference between their total strength (individual strengths can be ...
13
votes
7answers
1k views
Finding the most popular element with C# given O(1) space complexity requirement
I have tried to solve the following problem in C# with LINQ:
Given an integer array, find the most frequent number and it's count in the array. If multiple numbers have the same highest frequency ...
13
votes
5answers
8k views
“Algorithmic Crush” problem hitting timeout errors
This is the HackerRank problem Algorithmic Crush:
You are given a list of size N, initialized with zeroes. You have to perform ...
13
votes
4answers
3k views
Check if one string is a permutation of another using Python
The code below is an attempt at a solution to an exercise from the book "Cracking the Coding Interview."
I believe that the worst case time complexity of the code below is \$O(n)\$, where n is the ...
13
votes
1answer
354 views
Seating Students (partitioning sort of)
The goal of this code is to seat students in a classroom based on a
single test score. We want students to be evenly distributed across
the class such that every student is positioned next to the ...
13
votes
1answer
2k views
Nonogram puzzle solution space
I've written some code to brute-force enumerate the solution space of nonogram puzzles up to a certain size. It does a good job up to the first ~4 billion puzzles, but I run out of disk space to store ...
12
votes
3answers
1k views
Given some integers, return the k most frequent elements
Given a non-empty array of integers, return the k most frequent elements.
For example, given [1,1,1,2,2,3] and k = 2, return <...
12
votes
1answer
1k views
Extended stable marriage challenge
I've written a solution for the stable marriage problem in the case that the number of men is not equal to the number of women. My problem is not that I can't prove my code is right. The problem is I ...
11
votes
5answers
1k views
Refactoring my problem-solution to reduce complexity
I need some help refactoring my solution to the problem below:
Problem Statement
An Association of Computer Scientists meets on a weekly basis. There is a certain number of seats in the meeting ...
11
votes
3answers
1k views
Finding Pythagorean triplet in array
We have an integer array as:
private int[] arr = {1, 3, 5, 14, 18, 29, 78};
We have a function which takes three inputs of the array and checks whether:
...
11
votes
5answers
16k views
Checking if three numbers sum to a given number
I'm working on the following interview practice problem, and got the following solution, which runs in worst case n! time (best case constant), and I'm trying to ...
10
votes
8answers
12k views
Calculate square of a number without multiplication
I wrote these two methods to calculate the square of a number:
...
10
votes
6answers
3k views
Getting filtered autolist
Is there a better way to write the following code fragment?
I can't have more than 10 conditional statement in my method as it gives cyclomatic complexity.
...
10
votes
2answers
5k views
Fish Food Chain of complexity O(N)
I understand that if you don't know the trick, it's not easy create a solution with a complexity of \$O(N)\$. However, I would like to ask you how to solve this tricky question:
You are given two ...
10
votes
2answers
557 views
Minimum sub-array challenge
Below is my solution to finding the minimum product sub-interval. It passed 8/12 or so test cases, but the other test cases timed out if they hadn't finished within 2 seconds. When I compile this code ...
10
votes
4answers
1k views
Maximum consecutive subarray sum for a variable sliding window size
The Problem:
Given an array of integers L find the largest sum of a consecutive subarray of size k or less.
Constraints:
...
10
votes
2answers
418 views
Min sub array size with a given sum
How can the time complexity of the following code be improved (assuming it's \$O(N^2)\$)? What about style and patterns?
This code is trying to find the minimum subarray size that adds up to given sum ...
9
votes
4answers
14k views
Finding overlapping time intervals
You have two lists with meetings scheduling (start time, end time). Meetings in single list don't intersect. Find all intersecting meetings across the two lists.
Is my complexity \$O(N M)\$? If I use ...
9
votes
3answers
5k views
URLify a string using Python
I have been working my way through the exercises in the book Cracking the Coding Interview. I wanted to get feedback for the following exercise.
Write a method to replace all spaces in a string ...
9
votes
1answer
1k views
Codility MaxCounters peformance in Python capping out at 77% performance
My problem is quite similar to the question found here, except I am attempting to answer the question in Python.
Given an array of N counters, all initialized to 0, and an array ...
8
votes
3answers
439 views
Find the smallest positive integer that is absent from a given array
I made the acquaintance of big-O a couple of weeks ago and am trying to get to grips with it, but although there's a lot of material out there about calculating time complexity, I can't seem to find ...
8
votes
2answers
2k views
Solving 'decent numbers' that follow specific division rules
HackerRank Problem Statement
I have to find the largest 'decent number' having N digits. A decent number has the following properties:
3, 5, or both as its digits....
8
votes
1answer
849 views
Regular Expression Evaluator
Task to be accomplished:
Write a function that takes two strings s and p as arguments and returns a boolean denoting whether s matches p.
p is a sequence of any number of the following:
a-z - ...
8
votes
3answers
351 views
Calculating the mean differences of subarrays
I'm trying to devise a way to calculate the mean differences (the absolute average differences between any two values in a set), of sub-arrays (starting from arbitrary indices) in an ...
8
votes
1answer
160 views
An array with \$O(\log\ n)\$ time complexity for all operations
Does this exist already? It's an array (=variable-size list with integer indices) where add/remove/set and get all take \$O(\log\ n)\$ time.
I couldn't find this anywhere, so I made up the name "Log-...
8
votes
1answer
1k views
Finding largest subset of line segments that don't intersect
I completed a challenge of codeeval called BayBridges. It can be found here. I have uploaded my code on GitHub here.
In summary, the challenge is to take a list of line segments, each specified by ...
8
votes
3answers
717 views
Longest 'balanced' substring
I was given a task where given a string of '0's and '1's, return the longest substring where the count of '0's and '1's are equal. I was told also that the code should be O(n) and space O(1).
Below ...
8
votes
2answers
4k views
Finding the count of negative sub-arrays for a given array
I want to improve my implementation for the following problem:
You are given an array of n integers. A sub-array is "Negative" if sum of all the integers in that ...
8
votes
1answer
97 views
Joining collections… because it's fun
I'm working on a LinqEnumerable class (reviewable here), and I'm no Big-O expert and I'm pretty bad with algorithms, so I wonder what the complexity is for what I'...
8
votes
2answers
8k views
Finding the largest repeating substring
Here's my code that takes a large string, and searches for the longest reoccurring substring. It compares the first letter with every other until it finds a match, then saves it. Then it compares the ...
8
votes
1answer
175 views
Compute the height of a tower made of buckets
I need to speed up my algorithm. It is about finding the height of a tower. The tower is built from buckets. Each bucket has height and radius (1 <= height,radius <= 1000). Variable ...
8
votes
2answers
2k views
Codility “max slice swap” challenge
Problem Description:
Find the maximum sum of a compact subsequence of array elements after
performing a single swap operation.
Solution:
...
7
votes
3answers
1k views
Find the total number of ways W, in which a sum S can be reached in N throws of a dice
I was solving this question:
Given there is a 6 sided dice. Find the total number of ways W, in which a sum S can be reached in N throws.
Example:
S = 1, N = 6 => W = 0
S = 6, N = 6 => W ...
7
votes
6answers
12k views
Find maximum difference between values in an array
My task is to use the following pseudocode and improve it (make it run faster). Also I have to analyze the runtime of the given pseudocode and of my new code that i improved.
What does this algorithm ...
7
votes
5answers
2k views
Finding unique triplets adding up to 0
I am working on a problem "3Sum", in which, given an array S of n integers, are there elements ...
7
votes
3answers
4k views
Algorithm to compute the n-th derivative of a polynomial in Python
As a personal exercise, I'm trying to write an algorithm to compute the n-th derivative of an ordered, simplified polynomial (i.e., all like terms have been combined). The polynomial is passed as an ...
7
votes
1answer
2k views
Simplify function to sum the absolute value of the difference between all pairs of elements of a sorted array
Given a sorted array of N elements, I need to find the absolute sum of the differences of all elements.
Given 4 elements (1, 2, 3 and 4):
|1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4| = 10
Here is my code ...
7
votes
3answers
844 views
Finding the shortest excerpt that contains all search terms
Write a function called answer(document, searchTerms) which
returns the shortest snippet of the document, containing all of the
given search terms. The search ...
7
votes
3answers
2k views
A partition algorithm for positive integers
I have encountered the following problem that I found very interesting to solve:
Given an array of positive integers {a1, a2, ..., an} you are required
to partition the array into 3 blocks/...
7
votes
1answer
662 views
Monitoring the recursive growth of a zombie rabbit population
Breeding like rabbits
Write a function answer(str_S) which, given the base-10 string
representation of an integer \$S\$, returns the largest n such that \$R(...
7
votes
1answer
2k views
Check for valid parentheses nesting
I found this question on leetcode and that was my answer ... But someone told me it's too bad that it takes \$O(n^3)\$ I am not sure that it takes all that time ... and trying to find better ...
7
votes
2answers
748 views
Finding pairs of numbers within A that add up to N
I am working on an interview question from Amazon Software Interview:
Given an integer N and an array of unsorted integers A find all pairs of numbers within A which add up to N
I have a working ...
7
votes
1answer
10k views
Rotate Matrix using Python
This is my solution to Exercise 1.7 from Cracking the Coding Interview. I would appreciate any feedback on coding style and algorithm efficiency.
I do know that there is an existing function in ...
7
votes
1answer
180 views
Check consistency of a list of statements, with fuzzy rhyme matching
I made a program today that solves the following problem on a programming competition site (open.kattis.com): Check if all statements with the following format X is Y or X not Y are consistent. X and ...
7
votes
1answer
210 views
Extending the extended Stable Marriage Problem using a Python class
As soon as I saw this open source paper, I thought that the best way to replicate their code would be using a python class. After having replicated and extended the ...
6
votes
5answers
11k views
Finding the most common character in a string with a hash map
I created a method for finding the most common character in a string (using HashMap):
...
6
votes
4answers
1k views
Sufficient implementation of subset sum for 45 min interview
I am preparing for interviews, and have implemented a solution to this problem from Geeks for Geeks:
Given a set of non-negative integers, and a value sum, determine if there is a subset of the ...
6
votes
2answers
1k views
Sum the exponents of the prime factors of a number
My goal is to find the sum of the exponents of the prime factors of an integer.
I wrote the code below with the complexities specified here (I am not 100% sure of the complexities though):
Runtime ...
