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.
5
votes
2answers
93 views
JavaScript function for finding perfect numbers
The following function has been created for finding "Perfect Numbers".
About Perfect Numbers: Wikipedia
...
-1
votes
0answers
14 views
Really don't know how to calculate time complexity of below code [closed]
below is my brute force way to implement "longest common substring"
...
1
vote
1answer
55 views
Random permutation with defined order of last occurrences
This Python function takes two arguments:
chr_list which is a mutable sequence of characters c
...
0
votes
0answers
58 views
Parsing URL query strings in AngularJS
Here are two very small blocks of code I wrote while trying to fix a bug in AngularJS. Both do the same thing. I'm trying to understand how the two differ, mainly in terms of the tradeoff between cpu ...
0
votes
0answers
44 views
One-off string detection
Problem spec from CareerCup.
Given two strings, return boolean True/False if they are only one edit apart. Edit can be insert/delete/update of only one character in the string. Eg.
True
xyz,xz
xyz,...
2
votes
2answers
42 views
High execution time on number partitioning program in Python 2.7
I am writing a program to count only the partitions of a number with distinct parts.
I am using a bottom-up approach to dynamic programming to generate partition lists from previously obtained ...
7
votes
1answer
42 views
Check consistency of a list of statements, with fuzzy rhyme matching
I made a program today that solves the following problem on a programming competition site (open.kattis.com): Check if all statements with the following format X is Y or X not Y are consistent. X and ...
5
votes
1answer
109 views
Check for valid parentheses nesting
I found this question on leetcode and that was my answer ... But someone told me it's too bad that it takes \$O(n^3)\$ I am not sure that it takes all that time ... and trying to find better ...
6
votes
0answers
91 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 ...
4
votes
2answers
32 views
Split DAG into disjoint sets
I wrote an algorithm to separate a DAG into disjoint sets of vertices. I was hoping to have some comments on algorithmic complexity and efficiency of the Python code. Notably, I don't like the adding ...
4
votes
4answers
703 views
Find element that has been removed from a shuffled array
For a function to determine which element has been removed from a shuffled array, I came up with:
...
1
vote
1answer
69 views
MaxCounters solution
I am doing this Codility problem
You are given N counters, initially set to 0, and you have two possible operations on them:
increase(X) − counter X is increased by 1,
max counter − all ...
1
vote
1answer
41 views
Finding the distance between every indices in an array that contain odd numbers
I'm doing this HackerRank problem which basically boils down to what I've written in the title. We have to find out the distance between all the odd values in the array. I've written this code below ...
4
votes
1answer
85 views
Lexicographically smallest wave like array without sorting
Given an array of integers, sort the array into a wave like array and return it. In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5.....
Example:
Given [...
3
votes
1answer
58 views
Taxicab numbers algorithm check
With the programming language skills that are available to me at the time, I've written this program to find the "taxicab numbers" (e.g. a number
expressible as the sum of two cubes in two different ...
13
votes
7answers
430 views
Finding the most popular element with C# given O(1) space complexity requirement
I have tried to solve the following problem in C# with LINQ:
Given an integer array, find the most frequent number and it's count in the array. If multiple numbers have the same highest frequency ...
3
votes
1answer
54 views
Dividing a ThreadPool class into component classes to reduce/isolate complexity
I have a ThreadPool class which has grown to a point where it is becoming difficult to keep all of this unit of work in mind. It is also becoming harder to read. ...
3
votes
1answer
187 views
Finding line numbers of duplicate lines in a log file
I have a log file with a million lines, and my task is to code something that outputs the lines that have duplicates, and the line numbers.
I've thought of two ways to approach this :
1) Use python'...
3
votes
0answers
72 views
Word Wrap via Dynamic Programming
Word Wrap problem in short:
Given n words and a line length, break the words into lines in such a manner that minimizes the sum of the costs of all the lines. Consider the cost of each line being (...
1
vote
2answers
106 views
Massive file sorting algorithm
I was trying to sort a massive file of successive chars in C. I did some research and found a few file sorting algorithms that look the same. Their main idea is to read an amount of data to memory, ...
3
votes
1answer
78 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
votes
1answer
83 views
Complexities: Filtering out nested array inside an array
I am doing some iteration over an array which have another set of array (the nested array). I need to .map() the outer array in such a way that it should filter out ...
2
votes
1answer
168 views
Find the longest subarray with sum less than K
The problem consist of finding the longest contiguous subarray with a sum less than a given integer K.
The input data are:
K - ...
3
votes
1answer
2k 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];.
...
3
votes
1answer
125 views
Calculating binary tree height as asked in the interview
Input:
The first line contains the number of vertices \$n\$. The second line
contains \$n\$ integer numbers from the range \$\left[−1, n − 1\right]\$ representing the \$0\$-based index of the ...
0
votes
0answers
105 views
All combination of character alphabet
I write this code to find all combination of an alphabet z={A,B,C...N}.
In DNA case,we use z={A,C,T,G},then the function Words and ...
0
votes
1answer
121 views
Subset sum simple iterative implementation
Here is the simplest iterative implementation of Subset sum problem that I could come up with1, as a follow up to this recursive implementation of the same problem:
...
2
votes
1answer
309 views
HackerRank: Left Array Rotation in Python
Here is the problem on HackerRank. I want to know how I can improve this code. I am mainly trying to improve the following skills: Documentation, functional programming (top-down approach), accurately ...
4
votes
1answer
107 views
Modified Z-Algorithm for string similarity with one char difference
I have modified a Z-Algorithm for string similarity in order to match strings which differ in 0 or 1 char.
However, it seems much slower than original Z-Algorithm although from my point of view there ...
3
votes
1answer
61 views
Infinite Monkey Theorem Python Comparison
I wrote code to demonstrate the Infinite Monkey Theorem which states that if a monkey types at a keyboard for an infinite amount of time it will almost surely type a given text such as William ...
2
votes
2answers
147 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 ...
3
votes
1answer
241 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 ...
1
vote
2answers
911 views
Simple string compression in Python
This is my solution to exercise 1.6 in Cracking the Coding Interview. I am interested in receiving feedback on the coding style and time/space complexity.
The exercise statement is:
Implement a ...
4
votes
2answers
231 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 ...
4
votes
2answers
650 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
3answers
174 views
URLIfy a character array using Python - follow-up
This is a follow up to my last code review:
URLify a string using Python
This problem has been reviewed in other languages, but I tried to solve this without looking at those answers.
I am hoping ...
6
votes
2answers
438 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 ...
5
votes
2answers
925 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 length ...
1
vote
1answer
76 views
Stack which finds the minimum element
Write a program to implement stack which implements min a method
which gives the minimum element below the top element in the stack.
...
2
votes
1answer
123 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 ...
1
vote
1answer
292 views
0
votes
0answers
57 views
Suffix tree code
I am always having confusion when it comes to run time complexity of an algorithm. I wrote this code for suffix array, I am not sure of the run time complexity of ...
2
votes
1answer
207 views
Iterative solution for generating all permutations of a string
I know the runtime for generating all permutations is supposed to be \$O(n!)\$. I'm not sure if the code I wrote for it runs in \$O(n!)\$ though. I'm having trouble analyzing its runtime.
The ...
5
votes
2answers
90 views
Function to check truth value of a specific statement
I want to check the truth of A + B - (A & B) == A | B for N-bit numbers. For example, here's a "truth" table for 2-bit numbers. (I know I'm taking liberty with ...
7
votes
3answers
778 views
Algorithm to compute the n-th derivative of a polynomial in Python
As a personal exercise, I'm trying to write an algorithm to compute the n-th derivative of an ordered, simplified polynomial (i.e., all like terms have been combined). The polynomial is passed as an ...
11
votes
3answers
339 views
Finding Pythagorean triplet in array
We have an integer array as:
private int[] arr = {1, 3, 5, 14, 18, 29, 78};
We have a function which takes three inputs of the array and checks whether:
...
3
votes
2answers
132 views
TopCoder problem “Substitute” - SRM 160 (Division II Level One)
I have solved the problem "Substitute" at Topcoder.
A simple, easy to remember system for encoding integer amounts can be very useful. For example, dealers at flea markets put the information about ...
2
votes
0answers
64 views
Improving time efficiency of finding maximum area rectangles in a histogram
Here's my solution but I am looking for ways to improve the time complexity of solution. Also this question is categorized as being solved by stack so I would like to know how to approach it using ...
3
votes
1answer
129 views
Faster palindrome checker in Java
I wonder if there could be a faster palindrome checker in Java. The best one I have is O(n/2) which is O(n) eventually:
...
10
votes
2answers
175 views
Min sub array size with a given sum
How can the time complexity of the following code be improved (assuming it's \$O(N^2)\$)? What about style and patterns?
This code is trying to find the minimum subarray size that adds up to given sum ...
