Data structure and algorithms

1. How to reverse a string?

swap the charecters from initial to end and converge till middle point

2. How to reverse a sentence?

Put the words in linked list, and swap the nodes, this way words will also be reversed.

Other thing is,

swap the every charecter of sentence, on each space, swap the word again, sentence will be reversed but words wont

3. How to find the Median/middle of a List.

Traverse with two pointers, single and double, when double points to end, single will be at middle.

4. How to find cycle in the List.

Traverse with two pointers, single and double, at any point of time, double will reverse back and will point to single, means there is cycle, otherwise, stop till single reaches to the end, means no cycle.

5. Given a graph, find the cycle

6. Reversing a linkedlist: 

Again swap the first elment to last and converge to the middle.

7. Swaping two variables

1. using temp

2. Using arithmetic

  void swap(int &i, int &j) {

       i=i+j;        j=i-j;        i=i-j;    }

 3. XOR method

 void swap(int &i, int &j){

      i = i ^ j;       j = j ^ i;       i = i ^ j; 

 } 

8. Finding the merging point of two list

List1 length=L1

List2 length=L2

Start traversing from longer list, traverse till (L1-L2), Now start comparing the values of L1 and L2, after this point merge point is 

equidistant from each List, If equality found means merge point exist otherwise not. 

Mergring point index in Longer list=(L1-L2) + no of nodes required to reach merge point

Merging point index in small list= no of nodes required to reach merge point

9. How to find fibonacci of a number in o(logn) time.

Using these two formula, it can be achieved

F(2n-1) = F(n-1)2 + F(n)2
F(2n) = ( 2 F(n-1) + F(n) ) F(n)

check this link for detail

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html#exact

10. How to find nth max element in an Array.

By the approach of quicksort, choosing pivot at ith posivition make sure that ith max element is the pivot. We need to iterate only n times max to find out.  Other approach could be, after partitioning if n > i, then move ahead with quicksort in right  otherwise in left, and slowly we can converge to the nth index where pivot element will be only one, and of course that will the nth max element.

....??? not complete