# 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
Filter by
Sorted by
Tagged with
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)$...
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 ...
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): <...
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 ...
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 ...
171 views

### Program that prints star pattern

I have a program that prints the star pattern. Starr Pattern is: ...
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 ...
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 ...
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 ...
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];. ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 <...
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. ...
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 ...
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 ...
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 ...
194 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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] ...
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). ...
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 ...
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: ...
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 ...
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: ...
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 ...
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: <...
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, ...
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 ...
36 views

### Time complexity of tape equilibirum

As per the instructions on this Tape Equlibrium-Codility I've written the code ...
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 ...
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 ...
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 ...
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 ...
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? ...