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.

Filter by
Sorted by
Tagged with
-5
votes
2answers
2k 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 is 1)...
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. ...
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: ...
6
votes
1answer
5k 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
2k 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
1k 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 is ...
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 ...
2
votes
2answers
91 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
829 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 ...
2
votes
0answers
42 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
1k 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
104 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
331 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. ...
6
votes
1answer
466 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 air, ...
22
votes
3answers
31k 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 ...
6
votes
2answers
1k 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
1k views
15
votes
2answers
809 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 ...
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 room ...
4
votes
1answer
2k 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 ...
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 ...
5
votes
1answer
372 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: https:...
3
votes
2answers
2k views

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 ...
11
votes
5answers
17k 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 ...
5
votes
1answer
307 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 ...
50
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 ...
2
votes
1answer
164 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
245 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
2k 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
1k 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: ...
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 ...
7
votes
2answers
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 ...
6
votes
2answers
4k 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 ...
2
votes
2answers
10k views

Fibonacci sequence implementation

This was too slow for my computer: ...
3
votes
1answer
185 views

Space and time complexity of operation on lists

I'm new to programming and even more new to Haskell. Below is a little tid-bit I wrote that operates on a bunch of lists. I am wondering if someone would be kind enough to walk through the function <...
6
votes
1answer
5k views

Stable radix sort in-place using O(1) space

I am trying to implement a stable radix sort in place with O(1) space. I've seen Wikipedia, and I notice the C implementation is using a temporary variable to hold the sorted value for each pass, and ...
3
votes
2answers
853 views

Not getting Log(n) performance from quadtree

Here is my QuadTree class and node. The problem is really with Querying. In my game, I have a city which can have n * n streets (randomly generated). And each street has buildings. What I do is put ...
2
votes
1answer
2k views

Finding the pairs of intersecting discs

I have been following this question on SO, copied below. I put together a solution, but which is \$O(n^2)\$. In order to get a more efficient \$O(n \log n)\$ or \$O(\log n)\$ solution, I tried to ...
8
votes
3answers
354 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 ...

1
4 5 6 7
8