Remove every kth element (Josephus problem)

Problem:
There are n nodes in a circle and you will start removing every kth node from it until there is only one node left.

Design a datastructure which will allow above in O(n) time

Solution:
This is known as a Josephus problem. A solution is as follows: after removing kth element we end up with (n-1) elements left, and should then remove a kth element starting with the (k+1) element from the original sequence. Obviously, if we do that on the actual data structure, we'll need O(n^2) operations. So instead we should use modular arithmetic and simply find out the index of a remaining element. This can be done in O(n) time as follows:

def josephus(n, k):
   if n ==1:
     return 1
   else:
     return ((josephus(n-1,k)+k-1) % n)+1

This can also be implemented as a loop w/o recursion.
The answer to the original question is: a simple array will do.

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=20318662
http://en.wikipedia.org/wiki/Josephus_problem

Find the most frequent non-empty subarray

Problem:
Given an array of ints, find the most frequent non-empty subarray in it. If there are more than one such sub-arrays return the longest one/s.
Note: Two subarrays are equal if they contain identical elements and elements are in the same order.

For example: if input = {4,5,6,8,3,1,4,5,6,3,1}
Result: {4,5,6}

Solution:
The idea is to use a suffix array to easily identify repeated subarrays.

Suffix array is actually a 2D array. The suffix array for the given array {4,5,6,8,3,1,4,5,6,3,1} would be as below. Here, each element of the array itself is an array.

{4,5,6,8,3,1,4,5,6,3,1}
{5,6,8,3,1,4,5,6,3,1}
{6,8,3,1,4,5,6,3,1}
{8,3,1,4,5,6,3,1}
{3,1,4,5,6,3,1}
{1,4,5,6,3,1}
{4,5,6,3,1}
{5,6,3,1}
{6,3,1}
{3,1}
{1}

After sorting the suffix array, you'd get:
{8,3,1,4,5,6,3,1}
{6,8,3,1,4,5,6,3,1}
{6,3,1}
{5,6,8,3,1,4,5,6,3,1}
{5,6,3,1}
{4,5,6,8,3,1,4,5,6,3,1}
{4,5,6,3,1}
{3,1,4,5,6,3,1}
{3,1}
{1,4,5,6,3,1}
{1}

Checking for matching subarrays is easily done in a suffix array by comparing the prefixes. If you traverse the above sorted array and compare adjacent elements for similarity you'd see the prefix [4,5,6] is occurring maximum number(=2) of times and is also of maximum length. There are other subarrays as well, like [6], [5,6],[3,1] and [1] that are occurring 2 times, but they are shorter than the subarray [4,5,6], which is our required answer.

Complexity:

time - Θ(n) (to construct the suffix array)
space - O(n^2) (might probably avoid making copies of data, and only use indexes to the original array)

Links and credits:
http://www.careercup.com/question?id=20963685
http://en.wikipedia.org/wiki/Suffix_array

Given a string find the largest substring which is palindrome

Problem:
Given a string find the largest substring which is palindrome.

Solution:
Test if a substring is a palindrome starting from its potential "center":

int longestPalindromicSubstring(char* str)
{
 int len = strlen(str);
 int maxLength = 1;
 int start = 0;
 int low, high;
 
 for(int i = 1; i < len; i++)
 {
  // Find longest even length palindrome with
  // center points as i-1 and i
  low = i-1;
  high = i;
  while(low >= 0 && high < len && str[low] == str[high])
  {
   if(high - low + 1 > maxLength)
   {
    start = low;
    maxLength = high - low + 1;
   }
   low--;
   high++;
  }
  
  // Find longest odd length palindrom with
  // center point as i
  low = i-1;
  high = i+1;
  while(low >= 0 && high < len && str[low] == str[high])
  {
   if(high - low + 1 > maxLength)
   {
    start = low;
    maxLength = high - low + 1;
   }
   low--;
   high++;
  }
 }
 
 printf("Longest Palindromic Substring is: ");
 for(int i = start; i <= start + maxLength - 1; i++)
 {
  printf("%c", str[i]);
 }
 
 return maxLength;
}

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=20351666
O(n) algorithm (Manacher's Algorithm) is discussed at http://discuss.leetcode.com/questions/178/longest-palindromic-substring

Count bits in an integer

Problem:
Count the no. of 1's in an integer.

Solution:

Solution #1: The most straightforward approach is to check each bit one by one. Here is the code,

int count1(int n)
{
    int count=0;

    while(n)
    {
        if(n&1)
            count++;

        n = n>>1;
    }

    return count;
}

Solution #2: The below code is an efficient version which improves the average time.
This code is faster because on each iteration it always clears the LSB of the number.

int count2(int n)
{
    int count=0;

    while(n)
    {
        count++;
        n = n&(n-1);
    }

    return count;
}

Complexity:

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

Links and credits:
http://puddleofriddles.blogspot.ru/2012/03/count-bits-in-integer.html

Find number of coins summing up to a given sum

Problem:
Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.

Example:
Given coins with values 1, 3, and 5.
And the sum S is set to be 11.

Solution:
First of all we mark that for state 0 (sum 0) we have found a solution with a minimum number of 0 coins. We then go to sum 1. First, we mark that we haven't yet found a solution for this one (a value of Infinity would be fine). Then we see that only coin 1 is less than or equal to the current sum. Analyzing it, we see that for sum 1-V1= 0 we have a solution with 0 coins. Because we add one coin to this solution, we'll have a solution with 1 coin for sum 1. It's the only solution yet found for this sum. We write (save) it. Then we proceed to the next state - sum 2. We again see that the only coin which is less or equal to this sum is the first coin, having a value of 1. The optimal solution found for sum (2-1) = 1 is coin 1. This coin 1 plus the first coin will sum up to 2, and thus make a sum of 2 with the help of only 2 coins. This is the best and only solution for sum 2. Now we proceed to sum 3. We now have 2 coins which are to be analyzed - first and second one, having values of 1 and 3. Let's see the first one. There exists a solution for sum 2 (3 - 1) and therefore we can construct from it a solution for sum 3 by adding the first coin to it. Because the best solution for sum 2 that we found has 2 coins, the new solution for sum 3 will have 3 coins. Now let's take the second coin with value equal to 3. The sum for which this coin needs to be added to make 3 , is 0. We know that sum 0 is made up of 0 coins. Thus we can make a sum of 3 with only one coin - 3. We see that it's better than the previous found solution for sum 3 , which was composed of 3 coins. We update it and mark it as having only 1 coin. The same we do for sum 4, and get a solution of 2 coins - 1+3. And so on.

Set Min[i] equal to Infinity for all of i
Min[0]=0

For i = 1 to S
For j = 0 to N - 1
   If (Vj<=i AND Min[i-Vj]+1<Min[i])
   Then Min[i]=Min[i-Vj]+1

Output Min[S]

Complexity:

time - O(S*N)
space - O(S)

Links and credits:
http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

Modify bits x...y in an integer

Problem:
given two integers and two bit positions. Set the first integer between the two bit positions to be that of the second integer.

Solution:
The trickiest part is to calculate the mask:

int replace_bits(int a, int b, int x, int y) 
{ 
    int mask = ((1 << (y - x + 1)) - 1) << x; 
    // Clear a and replace with that of b 
    return ((a & ~mask) | (b & mask)); 
}

Complexity:

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

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

Calculate ceiling (y / x) w/o using % (modulo)

Problem:
given y bytes and you can transfer only x bytes at once..give a mathematical expression having only + - / * which gives the number of iterations to copy y bytes. ( dont try giving modulo operator answers )

Solution:

ceiling(y / x) = (y + (x - 1)) / x

In order to prove correctness you need to check two case sets:
1. y % x == 0 => addition of x-1 doesn't affect the result, so it is y/x (which is ok)
2. y % x > 0 => addition of x-1 increments result with 1 (which is ok because we need another copy for the remaining y % x bytes).

Complexity:

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

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

Print a decimal number in binary form

Problem:
Print a decimal number in binary form. eg: number=10 or 2.22 or 0.876 ....
Required to print only four number after decimal point.

Solution:
Subsequently divide the integer part by two, and then multiply the fractional part by two.

def dec2bin(number):
    ## integer part:
    int_number = int(number)
    int_bin_str = ''
    while int_number != 0:
        (int_number, remainder) = divmod(int_number, 2)
        int_bin_str = str(remainder) + int_bin_str

    ## fractional part
    frac_number = number - int(number)
    frac_bin_str = ''
    count = 0
    while( count < 4):
        frac_bin_str += str(int(2.0 * frac_number))
        frac_number  = 2*frac_number - int(2*frac_number)
        count += 1

    return int_bin_str+"."+frac_bin_str

## MAIN ##
print dec2bin(10)
print dec2bin(2.22)
print dec2bin(0.876)

Complexity:

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

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

Find subarray with given sum

Problem:
Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.

Solution:
Initialize a variable curr_sum as first element. curr_sum indicates the sum of current subarray. Start from the second element and add all elements one by one to the curr_sum. If curr_sum becomes equal to sum, then print the solution. If curr_sum exceeds the sum, then remove trailing elemnents while curr_sum is greater than sum:

int subArraySum(int arr[], int n, int sum)
{
    /* Initialize curr_sum as value of first element
       and starting point as 0 */
    int curr_sum = arr[0], start = 0, i;
 
    /* Add elements one by one to curr_sum and if the curr_sum exceeds the
       sum, then remove starting element */
    for (i = 1; i <= n; i++)
    {
        // If curr_sum exceeds the sum, then remove the starting elements
        while (curr_sum > sum && start < i-1)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }
 
        // If curr_sum becomes equal to sum, then return true
        if (curr_sum == sum)
        {
            printf ("Sum found between indexes %d and %d", start, i-1);
            return 1;
        }
 
        // Add this element to curr_sum
        if (i < n)
          curr_sum = curr_sum + arr[i];
    }
 
    // If we reach here, then no subarray
    printf("No subarray found");
    return 0;
}

Complexity:

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

Links and credits:
http://www.geeksforgeeks.org/find-subarray-with-given-sum/

Inorder Tree Traversal without recursion and without stack (Morris Traversal)

Problem:
Traverse a binary tree without using stack and recursion.

Solution:
Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.

1. Initialize current as root 
2. While current is not NULL
   If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as right child of the rightmost node in current's left subtree
      b) Go to this left child, i.e., current = current->left

void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;
 
  if(root == NULL)
     return; 
 
  current = root;
  while(current != NULL)
  {                 
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;      
    }    
    else
    {
      /* Find the inorder predecessor of current */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;
 
      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }
             
      /* Revert the changes made in if part to restore the original 
        tree i.e., fix the right child of predecssor */   
      else 
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;      
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}

Complexity:

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

Links and credits:
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
http://www.careercup.com/question?id=6154593645887488

Find the majority number in a given sequence of numbers

Problem:
Find the majority number in a given sequence of numbers (a number that occurs more than N/2 times where N is the count of numbers in the sequence). Don't maintain a map of all occurring numbers along with a count. No number may be a majority.

Example: 1 1 2 3 4 1 6 1 7 1 1
Majority number is 1 since it occurs 6 times (> 11/2)

Solution:
maintain a counter and store the current number. If next number is same increment the counter, if different then decrement counter. If counter becomes zero, then store the next number as current number and set counter to 1, like a fresh start. After itertation is done, you will be left with a current number. Traverse the array once more to check if it is really majority or not. O(n) complexity.
(Moore voting algorithm).

Complexity:

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

Links and credits:
http://www.careercup.com/question?id=5200260502650880
http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

Check if the given binary tree is BST or not

Problem:
Check if the given binary tree is BST or not.

Solution:

public boolean isBSTMain(Node root) {
 return (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}

private boolean isBST(Node node, int min, int max) {
 if (node == null)  return true;
 
 if (node.data < min || node.data > max) return false;

 // left should be in range min...node.data
 boolean leftOk = isBST(node.left, min, node.data);
 if (!leftOk) return false;

 // right should be in range node.data..max
 return isBST(node.right, node.data, max);
}

Complexity:

time - O(n)
space - O(n) (the stack space for the recursion)

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

Find all pairs summing up to a given number

Problem:
Given an integer array, find pairs in an array which sum up to a given number.
For example: Array{4,5,1,3,2} and required sum=6 then output should be [1,5] and [2,4].

Solution:
1. O(n)/O(n):
Put all items to a hashtable, and then iterate over the array once more and check if the hashtable contains (sum-a[i]). Print the pair if so.

2. O(n log n)/O(1)
Sort the array and start pointers from both ends of the array checking if the given pair add up to the given value.
- If the current pair sum equals the value of the given number print the pair.
- If the current pair sum exceeds the given number decrement the right pointer by 1
- else increment the left pointer by 1

Complexity:

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

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

Determine the average salary w/o revealing individual salaries

Problem:
There are three people and they need to know the average of their salaries without knowing each other's salary. How will you do that?

Solution:

1. Here's a simple solution. We start out assuming everyone's salary is in a certain range, say 0 - 1 trillion. The first person picks a number uniformly at random in that range and informs only the second person about this random number. Since this number is just random, it conveys no information. The second person adds their salary to the number and informs the third person about this sum. The third person receives no info from this because of the random element added in. The third person adds their salary to this running total and informs the first person about the sum. The first person knows the random number and subtracts it out, leaving the first person with the sum of the second and third person's salary. The first person could have obtained this info from the average anyway, so no extra information has been conveyed. Finally the first person adds their salary and divides by 3.

2. More secure solution: Have them pick "two" random numbers and reveal the sum of two random numbers and their salary, then sum them all up. Each developer now exchanges one of their random numbers. Now, when they subtract random numbers from the total, none of them can guess each other's salary.
Once the random numbers are subtracted, divide it by 3, which is the average salary of three developer.

The added security is to avoid the third person disclosing the sum given by the second person in the first solution. Otherwise the first person could determine the salary of the second person.

Complexity:

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

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

Check if two huge files contain the same strings

Problem:

given two very big files , each having around 1 billion lines , u have to print all the lines that are common to both files . Please suggest a good optimal approach

Solution:
Use a Bloom filter. From Wikipedia:

An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions with a uniform random distribution.
To add an element, feed it to each of the k hash functions to get k array positions. Set the bits at all these positions to 1.
To query for an element (test whether it is in the set), feed it to each of the k hash functions to get k array positions. If any of the bits at these positions are 0, the element is definitely not in the set – if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, or the bits have by chance been set to 1 during the insertion of other elements, resulting in a false positive. In a simple bloom filter, there is no way to distinguish between the two cases, but more advanced techniques can address this problem.

Complexity:

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

Links and credits:

Algorithms and Data Structures Development

(a discussion posted in this members only group on LinkedIn)
http://en.wikipedia.org/wiki/Bloom_filter

Selecting randomly from an unknown sequence

Problem:
How to choose randomly from a sequence of unknown length. The typical use is to choose a random line from a file.

Detailed description:
You are given a file (and you do not know how big the file is, nor how big the lines in the file are). Write an algorithm that will generate a random number (which will be used to index into the file) such that the output of lines will be roughly proportional? That is if the file contained 4 lines, and if I ran the program 1 million times I should get each line printed approximately 250K times.

Solution:

import random

def random_element(seq):
    """Return an element chosen at random from `seq`."""
    it = None
    for n, elem in enumerate(seq):
        if random.randint(0, n) == 0:
            it = elem
    return it

To see why this function works, consider it inductively. For the initial case, we'll always pick the first element as "it", since a random int between 0 and 0 will be 0. So after one element, we've chosen uniformly from the one element we've seen.

For the inductive case, imagine we've read N-1 elements already, and "it" is a random element chosen uniformly from those N-1 elements. The chance that the Nth element should be chosen instead is 1/N, because at this point, the chance that any particular line should be "it" is 1/N. So we choose a random number, and if it's the 1/N outcome, we take the Nth line as "it." In the case that we don't take the new line, which is (N-1)/N, the old line is kept. It was chosen randomly from the N-1 lines that preceded this one, so each line has a final chance of ((N-1)/N)/(N-1), or 1/N, or being chosen. Therefore the new line and each of the old lines is equally likely, so the distribution is uniform.

Since the initial case meets our uniform-selection criterion, and we've shown that if N-1 satisfies it then N satisfies it, then by induction, our selection will be uniformly random for any N.

Complexity:

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

Links and credits:
http://nedbatchelder.com/blog/201208/selecting_randomly_from_an_unknown_sequence.html

Compute a partial sum of array using plus operator only

Problem:
There's an array of numbers A[1]...A[N]. Need to compute another array of numbers S[1]...S[N] such that each S[i] is a sum of all the elements A[1]...A[N] except the element A[i]. In other words:

S[i] = ƩA[j], 1 <= j <= N && j != i

Solution:
We need two passes over the array A[]. One to compute the sum in the forward direction (1..N) and assign the accumulated sum to each S[i] element. Another pass is performed in the backward direction (N..1) and adds the accumulated sum to the corresponding S[i] element. Each of the passes ensures that the sum accumulated in S[i] does not contain the value of A[i] itself:

1. take a variable say, Sum, initialize it as Sum = 0. 
2. For index i=1 to N do : 
      S[i] = Sum; 
      Sum+=A[i]; 
3. Sum = 0; 
4. For index i=N down to 1 do: 
      S[i]+=Sum; 
      Sum+=A[i]; 
5. Done.

Complexity:

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

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

Intersection of two linked lists

Problem:
There are two linked lists that intersect. Given two pointers to the heads of the lists, find the intersection point.

Solution:
Determine the length of each list - let it be L1 and L2. Traverse |L1 - L2| nodes in the longest list. Now both lists contain equal number of nodes before the intersection point. Simply traverse both lists with two pointers. Once the pointers point to the same node the intersection is found.

Complexity:

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

Links and credits:
http://www.kodelog.com/spot-the-intersection-of-linked-list/