String and cache implementation

A cache contains a list of String of length atmost L.suppose cache contains n Strings. Given a String X (of length g) as input, Find out whether any anagram of X is in cache efficiently? Find out Time Complexity. [Hints - Tries /hash/ bit-map]

Remove overlapping sets and Merge overlapping intervals

Question 1: Remove overlapping sets
You are given n variable length sets with each set like set1: [s1.....e1], set2:[s2.....e2] with the condition that the sets overlap (i.e. if you represent them on number line, they intersect). Now you have to remove the minimum number of sets from here so that the remaining sets are disjoint.

For example you have set S1, S2, S3 with S1 and S3 disjoint and S2 overlapping both S1 and S3 then we remove S2 to get the answer.
Strategy:
Assume all the sets are sorted.
Find the maximum value out of all the sets i.e., compare the last value in each set & find the maximum value.
Create a bitset with a size that of this maximum value.
Walk through the first set & for each value set the corresponding bit. i.e, if s1 = 6, then the 6th bit is set.
Pick the next set. Walk through it. If you find any bit is already set, for any value of this set, then that set needs to be removed.
Follow the same for all the remaining sets.

Question 2: Merge Overlapping Intervals
Given a set of time intervals in any order, merge all overlapping intervals into one and output the result which should have only mutually exclusive intervals. Let the intervals be represented as pairs of integers for simplicity.
For example, let the given set of intervals be {{1,3}, {2,4}, {5,7}, {6,8} }. The intervals {1,3} and {2,4} overlap with each other, so they should be merged and become {1, 4}. Similarly {5, 7} and {6, 8} should be merged and become {5, 8}
Strategy:
1. Sort the intervals based on increasing order of
    starting time.
2. Push the first interval on to a stack.
3. For each interval do the following
   a. If the current interval does not overlap with the stack
       top, push it.
   b. If the current interval overlaps with stack top and ending
       time of current interval is more than that of stack top,
       update stack top with the ending  time of current interval.
4. At the end stack contains the merged intervals.
http://www.geeksforgeeks.org/merging-intervals/

Find smallest positive number

You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space.
Eg:
Input = {2, 3, 7, 6, 8, -1, -10, 15}
Output = 1
Input = { 2, 3, -7, 6, 8, 1, -10, 15 }
Output = 4

A naive method to solve this problem is to search all positive integers, starting from 1 in the given array. We may have to search at most n+1 numbers in the given array. So this solution takes O(n^2) in worst case.
We can use sorting to solve it in lesser time complexity. We can sort the array in O(nLogn) time. Once the array is sorted, then all we need to do is a linear scan of the array. So this approach takes O(nLogn + n) time which is O(nLogn).
We can also use hashing. We can build a hash table of all positive elements in the given array. Once the hash table is built. We can look in the hash table for all positive integers, starting from 1. As soon as we find a number which is not there in hash table, we return it. This approach may take O(n) time on average, but it requires O(n) extra space

A O(n) time and O(1) extra space solution:
The idea is similar to this post. We use array elements as index. To mark presence of an element x, we change the value at the index x to negative. But this approach doesn’t work if there are non-positive (-ve and 0) numbers. So we segregate positive from negative numbers as first step and then apply the approach.
Following is the two step algorithm.
1) Segregate positive numbers from others i.e., move all non-positive numbers to left side. In the following code, segregate() function does this part.
2) Now we can ignore non-positive elements and consider only the part of array which contains all positive elements. We traverse the array containing all positive numbers and to mark presence of an element x, we change the sign of value at index x to negative. We traverse the array again and print the first index which has positive value. In the following code, findMissingPositive() function does this part. Note that in findMissingPositive, we have subtracted 1 from the values as indexes start from 0 in C.

#include <stdio.h> #include <stdlib.h> void swap(int *a, int *b) {     int temp;     temp = *a;     *a   = *b;     *b   = temp; }   /* Utility function that puts all non-positive (0 and negative) numbers on left   side of arr[] and return count of such numbers */ int segregate (int arr[], int size) {     int j = 0, i;     for(i = 0; i < size; i++)     {        if (arr[i] <= 0)         {            swap(&arr[i], &arr[j]);            j++;  // increment count of non-positive integers        }     }       return j; }   /* Find the smallest positive missing number in an array that contains   all positive integers */ int findMissingPositive(int arr[], int size) {   int i;     // Mark arr[i] as visited by making arr[arr[i] - 1] negative. Note that   // 1 is subtracted because index start from 0 and positive numbers start from 1   for(i = 0; i < size; i++)   {     if(abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0)       arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];   }     // Return the first index value at which is positive   for(i = 0; i < size; i++)     if (arr[i] > 0)       return i+1;  // 1 is added becuase indexes start from 0     return size+1; }   /* Find the smallest positive missing number in an array that contains   both positive and negative integers */ int findMissing(int arr[], int size) {    // First separate positive and negative numbers    int shift = segregate (arr, size);      // Shift the array and call findMissingPositive for    // positive part    return findMissingPositive(arr+shift, size-shift); }   int main() {   int arr[] = {0, 10, 2, -10, -20};   int arr_size = sizeof(arr)/sizeof(arr[0]);   int missing = findMissing(arr, arr_size);   printf("The smallest positive missing number is %d ", missing);   getchar();   return 0; }

Note that this method modifies the original array. We can change the sign of elements in the segregated array to get the same set of elements back. But we still loose the order of elements. If we want to keep the original array as it was, then we can create a copy of the array and run this approach on the temp array.

The Nuts n Bolts Problem (Lock & Key problem)

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently.
Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

There are n nuts and corresponding bolts. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently.However, all nuts and bolts are shuffled and we have to device a technique to pair them.

• No two pairs are of same size.
• Each nut has exactly one bolt for it.
• You can’t compare nut with a nut and same with bolt.
• You can determine by a comparison if a nut is greater or a bolt is greater.

Other way of asking this problem is, given a box with locks and keys where one lock can be opened by one key in the box. We need to match the pair.

http://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem/

Strategy:

This problem can also be solved in a quick sort kind of technique.

• Pick up nut n1 with all bolts. Divide all bigger bolts on one side and smaller bolt on other side. One bolt say b1 matches n1 to make the pair.
• Take nut n2 and compare with bolt b1. If bigger bolt is required look in greater set otherwise in the smaller set.
• Do the same with rest of the nuts. This way we are saving the number of comparisons by categorizing.

Time complexity is approximately O(nlogn)

Maximum Sum Increasing Subsequence

Variation of LIS:
Given an integer array, how will you find out the increasing subsequence which gives the largest sum. For example,
50,23,1,67,30 in this subsequence a few possible increasing subsequences are
1)    23,30
2)    23,67
2)    50,67
3)    1,67
4)    1,30
5)    67
6)    30

but 50, 67 gives the maximum sum. How to find it
Note: In the above scenario however if we have 128 at index 0 then it will have the max sum although it is not forming longest LIS. 

Code:
int lis( int arr[], int n )
{
int *lis,*arr1, i, j, max = 0,max_value=0;

lis = (int*) malloc ( sizeof( int ) * n );
arr1 = (int*) malloc ( sizeof( int ) * n );

for ( i = 0; i < n; i++ )
lis[i] =1;


for ( i = 0; i < n; i++ )
arr1[i]=arr[i];


for ( i = 1; i < n; i++ )
  {
    for ( j = 0; j < i; j++ )
       { if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
             { lis[i] = lis[j] + 1;
                if(lis[i] > max)
                 { if (arr1[i] <(arr1[i]+arr1[j]))
                     arr1[i]=arr1[i]+arr1[j];
                    max=lis[i];
                  }
              }
        }
}

for(i=1;i < n;i++)
{ max_value=arr1[0];
if(arr1[i] > max_value)
max_value=arr1[i];
}

printf("\nThe Maximum sum is %d",max_value);
free( lis );
free( arr1 );

return max;
}

Ugly Numbers

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 150′th ugly number.

Largest sum contiguous subarray - Kadane's Algorithm

Variation 1: Kadane Algo. for 1d Array/ Maximum Sum of All Sub-arrays
Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum. Also find the subarray.

http://www.programcreek.com/2013/02/leetcode-maximum-subarray-java/
http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
http://codercareer.blogspot.in/2011/09/no-03-maximum-sum-of-all-sub-arrays.html

Variation 2: Maximum subset [ Not Sub-array ] sum Problem.
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
http://www.ideserve.co.in/learn/subset-sum-dynamic-programming

Variation 3:  Largest Sum Contiguous Subarray for 2D array.
Given a 2D array, find the maximum sum subarray in it.
http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

Variation 4: Maximum circular subarray sum
n numbers (both +ve and -ve) are arranged in a circle. find the maximum sum of consecutive nos. Do this in O(n) time

E.g.: {8,-8,9,-9,10,-11,12}
max = 22 (12 + 8 - 8 + 9 - 9 + 10)
http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/

Variation 6: Maximum Product Subarray
Also, Given an array of integers (possibly some of the elements negative), write a C program to find out the *maximum product* possible by adding 'n' consecutive integers in the array, n <= ARRAY_SIZE. Also give where in the array this sequence of n integers starts.
http://www.programcreek.com/2014/03/leetcode-maximum-product-subarray-java/
http://www.geeksforgeeks.org/maximum-product-subarray/

Method 1:

Kadanes Algorithm:

We will use a scanning algorithm using two pointers.
Pointer A stays at 0 and pointer B starts scanning ahead.
Calculate the sum at every step of B and compare with the max sum found so far.
Maintain the max sum pointer position (of B) and the max sum found so far.
When the sum hits negative or zero, bring Pointer A to the current position and restart the scanning using pointer B. O(n)


Code:

int maxSubArraySum(int a[], int size)

{

   int max_so_far = 0, max_ending_here = 0;

   int i;

   for(i = 0; i < size; i++)

   {

     max_ending_here = max_ending_here + a[i];

     if(max_ending_here < 0)

         max_ending_here = 0;

     /* Do not compare for all elements. Compare only

        when  max_ending_here > 0 */

     else if (max_so_far < max_ending_here)

         max_so_far = max_ending_here;

   }

   return max_so_far;

}

Time:O(n)

For int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};the answer comes as 7

E.g.: {8,-8,9,-9,10,-11,12}
max = 22 (12 + 8 - 8 + 9 - 9 + 10)
 
To get indexes of subarray
#include <stdio.h>
#include <stdlib.h>

int maxSubArraySum(int a[], int size,int *begin,int *end)
{
   int max_so_far = 0, max_ending_here = 0;
   int i,current_index = 0;
 
   for(i = 0; i < size; i++)
   {
     max_ending_here = max_ending_here + a[i];
   
     if(max_ending_here <= 0)
        {
         max_ending_here = 0;
         current_index=i+1;
        }
     else if (max_so_far < max_ending_here)
         {
          max_so_far = max_ending_here;
          *begin = current_index;
          *end=i;
          }
   }
   return max_so_far;
}

int main()
{
  int arr[] = {6,-5,7,9,-4,-3,5,-6};
  //int arr[] = {5,2,-1,-2,-4,3,5,-6};
  int begin=0,end=0;
  int size=sizeof(arr)/sizeof(arr[0]);

  printf(" The max sum is %d",maxSubArraySum(arr,size,&begin,&end));
  printf(" The begin and End are %d & %d",begin,end);
  getchar();
  return 0;
}

Method 2:

Use divide n conquer. Divide the problem into two, compare best case of left, right and maximum subset at the junction.
For checking the maximum subset at the junction, we have to get maximum subset at the corners and merge them. The complexity of this approach will be nlogn.

Method 3:

First, you can convert the list into a list of cumulative sums, turning [5,-2,10,-4] into [0,5,3,13,9]. Then walk through the list of cumulative sums, to get the maximum positive difference. If minimum lies before the maximum in the cumulative sum, then that is the answer. For example, minimum here is 0 and maximum is 13. The answers will be numbers contributing towards it [5,-2, 10]
The gist of the concept is to get the maximum positive delta.

Push(),Pop(), and GetMin() elements at complexity O(1)

Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.

http://www.geeksforgeeks.org/design-and-implement-special-stack-data-structure/
http://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/

Method 1:2 stacks
A constant time minimum lookup can be achieved by using an extra stack. Let's call this stack 'min_stack'. This stack will always have the minimum value at the top.

Modify 'push' and 'pop' operations as follows:

push:
- If the element being pushed is less than the top element of 'min_stack' then push it on 'min_stack' as well.
- Else, push the top element of 'min_stack' again on 'min_stack'.

pop:
- Every time you pop an element from the original stack, pop from 'min_stack' as well.

Example:
Suppose, elements are pushed in the following order: 7 3 5 8 9 1 2

original_stack                min_stack
        2                                 1
        1                                 1
        9                                 3
        8                                 3
        5                                 3
        3                                 3
        7                                 7

You can see that at any stage, the 'min_stack' can be queried for the minimum element in the stack.

Method 2:Single Stack

PUSH : While inserting the element into stack we insert the element and also keep track of minimum element at every insert and also insert the minimum element. This doubles up the stack usage to 2n. where n is number of element. O(1).

POP : While extracting element out of the stack, we need to extract two elements one is the minimum element tracked so far and the actual element of the array. O(1)

FIND MIN:Single pop operation will be able to fetch the minimum element. O(1).

Big Endian or little Endian

 Write a program to find whether a machine is BIG endian or Little endian.

A big-endian machine stores the most significant byte first i.e. at the lowest byte address, and a little-endian machine stores the least significant byte first.

Concepts:
Little and big endian are two ways of storing multibyte data-types ( int, float, etc). In little endian machines, last byte of binary representation of the multibyte data-type is stored first. On the other hand, in big endian machines, first byte of binary representation of the multibyte data-type is stored last.

Suppose integer is stored as 4 bytes (For those who are using DOS based compilers such as C++ 3.0 , integer is 2 bytes) then a variable x with value 0×01234567 will be stored as following.

Memory representation of integer ox01234567 inside Big and little endian machines

 

What are bi-endians?
Bi-endian processors can run in both modes little and big endian.


How to see memory representation of multibyte data types on your machine?
Here is a sample C code that shows the byte representation of int, float and pointer.

#include <stdio.h> /* function to show bytes in memory, from location start to start+n*/ void show_mem_rep(char *start, int n) {     int i;     for (i = 0; i < n; i++)          printf(" %.2x", start[i]);     printf("\n"); } /*Main function to call above function for 0x01234567*/ int main() {    int i = 0x01234567;    show_mem_rep((char *)&i, sizeof(i));    getchar();    return 0; }

When above program is run on little endian machine, gives “67 45 23 01″ as output , while if it is run on endian machine, gives “01 23 45 67″ as output.

Determine endianness of your machine
There are n no. of ways for determining endianness of your machine. Here is one quick way of doing the same.

#include <stdio.h> int main() {    unsigned int i = 1;    char *c = (char*)&i;    if (*c)        printf("Little endian");    else        printf("Big endian");    getchar();    return 0; }

In the above program, a character pointer c is pointing to an integer i. Since size of character is 1 byte when the character pointer is de-referenced it will contain only first byte of integer. If machine is little endian then *c will be 1 (because last byte is stored first) and if machine is big endian then *c will be 0.

Does endianness matter for programmers?
Most of the times compiler takes care of endianness, however, endianness becomes an issue in following cases.
Case 1:
It matters in network programming: Suppose you write integers to file on a little endian machine and you transfer this file to a big endian machine. Unless there is little andian to big endian transformation, big endian machine will read the file in reverse order.

Standard byte order for networks is big endian, also known as network byte order. Before transferring data on network, data is first converted to network byte order (big endian).

Case 2: 
Sometimes it matters when you are using type casting, below program is an example.

#include <stdio.h> int main() {     unsigned char arr[2] = {0x01, 0x00};     unsigned short int x = *(unsigned short int *) arr;     printf("%d", x);     getchar();     return 0; }

In the above program, a char array is typecasted to an unsigned short integer type. When I run above program on little endian machine, I get 1 as output, while if I run it on a big endian machine I get 256. To make programs endianness independent, above programming style should be avoided.

Case 3:
Does endianness effects file formats?
File formats which have 1 byte as a basic unit are independent of endianness e..g., ASCII files . Other file formats use some fixed endianness forrmat e.g, JPEG files are stored in big endian format.

Examples of little, big endian and bi-endian machines
Intel based processors are little endians. ARM processors were little endians. Current generation ARM processors are bi-endian.
Motorola 68K processors are big endians. PowerPC (by Motorola) and SPARK (by Sun) processors were big endian. Current version of these processors are bi-endians.


Which one is better — little endian or big endian

The term little and big endian came from Gulliver’s Travels by Jonathan Swift. Two groups could not agree by which end a egg should be opened -a-the little or the big. Just like the egg issue, there is no technological reason to choose one byte ordering convention over the other, hence the arguments degenerate into bickering about sociopolitical issues. As long as one of the conventions is selected and adhered to consistently, the choice is arbitrary.

How to switch from One format to other:

unsigned long ByteSwap2 (unsigned long nLongNumber)
{
   return (((nLongNumber&0x000000FF)<<24)+((nLongNumber&0x0000FF00)<<8)+
   ((nLongNumber&0x00FF0000)>>8)+((nLongNumber&0xFF000000)>>24));
}

Useful Links:
http://www.codeproject.com/Articles/4804/Basic-concepts-on-Endianness
http://www.ibm.com/developerworks/aix/library/au-endianc/index.html?ca=drs-

Detect heavy/light ball (among 12 balls)

There are 12 balls that you have out of which one is the odd one out, which means it can be heavy/light. You have three chances to find the odd ball and also whether it's heavy or light.

Variant:

You are given 9 balls. Out of these, 8 are of 1kg and 1 is heavier by 0.5 kg. Given a weight balance which can take tell you which side is heavier at a given trial, you have to compute heavier ball by weighing only twice.

Strategy:
Divide 9 balls in groups of 3.

• Compute the heavier group using balance by keeping two groups on it. If they come as equal, we can conclude third group contains the heavier ball.
• After we have the group that contains the heavier ball, keep the two balls on the balance, you will get the heavier one. (In case, both are equally weighed, the left out will be the heavier one)