Monthly Archives: July 2012

Beyond algorithm complexity

When will you choose an algorithm whose time complexity is O(n^2) instead of the other one whose time complexity is O(n)? 1.When n is small, O(n^2) could be smaller than O(n) or they do not differ much. 2. When time … Continue reading

Posted in Complexity | Leave a comment

Find two elements with certain sum in a sorted array

Given a sorted array A[n], find out if there exist two elements whose sum is equal to S. The complexity of the algorithm needs to be O(n). C++: 01 void equalsum(int *A, int size, int S,  int& a, int &b) 02 { … Continue reading

Posted in Array and linked list | Leave a comment

Detect circle in linked list

How to detect whether a singly linked list has a circle? If there is a circle, how to determine the beginning of the circle? C++: 01 Node* begincircle(Node* head) 02 { 03     Node* p=head; 04     Node* q=head; 05     while(true){ … Continue reading

Posted in Array and linked list | Leave a comment

Find Max and Min in array

Given an array of integers, how to find the maximum and minimum? Simple solution: C++: 01 void maxmin(int *A, int size, int& max, int &min) 02 { 03     max=min=A[0]; 04     for(int i=1;i<size;i++){ 05         if(max<A[i]) 06      … Continue reading

Posted in Array and linked list | Leave a comment

Delete duplicate element in sorted array

Given an array (1,1,2,2,3,3,4,4,5,5,6), return pointer to an array with no duplicates (1,2,3,4,5,6).  Hint: two pointers, in place, no extra memory. C++: 01 int delduplicate(int* A, int size) 02 { 03     int t=1; 04     int* p=A; 05     int* q=p; … Continue reading

Posted in Array and linked list | Leave a comment

Swap without temporary variable

Do you know how to swap values without a temporary variable? C++: 1 void swap(int& a, int& b) 2 { 3     a=a^b; 4     b=a^b; 5     a=a^b; 6 } Alternative solution: C++: 1 void swap(int& a, int& b) 2 { 3     a=a+b; … Continue reading

Posted in Number trick | Leave a comment

Reverse a singly linked list(iteratively)

What is the most efficient method to reverse a Singly Linked List?  Iterative solution: C++: 01 Node* reverse_iterative(Node* head) 02 { 03     if(head==NULL) 04         return NULL; 05     Node *prv=head; 06     Node *p=head->next; 07     Node *tmp=NULL; … Continue reading

Posted in Array and linked list | Leave a comment