All Questions
40 questions
6
votes
4
answers
483
views
Traversal Heap Sort (No Extractions)
I developed a heap sort variant that sorts a heap through traversal. Unlike in the standard heap sort, the algorithm does not remove the min element from the heap instead it traverses all the nodes of ...
7
votes
1
answer
257
views
Colorful Subgraph Dynamic Programming Solution and a Naive One
Given a graph \$G(V, E)\$ with vertices \$V\$ and edges \$E\$, where each vertex is associated with a single color from a set of colors \$C=\{1, 2, ..., k\}\$, we define the following problem:
Problem ...
3
votes
1
answer
266
views
Find the largest decrease in a sequence of numbers
I have written a function that takes as input a list of 5 numbers, then the program's goal is to return the largest drop in the list. It is important to understand that [5, 3, ...] is a decrease of 2 ...
1
vote
3
answers
222
views
Finding unique top sums from multiple lists
My question arises from this post on MSE where I have provided an answer to solve the question :
There are multiple lists given. The number of lists is arbitrary.
Each list contains numbers and is ...
- 121
1
vote
1
answer
47
views
What is the optimal way to retrieve a list of sorted dates in a list of sorted periods in python?
Suppose I have a list with N sorted dates and M non-overlapping sorted periods with start date, end date (inclusive), and a tax rate for example. I have to make an efficient algorithm retrieve all tax ...
- 113
11
votes
5
answers
2k
views
Are the sum of two numbers desired?
Given two input arrays [-1, 8, 3] and [3, 7, 2] your function will return true if any two of the numbers in the first array add ...
- 383
3
votes
0
answers
295
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, ...
- 31
5
votes
2
answers
313
views
2
votes
1
answer
72
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 ...
- 3,592
2
votes
1
answer
80
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 conventions ...
- 3,592
4
votes
1
answer
212
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 ...
- 141
7
votes
1
answer
332
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 ...
- 133
4
votes
2
answers
451
views
Compare Strings
You have been given two strings, A and B (of length N each) and Q
queries. The strings contain only 0s and/or 1s.
For every query, you are given an index i. You have to update the
value at ...
- 676
1
vote
1
answer
90
views
Algorithmic complexity of this algorithm to find all ordered permutations of length X
I have written a recursive function to generate the list of all ordered permutations of length X for a list of chars.
For instance: ['a', 'b', 'c', 'd'] with X=2 will give [['a', 'a'], ['a', 'b'], ['...
user168305
3
votes
0
answers
671
views
Finding the majority element in a sequence of integers in \$O(n \log n)\$
I wrote this piece of code as solution to a problem set that required finding the majority element in a list using divide and conquer in \$ O(n \log n)\$. The majority element is defined as the ...
- 201