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.
3
votes
0answers
44 views
finding substrings within arrays - javascript
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
76 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
71 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 - ...
2
votes
1answer
113 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
110 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
69 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
90 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:
...
1
vote
1answer
128 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
92 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
50 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
90 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
83 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
192 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
131 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
2answers
249 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
156 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 ...
4
votes
1answer
165 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
790 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
74 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
96 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
267 views
0
votes
0answers
45 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
106 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
85 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
551 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
305 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
98 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
61 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
90 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
158 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 ...
3
votes
1answer
91 views
Finding the maximum distance from the starting node
I've tried everything to make my program faster but with 250 nodes my code takes around 9 seconds to print the result, and with 5000 nodes it took around 260 seconds.
Is there a way to make my ...
3
votes
1answer
41 views
Creating List of String elements that occur a certain amount of times using only the List ADT
I am tasked with creating a list with no duplicates of all String elements, in this case first names, of an ArrayList. The method is passed a threshold, and the ...
3
votes
2answers
52 views
Given a set of random strings, write a function that returns a set that groups all the anagrams together in objective-c
I would like to get feedback on the solution and a question regarding Big O.
I am first converting each character in the string into the array and that would be O(n) then i am sorting the array O(n ...
6
votes
6answers
568 views
Find maximum difference between values in an array
My task is to use the following pseudocode and improve it (make it run faster). Also I have to analyze the runtime of the given pseudocode and of my new code that i improved.
What does this algorithm ...
1
vote
2answers
94 views
Summing all keys in the leaves of a tree
My program takes 35 sec to run example 2. How can I make my program faster?
...
-5
votes
1answer
81 views
Reverse a string [closed]
I use this for reversing a string, but it has O(n) :
reverse(y.begin(),y.end());
How can I reverse a string in O(n/2) ?
4
votes
1answer
84 views
Local variable lookup table
I'm currently in the process of writing my own programming language and the Virtual Machine for the language is responsible for handing all of the local variable scopes.
I need to support the ...
2
votes
2answers
2k views
JavaScript function to convert decimal number to binary
I was recently asked this in an interview for a front-end position and I came up with something like this which seems to work but is clunky. (Number.toString() was ...
1
vote
1answer
55 views
Return Object[] while connecting to DB once
I have written this code according to my requirements. But after finishing the code, it looks like there are too many loops. I have reduced it as much as I can. Can you find any improvements that I ...
3
votes
0answers
100 views
ACM-ICPC HackerRank challenge in C++
I was doing a programming question in C++ at HackerRank. Given a set of up to 500 bitstrings, each up to 500 bits long, the task is to find the pair a and b such that the bitwise OR contains the most ...
3
votes
1answer
48 views
Sum to zero of all triples in a list - n^2 running time
As part of an interview, I had to submit a code sample to solve the classical "triples sum to 0" problem. The reviewer said the algorithm needed to be in n2 time, and I was later informed that the ...
4
votes
1answer
296 views
Find given number by summing up integers from 2 sorted arrays
I am working on an algorithm question in which I need to find out pair of number out of 2 sorted arrays which sum up to the given number. I need to print out the indexes of those pairs rather than ...
4
votes
2answers
503 views
Sort a stack of numbers in ascending order only using push
I have a stack of numbers ranging from 1 to 1 million representing a pile of numbered DVDs. Given the stack in random order I am to sort the stack by only taking an element from the stack and push it ...
2
votes
1answer
734 views
Finding the sum closest to a target number
Wallace the Weightlifting Walrus is training for a contest where it will have to lift 1000 kg. Wallace has some weight plates lying around, possibly of different weights, and its goal is to add some ...
3
votes
2answers
225 views
Sorting a Stack in ascending order
Here's my implementation of sorting a stack in ascending order. The problem statement is as follows :
Write a program to sort a stack in ascending order (with biggest items on top).
You may use ...
4
votes
1answer
66 views
Worst case runtime analysis of a string partitioning algorithm
Give all the partitionings of a string s such that every substring of the partition is a
palindrome
What is the time complexity of this solution? And, how can I improve my code overall?
...
2
votes
0answers
42 views
Byzantine payment processing code
I've been working on a large Ruby on Rails application for several years. We inherited it and refactored and upgraded it, but there are some sections that have not been touched in at least 5 years (...
4
votes
2answers
131 views
Does my Linklist implementation have memory leaks?
Are there any memory leaks in this linklist implementation.Also is the implementation correct?Can the time complexity be optimized?
...
2
votes
2answers
215 views
Improving the time complexity of my back pack algorithm
Is there anyone who can help me improve the time complexity of this backpack algorithm, for which I already use sliding array to improve the space complexity.
The problem is as follows:
Given <...
1
vote
3answers
178 views
Simple 1-dimensional labyrinth
I am training a colleague who is familiar with Python but has a limited knowledge of C# and complexity. I thought the following problem could be a good start.
You are in a desert, there is a (...
