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.
0
votes
0answers
14 views
Analying complexity of an implementation of Prim's algorithm [migrated]
This is a Prim's implementation! Indeed this is very complex and slow and a better version is here but I still want to know the time complexity of below code. You can check the same code here too nice ...
5
votes
4answers
241 views
Sufficient implementation of subset sum for 45 min interview
I am preparing for interviews, and have implemented a solution to this problem from Geeks for Geeks:
Given a set of non-negative integers, and a value sum, determine if there is a subset of the ...
4
votes
2answers
73 views
Hackerrank “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 M operations on the list and output the maximum of final values of ...
0
votes
2answers
76 views
Big O notation for quicksort implementation [closed]
I am trying to find out what would be the Big O notation of a quick sort implementation I wrote. If I can get some analysis on the code, that would be great.
...
10
votes
2answers
197 views
Minimum sub-array challenge
Below is my solution to finding the minimum product sub-interval. It passed 8/12 or so test cases, but the other test cases timed out if they hadn't finished within 2 seconds. When I compile this code ...
2
votes
3answers
44 views
Intersection of subset between two lists of dicts
I want to find the intersection of two lists of dicts.
Note that equality—i.e.: what is to appear in the intersection—is given by which keys they must have equal. See the ...
3
votes
1answer
62 views
Number of paths in a grid (lattice) graph
I am trying to solve a variant of the very popular question in which we find the number of distinct valid paths on a directed graph. The graph's nodes make up a m x n lattice (grid), and the edges ...
4
votes
2answers
121 views
Extracting and analyzing data from SAP
I developed a script for the company I work for in order to extract data from SAP (CJ74) and analyze the data.
One particular issue I am finding is that for any data sets which have over 1000 lines, ...
2
votes
2answers
71 views
Given bit strings, perform a bitwise addition
I'm looking for code-review, optimizations and best practices. This code is a Java adaptation of code on geeksforgeeks.org. Please verify if space complexity is \$O(n)\$ where n is number of bits, and ...
4
votes
1answer
192 views
Finding whether there exists a pair of numbers in a set having a given product
Devise an algorithm that will operate on a number x and a set of n
distinct numbers such that in \$O(n \lg n)\$ time, the algorithm indicates
whether or not there are two numbers in the set ...
2
votes
2answers
89 views
Improving the efficiency of my FizzBuzz algorithm [closed]
I worked on an exercise from codewars, which is a variation of the popular fizzbuzz game. (If the link doesn't work, you may need to reload the page.)
In this variation, I'm supposed to find the sum ...
3
votes
1answer
51 views
Spending a target sum, preferably split equally
I have a strange programming prompt. I managed to complete an algorithm to solve smaller test entries (which i'll post). One of my test cases has to complete a 200,000 int input and my algorithm isn't ...
3
votes
1answer
49 views
Acquiring indices for anagrams of an input string
I am working on an interview question from Amazon Software:
Design an algorithm to take a list of strings as well as a single input string, and return the indices of the list which are anagrams of ...
6
votes
2answers
239 views
Finding pairs of numbers within A that add up to N
I am working on an interview question from Amazon Software Interview:
Given an integer N and an array of unsorted integers A find all pairs of numbers within A which add up to N
I have a working ...
1
vote
4answers
60 views
Finding the second largest element of large input sets
I have a problem where I need to find the second maximum element of the user inputs. It's an online practice problem and I can't figure out why the server responds back with a Non-Zero Exit Code error ...
6
votes
2answers
359 views
Sum the exponents of the prime factors of a number
My goal is to find the sum of the exponents of the prime factors of an integer.
I wrote the code below with the complexities specified here (I am not 100% sure of the complexities though):
Runtime ...
4
votes
2answers
418 views
Non-recursive method for finding a ^ n
I am working on an interview question from Amazon Software. The particular question I am working on is "to write a program to find an."
Here is my recursive solution to this problem (in Java):
...
3
votes
3answers
345 views
Find the index of the element with maximum absolute deviation
I just completed a Codility test. The question presented was pretty simple but I may have over thought it.
Question:
Find the element which has the highest absolute deviation from the mean. E.g. ...
0
votes
2answers
95 views
Uva Online Judge problem 100, 3n + 1
I am having a tough time submitting this code to UVa Online judge and having it pass. I keep getting the message - Your program used more CPU time than what is allowed for this problem. That means ...
0
votes
3answers
215 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 ...
5
votes
3answers
264 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
139 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
33 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
205 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 ...
1
vote
0answers
204 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
69 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
269 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 ...
3
votes
1answer
95 views
Google Code jam puzzle - Welcome to Code Jam
The problem is to count all possible sub-sequences of "welcome to code jam" in a given input string (and only return the last 4 digits of the count). Here is the link to the problem for reference.
...
-1
votes
1answer
127 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
253 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
109 views
10
votes
7answers
2k views
Calculate square of a number without multiplication
I wrote these two methods to calculate the square of a number:
...
4
votes
3answers
1k 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
40 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
1k 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
255 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
285 views
1
vote
2answers
253 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 ...
6
votes
1answer
355 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
2answers
1k 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
991 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
496 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 ...
7
votes
1answer
50 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
647 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
561 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
542 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
190 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
284 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
552 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
83 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 ...
