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.
343
questions
4
votes
5answers
137 views
Find the smallest element in a sorted and rotated array [closed]
I was solving a question asked in interview by Uber. It says:
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in \$O(\log n)\$...
5
votes
1answer
319 views
Finding the upper and lower bound using binary search
I am trying to solve this InterviewBit question
https://www.interviewbit.com/problems/search-for-a-range/.
My code for this seems to be working properly and it does give me the correct answers on my ...
5
votes
2answers
2k 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 \$a^n\$."
Here is my recursive solution to this problem (in Java):
<...
13
votes
5answers
8k 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 ...
4
votes
1answer
106 views
Time(n) Complexity of Fibonacci Algorithms
It is my first use of classes in Python. I wanted to create something useful and try some new things as I learn this cool language: strategy pattern, testing with nanoseconds precision, curve/poly ...
2
votes
2answers
171 views
Program that prints star pattern
I have a program that prints the star pattern.
Starr Pattern is:
...
6
votes
1answer
137 views
Phonebook using a trie
I implemented a PhoneBook utilizing a Trie data structure.
Could I ask you to evaluate it?
Did I apply Trie correctly for such ...
7
votes
1answer
210 views
Extending the extended Stable Marriage Problem using a Python class
As soon as I saw this open source paper, I thought that the best way to replicate their code would be using a python class. After having replicated and extended the ...
13
votes
4answers
3k views
Check if one string is a permutation of another using Python
The code below is an attempt at a solution to an exercise from the book "Cracking the Coding Interview."
I believe that the worst case time complexity of the code below is \$O(n)\$, where n is the ...
5
votes
2answers
6k views
Find the number of K-Complementary pairs in an array
Below is the program to find k-complementary pairs: K = A[i] + A[j];.
...
1
vote
1answer
573 views
The quicksort algorithm in Haskell
I am learning Haskell programming language mainly from this source. And there I have encouraged with "an elegant" realization of the quicksort sorting algorithm (the Quick, sort! section). Here it is:
...
1
vote
1answer
358 views
Finding pairs that add up to a given sum, using recursion
I'm currently tasked with using recursion to find pairs that add up to a given sum. How would I make the function recursiveFixedSumPairs function more efficient and truncate this code? Also, what is ...
12
votes
1answer
1k 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 ...
3
votes
1answer
757 views
Circuit builder that calculates resistance/current/voltage
I am somewhat new to programming. I've written a program that takes user input accepting voltages and resistors, and calculating total resistance/current/voltage in the circuit. I am looking for ways ...
4
votes
3answers
533 views
Detecting if two strings are anagrams
I am trying to write a function that detects if two strings are anagrams of one another; more specifically, I want the function to be linear in its time complexity (\$O(n)\$ where \$n\$ is the length ...
12
votes
3answers
1k 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 <...
0
votes
1answer
64 views
Searching for a sum of any series in array
I'm given this method, and requested to analyze what it does, and minimize its complexity (both time and space).
All values are known to be larger than zero.
...
4
votes
2answers
3k views
Check if two strings are one 'edit' apart using Python
The code below is my solution in python 3 to exercise 1.5 in Cracking the Coding Interview. I would appreciate feedback on both the algorithm (improvements to space and time complexity) and/or coding ...
3
votes
1answer
11k views
Counting all substrings with exactly k distinct characters
Problem Statement : Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that has exactly k distinct characters. Example:
Input: abc, k = 2 Output: 2 ...
2
votes
1answer
497 views
Vertex Cover Problem Greedy Solution [closed]
As far as I understood this problem, it is a subset of vertices of Graph G, such that every edge has at least one endpoint in the subset. This problem is considered to be NP Complete. However I think ...
2
votes
0answers
194 views
MergeSort linked list implementation
I wrote a MergeSort implementation of doubly linked list, based on the MergeSort implementation of array on the textbook Algorithms 4th, which is definitely \$O(n \log n)\$.
I think my linked list ...
9
votes
4answers
14k 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 use ...
1
vote
1answer
214 views
Implementing `components(separatedBy:)` method in Swift
On looking at the components(separatedBy separator: String) -> [String] method from the Swift Standard Library, I tried to come up with an implementation just ...
0
votes
2answers
62 views
Unbalanced Binary Search Tree insertion and search with random and sorted values
I have created this unbalanced binary search tree in C. Can anyone say this is a true approach or not? I have two scenarios for insertion and search: in the first scenario I am inserting 10000 random ...
2
votes
2answers
130 views
Substrings search (Aho-Corasick algorithm)
I have a code where the goal is to give score to strings based on how much score certain substrings are worth (including repeating substrings).
The way my code (which is based on the Aho-Corasick ...
1
vote
0answers
126 views
Codility Tape Equilibrium
This question is related to this one, since it's about the same Codility exercise (Tape Equilibrium instructions): Time complexity of tape equilibirum
Basically, given an integer array, the objective ...
3
votes
1answer
198 views
“Counter Game” Powers of 2 Game
I have been working on this hackerrank problem:
Louise and Richard have developed a numbers game. They pick a number (1 ≤ n < 264)
and check to see if it is a power of 2. If it is, they divide ...
0
votes
2answers
44 views
Incrementing specified list values, with “catch-up” [closed]
I completed a coding challenge recently in which my function was to be given two parameters: N, the number of counters to be used (numbered 1 through N) - and A, an array of integers. Iterating ...
1
vote
3answers
67 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 ...
1
vote
0answers
36 views
Mixed Duo String Generator Part 2
Mixed Duo String Generator
Hello again;
Previously my code was critique and I applied this feedback to form my new revised code for the Mixed Duo String Generator. In the code below I revised it to ...
3
votes
2answers
69 views
Place arithmetic signs in correct order to get the number
Given a list of numbers, place signs + or - in order to get the
required number.
If it's possible then return ...
9
votes
1answer
1k 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 ...
1
vote
1answer
256 views
Find maximum in sorted and rotated array
This is an interview question.
A sorted rotated array is a sorted array which was rotated 0 or more times.
For example: [1,2,3] -> [2,3,1]
...
1
vote
1answer
560 views
Median of two sorted arrays JavaScript
Trying to find the median of two sorted arrays in O(log(m+n)) or better. I believe this is O(log(m+n) or O(log(m)) or O(n).
...
2
votes
1answer
67 views
O(n) Object Pool
I recently rewrote my object pool design to \$O(n)\$ complexity. I did this using a linked list, which is not native in JavaScript. It does not, unfortunately, automatically assign ...
-3
votes
1answer
59 views
Given an array of positive integers, find shortest subarray whose sum exceeds a threshold [closed]
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
Example:
Input: ...
8
votes
1answer
175 views
Compute the height of a tower made of buckets
I need to speed up my algorithm. It is about finding the height of a tower. The tower is built from buckets. Each bucket has height and radius (1 <= height,radius <= 1000). Variable ...
5
votes
2answers
237 views
Finding substrings within arrays
I need to find the substrings within my array. If I have an array: ["abc", "abcd", "abcde", "xyz"], my method should return the array members: ...
1
vote
1answer
80 views
Form the largest number by swapping one pair of digits
You are given a number. You are given the opportunity to swap only once to produce the largest number.
My approach was to use buckets whose values were their indexes and their locations were their ...
4
votes
1answer
586 views
Time complexity of Max counters
As per the instructions are given in MaxCounters-Codility,
You are given N counters, initially set to 0, and you have two possible operations on them:
<...
6
votes
2answers
2k 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, ...
2
votes
1answer
413 views
Return the optimal time slot
Implement a function meetingPlanner that given the availability, slotsA and slotsB, of two people and a meeting duration dur, returns the earliest time slot that works for both of them and is of ...
1
vote
1answer
36 views
Time complexity of tape equilibirum
As per the instructions on this Tape Equlibrium-Codility
I've written the code
...
2
votes
2answers
2k views
'Zero out' a matrix using Python
Below is my code for an attempted solution to cracking the coding interview exercise 1.8 written in python 3.5. The problem statement is:
Write an algorithm such that if an element in an MxN ...
2
votes
1answer
671 views
Swift - Finding longest binary gap of a given integer
I recently had the chance to try Codility's algorithm training, and the very first one in the list is finding the longest binary gap of a given integer.
I tried to implement this in Swift, and after ...
1
vote
1answer
114 views
Rearrange an array in place such that the first and last halves are interleaved
Given an array of n elements in the following format { a1, a2, a3, a4,
….., an/2, b1, b2, b3, b4, …., bn/2 }. The task is shuffle the array
to {a1, b1, a2, b2, a3, b3, ……, an/2, bn/2 } without ...
0
votes
1answer
269 views
Iteratively determine the diameter of a binary tree
Can the performance of the iterative approach be improved? I find that this approach lags behind many recursive options. no recursive answers, please.
Baseline recursive approach: takes 52 steps ...
0
votes
1answer
798 views
Median of two sorted arrays
The task is to find the median of two Arrays. I have an O(n) solution.
Can it be written in a better time complexity?
...
2
votes
3answers
113 views
Three Numbers in Java
Given three positive numbers A, B, and C. Find the number of positive
integers less than D that are divisible by either of A, B or C.
Input format
The 1st argument given is an Integer A. ...
1
vote
3answers
2k views
Sort all even numbers in ascending order and then sort all odd numbers in Descending order Java
Given an array of integers (both odd and even), the task is to sort
them in such a way that the first part of the array contains odd
numbers sorted in descending order, rest portion contains even ...
