Alogorithm Problems

Alogorithm Problems
Question #1 - Given an array of N integers in which each element from 1 and N-1 occurs once and one occurs twice. Write an algorithm to find duplicate integer. Note- You may destroy the array.
Solution1:
Example Array is {1,2,4,7,8,9,4}
Use Negation to Identify the duplicate one. When you negate every element when you parse it would be like
{0,0,4,0,0,0}. Since 4 occurs more than once for the second time it would be 0-(-4). The resulting <> 0 number in the array is the duplicate occurence.
Note: Same logic can be used to count number of unique elements in an array.

Solution 2: Use XOR for solving this problem
Question#2 - Write a function to reverse a word in place O(n) time and O(1) space.
Solution:
void ReverseWord( char *t, int len)
{
  if(len<=1) return 1;
  Swap(&s[0],&s[len-1]);
  ReverseWord(s+1,len-2);
}

Question#3- Find Longest Sequence Palindrome in a String "abcabcad"
This is a Dynamic Programming problem.
Answer: Link1, Link2

Dynamic Programming
Good problems and answers
From the above link posting the solution
Let us define the maximum length palindrome for the substing x[i,...,j] as L(i,j)
Procedure compute-cost(L,x,i,j)

Input: Array L from procedure palindromic-subsequence; Sequence x[1,...,n] i and j are indices
Output: Cost of L[i,j]
if i = j:
    return L[i,j]
else if x[i] = x[j]:
    if i+1 < j-1:
        return L[i+1,j-1] + 2
    else:
         return 2
else:
return max(L[i+1,j],L[i,j-1])

Read Quote of Michal Danilák's answer to Dynamic Programming: Are there any good resources or tutorials for Dynamic Programming besides TopCoder tutorial? on Quora

More Reads
Are there any good resources or tutorials for Dynamic Programming besides TopCoder tutorial ?

What are few must-do DP problems and why?

Happy Learning!!!!