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.
28
questions
13
votes
1
answer
2k
views
Extended stable marriage challenge
I've written a solution for the stable marriage problem in the case that the number of men is not equal to the number of women. My problem is not that I can't prove my code is right. The problem is I ...
- 251
2
votes
2
answers
658
views
Finding number of number pairs with given difference [closed]
pairs() is a function which returns the total number of combinations whose difference is k.
...
- 131
13
votes
7
answers
2k
views
Finding the most popular element with C# given O(1) space complexity requirement
I have tried to solve the following problem in C# with LINQ:
Given an integer array, find the most frequent number and it's count in the array. If multiple numbers have the same highest frequency ...
- 295
13
votes
5
answers
9k
views
"Algorithmic Crush" problem hitting timeout errors
This is the HackerRank problem Algorithmic Crush:
You are given a list of size N, initialized with zeroes. You have to perform ...
- 231
12
votes
3
answers
2k
views
Given some integers, return the k most frequent elements
Given a non-empty array of integers, return the k most frequent elements.
For example, given [1,1,1,2,2,3] and k = 2, return <...
- 539
9
votes
2
answers
9k
views
URLify a string using Python
I have been working my way through the exercises in the book Cracking the Coding Interview. I wanted to get feedback for the following exercise.
Write a method to replace all spaces in a string ...
- 841
8
votes
2
answers
12k
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 ...
- 181
7
votes
3
answers
2k
views
Find the total number of ways W, in which a sum S can be reached in N throws of a dice
I was solving this question:
Given there is a 6 sided dice. Find the total number of ways W, in which a sum S can be reached in N throws.
Example:
S = 1, N = 6 => W = 0
S = 6, N = 6 => W ...
- 1,291
7
votes
1
answer
527
views
Check consistency of a list of statements, with fuzzy rhyme matching
I made a program today that solves the following problem on a programming competition site (open.kattis.com): Check if all statements with the following format X is Y or X not Y are consistent. X and ...
- 917
6
votes
4
answers
573
views
Longest spell to cast from pages of spellbook
While practicing for a school coding challenge, I came across this problem. My code got the right answers but exceeded the time limited. Any tips for how to reduce the time complexity?
https://pctc....
- 109
6
votes
2
answers
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 ...
- 63
6
votes
1
answer
2k
views
MaxCounters solution
I am doing this Codility problem
You are given N counters, initially set to 0, and you have two possible operations on them:
increase(X) − counter X is increased by 1,
max counter − all ...
- 493
6
votes
5
answers
3k
views
Sort an array of 0s, 1s and 2s in Java
Write a program to sort an array of 0's,1's and 2's in ascending
order.
Input:
The first line contains an integer 'T' denoting the total number of
test cases. In each test cases, First ...
6
votes
1
answer
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 ...
- 163
5
votes
3
answers
13k
views
Rotate image 90 degree clockwise
* Time complexity: O(N)
* Memory complexity: \$O(1)\$
Is my calculation of complexity correct for this code?
...
- 3,278
4
votes
1
answer
1k
views
Find given number by summing up integers from 2 sorted arrays
I am working on an algorithm question in which I need to find out pair of number out of 2 sorted arrays which sum up to the given number. I need to print out the indexes of those pairs rather than ...
- 143
3
votes
0
answers
129
views
Benchmarking multiple implementations of a Code Kata: queue for the self-checkout tills at the supermarket
I was reading this question:
Why is my function timing out when run with a larger data set?
And although I couldn't quite grasp the OP's implementation and so didn't feel like answering.
I did some ...
- 5,477
2
votes
2
answers
10k
views
2
votes
4
answers
276
views
Long arithmetic addition in JS
The implementation of the algorithm which adds two number in string form with arithmetic rules.
...
- 779
2
votes
1
answer
66
views
Merging Two Bubble Sorted Linked Lists (Python)
I'm following a tutorial on merging two bubble-sorted Single Linked Lists in Python.
merge1 creates a new list and does the merging.
Other than naming ...
- 3,517
1
vote
1
answer
360
views
Printing subarrays ⚡
I was trying to to print all subarrays of an array in quadratic time. Here is my code:
...
1
vote
0
answers
67
views
1
vote
2
answers
351
views
Massive file sorting algorithm
I was trying to sort a massive file of successive chars in C. I did some research and found a few file sorting algorithms that look the same. Their main idea is to read an amount of data to memory, ...
- 13
1
vote
3
answers
77
views
Mixed Duo String Generator 2 [duplicate]
I've create a program that finds mixed duo within a string. It removes characters from a string that do not form the first mixed duo. It does not rearrange the order of the string, it ony remove ...
- 89
1
vote
1
answer
2k
views
Hackerrank "Breaking the Record" solution
I have solved the hacker rank problem listed here. Given a sequence of scores, I need to count the number of times the records for the high and low scores have been broken.
Easiest way for me was to ...
- 171
0
votes
1
answer
53
views
Time complexity of tape equilibirum
As per the instructions on this Tape Equlibrium-Codility
I've written the code
...
- 153
0
votes
1
answer
77
views
Choosing between 2 Fibonacci alternatives [closed]
Task:
Return the fibonacci value at a given index.
e.g: input: 6, return: 8.
Algorithm 1:
...
- 157
0
votes
4
answers
7k
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 ...
