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.
7
votes
1answer
106 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 ...
10
votes
3answers
328 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
55 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
74 views
Helper method to extract a specific string from long message
private string ExtractExceptionMesssage(string exceptionMessage)
{
const string startWord = "Message>";
int startWordLength = startWord.Length;
const string endWord = ...
8
votes
2answers
437 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
390 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
57 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 ...
3
votes
0answers
138 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
161 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
65 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
1k 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 optimize it.
Can you offer any ...
4
votes
1answer
67 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 ...
26
votes
11answers
2k views
Searching in an array in less than O(n) time
I've an array where each element is either one less or one greater than the preceding element. I've to search an element in it in less than O(n) time. I've implemented it like this:
public int ...
2
votes
1answer
53 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 cube1: {a, b, c} and ...
4
votes
1answer
69 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,
String input;
double a;
if (null != input && !input.isEmpty()) {
a = Double.parseDouble(input);
} else {
a = defaultValue;
}
With Guava, ...
3
votes
5answers
265 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: i == list[i] (where i is the index 0 <= i <= len(list)).
def ...
1
vote
3answers
64 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:
1,
1,2
1,2,3
1,2,3,4
1,2,3,4,5
2,
2,3,
2,3,4,
2,3,4,5
3,
3,4
3,4,5
4
4,5
5
This ...
2
votes
2answers
1k 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 ...
2
votes
0answers
40 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 ...
5
votes
1answer
110 views
Finding an efficient algorithm in terms of reducing Big O complexity
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 ...
4
votes
4answers
154 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
903 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
750 views
Fibonacci sequence implementation
This was too slow for my computer:
int f(unsigned int x)
{
if(x <= 1) return 1;
else return f(x-1)+f(x-2);
}
/* main */
int main()
{
for(int i = 0; i < 50; i++) cout << f(i) ...
0
votes
0answers
134 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 ...
5
votes
1answer
1k 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
283 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 ...
8
votes
3answers
215 views
Can anyone make my O(n^3) function more efficient, or offer suggestions to make handling it more efficient?
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 int array. I'll ...
