### Blogroll

### Topics

- Apartment rental and roommate finding
- Array and linked list
- Backtrack
- Binary search
- Bit operation
- C++
- Complexity
- Divide and Conquer
- Dynamic programming
- File operation
- Geometry
- Graph
- Greedy algorithm
- Hashtable and Map
- Heap
- JAVA
- Large scale data
- Number trick
- Object orientated design
- Probability
- Recursive
- Stack and Queue
- String
- Threads and locks
- Tree
- Uncategorized

### Archives

# 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