time-complexity Questions
2
Solved
f (int n){
if (n<=0){
return 1;
}
return f(n-1) + f(n-1);
}
Suppose we did f(4). My thought was that it would be O(2^n), since then in order to find f(n-1) + f(n-1) we would have to push f...
Sumbawa asked 8/11, 2015 at 2:51
4
Solved
I came across an interview question that went like this:
There are factories in an area which produce a pollutive gas and filters are to be installed at each factory to reduce the pollution. Each ...
Guarantor asked 15/5, 2022 at 13:12
6
Solved
This is a question that I was asked in an interview:
Implement a function that gets an integer n and does the following:
1. if n is 3 -> return 7.
2. else if n is 7 -> return 3.
3. otherwise return...
Galer asked 28/11, 2018 at 15:42
1
Solved
I am looking at the following code challenge:
The “push_swap” program
You have to write a program named push_swap which will receive as an argument a stack formatted as a list of integers. The fir...
Tzar asked 4/10, 2023 at 9:45
19
Solved
I found this programming problem while looking at a job posting on SO. I thought it was pretty interesting and as a beginner Python programmer I attempted to tackle it. However I feel my solution i...
Blockus asked 9/11, 2010 at 6:43
3
Solved
In some of the projects I'm working on as part of my day job, I need to access data in very large JS objects (on the order of thousands of key-value pairs). I'm trying to improve the efficiency of ...
Microcline asked 23/7, 2017 at 15:44
6
Solved
What is the cost of len() function for Python built-ins? (list/tuple/string/dictionary)
Nonsense asked 12/7, 2009 at 4:31
3
Solved
This earlier question addresses some of the factors that might cause an algorithm to have O(log n) complexity.
What would cause an algorithm to have time complexity O(log log n)?
Papaw asked 9/5, 2013 at 22:13
10
Solved
Is there an way to zero out an array in with time complexsity O(1)? It's obvious that this can be done by for-loop, memset. But their time complexity are not O(1).
Hackler asked 29/5, 2012 at 10:25
3
Solved
I need help finding an Algorithm that is as effective as possible for checking if a given binary matrix can be reached by flipping rows and columns of a matrix with only one's.
Whenever you flip a ...
Inversion asked 27/2, 2018 at 12:11
5
I'm stuck on this problem(2 weeks). Any idea of how to approach it?.
Let L be a list of n different integer numbers, assume that the elements of x of L are in the range [1,750]. Design a linear ...
Shults asked 23/10, 2013 at 5:43
3
I have read that insert operation in a set takes only log(n) time. How is that possible?
To insert, first we have find the location in the sorted array where the new element must sit. Using binary...
Fraxinella asked 8/10, 2012 at 6:37
5
Solved
I'm trying to solve this hackerrank problem https://www.hackerrank.com/challenges/xor-subsequence/problem
from functools import reduce
def xor_sum(arr):
return reduce(lambda x,y: x^y, arr)
def ...
Incomparable asked 21/7, 2022 at 11:58
2
Solved
Which is more expensive operation swap or comparison in integer array in Java ? Or they can all be thought as same ?
Context: Sorting for an almost sorted array (I am not talking about k-sorted a...
Pappy asked 11/1, 2015 at 12:44
5
Solved
There are many problems that can be solved using Dynamic programming e.g. Longest increasing subsequence. This problem can be solved by using 2 approaches
Memoization (Top Down) - Using recursion...
Tantalic asked 20/8, 2012 at 17:40
44
This question was asked in the Google programming interview. I thought of two approaches for the same:
Find all the subsequences of length. While doing so compute the sum and of the two elements ...
Naturalism asked 12/7, 2018 at 8:6
25
I have the following problem to test:
Rotate an array of n elements to the right by k steps.
For instance, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to
[5,6,7,1,2,3,4]. How many d...
Cocotte asked 2/7, 2015 at 2:47
62
Solved
What is the most concise and efficient way to find out if a JavaScript array contains a value?
This is the only way I know to do it:
function contains(a, obj) {
for (var i = 0; i < a.length; i+...
Overslaugh asked 25/10, 2008 at 22:14
17
Solved
Is there any algorithm to compute the nth fibonacci number in sub linear time?
Brose asked 6/10, 2009 at 13:16
7
Solved
The last week I stumbled over this paper where the authors mention on the second page:
Note that this yields a linear running time for integer edge weights.
The same on the third page:
This...
Burgrave asked 28/2, 2010 at 19:27
3
Solved
In the problem , I parse the input (integer) and simultaneously check if it exists in the data structure , if not then add it.
Input is - 2 integers separated by space of size >=1 and <= 100000...
Slung asked 10/7, 2015 at 2:56
34
Solved
Project Euler and other coding contests often have a maximum time to run or people boast of how fast their particular solution runs. With Python, sometimes the approaches are somewhat kludgey - i.e...
Hiccup asked 24/2, 2009 at 16:1
7
What is the difference between time complexity and running time? Are they the same?
Czarra asked 6/2, 2011 at 20:21
8
Solved
Given this sort algorithm how do you express its time complexity?
Originally presented here (partial archive).
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &...
Meditate asked 24/6, 2011 at 22:14
1
The "simple/naive backtracking brute force algorithm", "Straightforward Depth-First Search" for sudoku is commonly known and implemented.
and no different implementation seems ...
Fearfully asked 10/7, 2014 at 16:41
© 2022 - 2024 — McMap. All rights reserved.