Converting Text file to wav file

Below Code can be used to convert any text file to wav file

Converting Text to wav File

Below code can be used to convert text to wav file:

Generate all the strings of n bits

Problem:
Generate all the strings of n bits.
Solution:
Subtract and Conquer.
Complexity: O(2^n)
Code:

Problem:
Given an array of integers. How do we pick two numbers such that their sum is closest to zero.
Solution: 

• Sort the array by comparing absolute value.
• traverse the array once to find the two consecutive numbers with minimum sum.

Complexity: O(n log n)
Code:

a1a2a3....anb1b2b3....bn to a1b1a2b2a3b3....anbn

Problem:
Convert a1a2a3....anb1b2b3.....bn to
a1b1a2b2a3b3.....anbn
in O(n) time and O(1) space
Solution:

[b]       a b c d e 1 2 3 4 5      [2<=5, index=2*2-1=3]

[c]       a b b d e 1 2 3 4 5      [3<=5, index=3*2-1=5]

[e]       a b b d c 1 2 3 4 5      [5<=5, index=5*2-1=9]

[4]       a b b d c 1 2 3 e 5      [9>5, index=(9-5)*2=8]

[3]       a b b d c 1 2 4 e 5      [8>5, index=(8-5)*2=6]

[1]       a b b d c 3 2 4 e 5      [6>5, index=(6-5)*2=2]

[b]       a 1 b d c 3 2 4 e 5      [startindex=index=2]

[d]       a 1 b d c 3 2 4 e 5      [4<=5,index=4*2-1=7]

[2]       a 1 b d c 3 d 4 e 5      [7>5,index=(7-5)*2=4]

[d]       a 1 b 2 c 3 d 4 e 5      [startindex=index=4]

Complexity: O(n) time O(1) space
Code:

|a-b| + |b-c| + |c-a|

Problem:

Given n arrays, find n number such that sum of their differences is minimum. For e.g. if there are three arrays

A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}

find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum 

where a E A , bEB , cEC

. Here the answer is a = 15, b = 13, and c = 14

Solution:
Let,
min_dif=INT_MAX
1.Sort the N arrays A,B,C.....
2.Find the minimum and maximum of A[0],B[0],C[0].....
3.Take the difference between MAX-MIN values.
5.If the difference is less than min_dif then update min_dif and save all n values.
6.Now increment the index of the array which contains minimum element.
7.repeat these steps till end of array is reached for atleast one array.

Complexity: O(total no of elements)
Code:

Diameter of a binary tree

Problem:
Find the diameter of a binary tree.
Solution:

1. Do Post order traversal
2. if Left Max path + Right Max path > Max then
3. Max = Left Max path + Right Max path 
4. return 1 + MAX(Left Max path length + Right Max path length)

Complexity: O(n), where n = no of nodes
Code:

CLRS (Page 85): Problems 4-2 : Finding the missing integer

Problem:

An array A[1...n] contains all the integers from 0 to n except one. It would be easy to determine the missing

integer in O(n) time by using an auxiliary array B[0...n] to record which numbers appear in A. In this
problem, however, we cannot access an entire integer in A with a single operation. The elements of A are
represented in binary, and the only operation we can use to access them is ”fetch the jth bit of A[i],” which
takes constant time.
Show that if we use only this operation, we can still determine the missing integer in O(n) time.

Solution:

Our convention is to call the least significant bit (LSB) as 0-th bit. Number of digits required to represent
n is at least dlg(n + 1)e. Most significant bit (MSB) of n is the (dlg(n + 1)e − 1)-th bit of it.
Among the integers between 0 to n, exactly 2
(dlg(n+1)e−1)
numbers are < 2
(dlg(n+1)e−1)
. If we look at
the (dlg(n + 1)e − 1)-th bit of any non-negative number ≤ n we can determine whether the number is
< 2
(dlg(n+1)e−1)
. We now look at the (dlg(n + 1)e − 1)-th bit of all the numbers in A[1...n]. We populate two
lists of references (e.g. pointer, index, handle etc) during the first n lookup. Reference to the numbers having
0 in their (dlg(n + 1)e − 1)-th bit are kept in one and the rest in the other. The size of the first list is the
count of numbers < 2
(dlg(n+1)e−1)
. The missing integer is < 2
(dlg(n+1)e−1)
iff this count is 2
(dlg(n+1)e−1) − 1.
We look for the missing integer in the first list in that case. Otherwise, we look in the second list. In this
process, we figure out the (dlg(n + 1)e − 1)-th bit of the missing integer in n bit lookup.
We want to use recursion to search the appropriate list. The fact that now we search in a list of references
to numbers in stead of a list of numbers can be handled as follows. The initial problem comes with the list
all the references. The fact that the search range could be shifted in the subproblem is handled by replacing
all the (dlg(n + 1)e − 1)-th bits as 0. However, as we never read the (dlg(n + 1)e − 1)-th bits again we don’t
have to do this modification explicitly.



find_missing_integer ( list_of_references, n )
if ( n is 1 )
print 0-th bit of missing number is (1 - the number in the list)
return
left_list . initialize ()
right_list . initialize ()
msb_position <- ceiling( lg(n+1) ) - 1
forall number in list_of_references
if ( number [ msb_position ] is 0 )
left_list . insert ( number )
else
right_list . insert ( number )
if ( left_list . size () < power_of_two ( msb_position ) )
print msb_position-th bit of missing number is 0
find_missing_integer ( left_list, power_of_two ( msb_position ) - 1 )
else
print msb_position-th bit of missing number is 1
find_missing_integer ( right_list, n - power_of_two ( msb_position ) )


Complexity: O(log n)
Code:

CLRS Exercises 5.1-2

Problem:

Describe an implementation of the procedure RANDOM(a, b) that only makes calls to
RANDOM(0, 1). What is the expected running time of your procedure, as a function of a and
b?

Solution:

1. n = ceil(log(b-a+1))
2. decimal_number=0;
3. do
4. for i = 1 to n: get all binary
5. decimal_number = generate decimal from binary digits
6. while decimal_number > b-a+1
7. return decimal_number

Complexity:  Θ(log (b-a+1))

CLRS Exercises 5.1-3:

Problem:

Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your
disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some
probability p and 0 with probability 1 - p, where 0 < p < 1, but you do not know what p is.
Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased
answer, returning 0 with probability 1/2 and 1 with probability 1/2. What is the expected
running time of your algorithm as a function of p?

Solution:

1. Start while loop
2. a=rand(); b=rand()
3. if(a==0 && b==1) return 0;
4. else if(a==1 && b==0) return 1;
5. else continue;

Complexity:

Expand a random range from 1-5 to 1-7

Problem:
Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
Solution:

int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;  // result is now uniformly random between 1 and 7

Complexity:

CLRS - Problem 2.1

Problem:

Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n2) worstcase
time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense
to use insertion sort within merge sort when subproblems become sufficiently small. Consider
a modification to merge sort in which n/k sublists of length k are sorted using insertion sort
and then merged using the standard merging mechanism, where k is a value to be determined.
a. Show that the n/k sublists, each of length k, can be sorted by insertion sort in Θ(nk)
worst-case time.
                  Time to sort each list of length k using insertion sort= T(k^2)
                  Time to sort n/k lists each of length k = T(n/k *  k^2) = Θ(nk)
                                                           
b. Show that the sublists can be merged in Θ(n lg (n/k) worst-case time.
                  Height of the tree with n elements and with k = log n - log k = log(n/k)
                  so for merging it will take Θ(n * log(n/k))

c. Given that the modified algorithm runs in Θ(nk + n lg (n/k)) worst-case time, what is

the largest asymptotic (Θnotation) value of k as a function of n for which the modified

algorithm has the same asymptotic running time as standard merge sort?

Let k=n,
it will become Θ(n^2 + n lg(1)) = Θ(n^2)

Lets take k=1,
it will become Θ(n + n lg n)

Lets take k= lg n
it will become Θ(n lg n + n lg(n/(lg n)) => Θ(n lg n + n lg n - n lg(lg n)) => Θ(2 lg n - n lg(lg n)) => Θ(n lg n)

So, k= Θ(lg n)

d. How should k be chosen in practice?

In practise k should be taken greater the lg n depending upon the constant factors.

CLRS Exercises 2.3-7

Problem:

Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x,
determines whether or not there exist two elements in S whose sum is exactly x.

Solution:

1. Merge sort the elements which will take O(n log n)
2. then have two pointers one from beginning and another from end
3. if sum of both the elements a[i]+a[j] < sum then i++
4. else if sum of both the elements a[i]+a[j] > sum then j--
5. else we found print those elements a[i] and a[j].
6. complexity is O(n) in worst case.
7. Alternatively, after merge sort, do binary search for tmp=Sum - a[i] in the array a[i+1 ... n]
8. here for binary search complexity is O(log n), so still total worst case complexity is O(n log n)

Complexity: O(n log n)
Code:

CLRS - Exercises 2.3-6

Problem:

Observe that the while loop of lines 5 - 7 of the INSERTION-SORT procedure in Section 2.1
uses a linear search to scan (backward) through the sorted subarray A[1 j - 1]. Can we use a
binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of
insertion sort to Θ(n lg n)?

Solution:
No, for finding correct place lets say O(log n) then for moving all the elements will take O(n) time. So, its running time will be O(n^2)
Complexity:
Code:

CLRS Exercises 2.3-5 Binary search

Problem:

Binary search is an algorithm that repeats this
procedure, halving the size of the remaining portion of the sequence each time. Write
pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running
time of binary search is Θ(lg n).

Solution:

1. If there are 2^i elements then the height of the tree will be i+1
2. At each level we will just do comparison [key with middle element] which is a constant time O(1)
3. So for any n, height of the tree will be log n + 1
4. Thus, worst case running complexity will be Θ(lg n).

Complexity: Θ(lg n).
Code:

CLRS Exercises 2.3-4 Recursive insertion sort

Problem:

Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 n],
we recursively sort A[1 n -1] and then insert A[n] into the sorted array A[1 n - 1]. Write a
recurrence for the running time of this recursive version of insertion sort.

Solution:

1. Initially the array size will be n
2. call insertionsort function until the size becomes 1
3. then start the normal insertion approach as shown in code

T(n) = T(n-1) + 1 +  O(n) = O(n^2)

Complexity: O(n^2) TC
Code:

Problem:
You have two numbers represented by a linked list, where each node contains a single digit   The digits are stored in reverse order, such that the 1’s digit is at the head of
the list   Write a function that adds the two numbers and returns the sum as a linked
list
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8
Solution:

1. Have pointer on each head of the two list
2. Add the data of two nodes along with carry.
3. create new result node and put the value, SUM % 10
4. assign SUM / 10 to carry
5. Repeat until any one list exhausts.
6. Then add the carry to the node, repeat till end of list

Complexity: O(n) where n>=m, m and n are length of two lists
Code:

Problem:
  Write code to remove duplicates from an unsorted linked list
Solution:

1. Have two pointers ptr1 and ptr2.
2. For each node ptr1 visits check from head [head  to node before ptr1] whether that data is already present.
3. If so, remove the ptr1 node.
4. return the new list without any duplicates

Complexity: O(n^2)
Code:

Problem:
 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes   Create an algorithm to decide if T2 is a subtree of T1
Solution:

1. Traverse the Tree T1.
2. For each node, call a method to do the following (Step 3),
3. traverse both the Tree T1 and T2, until tree T2 exhausts or until data of T1 and T2 does not match. 
4. Return true if T2 is a subtree of T1 else return false.

 

 Complexity: O(m*n) in the worst case
Code:

Problem:
There are 2 link lists merging at some node. Find the node, where these 2 lists merge.

Solution:
             

1. Point both the heads with temp1 and temp2 pointers.
2. Move both pointers one step at a time.
3. Repeat step 2 until temp1 or temp2 reaches the last node.
4. Make a pointer P1 to point the head of longest list and pointer P2 to point the head of another list.
5. Move the temp pointer of longest list and another pointer from its list head one position at a time until temp reaches the last node.
6. Now we have two pointers with equal numbers of nodes.
7. move two pointers one at a time until they both meet.
8. return the merge node.

Complexity: O(m+n)
Code:

Reverse a Linked List recursively

A Problem with Fenwick Tree

Problem:
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.

Solution:
              Use Binary Indexed Tree.

Complexity: O(n log n)
Code:

Binary Indexed Trees

Refer here for complete tutorial : http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

C 3D Array

To do so, we start by allocating space for all array elements in one call to malloc.

int *allElements = malloc(x * y * z * sizeof(int));

Next, we create the arrays of pointers, and point to the contiguous elements we’ve already allocated.

int ***array3D = malloc(x * sizeof(int **));

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

{

    array3D[i] = malloc(y * sizeof(int *));

    for(j = 0; j < y; j++)

    {

        array3D[i][j] = allElements + (i * y * z) + (j * z);

    }

}

Endianness

Temple Puzzle

Problem:

Mr. X has gone to Temple A, B.C. These temples are having magic pond in each. It will double the thing, whatever you have in your hand, when you come out of the pond. (e.g. if you have Rs.1/- in your hand, and when you come of pond, you will have Rs.2/- in your hand)


Mr. X is having certain number of flowers. The terms and conditions of this quiz is that you have to surrender equal number of flowers to each temple and when you come out of Temple C, no flower should be in your hand.


Please find out how many flowers Mr. X was having with him when he entered into Temple A and how much flowers has he surrendered at each temple.



Solution:

     8X-7Y  =  0
     8X        =  7Y
           X    =  7/8Y     
    =>  X    =   7  when Y = 8 

Which can be generalized as X = 2^n - 1 and Y = 2^n          

Simultaneous minimum and maximum

How many comparisons are necessary to determine the minimum of a set of n elements?
n-1 comparisions.



It is not difficult to devise an algorithm that can find both the minimum and the maximum of
n elements using Θ(n) comparisons, which is asymptotically optimal. Simply find the
minimum and maximum independently, using n - 1 comparisons for each, for a total of 2n - 2
comparisons.
In fact, at most 3 ⌊n/2⌋ comparisons are sufficient to find both the minimum and the
maximum. The strategy is to maintain the minimum and maximum elements seen thus far.
Rather than processing each element of the input by comparing it against the current
minimum and maximum, at a cost of 2 comparisons per element, we process elements in
pairs. We compare pairs of elements from the input first with each other, and then we
compare the smaller to the current minimum and the larger to the current maximum, at a cost
of 3 comparisons for every 2 elements.
Setting up initial values for the current minimum and maximum depends on whether n is odd
or even. If n is odd, we set both the minimum and maximum to the value of the first element,
and then we process the rest of the elements in pairs. If n is even, we perform 1 comparison
on the first 2 elements to determine the initial values of the minimum and maximum, and then
process the rest of the elements in pairs as in the case for odd n.
Let us analyze the total number of comparisons. If n is odd, then we perform 3 ⌊n/2⌋
comparisons. If n is even, we perform 1 initial comparison followed by 3(n - 2)/2
comparisons, for a total of 3n/2 - 2. Thus, in either case, the total number of comparisons is at
most 3 ⌊n/2⌋.

Binary tree, find 2 leaf nodes say X and Y

Problem:
Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is maximum where F(X,Y) = sum of nodes in the path from root to X + sum of nodes in the path from root to Y - sum of nodes in the common path from root to first common ancestor of the Nodes X and Y
Solution:

Complexity: O(n) TC O(n) SC
Code: