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
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 ...