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 array algol for the entire array once.

2.Do reversing an array algol 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 :

  1. appease assuage allay
  2. ascetic austere
  3. auxiliary ancilliary adjunct adjuvant appurtenant
  4. assert aver avow
  5. awry askew
  6. Not exact : bastion bulwark
  7. badinage banter
  8. beleaguer badger
  9. bellicose belligerent
  10. benediction benison
  11. bereavement bereft
  12. blow-hard braggart
  13. calumny aspersion
  14. bluster braggadocio
  15. 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 🙂

Advertisements

~ by toolweb on February 24, 2009.

5 Responses to “Like a pendulum ….”

  1. 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..
    😦

  2. 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!

  3. Also try posting answer for the following question 🙂
    Qn: Find out the sub matrix with max sum in a 2D array..

  4. 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..

  5. 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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: