## Like a pendulum ….

The days when we *somehow* 🙂 were able to spend our time idly came to an end and the shadow of future bluster us now.

Had our Pre^2 Mock today which I, obviously, didnt do well.

I ought to pick up a bicker with the attender at Caramel for what he did, whom am lambasting right now 🙂

**+ 45 ^{o} :**

**Onnu :** Contiguous Sub Array with Max Sum

Sample : [ 3, -1, 3, 6, 2, -3, 8]

Output : 13, Index : 3 to 6

Array Input : A[]

Max1 = Max2 = 0

Index1 = Index2 = 0

for Count=0 to (Length-1) {

Max1 = Max1 + A[i]

if ( Max1<0){

Max1 = 0

Index1 = (Count +1)

}

if( Max1 > Max2 ){

Max2 = Max1

Index2 = Count

}

}

**Rendu :** How do u find if a given no. is a power of 2?

Input : Number

( Number & (Number-1) )? Print “Not a Power of 2” : Print “Power of 2”

The & does a Binary AND function.

**Moonu :** Middle Element in a Singly Linked List

Have Two Pointers. Ptr2 Moves Two Steps for every single move of Ptr1.

When Ptr1 reaches the end of the list, Ptr2 would be pointing to the middle element.

For getting the Kth Element from the last in a SLL :

Modify Ptr2 in above to move K times for a single move by Ptr1

**Naalu :** Find the point of Convergence of two SLL :

O – O – O –

O– O – O – O|

O – O – O – O

Find the length of both of the SLL

Take the Magnitude of their difference and traverse from the shorter SLL

**Anju :** Reverse Words (seperated by space) in a given array.

1.Do

reversing an arrayalgol for the entire array once.2.Do

reversing an arrayalgol in the array resulting from (1) limiting it to operate within a specifed index ( Index are indicated by the next space )

**Aaru :** Count the number of bits set (One bits) in a given number

Count = 0

while ( Number ) {

Count ++

Number &= (Number-1)

}

**– 45 ^{o} :**

- appease assuage allay
- ascetic austere
- auxiliary ancilliary adjunct adjuvant appurtenant
- assert aver avow
- awry askew
- Not exact : bastion bulwark
- badinage banter
- beleaguer badger
- bellicose belligerent
- benediction benison
- bereavement bereft
- blow-hard braggart
- calumny aspersion
- bluster braggadocio
- a,b,c -ine : asinine, bovine, canine

Thanks :

GCT, Vedi Gilli, ARuVi, KuMary, Brinda

Special Thanks (for teaching* to the board) :

DSP Sir, Trisha, Net-u and Net Sec-u

* – Not applicable to all four 🙂

P.S : Please forgive if usage of any word is not appropiate, First time la 🙂

he he.. 🙂 amazing how u manage to do so much in college.. my brain stagnates like a fly in a bucket full of glue during classes..

😦

hari said this on February 25, 2009 at 1:46 am |

Ref: “Onnu : Contiguous Sub Array with Max Sum”

Will this work for all test cases?? How about all negative numbers?

-4 -1 -3 should give -1 as the ans..

correct me if i am wrong!

Sharmi Nair said this on April 3, 2009 at 4:16 pm |

Also try posting answer for the following question 🙂

Qn: Find out the sub matrix with max sum in a 2D array..

Sharmi Nair said this on April 3, 2009 at 4:21 pm |

DP would be simple and good..

The other option would make the code look dirty.. 🙂

array a: -4 -1 -3

DP[i]=max(a[i]+DP[i-1],DP[i])

So,here DP will be same as array a itself

DP array: -4 -1 -3

This checks if we shud include a[i] to the solution set or not.. Finally traverse thru the DP array to return the max sum. We can also save the index in separate list if we want the starting address of the required subarray..

This works well..

Sharmi Nair said this on April 6, 2009 at 7:11 pm |

My solution:

Every time we see if we can start the subarray from the current index or simply include it in the middle of the subarray(formed by the previous element).

To explain this:

eg: −2, 1, −3, 4, −1, 2, 1, −5, 4

I maintain one more array index[] to save the start index of the solution

Now, first element.. -2..

DP[0]=-2

index[0]=0

Next element is 1. Now, max(DP[i-1]+a[i],a[i])

ie, max(DP[0]+a[1],a[1])=max(-2+1,1)=1

So DP[1]=1

index[1]=1

Next is -3

DP[2]=max(1-3,-3)=-2

DP[2]=-2

index[2]=1 (since we have added a[2] to a[1])

Next is 4

DP[3]=max(4-2,4)=4

DP[3]=4

index[3]=3

Next is -1

DP[4]=max(4-1,-1)=3

index[4]=3

Next is 2

DP[5]=5

index[5]=3

Next is 1

DP[6]=6

index[6]=3

Next is -5

DP[7]=1

index[7]=3

Last ele is 4

DP[8]=4

index[8]=8

DP array:-2 1 -2 4 3 5 6 1 4

index : 0 1 1 3 3 3 3 3 8

Now we see that max in DP is DP[6] (which is 6) and the corresponding index is 3. So the solution is a[3 to 6].

solution is: 4, −1, 2, 1, with sum 6

Hope this is clear!

Sharmi Nair said this on April 6, 2009 at 11:22 pm |