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.
0
votes
0answers
7 views
Time Complexity Analysis,Linear Sliding Window Algorithm Fails in SPOJ Aliens in a Train?
I need to find the largest interval with Value Less than a Limit Lt.
The Data is as Follows
For Every Test Case T
Number of elements N , limit Lt
N number of elements data
I wrote the ...
2
votes
3answers
124 views
Long arithmetic addition in JS
The implementation of the algorithm which adds two number in string form with arithmetic rules.
...
3
votes
1answer
38 views
Finding all backedges in an undirected graph
I have tried to implement the DFS algorithm to find all the back-edges in a graph that lead to a cycle in the graph:
...
3
votes
1answer
74 views
Count Acute, Right and Obtuse triangles from n side lengths
EDIT : The Code after changes suggested by @vnp. CODE
Problem Statement: We have N sticks. The size of the ith stick is Ai. We want to know the number of different types of triangles created with ...
1
vote
1answer
39 views
Printing a singly linked list with time complexity O(n) and space complexity O(sqrt(n)) [closed]
My aim is to write a method which prints contents of a singly linked list in reverse order with time complexity \$O(n)\$ and space complexity \$O(\sqrt{n})\$. The best I could come up with is to store ...
2
votes
2answers
47 views
Count number of matching nodes in a Binary tree
Problem
Count the number of matching nodes in the subtree rooted at some node n.
Solution
...
1
vote
2answers
109 views
Determining if two strings are anagrams
Two strings are said to be anagrams of each other if the letters of
one string may be rearranged to make the other string. For example,
the words 'elvis' and 'lives' are anagrams.
In this ...
1
vote
1answer
57 views
Check if a Binary Tree is full
Problem statement
Given a node check whether the sub-tree rooted at given node is full binary tree or not.
Definition
A full binary tree (sometimes proper binary tree or 2-tree) is a tree in ...
4
votes
1answer
64 views
Knights Tour — Something I am doing wrong
I have an assignment to write a knights tour backtracking program in Java where the professor says to:
Eliminate backtracking time by:
...
4
votes
1answer
103 views
How to tweak Tape Equilibrium assignment on Codility to be of complexity O(N)?
Why Codility detects my solution for Tape Equilibrium to have complexity of \$O(n^2)\$. How can I make my code better?
...
6
votes
1answer
106 views
Monitoring the recursive growth of a zombie rabbit population
Breeding like rabbits
Write a function answer(str_S) which, given the base-10 string
representation of an integer \$S\$, returns the largest n such that ...
4
votes
1answer
77 views
SQL Permission Handling in WinForms
For my application, I've opted to use Integrated Security with Windows Authentication to access the SQL database. I've created AD security groups for each role and given them ...
1
vote
1answer
51 views
Calculate trapped “rain water” in structure [closed]
Supposed my input is [1, 4, 2, 5, 1, 2, 3] . Then we can create a
structure like this:
...
7
votes
3answers
163 views
Finding the shortest excerpt that contains all search terms
Write a function called answer(document, searchTerms) which
returns the shortest snippet of the document, containing all of the
given search terms. The ...
1
vote
2answers
97 views
Finding number of number pairs with given difference [closed]
pairs() is a function which returns the total number of combinations whose difference is k.
...
5
votes
4answers
398 views
Finding the most common character in a string with a hash map
I created a method for finding the most common character in a string (using HashMap):
...
0
votes
1answer
45 views
Summing sub arrays (maximal subarray)
I have this piece of code, and I want to make if the way I'm calculating the time complexity is valid:
...
6
votes
1answer
251 views
Finding the count of negative sub-arrays for a given array
I want to improve my implementation for the following problem:
You are given an array of n integers. A sub-array is "Negative" if sum of all the integers in ...
2
votes
1answer
64 views
Counting occurrences of sorted elements [closed]
Forgive the hard coded test data - but I'm looking to make the inner while loop disappear, or at least simplified so this code doesn't run in \$O(n^2)\$. I've been thinking over some ideas of how to ...
4
votes
2answers
129 views
Google's Python exercise about lists very different from the given solution
Disclaimer: Although I do believe that this is somewhat a code review, I'm not sure if this kind of question applies to the site; if not, please let me know and I'll delete it promptly.
I found ...
3
votes
1answer
54 views
Prim's minimal spanning algorithm
Is there a way to speed up this code so it is \$O(n^2)\$ instead of \$O(n^3)\$? I'd appreciate if someone showed me how to do so.
...
8
votes
2answers
483 views
Solving 'decent numbers' that follow specific division rules
HackerRank Problem Statement
I have to find the largest 'decent number' having N digits. A decent number has the following properties:
3, 5, or both as its ...
5
votes
4answers
310 views
Sufficient implementation of subset sum for 45 min interview
I am preparing for interviews, and have implemented a solution to this problem from Geeks for Geeks:
Given a set of non-negative integers, and a value sum, determine if there is a subset of the ...
5
votes
2answers
376 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 ...
0
votes
2answers
94 views
Big O notation for quicksort implementation [closed]
I am trying to find out what would be the Big O notation of a quick sort implementation I wrote. If I can get some analysis on the code, that would be great.
...
10
votes
2answers
248 views
Minimum sub-array challenge
Below is my solution to finding the minimum product sub-interval. It passed 8/12 or so test cases, but the other test cases timed out if they hadn't finished within 2 seconds. When I compile this code ...
2
votes
3answers
100 views
Intersection of subset between two lists of dicts
I want to find the intersection of two lists of dicts.
Note that equality—i.e.: what is to appear in the intersection—is given by which keys they must have equal. See the ...
3
votes
1answer
123 views
Number of paths in a grid (lattice) graph
I am trying to solve a variant of the very popular question in which we find the number of distinct valid paths on a directed graph. The graph's nodes make up a m x n lattice (grid), and the edges ...
4
votes
2answers
134 views
Extracting and analyzing data from SAP
I developed a script for the company I work for in order to extract data from SAP (CJ74) and analyze the data.
One particular issue I am finding is that for any data sets which have over 1000 lines, ...
3
votes
2answers
90 views
Given bit strings, perform a bitwise addition
I'm looking for code-review, optimizations and best practices. This code is a Java adaptation of code on geeksforgeeks.org. Please verify if space complexity is \$O(n)\$ where n is number of bits, and ...
4
votes
1answer
306 views
Finding whether there exists a pair of numbers in a set having a given product
Devise an algorithm that will operate on a number x and a set of n
distinct numbers such that in \$O(n \lg n)\$ time, the algorithm indicates
whether or not there are two numbers in the set ...
2
votes
2answers
107 views
Improving the efficiency of my FizzBuzz algorithm [closed]
I worked on an exercise from codewars, which is a variation of the popular fizzbuzz game. (If the link doesn't work, you may need to reload the page.)
In this variation, I'm supposed to find the sum ...
3
votes
1answer
54 views
Spending a target sum, preferably split equally
I have a strange programming prompt. I managed to complete an algorithm to solve smaller test entries (which i'll post). One of my test cases has to complete a 200,000 int input and my algorithm isn't ...
3
votes
1answer
53 views
Acquiring indices for anagrams of an input string
I am working on an interview question from Amazon Software:
Design an algorithm to take a list of strings as well as a single input string, and return the indices of the list which are anagrams of ...
6
votes
2answers
286 views
Finding pairs of numbers within A that add up to N
I am working on an interview question from Amazon Software Interview:
Given an integer N and an array of unsorted integers A find all pairs of numbers within A which add up to N
I have a working ...
1
vote
4answers
71 views
Finding the second largest element of large input sets
I have a problem where I need to find the second maximum element of the user inputs. It's an online practice problem and I can't figure out why the server responds back with a Non-Zero Exit Code error ...
6
votes
2answers
449 views
Sum the exponents of the prime factors of a number
My goal is to find the sum of the exponents of the prime factors of an integer.
I wrote the code below with the complexities specified here (I am not 100% sure of the complexities though):
Runtime ...
4
votes
2answers
444 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 an."
Here is my recursive solution to this problem (in Java):
...
3
votes
3answers
680 views
Find the index of the element with maximum absolute deviation
I just completed a Codility test. The question presented was pretty simple but I may have over thought it.
Question:
Find the element which has the highest absolute deviation from the mean. E.g. ...
0
votes
2answers
168 views
Uva Online Judge problem 100, 3n + 1
I am having a tough time submitting this code to UVa Online judge and having it pass. I keep getting the message - Your program used more CPU time than what is allowed for this problem. That means ...
0
votes
3answers
480 views
Finding all integers in an array with odd occurrence
I am doing an interview exercise problem from here.
The problem is to find "all numbers that occurred an odd-number of times in an array".
Here is my high level psuedo code thinking:
Construct a ...
6
votes
3answers
517 views
A partition algorithm for positive integers
I have encountered the following problem that I found very interesting to solve:
Given an array of positive integers {a1, a2, ..., an} you are required
to partition the array into 3 ...
3
votes
2answers
235 views
Removing duplicates from an array
I recently wrote this JavaScript algorithm for removing duplicates from an array as part of a job interview process, but was turned down for the position after submitting the code. I didn't receive ...
3
votes
1answer
38 views
Integrate the product of four infinite series functions
I wrote the following code to integrate the product of four functions.
Two of the functions are hypergeometric functions and the other two are incomplete gamma functions. I have written each function ...
3
votes
3answers
213 views
Determining if a pair exists in a large sorted array
I'm doing practice interview questions from here. Here is the one I am currently on - if you are given a very large sorted int array, then check of there exists a ...
1
vote
0answers
325 views
DP algorithm to find minimum average wait for customer-serving system
Below is the code to find the minimum average waiting time for customers at a store. I want improve the time complexity of the code. As an overview of the logic, I start from ...
3
votes
1answer
79 views
Extracting length-3 subsequences from a list
For a list li, I want to print only the values of the triplets a, b, c where ...
3
votes
3answers
428 views
Find intersection of two arrays without duplicates
A = [9, 1, 4, 2, 5] k unique integers
B = [3, 1, 8, 7, 6, 5] n unique integers
Intersection => [1, 5]
Find an algorithm that uses \$O(1)\$ space (the space used by the return variable is not ...
3
votes
1answer
106 views
Google Code jam puzzle - Welcome to Code Jam
The problem is to count all possible sub-sequences of "welcome to code jam" in a given input string (and only return the last 4 digits of the count). Here is the link to the problem for reference.
...
-1
votes
1answer
202 views
Finding the distance from each array element to the nearest zero entry
I wrote a program, that gets a certain array and replaces each value in the array with the distance from it to the closest zero value.
Time complexity is 4n => O(n). (please correct me if I'm wrong, ...
