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.
3
votes
1answer
79 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 ...
0
votes
0answers
247 views
Length of longest distinct characters subsequence [closed]
I want to find the length of the longest distinct characters subsequence. If the logic is correct is there any way to make it more optimized? What would be the limit on the size of the string up till ...
2
votes
1answer
89 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
326 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
43 views
7
votes
1answer
41 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
103 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
230 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
97 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
105 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
51 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 ...
1
vote
2answers
82 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
41 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
125 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
138 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
288 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
298 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
108 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
69 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
132 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
108 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
74 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
249 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
30 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
141 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
89 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
298 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
156 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
3k 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
197 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
199 views
9
votes
2answers
495 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 ...
10
votes
5answers
461 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 ...
3
votes
1answer
260 views
Big-O complexity calculation for a merge and sort function
I have the following code which basically takes a list of sorted integer arrays and merges them together removing the duplicates.
I have tried to do the complexity analysis and came to a rough ...
4
votes
0answers
331 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 ...
5
votes
1answer
175 views
Reducing complexity of method
I'm trying to reduce the complexity of some methods, and I'm not exactly sure what approach to take. I'm currently building a PHP wrapper for a REST API, and the main problematic class is here:
...
1
vote
1answer
210 views
Performance issue of LFU-like web caching replacement algorithm
I have implemented a simulation program that runs LRU and another web caching algorithm called Sliding Window LFU. I want to compare them both in terms of the hit rate and their run time. SW-LFU works ...
7
votes
4answers
4k 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 ...
4
votes
1answer
119 views
Is this an efficient merge sort implementation with regards to average time complexity in Big-O notation?
Is my below merge sort implementation in O(n log n)? I am trying to implement a solution to find k-th largest element in a given integer list with duplicates with O(N*log(N)) average time complexity ...
31
votes
11answers
4k 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 ...
2
votes
1answer
54 views
Given set of cubes can we get a given word?
Given some cubes, can cubes be arranged such that an input word can be formed from the top view of the cubes?
For example: assume an imaginary cube with only 3 surfaces where ...
4
votes
1answer
126 views
Using Guava to reduce code complexity (and possibiliy to improve readability) of null check and assign default value
Below is my java code with some complexity,
...
3
votes
5answers
460 views
count all array[index] == index occurrences
The method foo gets a sorted list with different numbers as a parameter and returns the count of all the occurrences such that: ...
1
vote
3answers
92 views
Find all consecutive sequences in an ordered set
I have the following set. a = [1,2,3,4,5] and i want to find all of the following sequences of consecutive elements:
...
2
votes
2answers
2k views
Fish Food Chain 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 ...
3
votes
0answers
55 views
TLE for SPOJ Upper Right King
I am solving this problem on SPOJ Upper Right King (Hard).
I've written a solution in Python with a time complexity of O(n(logm)2). But it's showing TLE. Can anyone help me out with this?
For more ...
6
votes
1answer
284 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 ...
6
votes
4answers
281 views
Reduce complexity of state machine method
I've asked Code Climate to generate metrics for the ftpd Ruby gem. It correctly identified the God class; I know what to do about that. But one of the smaller classes has me stumped. This is ...
6
votes
2answers
2k views
Permutation of given string
I am reading a book on DSA, and the author explains how to generate the permutation of strings using recursion. I want to know if there are better ways of doing the same, unless this is the best ...
