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.
388
questions
1
vote
3answers
131 views
Transpose 2D Matrix in Java - Time & Space Complexity?
Here's my algorithm / approach for transposing a 2D Matrix on the main diagonal.
Before:
a L M d
b G c N
H K e F
I J O P
After:
...
0
votes
2answers
185 views
Java Palindrome - Time & Space Complexity
Which of these three methods is the most efficient?
Also, what is the time & space complexity of each?
...
4
votes
3answers
780 views
How to do these extraction/computations efficiently?
I have a set of products(e.g. P0006, P0009, etc.) and a set of production lines (eg. L1H175, L2H175). A product can be produced on a subset of the lines set (and not necessarily all of them).
If we ...
1
vote
0answers
59 views
My C# code to evaluate order of algorithm is returning logN or N^3 instead of N for simple loop [closed]
As a learning exercise, I am writing a library to evaluate the complexity of an algorithm. I do this by seeing how long the alorgorithm takes for given inputs N, and then do a polynomial regression ...
2
votes
1answer
57 views
Find the maximum GCD of a number with respect to all the values in an array for competitive programming
Here is the Question. Find the largest GCD of the input variable with the values of an array.
Inputs are as follows:- First-line contains two integers, N and Q.
Second-line contains N integers which ...
5
votes
4answers
7k 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 ...
3
votes
1answer
92 views
Searching an element in a 2D sorted array
I had to write a code (as an exercise) that receives a 2D row wise and col wise sorted array and an element, and return true is the element exists in the array.
The first thing that came to mind when ...
9
votes
2answers
6k 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 ...
1
vote
0answers
21 views
Intersection of Two Arrays - Space Time And Complexity [closed]
The problem is as follows: Given two arrays, write a function to compute their intersection.
The below code is my solution.I'm just curious as to what the space time and complexity of below algorithm ...
2
votes
1answer
81 views
Permutation 1…N. Answer queries “How many numbers between [X,Y] position are in the interval [L,K]”?
So I am solving this task:
We have an permutation of the numbers 1..n.
I need to answer m queries:
-How many numbers between X-th and Y-th position are in the interval [L,K] (<=k and >= L)?
So my ...
0
votes
1answer
64 views
Choosing between 2 Fibonacci alternatives [closed]
Task:
Return the fibonacci value at a given index.
e.g: input: 6, return: 8.
Algorithm 1:
...
3
votes
1answer
244 views
Algorithm to find the Array Balance Point
Task: Find the balance point of an array; return the index that if you break the array into left and right at that point will ...
3
votes
2answers
960 views
Finding unpaired number in an odd length Array of integers
codility OddOccurrencesInArray:
A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element ...
1
vote
0answers
99 views
Binary Heap module in Typescript/Javascript supporting min-heap and max-heap
About binary heaps: https://en.wikipedia.org/wiki/Binary_heap
The purpose of this module is to allow quick and efficient priority queue management, compared to linked list.
Efficiency: insert: \$O(\...
2
votes
0answers
32 views
Snake string implementations
This snippet uses a string as an output. As we iterate through the input string, I just keep appending a character to the string and I know this just pretty much creates a new string everything I add ...
2
votes
1answer
53 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 ...
2
votes
1answer
55 views
In-Place Merging of Two Bubble Sorted Linked Lists (Python)
I'm following a tutorial on merging two bubble-sorted Single Linked Lists in Python.
merge1 does the merging by creating a new list with maybe \$O(N+M)\$ memory ...
1
vote
0answers
68 views
leetcode 230: kth smallest element in a Binary Search Tree
Here is my implementation: the goal of the algorithm is to find the kth smallest element in a BST.
...
3
votes
0answers
135 views
Calculating the total sum of inversion count for all subarrays
My approach was to visit all inversion count pair and count how many subarrays these pair contribute. Visiting every pair requires \$\mathcal{O}(n^2)\$ time, but I want an optimized version of this, ...
2
votes
1answer
321 views
CCC '19 S5:Triangle: The Data Structure
This problem is from [CCC2019]: https://dmoj.ca/problem/ccc19s5/ (Canadian Computing Contest 2019) and I have implemented it in C++.
I used sequence [A054237]: https://oeis.org/A054237/table to ...
2
votes
1answer
48 views
Finding minimum weighted matching in sink source graph
I have three lists of nodes.
sources
sinks
pipes
There is a directed weighted graph from sources to pipes to sinks.
Sources are only connected to pipes and pipes only to sinks. But sources are not ...
4
votes
1answer
498 views
Hacker Rank Climbing The Leaderboard
This has been asked a couple of times but here is my implementation in C++. I have 11/12 solutions completed. The 6th test case which has 200000 intial scores and Alice has even more scores causes my ...
4
votes
1answer
167 views
Finding all simple (without internal cycles) paths in a directed graph with total >1.0 weight
Assume directed graph with each edge being weighted by some positive float.
Problem: find all simple paths (in other words, ...
8
votes
1answer
13k views
Rotate Matrix using Python
This is my solution to Exercise 1.7 from Cracking the Coding Interview. I would appreciate any feedback on coding style and algorithm efficiency.
I do know that there is an existing function in ...
8
votes
3answers
2k views
Find the smallest positive integer that is absent from a given array
I made the acquaintance of big-O a couple of weeks ago and am trying to get to grips with it, but although there's a lot of material out there about calculating time complexity, I can't seem to find ...
6
votes
2answers
183 views
8
votes
1answer
173 views
An array with \$O(\log\ n)\$ time complexity for all operations
Does this exist already? It's an array (=variable-size list with integer indices) where add/remove/set and get all take \$O(\log\ n)\$ time.
I couldn't find this anywhere, so I made up the name "Log-...
2
votes
2answers
91 views
Print Integers in a Pyramid
I need to write a method that will print the integers from [1, maxValue] in a pyramid where the nth row contains ...
2
votes
1answer
52 views
Circular Doubly Linked List with generators
I didn't find an implementation on CR of the circular doubly linked list, using generators. Hence, I tried it myself.
Description
The class Deck represents a ...
2
votes
0answers
41 views
Find target in sorted array pivoted at some unknown point in O(log n)
You are given an array sorted in ascending order which is rotated at
some pivot unknown to you beforehand. Find your target in \$O(log n)\$
which means it should be a binary search. If the value ...
0
votes
1answer
162 views
Create custom Queue class with O(1) Enqueue and O(1) Dequeue [closed]
I am implementing a Queue class in C# using a Node/LinkedList class that I also implemented, and I wonder if there is a way to implement the enqueue and the dequeue methods, both in algorithmic ...
3
votes
2answers
104 views
Time and space complexity of base conversion code
I have an algorithm that performs the base conversion. The input is a string and two ints b1 and b2. The string represents an int in base b1 and converts it into base in b2.
My code is:
...
4
votes
1answer
246 views
Min Heap Priority Queue
This was a part of one an assignment I found online and tried to solve it myself.
The objective was to implement a Priority Queue using Min Heap and use Array as the underlying data structure to ...
0
votes
1answer
247 views
Reverse String in Java
I've been revamping on my coding puzzles practices. What is the complexity (both time and space) for this method?
...
4
votes
3answers
122 views
Find the first missing positive integer in an array of integers
The problem is the one explained in Given an unsorted integer array, find the first missing positive integer
Given an unsorted integer array, find the first missing positive
integer.
For ...
3
votes
1answer
294 views
LinkedList Swift Implementation
Linked List Implementation in Swift
Swift 5.0, Xcode 10.3
I have written an implementation for a doubly linked list in Swift. As well, I decided to make the node class private and thus hidden to the ...
5
votes
2answers
243 views
LeetCode: Linked List Cycle
Challenge
https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/773/
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the ...
-2
votes
1answer
60 views
Challenge - Construct binary tree from array [closed]
A coding challenge to construct a binary tree from an array.
...
12
votes
1answer
1k views
Seating Students (partitioning sort of)
The goal of this code is to seat students in a classroom based on a
single test score. We want students to be evenly distributed across
the class such that every student is positioned next to the ...
2
votes
3answers
136 views
Modeling, view and projection transformation using vector and point in homogenous form
I know this is horrible code. This program is for performing modeling, view and projection transformation.
The program reads input from scene.txt and outputs the <...
2
votes
1answer
61 views
Find the number of all specific substrings in a string
I would like to ask a code review regarding a concrete exercise. Let's suppose I have to get the number of all specific substrings in a string.
We call something specific if any of these conditions ...
2
votes
1answer
112 views
Kruskal MST algorithm
I came up with the following code by following Prof. Sedgewick's lecture on Coursera.
Please review this code and let me know if there is anything that I got wrong in implementing Kruskal's ...
4
votes
2answers
5k views
Check if a string is a permutation of a palindrome using Python
This is a solution to exercise 1.4 from Cracking the Coding Interview written using Python 3.
Given a string, write a function to check if it is a permutation of a palindrome.
Example: 'Tact Coa'
...
3
votes
1answer
193 views
LeetCode: Best Time to Buy and Sell Stock II
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
Please review for performance.
Say you have an array for which the i-th element is the price of a
given stock on day i.
...
1
vote
1answer
437 views
Rotate matrix clockWise and counter clockWise
This code is a mix of the same question one time rotating to the right and one time to the left.
I tried to simplify the code since I'm struggling with all of the indexing here.
https://leetcode.com/...
3
votes
1answer
87 views
Coding Challenge: Return The Smaller String
A coding challenge in which we are to write a function that compares two strings and returns the one that is smaller. The comparison is both lexicographical and numerical, depending on the content of ...
2
votes
0answers
415 views
Frog Jump time complexity
I have tried to work out the Frog Jump task on Codility. The algorithm for solving this is rather simple but the maximum score I am able to achieve is 55% (also 44% with modulus operations).
A ...
1
vote
2answers
152 views
Checking whether two lists contain the same elements
I have two lists of numbers:
$$\{i_1, i_2, i_3,i_4\}$$ and $$\{j_1,j_2,j_3,j_4\}$$
The problem I want to solve is: Inside a loop, if the following two conditions are satisfied, then it will do ...
8
votes
1answer
864 views
Regular Expression Evaluator
Task to be accomplished:
Write a function that takes two strings s and p as arguments and returns a boolean denoting whether s matches p.
p is a sequence of any number of the following:
a-z - ...
4
votes
5answers
182 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)\$...
