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.
-2
votes
0answers
20 views
Time complexity of pairing method [on hold]
I have to write code to take a sorted double array having an odd number of elements, find the pairs of values with the shortest distance between them, and return the remaining value, which is ...
5
votes
3answers
125 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
59 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
28 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
193 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
56 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
109 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
84 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
166 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
96 views
10
votes
7answers
1k views
Calculate square of a number without multiplication
I wrote these two methods to calculate the square of a number:
...
4
votes
3answers
205 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
29 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
468 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
160 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
102 views
1
vote
2answers
110 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
129 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
331 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
148 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
375 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
59 views
7
votes
1answer
45 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
208 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
357 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
172 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
132 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
111 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
214 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
65 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
161 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
422 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
1k 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
516 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
340 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
87 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
149 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
163 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
279 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 ...
0
votes
0answers
31 views
Proving a conjecture given a set of clauses - calculating complexity
I have written this Perl program to prove a conjecture given a set of clauses. I've actually posted some code from it on here in another question.
This time its all done and I've made it as fast as ...
8
votes
3answers
164 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 ...
5
votes
1answer
90 views
Calculate difference of indices
The challenge is to reconstruct an n-digit number using the following information:
On each step, you choose an index x from 1 to n. For all indices y (y
< x), you calculate the difference by ...
6
votes
3answers
305 views
Performance analysis of 3 digits sum
I have a method that finds 3 numbers in an array that add up to a desired number.
...
7
votes
1answer
167 views
Determine total number of ways of reaching a destination
Question:
One of Scotland Yard’s most wanted criminal (Mister X) is on the run
and needs to reach a certain destination safely. There are three modes
of transport available for him - By ...
11
votes
3answers
5k 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 ...
5
votes
2answers
261 views
Genomic Range Query
Recently I worked on one of the Codility Training - Genomic Range Query (please refer to one of the evaluation report for the detail of this training).
The proper approach for this question is using ...
5
votes
2answers
248 views
