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.
4
votes
1answer
64 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
79 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
54 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
77 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
34 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
233 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
1answer
56 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 ...
-1
votes
2answers
87 views
Calculating whether movie times overlap
The goal of this example is to find if movies are overlaping.
What is the Big O complexity here and how can I calcualte it? Is there better way to write it simpler?
...
2
votes
1answer
173 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 ...
3
votes
2answers
82 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
54 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
38 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
122 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
206 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
108 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 ...
0
votes
0answers
11 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
137 views
Long arithmetic addition in JS
The implementation of the algorithm which adds two number in string form with arithmetic rules.
...
3
votes
1answer
50 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
103 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
52 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
77 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
132 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
80 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
67 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
146 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
164 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
114 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 ...
7
votes
3answers
207 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
120 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
946 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
50 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
518 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
66 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
225 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
61 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
3answers
1k 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
369 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
723 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
109 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
272 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
292 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
188 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
143 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
92 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
440 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
117 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
55 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
58 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
335 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
82 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 ...
