Wednesday, August 12, 2009

Climb the Pyramid

Cal Newport describes the pyramid strategy to evaluate one’s progress.

http://calnewport.com/blog/2009/06/03/the-pyramid-method-a-simple-strategy-for-becoming-exceptionally-good/

From the blog:

[quote]

I call this general technique the Pyramid Method. I claim that it’s a powerful approach for anyone looking to transform an interest or natural talent into an expertise that cannot be ignored. Regardless of the pursuit in question, if you want to take it someplace serious, follow Chris’s example. This means:

  1. Pick a single relevant venue to join at the entry level and work to increase your standing.
  2. Make sure the venue offers clear metrics on your progress; use these metrics to guide your efforts to get better.
  3. Forget all the other bullshit advice and mini-strategies people offer for getting ahead in your pursuit. If you can’t master this one venue, then you don’t yet deserve the world’s respect.
  4. Put your head down, and get it done.

[/quote]

The strategy can work for many skills music, sports and coding. But choosing the proper venue is critical. IMO, apart from the above properties mentioned by Chris, The venue should have some other properties.  I would talk about them from a coder’s perspective.

1. Have a low entry barrier: So that you can start early from a entry-level. So, when you only know the syntax and basic constructs of a high level language (C++, Java, C#)

2. A high competition/quality: So, you don’t “win” the venue too soon. So, you are actively engaged when you can solve non-trivial problems in your arena also. This also ensures that good coders will keep coming to your venue rather than taking off someplace else.

3. Can cater to more than 1 skill: I find this important to be a successful programmer you have to do more than code! This can involve making system architecture, understanding existing codebases, soft skills like communication.

One of the venues I know is Topcoder.com as it offers all what Chris has outlined in his article and what I have outlined here in this post.

Now, I just have to go and follow the all important Step 4 from Chris’s post.

Monday, May 18, 2009

Largest Element in the Stack

Problem: Given a stack you have to insert a stream of numbers in it and you have to keep track of the highest element at any point in the stack

In general, the solution will require traversing through the entire stack hence taking O(n) time. However, given the option of using another data-structure this can be done using minimal extra memory using another "Stack" !.

The basic idea is when pushing an element in the original, check if the the "highest_elem_stack" is empty or if its top element is less than or equal to the element being pushed, if yes push this element on both stacks.

While popping check if the popped element is equal to the top element of the "highest_elem_stack". If yes pop both stacks.

The highest element in the original stack would always be equal to the top element in the "highest_elem_stack"

Tuesday, December 9, 2008

3 sum problem

The problem is defined as given a array find a set of elements such that c=a+b.

Approach
1. Sort the array
2. for each element c=arr[i] in the array
3. left=0; right=i;
4. while left<right
5. check if c==arr[left]+arr[right]
6. then add c to output
7. else if c<arr[left]+arr[right] right--
8. else left++
9. end
10.end


#include <iostream>

using namespace std;

int compare (const void * a, const void * b);
void sum3(int arr[], int n);
void main(){
int arr[]={2,3,5,1,4,9};

qsort(arr,6,sizeof(int),compare);

sum3(arr,6);

}
void sum3(int arr[], int n){
int l,r;
int count=0;
int index[6];
int curr=0;
for(int i=n-1;i>=0;i--)
{
l=0; r=i;
while(l<r){
curr=arr[l] +arr[r];
if(arr[i] == curr){
index[count++]=i;
cout<<arr[i]<<" ";
break;
}
else if(arr[i] < curr)
r--;
else l++;
}
}
}
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}


Complexity of the above procedure is O(n^2). Apparently a better solution for the problem doesn't exist. Also, a number of problems can be reduced to the 3 sum problem and are called 3sum hard.

Implement a queue using 2 stacks

Use 2 stacks, S and T

1. Enqueue
S.push()

2. Dequeue
if T.count==0
while (S.count>0) t.push(s.pop());

T.pop();

The operations take O(1) amortized time.

Reference
C SC 545 Exam Fall 08

Kth smallest in merge of 2 sorted arrays

Idea:
The solution goes like this

A[1...m] B[1...n]

1. Compare A(k/2) and B(k/2)
if A(k/2) < B(k/2)

So the kth smallest can't be in A[1..k/2] and B[k/2+1 .. n]. A[1...k/2] < Kth smallest < B[k/2+1 ... n]

So we discard these elements. And now search for the k/2th smallest number in the 2 remaining arrays

if the reverse is true we do the same operation but with B and A swapped

2. if m<k

we discard B[1...k-m-1]

and look for (m+1)th (= k-(k-m-1)) smallest element in remaining arrays

const trick

1. const int* x=5;

Declares a pointer to a constant.
So now a assignment *x=10; will fail

2. int* const x=5;
Declares a constant pointer to a variable.
so *x=10 will PASS while x=10 will fail.

3. const int * == int const *
The above 2 mean the same thing

4. const int const *x=5;

Using 3. statement 4 Declares a pointer to a constant. (same as 1)

Wednesday, December 3, 2008

New vs. Malloc

New calls the "operator new(...)" method to allocate memory (like what malloc does), but memory allocation is followed by a call to the appropriate constructor. Also new is type-safe, yet malloc is not.
Related Posts with Thumbnails