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.

learn more… | top users | synonyms

3
votes
1answer
34 views

Spending a target sum, preferably split equally

I have a strange programming prompt. I managed to complete an algorithm to solve smaller test entries (which i'll post). One of my test cases has to complete a 200,000 int input and my algorithm isn't ...
3
votes
1answer
40 views

Acquiring indices for anagrams of an input string

I am working on an interview question from Amazon Software: Design an algorithm to take a list of strings as well as a single input string, and return the indices of the list which are anagrams of ...
6
votes
2answers
201 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 ...
1
vote
4answers
51 views

Finding the second largest element of large input sets

I have a problem where I need to find the second maximum element of the user inputs. It's an online practice problem and I can't figure out why the server responds back with a Non-Zero Exit Code error ...
6
votes
2answers
284 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 ...
4
votes
2answers
388 views

Non-recursive method for finding a ^ n

I am working on an interview question from Amazon Software. The particular question I am working on is "to write a program to find an." Here is my recursive solution to this problem (in Java): ...
3
votes
3answers
185 views

Find the index of the element with maximum absolute deviation

I just completed a Codility test. The question presented was pretty simple but I may have over thought it. Question: Find the element which has the highest absolute deviation from the mean. E.g. ...
0
votes
2answers
46 views

Uva Online Judge problem 100, 3n + 1

I am having a tough time submitting this code to UVa Online judge and having it pass. I keep getting the message - Your program used more CPU time than what is allowed for this problem. That means ...
0
votes
3answers
82 views

Finding all integers in an array with odd occurrence

I am doing an interview exercise problem from here. The problem is to find "all numbers that occurred an odd-number of times in an array". Here is my high level psuedo code thinking: Construct a ...
5
votes
3answers
180 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 ...
3
votes
2answers
77 views

Removing duplicates from an array

I recently wrote this JavaScript algorithm for removing duplicates from an array as part of a job interview process, but was turned down for the position after submitting the code. I didn't receive ...
3
votes
1answer
31 views

Integrate the product of four infinite series functions

I wrote the following code to integrate the product of four functions. Two of the functions are hypergeometric functions and the other two are incomplete gamma functions. I have written each function ...
3
votes
3answers
198 views

Determining if a pair exists in a large sorted array

I'm doing practice interview questions from here. Here is the one I am currently on - if you are given a very large sorted int array, then check of there exists a ...
0
votes
0answers
71 views

DP algorithm to find minimum average wait for customer-serving system

Below is the code to find the minimum average waiting time for customers at a store. I want improve the time complexity of the code. As an overview of the logic, I start from ...
3
votes
1answer
64 views

Extracting length-3 subsequences from a list

For a list li, I want to print only the values of the triplets a, b, c where ...
3
votes
3answers
155 views

Find intersection of two arrays without duplicates

A = [9, 1, 4, 2, 5] k unique integers B = [3, 1, 8, 7, 6, 5] n unique integers Intersection => [1, 5] Find an algorithm that uses \$O(1)\$ space (the space used by the return variable is not ...
-1
votes
1answer
93 views

Finding the distance from each array element to the nearest zero entry

I wrote a program, that gets a certain array and replaces each value in the array with the distance from it to the closest zero value. Time complexity is 4n => O(n). (please correct me if I'm wrong, ...
4
votes
2answers
185 views

Python Find All Adjacent Subsets of Set of Coins Which Have a Tails Minority

Given a sequence of heads and tails I want to find how many significant subsequences are in this sequence where the number of heads is not less than the number of tails. I want to achieve this in ...
2
votes
1answer
100 views
10
votes
7answers
2k views

Calculate square of a number without multiplication

I wrote these two methods to calculate the square of a number: ...
4
votes
3answers
321 views

Rotate image 90 degree clockwise

* Time complexity: O(N) * Memory complexity: \$O(1)\$ Is my calculation of complexity correct for this code? ...
1
vote
0answers
32 views

A scalable function for get boundary vertices in a graph

Given a community division I need a list of vertices that have edges in more than one community, i.e., boundary vertices. I've tried this: ...
5
votes
4answers
568 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 ...
5
votes
4answers
172 views

Stack with a minimum

A practice interview question: How would you design a stack which, in addition to push and pop, also has a function getMin which returns the minimum element? Push, pop and min should all operate ...
3
votes
1answer
130 views

Removing duplicates from unsorted LinkedList

Removing Duplicates: ...
1
vote
2answers
138 views

Codility AbsDistinct: Why is this solution not O(n)?

This is part of a series of algorithmic lessons and tests by Codility. For copyright reasons, I cannot reproduce the question, which asks to compute the number of distinct absolute values in a given ...
5
votes
1answer
142 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 ...
3
votes
1answer
452 views

PermCheck Codility with time complexity of O(N)

I have this solution for Codility's PermCheck problem. In summary, the task is to check whether array A contains each number in \$1 \ldots N\$ exactly once. I got ...
2
votes
1answer
191 views

Permutations of any given numbers

I have solved one programming problem where we have to find all the permutations of given numbers. For example, \$[1,2,3]\$ have the following permutations: $$[1,2,3], [1,3,2], [2,1,3], [2,3,1], ...
6
votes
5answers
398 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 ...
3
votes
1answer
67 views

Count Point in an area

I created this to count points in an area. This is my JavaScript code: ...
7
votes
1answer
47 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 ...
3
votes
1answer
282 views

Finding the longest unique sub-string in a string

I recently interviewed with a company for software engineering position. I was asked the question of finding the longest unique sub-string in a string. My algorithms was as follows: Start from the ...
5
votes
2answers
433 views

Re-arrange a string into a { consonant, vowel, consonant, vowel … } sequence

I was prompted to give someone advice about the following problem: Given a string with equal amount of vowels and consonants, re-arrange it so that it follows the sequence { consonant, vowel, ...
4
votes
3answers
216 views

Print all nodes from root to leaves

I've made a function to print all paths from root to all leaves in a binary search tree. I already have an insert function, which I haven't included in the code here as I felt it was irrelevant to the ...
0
votes
2answers
145 views

Fastest way to find maximum deviation

I acknowledge that this exact question was asked here. I was working on the same problem from the same website. I had the same question and consulted the above as a reference, however with respect ...
3
votes
1answer
155 views

Time complexity of anagram solution

I have written code to return anagrams from a list of words. I'm a newbie in time complexity analysis so pardon my ignorance if this is a blatantly obvious question. Am I right in thinking this is in ...
3
votes
2answers
291 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 ...
2
votes
1answer
68 views

Time complexity of 0/1 Knapsack challenge

The code gives correct output. How do I calculate time complexity for code like this? The program finds all the combinations of items and sees if the combination gives the max profit. If the last ...
3
votes
2answers
129 views

Optimizing code for sequence A064604

I am implementing A064604 - OEIS for positive integers up to 10 billion. I am finding the divisors in \$O(\sqrt N)\$. So, the overall time complexity of running the formula right now is \$O(N\sqrt ...
3
votes
1answer
166 views

Interview task to efficiently find compact representation of nodes in tree and find big O time

I recently had an interview problem where I was asked to find a compact representation of nodes in a tree. As an example, consider the following tree: ...
-4
votes
2answers
460 views

“Magic Fraction” finder

A Magic Fraction for N is one that has the following properties: It is a proper fraction (the value is < 1) It cannot be reduced further (the GCD of the numerator and the denominator ...
10
votes
6answers
2k views

Reducing conditional statements to avoid cyclomatic complexity

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. ...
6
votes
2answers
563 views

Improving performance for Codility max slice swap problem

Problem Description: Find the maximum sum of a compact subsequence of array elements after performing a single swap operation. Solution: ...
4
votes
1answer
409 views

Is this a good Ruby implementation of Prime Factorization?

I'm doing some practice problems on Khan Academy. The current one is Prime factorization. I came up with this: ...
3
votes
1answer
104 views

Construct KD-Tree in Java

I want to construct KD-Tree from unsorted List of points in the plane (i.e. 2-KD-Tree). To do so I used the method from Wikipedia: http://en.wikipedia.org/wiki/Kd-tree#Construction This is my code: ...
6
votes
1answer
162 views

Russian doll envelops

Interview question from the interwebz You have a set of envelopes of different widths and heights. One envelope can fit into another if and only if both the width and height of one envelope ...
8
votes
1answer
175 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 ...
2
votes
2answers
78 views

Two squares or not two squares - constant time optimization

I have been trying to solve this problem, and after a bit of googling, I realised a \$O(\sqrt{n})\$ time complexity works fine (though the algorithm suggested is different from that I have used). My ...
5
votes
3answers
287 views

Psycho and ordinary numbers

The problem statement can be found here. In short, here's what the problem is about: You're given a set of numbers and you need to find whether the the numbers are ordinary or psycho. For a number ...