Problem Detail: I was researching dynamic programming and read the following: Often when using a more naive method, many of the subproblems are generated and solved many times. What is a naive method? Asked By : chopper draw lion4 Answered By : usul Read More …
Blog
Matrix powering in $O(log n)$ time?
Problem Detail: Is there an algorithm to raise a matrix to the $n$th power in $O(log n)$ time? I have been searching online, but have been unsuccessful thus far. Asked By : Jack Hunt Answered By : Massimo Cafaro Here is the pseudocode Read More …
Is 0* decidable?
Problem Detail: I found a statement (without explanation) that a language $A = 0^*$ is decidable. How is that possible? I mean, how would we build a Turing machine that would accept (or reject) a possibly infinite string of 0’s? I Read More …
Rearrange an array using swap with 0
Problem Detail: This is a Google interview question. I got it from a website. You have two arrays source and target, containing two permutations of the numbers [0..n-1]. You would like to rearrange source so that it equals to target. The Read More …
Who needs linearizability?
Problem Detail: I’ve been reading about the differences between serializability and linearizability, which are both consistency criteria for replicated systems such as replicated databases. However, I don’t know in which cases linearizability would be needed, even though it’s stronger than serializability. Read More …
Finding the grammar type of the programming language
Problem Detail: How can someone find what type of grammar for a given programming language? Formerly I’m looking for a grammar type for most popular programming languages: C, C++, C#, Java, List, OCaml, Haskell etc. Asked By : m0nhawk Answered By : Gilles Read More …
Finding maximum and minimum of consecutive XOR values
Problem Detail: Given an integer array (maximum size 50000), I have to find the minimum and maximum $X$ such that $X = a_p oplus a_{p+1} oplus dots oplus a_q$ for some $p$, $q$ with $p leq q$. I have tried this Read More …
k-ordered array problem
Problem Detail: An array $A[1…n]$ is said to be k-ordered if $$A[i – k] leq A[i] leq A[i + k]$$ for all $i$ such that $k < i leq n – k$. For example, the array $A = [1, 4, Read More …
What is the time complexity of the following program?
Problem Detail: Please help me calculate the time complexity of the following program. int fun (int n) { if (n <= 2) return 1; else return fun(sqrt(n)) + n; } Please explain. There were four choices given. $Theta(n^2)$ $Theta(n log n)$ Read More …
Complexity analysis of while loop with two conditions
Problem Detail: I am curious how to do a line by line analysis of this piece of code using the “Big O” notation. i = 0; j = 0; while ( ( i < n ) && ( j < m Read More …
