Find the equilibrium position of an array

Problem:
write a code to find the equilibrium position of the array.

given an array: 3,-3,8,6,-1,-5

equilibrium position should be 2(element 8) sum of lower index(3+-3)=sum of higher index(6+(-1)+(-5))

Solution:
For any index i, if we know the sum of items 0..i, we can find the sum of items i+1..n-1 by subtracting it from the sum of all elements. So:
1. Find the total sum of the array
2. For each element in the array
2.a. keep contSum, which is the sum up to the point in the array
2.b. if the (sum - A[i] - contSum) == contSum, return index (This is the point where the leftSum and the rightSum equals)
3. Return -1 if not found

public static int equilibriumIndex(int[] A) {
 int sum = 0;
 int i = 0;
 for (i = 0; i < A.length; i++) 
  sum += A[i];
  
 int contSum = 0;
 for (i = 0; i < A.length; i++) {
  if ( (sum - A[i] - contSum) == contSum) return i;
   
  contSum += A[i];
 }
  
 return -1; // not found
}

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=23088665

Find a missing number

Problem:
Given you an array of 100 Elements with one number missing, how will you find the missing number?

Ex.: Array 1 to 100 with 55 missing.

Solution:
Just do sum of all the numbers from 1 to 100 : (n * (n+1))/2 and find sum of all the elements from actual array. Just take the difference and you will get missing number.
If numbers start with n > 1, then normalize them by subtracting n-1.

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=23092662
See also: Find two missing numbers

Calculate (x^y)%z without pow()

Problem:
Calculate (x^y)%z without pow().

Solution:
The question here is how we can reduce the complexity... if we compute the x^y by normal method the complexity is O(y)... to reduce the complexity we can use binary weighted power computation method in which complexity is O(logy)..

ans=1;
square=x;
if(y==0)
    return 1;
while(y!=0)
{
    if(y%2)
        ans=ans*square;
    square=(square*square)%z;
    y=y/2;
    if(ans>z)
        ans=ans%z;
}
return ans;

Complexity:

time - O(log n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=22767685

Find tree height

Problem:
A tree, (NOT NECESSARILY BINARY), has nodes numbered 0 to N-1. An array has indices ranging from 0 to N-1. The indices denote the node ids and values denote the ids of parents. A value of -1 at some index k denotes that node with id k is the root. For ex:

3 3 3 -1 2
0 1 2 3 4

In the above, nodes with ids 0, 1 & 2 have 3 as parent. 3 is the root as its parent = -1 and 2 is the parent of node id 4.

Given such an array, find the height of the tree.

Solution:
A straightforward approach is to find the root, then find all its children, etc. (i.e. perform a BFS), and find out the maximum depth. This is a O(n^2) solution, although it requires only O(1) memory.

Using dynamic programming we can do this in O(n) time using O(n) memory:

public int countDepth(int[] tree) {
    int[] height = new int[tree.length];
    for (int i = 0; i < tree.length; i++)
        height[i] = -1;
    int maxHeight = -1;
    for (int i = 0; i < tree.length; i++) {
        if (height[i] == -1)
            maxHeight = max(maxHeight, findHeight(i, height, tree));
    }
    return maxElement(height);
}

private int findHeight(int i, int[] height, int[] tree) {
    if (height[i] != -1)
        return height[i];
    if (tree[i] == -1) {
        height[i] = 0;
    else
        height[i] = 1 + findHeight(tree[i], height, tree);
    return height[i];
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=22809662

Generate integer from 1 to 7 with equal probability

Problem:
Given a function foo() that returns integers from 1 to 5 with equal probability, write a function that returns integers from 1 to 7 with equal probability using foo() only. Minimize the number of calls to foo() method. Also, use of any other library function is not allowed and no floating point arithmetic allowed.

Solution:
If we somehow generate integers from 1 to a-multiple-of-7 (like 7, 14, 21, …) with equal probability, we can use modulo division by 7 followed by adding 1 to get the numbers from 1 to 7 with equal probability.

Consider

5*foo() + foo() - 5

This expression generates numbers 1..25 with equal probability. Now, if we only accept numbers 1..21 and return i%7+1, then we get numbers 1..7 with equal probability. If the above expression returns a number >= 22, then ignore it and run the procedure once again until a proper number is returned.

int my_rand() // returns 1 to 7 with equal probability
{
    int i;
    i = 5*foo() + foo() - 5;
    if (i < 22)
        return i%7 + 1;
    return my_rand();
}

Complexity:

time - O(1), but really unpredictable, depends on the behavior of foo()
space - O(1)

Links and credits:
http://www.careercup.com/question?id=22457666
http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/
ARRAY: http://stackoverflow.com/questions/137783/expand-a-random-range-from-15-to-17

Find square root of an integer without using built in functions

Problem:
Find square root of an integer without using built in functions.

Solution:
Provided we don't know or can't recall any math: square roots of integer numbers are "sorted" in a way that the grater the number, the greater its square root is. So we can use binary search starting with the interval (0; n) and set x = (n - 0) / 2, continuing dividing the interval until we get | x*x - n | < epsilon, where the epsilon is some very small number (e.g. 0.0000000001).

Complexity:

time - O( ??? ) - I'd speculate something like O (log n / epsilon). log n comes from using the binary search, and obviously, the higher the required precision, the longer the search takes, hence the (1 / epsilon) multiplier.
space - O(1)

Links and credits:
http://www.careercup.com/question?id=6657802751705088