Print Tree Level Order one in each line

Given a binary tree, which is not necessarily balanced, print the nodes in the tree in a level-wise manner. Also, nodes on the same level should be printed on a single line.

Can be done with Queue data structure with null pointer additiond

Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

vector<vector<bool> > checked;

int xi[3] = {-1, 0, 1};
int yi[3] = {-1, 0, 1};

void explore(bool fliprequired, int i, int j, vector<vector<char> > &board)
{
    queue<pair<int, int> > Q;     
    Q.push(make_pair(i, j));
    while(Q.size() > 0 )
    {
        if(fliprequired)
            board[i][j] = 'X';
        
        checked[i][j] = true;
        
        pair<int, int> rt = Q.front();
        Q.pop();
        
        for(int l = 0; l < 3; l++)
        {
            for(int r = 0; r  < 3; r++)
            {
                int newx  = rt.first  + xi[l];
                int newy =  rt.second + yi[r];
                
                if(newx >= 0 && newx < board.size() && newy >=0 && newy < board[0].size())
                {
                    if(!checked[i][j]  && board[newx][newy] == 'O')
                    {
                        Q.push(make_pair(newx, newy));
                    }
                }
            }
        }
    }
    
    return ;
}


bool verify(int i, int j, vector<vector<char> > &board)
{
    bool t = false, b = false, l = false, r = false;
    for(int x  =   i ;  x  >=0 ; x--)
    {
        if(board[x][j] == 'X')
        {
            l = true;
            break;
        }
    }
    
    for(int x  =   i ;  x  < board.size() ; x++)
    {
        if(board[x][j] == 'X')
        {
            r = true;
            break;
        }
    }
    
    
    for(int x  =   j ;  x  >=0 ; x--)
    {
        if(board[i][x] == 'X')
        {
            t= true;
            break;
        }
    }
    
    for(int x  =   j ;  x  < board[0].size() ; x++)
    {
        if(board[i][x] == 'X')
        {
            b = true;
            break;
        }
    }
    
    
    if(t && b && l && r)
        return true;
    return false;
}
             
void solve(vector<vector<char> > &board) {
    int m  = board.size();
    if(m <= 0)
        return;
    
    int n = board[0].size() ;
    
    for(int i  =0; i < m; i++)
    {
        vector<bool> x(false, n);
        checked.push_back(x);
    }
    
    
    for(int i = 0; i < m ;i++)
    {
        for(int j  = 0; j < n; j++)
        {
            if(board[i][j] == 'O' && checked[i][j] == false)
            {
                bool flipneeded  = verify(i, j, board);
                explore(flipneeded, i, j, board);
            }
        }
    }
}

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

bool isPalin(string r)
{
    int i  =0;
    int j = r.size() - 1;
    while(i < j)
    {
               
            if(r[i] != r[j])
                return false;
    
        i++;
        j--;
    }
    
    return true
    ;
}
 
bool isPalindrome(string s) {

    if(s.size() <=0 )
        return true;
        
    string r = "";
    for(int i =0; i < s.size(); i++)
    {
         if(
            (s[i] >= 'a'  && s[i] <= 'z')
                        ||
            (s[i] >= '1'  && s[i] <= '9')
            )
         {
             r = r + s[i];
         }
        
        if(                        
           (s[i] >= 'A'  && s[i] <= 'Z')

           )
        {
            char t  = ('a' + s[i] - 'A');
            r = r + t;
        }
    }
    
    
    return isPalin(r);
        
    
}

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

using Dynamic appaorach
int jump(int A[], int n) {
    int minJumps[1000] = {0};
    minJumps[0] = 0;
    for(int i = 1; i < n; i++)
    {
        minJumps[i] = INT_MAX;
        for(int j = 0; j < i; j++)
        {
            if(A[j] + j >= i)
            {
                minJumps[i] = min(minJumps[i], 1 + minJumps[j]);
            }
        }
    }
    
    
    if(minJumps[n-1] == INT_MAX)
    {
        return -1;
    }
    
    return minJumps[n-1];
}


 int jump(int A[], int n) {
        int step = 0;
        int start =0;
        int end = 0;
        int next = 0;
        while (end < n - 1){
            step++;
            for (int i = start; i <= end; i++)
                next = max(next, A[i] + i);
            start = end + 1;
            if (next <= end) return -1;
            end = next;
        }
        return step;
    }

Letter Combination of Phone number

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

 string keypad[8]  = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

void generate(string digits, string result, int i,vector<string> &ans)
{

 if(i >= digits.size())
 {
  ans.push_back(result);
  return;
 }


 if(digits[i] <= '1' ||  digits[i] > '9')
   {
       generate(digits, result, i +1, ans);
   }
   else
   {
    string t  = keypad[digits[i] - '2'];
    for(int r  = 0; r < t.size(); r++)
    {
     generate(digits, result + t[r], i+1, ans);
    }
   }
}

vector<string> letterCombinations(string digits) {
  string result = "";      
  vector<string> ans;
  generate(digits, result, 0, ans);
  return ans;
 }

ATOI : Convert String to Integers

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

class Solution {
public:
int atoi(const char *str) {
    int  l = strlen(str);
    if(l <= 0 )
        return 0;
    // scan till we get first non white space
    int i  =0;
    while(i < l)
    {
        if(*(str + i) != ' ')
            break;
        
        i++;
    }
    
    
    if(i >= l)
        return 0;
    
    // check if if sign 
    bool is_positive = true;
    if(str[i] == '+' || str[i] == '-')
    {
        if(str[i] == '-')
            is_positive = false;
        
        i++;
    }
    
   long long num =  0;
    while(i < l)
    {
        if(!(str[i] >= '0'  && str[i] <= '9'))
        {
            break;
        }
        
        num = num * 10 + str[i] - '0';
        long long t  = is_positive ? num :  -1 * num;;
        if(t >= INT_MAX  ||  t<= INT_MIN)
            return (t >= INT_MAX) ? INT_MAX : INT_MIN;
        
        i++;
    }
    
        long long t  = is_positive ? num :  -1 * num;
    if(t >= INT_MAX  ||  t<= INT_MIN)
        return (t >= INT_MAX) ? INT_MAX : INT_MIN;
        
    return  is_positive ? num :  -1 * num;
}
};

Find Median of two sorted arrays of different length

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

 
double findMedianHelper(int A[], int m, int B[], int n, int l, int r)
{
    if(l > r)  
        return findMedianHelper(B, n, A, m,  max(0, (n - m ) / 2), min(n - 1, (m + n ) / 2) );
    
    int i = (l + r ) / 2;
    int j = (m + n ) /2 - i;
    int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);
    int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);
    
    int Ai = (i == m ) ? INT_MAX:  A[i];
    int Bj = (j == n ) ? INT_MAX : B[j];
    
    if(Ai < Bj_1)
        return findMedianHelper(A, m, B, n, i+1, r);
    
    if(Ai > Bj)
        return findMedianHelper(A, m, B, n, i, r-1);
    
    if((m + n ) % 2) return Ai;
    
    return (Ai + max(Ai_1, Bj_1)) / 2.0;
}

double findMedianSortedArrays2(int A[], int m, int B[], int n)
{
    return findMedianHelper(A, m, B, n,  max(0, (m - n ) / 2), min(m -1, (m + n ) / 2));
 }



 double findMedianSortedArrays(int A[], int m, int B[], int n)
{
    return findMedianSortedArrays2(A, m, B, n);
}

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

string addBinary(string a, string b) {
    if(a.size() <= 0)
        return b;
    
    if(b.size() <= 0)
        return a;
    
    string result = "";
    int i = a.size() - 1;
    int j = b.size() - 1;
    
    int carry = 0;
    int sum = 0;
    while(i >=0 && j >= 0)
    {
        sum = a[i] - '0' + b[j] - '0'+ carry;
        carry = sum / 2;
        sum = sum % 2;
        char t = sum + '0';
        result = t+ result ;
        i--;
        j--;
    }
    
    while(i >=0)
    {
        sum = a[i] - '0' +  carry;
        carry = sum / 2;
        sum = sum % 2;
        char t = sum + '0';
        result = t + result ;
        i--;
    }
    
    
    while(j >= 0)
    {
        sum =  b[j] - '0'+ carry;
        carry = sum / 2;
        sum = sum % 2;
        char t = sum + '0';
        result = t + result ;
        j--;
    }
    
    if(carry)
    {
        char t = carry + '0';
    result = t + result ;
    }
    return result;
}

Delete nth Node from the last of Link List

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

   ListNode *removeNthFromEnd(ListNode *head, int n) {

        if(n <= 0  || !head)

                return head;

        // take slow pointer and fast pointer

        ListNode *slow = NULL;

        ListNode *fast = NULL;

        // move fast pointer to n nodes

        while(n > 0)

        {  

            if(!fast)

                fast = head;

            else 

                fast = fast->next;

         

            if(!fast)

                break;

            n--;

        }

        if(!fast)

            return head;

        fast = fast->next;

        // now move slow pointer and fast pointer

        ListNode *prevNode = NULL;

        slow = head;

        while(fast)

        {

            if(!prevNode)

            {

                prevNode = slow;

            }

            else {

                prevNode = prevNode->next;

            }

            fast = fast->next;

        }

        // now need  

        if(!prevNode)

            head =  head->next;

        else

            prevNode->next = prevNode->next->next;

        return head;

}

Median in a stream of Integers

Given an unsorted stream of integers, we need to find the medians at the scanned numbers.  For a given data we need to sort the data and need to find the median. Once the median is calculated we get the data and need to resort the data to find the data. Basically we need to find a data structure where we need to store our data sorted after every insertion in efficient way.

Possible Solutions.

Solution A:

   1. store the unsorted data in array
   2. use median of medians to find the median.

Overall time complexity is quadratic.
insertion O(1)
median find O(N) at each iteration.



Solution B:

Keep the data sorted after every iteration. Once we get the data insert the data at sorted position. This requires shifting of the element. So after every insert we need O(N) time to shift the data but median find will take O(1) now.



Solution  C:
Sorted Link List:
1. insertion O(1)
2. find median O(N)


Solution D:
Balanced Binary Search Tree:
1. Insertion O(log N).
2. Median Find O(1)


Solution E:
Let us try better and simple approach. We can use two heaps simultaneously, a max heap and min heap with two requirements. First condition the max heap contains smallest part of the  half of numbers and min heap contains largest part of half of numbers. So number is max heap are always less than equal to min heap.  Second condition is that number of elements in in max heap is greater than equal to min heap (in case of N is even both have same numbers. In case N is odd then max heap has N/2 + 1 numbers but min heap has N /2 numbers).

If heap is created and N is even then median = average of root elements of two heaps.
If N is odd then median = root of max heap.

So the above approach will have two methods.
one to insert element in heap.
Another to find the median. The first method takes care of two conditions listed above.


Insertion steps:
1. we take two different steps for data insertion based on the total current size. In both the cases we need to add data in max heap only.

let us take even case.
In case of even after addition of data in max heap our size criteria will remain satisfied.

In case of odd numbers then if we add data into max heap then size of max heap = N+2 and size of min heap = N. in this case we need to move one elements from max heap to min heap.


In case total no of elements = 2N. We insert element into the max heap. If the inserted element is less than root element in min heap. We need to just insert element into max heap and we are done.

if element is greater than the min element in the min heap. Need to exchange the root of the max heap and root of min heap. then heapify and insert elements into the max heap.




https://gist.github.com/Vedrana/3675434
 

Find K random sample in Infinite Stream of numbers

Given Infinite stream (incoming stream) where size is not know, we need to find the k random samples where probability of randomness of each element  is same.

Solution:
    This is class of problem called online algorithm. Online algorithm deals with the infinite streams (infinite means size of data set is not known). This class is famous where source is continuous getting data.

Some popular hits in this category are:
1. Find the running median in stream of integers.
2. Find top N searches in search engines.

Let us see why can't we solve this problem in a trivial way. If i want to solve this problem in trivial way i need to just get K random number in a set of N numbers. Now for the above problem we do not know the size of the data so we can't get the K random numbers (or medians in case of median problems).


Let us try different approach with example. Suppose i have to select 2 numbers and i have stream up to 2 numbers, then answer will contain the two numbers. Now the moment i get the third data then we have two options either to escape that 3rd number or to replace the either of 2 numbers with 3rd number. Now while replacing we need to find a way which number to replace. So whole problem lies in finding the probability with which  new number is candidate for set and then the probability of replacing the numbers in the list (list of k set). This is called reservoir sampling. Let us go ahead and try to find an optimal way to find the probability.


First i will put algorithm then i will show the correctness of algorithm (source : Wikipedia

array R[k];    // result
integer i, j;

// fill the reservoir array
for each i in 1 to k do
    R[i] := S[i]
done;

// replace elements with gradually decreasing probability
for each i in k+1 to length(S) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        R[j] := S[i]
    fi
done

#include<iostream>
#include<ctime>
using namespace std;

#define SIZE 10
#define STREAM_AVERAGE 10

int reservoirSample(int sample, int* samples, int size, int count)
{
  if(count < size)
    samples[count] = sample;
  else
    if((rand()%count) < size)
      samples[rand()%size] = sample;
   
  return ++count;
}
 
int main()
{
  int count = 0;
  int samples[SIZE];
  int sample;
  int i = 0;
 
  srand(time(NULL));
 
  cout << "Sample Stream: " << endl;
  while(
        (count < SIZE) || 
        (rand()%STREAM_AVERAGE > 0)
        )
    {
      sample = rand()%1000;
      cout << sample << " ";
 
      count = reservoirSample(sample, samples, SIZE, count);
    }

  cout << endl;
  cout << "Total samples: " << count << endl;
  cout << "Output samples: " << endl;
  for(i = 0;i < SIZE;i++)
    cout << samples[i] << " ";
  cout << endl;
}

Proof of correctness:  Now when sample k + i arrives then probability of occurrence in one of the slot will be 1/ (k+i). since there are k outout slots. So probability of chances in being output is k / (k + i).

chances of not in output  = 1 - k / (k + i) = i / (k + i). so logically it makes sense if we say generate random no between 1 to k + i if it less than k then it is in output otherwise not.


Proof by induction.
Assuming the prior stage worked correctly each element in the output should have K/(K+i-1) chance of being present.
There is i/(K+i) chance that prior output will be unchanged this round. Hence each element has Ki/(K+i)(K+i-1) chance of being output if the unchanging choice is made for this stage.
There is K/(K+i) chance that this something in the output will change
And for each element there is (K-1)/K chance it will not be replaced thus a total of (K-1)/K * K/(K+i) * K/(K+i-1) chance it will not be removed.
So conversely there is a 1/K * K/(K+i) * K/(K+i-1) chance that it will be replaced.
Hence the net chance of the existing elements making it to the next round is the sum of the chance that nothing changed with the chance that it was not the one that changed.
= Ki/(K+i)(K+i-1) + (K-1)K/(K+i-1)(K+i)
=> (Ki + (K-1)K)/(K+i-1)(K+i)
=> K(i+K-1)/(K+i-1)(K+i)
=> K/(K+i)



  

Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

  int reverse(int x) {

   if(x == 0)
    return 0;
   bool isneg = false;
   
   if(x  < 0)
   {
    x  = -x;
    isneg = true;
   }

   int result  = 0; 
   while(x)
   {
    int t  = x % 10;
    x  = x / 10;
    result = result * 10 + t;
   }


   if(isneg)
    return -result;
   else
    return result;

}

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, � , a_k) must be in non-descending order. (ie, a₁ ? a₂ ? � ? a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

[0,1,0,2,1,0,1,3,2,1,2,1],

void generate(vector<int> v, int current_sum,  int target, int i,  vector<int> &candidates, vector<vector<int> > &results)
{
   if(current_sum == target)
   {
    results.push_back(v);
    return;
   }

   if(i >=  candidates.size() || current_sum > target)
    return;

   generate(v, current_sum, target, i+1, candidates, results);
   v.push_back(candidates[i]);
   generate(v, current_sum + candidates[i], target, i, candidates, results);
}

 vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
   vector<int> v;
   vector<vector<int> > results;
   sort(candidates.begin(), candidates.end());
   generate(v, 0, target, 0, candidates, results);
   return results;
} 

Combine

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

void generate(vector<int> current_set, int i, int n,  int targetcount, vector<vector<int> > &result)
{
   if(current_set.size() == targetcount)
   {
    result.push_back(current_set);
    return;
   }

   if(i > n)
    return;

   generate(current_set, i+1, n, targetcount, result);
   current_set.push_back(i);
   generate(current_set, i+1, n, targetcount, result);
}

 vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > result;
  if(n <= 0 || k <= 0)
   return result;

  vector<int> v;
  generate(v, 1, n, k, result);
  return result;
} 

Add Two number represented as Link List

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

    ListNode* getnode(int x)
 {
  ListNode *head  = (ListNode *)malloc(sizeof(ListNode));
  head->val = x;
  head->next = NULL;
  return head;
 }

    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
  if(!l1)
   return l2;

  if(!l2)
   return l1;

  ListNode *head = NULL;
  ListNode *prev = NULL;
  int carry = 0;
  while(l1 && l2)
  {
   int sum  = l1->val + l2->val + carry;
   carry = sum / 10;
   sum = sum % 10;

   ListNode *newnode  = getnode(sum);
   if(!head)
   {
    head = newnode;
    prev = head;
   }
   else
   {
    prev->next = newnode;
    prev = prev->next;
   }

   l1 = l1->next;
   l2 = l2->next;
  }

  while(l1)
  {
   int sum  = l1->val + carry;
   carry = sum / 10;
   sum = sum % 10;

   ListNode *newnode  = getnode(sum);
   prev->next = newnode;
   prev = prev->next;

   l1 = l1->next;
  }

  while(l2)
  {
   int sum  = l2->val + carry;
   carry = sum / 10;
   sum = sum % 10;

   ListNode *newnode  = getnode(sum);
   prev->next = newnode;
   prev = prev->next;

   l2 = l2->next;
  }


  if(carry)
   prev->next = getnode(carry);

  return head;
}

Four Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ? b ? c ? d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

vector<vector<int> > fourSum(vector<int> &num, int target) {
  vector<vector<int> > result;
  if(num.size() <= 3)
   return result;
  sort(num.begin(), num.end());
  int i = 0;
  while(i < num.size())
  {
   int j = i +1 ;

   while(j < num.size())
   {
   int k = j+1;

   int w = num.size() - 1;
   
   while(k < w )
   {
    bool kinc = false, winc = false;
    if((num[i] + num[j] + num[k] + num[w]) == target)
    {
     vector<int> v;
     v.push_back(num[i]);
     v.push_back(num[j]);
     v.push_back(num[k]);
     v.push_back(num[w]);
     result.push_back(v);
     
     k++;
     w--;
     kinc = true;
     winc = true;
    }
    else if((num[i] + num[j] + num[k] + num[w]) < target)
    {
     k++;
       kinc = true;
    }
    else
    {
     w--;
     winc = true;
    }

    while(kinc && k < w && num[k] == num[k-1])
     k++;

    while(winc && k < w && num[w] == num[w+1])
     w--;
             }

       j++;
       while(j < num.size()  && num[j] == num[j-1])
   j++;
  }

    i++;
     while(i < num.size()  && num[i] == num[i-1])
   i++;

  }

  return result;
}

3 SUM closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

int threeSumClosest(vector<int> &num, int target) {
  int result = 0;
  if(num.size() <= 2)
   return result;

  int mindiff  = INT_MAX;
  sort(num.begin(), num.end());
  
  int i = 0;
  
  while(i < num.size())
  {
   int j = i +1 ;
   int k = num.size() - 1;
   while(j < k )
   {
    int x = num[i] + num[j] + num[k];

    if(abs(x  - target) < mindiff)
    {
     mindiff = abs(x - target);
     result = x;
    }

    if(x == target)
               return x;
    else if(x  > target)
     k--;
    else
     j++;
       }

    i++;
  }

 
  return result;
}

3 SUM

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c)
• The solution set must not contain duplicate triplets.

  vector<vector<int> > threeSum(vector<int> &num) {
  vector<vector<int> > result;
  if(num.size() <= 2)
   return result;
  sort(num.begin(), num.end());
  int i = 0;
  while(i < num.size())
  {
   int j = i +1 ;
   int k = num.size() - 1;
   while(j < k )
   {
    bool jinc = false, kinc = false;
    if(num[i] + num[j] + num[k] == 0)
    {
     vector<int> v;
     v.push_back(num[i]);
     v.push_back(num[j]);
     v.push_back(num[k]);
     result.push_back(v);
     j++;
     k--;
     jinc = true;
     kinc = true;
    }
    else if((num[i] + num[j] + num[k]) > 0)
    {
     k--;
                   kinc = true;
    }
    else
    {
     j++;
     jinc = true;
    }

    while(jinc && j < k && num[j] == num[j-1])
     j++;

    while(kinc && j < k && num[k] == num[k+1])
     k--;
      
   }

   i++;
   while(i < num.size()  && num[i] == num[i-1])
    i++;
  }

  return result;
}

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

string getpalin(int i, int j, string s)
{
 string result = "";
 while(i >= 0 && j <= s.size())
 {
  if(s[i] != s[j])
   break;
  i--;
  j++;
 }

 i++;
 j--;
 if(i <= j)
 {
  result = s.substr(i, j - i +1);
 }

 return result;
}

string longestPalindrome(string s) {
 if(s.size() <= 1)
  return s;
 string result = "";
 for(int i  =0; i < s.size(); i++)
 {
  string t  = getpalin(i, i, s);
  if(t.size() > result.size())
   result = t;
 }

 for(int i  =0; i < s.size() -1; i++)
 {
  string t  = getpalin(i, i+1, s);
  if(t.size() > result.size())
   result = t;
 }

 return result;
}

Remove Duplicates from Sorted Link List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

  ListNode *deleteDuplicates(ListNode *head) {
    if(!head  || !(head->next))
  return head;

 ListNode *retAdd = NULL;
 ListNode *prev = NULL;
 while(head)
 {
  if(!prev)
  {
   prev = head;
   retAdd = head;
  }
  else
  {
   if(head->val != prev->val)
   {
     prev->next = head;
     prev = prev->next;
   }
  }

  head = head->next;
  prev->next = NULL;
 }

 return retAdd;
}

Unique Path Generation with obstacles

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

 [

    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {

 int m  = obstacleGrid.size();
   
 if(m <= 0 )
  return 0;

 int n = obstacleGrid[0].size();

 if(obstacleGrid[0][0] == 1)
  return 0;

   int paths[100][100];
   paths[0][0] = 1;

   for(int i = 1; i < n; i++)
    paths[0][i] = (obstacleGrid[0][i] ?  0 : paths[0][i-1]);

   for(int j = 1; j < m; j++)
    paths[j][0] = (obstacleGrid[j][0] ?  0 : paths[j-1][0]);

   for(int i = 1; i < m ; i++)
    for(int j = 1  ; j < n ; j++)
     paths[i][j]  = obstacleGrid[i][j] ?  0 :  paths[i-1][j] + paths[i][j-1];

   return paths[m-1][n-1];
}

Unique Paths Count

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

  int uniquePaths(int m, int n) {    
   if(m <= 0 || n <= 0 )
    return 0;

   int paths[100][100];
   paths[0][0] = 1;

   for(int i = 1; i < n; i++)
   {
    paths[0][i] = 1;
   }

   for(int j = 1; j < m; j++)
   {
    paths[j][0] = 1;
   }


   for(int i = 1; i < m ; i++)
   {
    for(int j = 1  ; j < n ; j++)
    {
     paths[i][j]  = paths[i-1][j] + paths[i][j-1];
    }
   }


   return paths[m-1][n-1];
    }

 

Sets generation

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

void generateSubSets(vector<int> &S, int currentIndex, vector<int> currentSet, vector<vector<int> > &result)
{
  if(currentIndex >= S.size())
  {
   result.push_back(currentSet);
   return;
  }

  generateSubSets(S, currentIndex + 1, currentSet, result);
  currentSet.push_back(S[currentIndex]);
  generateSubSets(S, currentIndex + 1, currentSet, result);

}

 vector<vector<int> > subsets(vector<int> &S) {
              vector<vector<int> > result;
     if(S.size() <= 0 )
     {
      return result;
     }

     sort(S.begin(), S.end());
     vector<int> currentSet;
     generateSubSets(S, 0, currentSet, result);
     return result;
}

Roman To Integers

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

   int romanToInt(string s) {
    
  map<char, int> st;
  char romans[] =  {'I',  'V', 'X',  'L',   'C',    'D',     'M' };

  int ints[] =    {1,     5,  10,   50,   100,    500,    1000 };
  for(int i  = 0; i < 7; i++)
  {
   st[romans[i]] = ints[i];
  }

  int sum  = 0;
  int i = 7;
  if(s.size() <= 0)
  {
   return 0;
  }
 
  sum = st[s[s.size()-1]];

  for(int j  = s.size() - 2; j >= 0; j--)
  {
   int  x = st[s[j]];     
   if(st[s[j]] < st[s[j+1]])
   {
    sum = sum - x;
   }
   else
   {
       sum = sum + x;
   }
  }

  return sum;
}

Integer to Romans conversion

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

string intToRoman(int num) {
 string romans[] =  {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C",  "CD",  "D",   "CM",      "M" };
  int ints[] =       {1,    4,    5,   9,   10,   40,  50,  90, 100,    400,   500,  900,      1000 };
  int i  = sizeof(ints)/ sizeof(ints[0]) - 1;
  string result = "";
  while(i >= 0)
  {
  if(num > 0 )
  {
   if(ints[i] > num)
   {
    i--;
   }
   else
   {
    num = num - ints[i];
    result =   result + romans[i] ; 
   }
  }
  else
  {
   break;
  }
  }

  return result;
}

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, 
Given s = "Hello World",
return 5.

 int lengthOfLastWord(const char *s) {
 int l = strlen(s);
        if(l <= 0)
  return 0;
 // run from the reverse
 // get the first non empty character index;
 int i  = l - 1;
 for(i = l - 1; i >= 0; i--)
 {
  if(s[i] != ' ')
   break;
        }

 int j =0 ;
 for(j = i; j >= 0; j--)
 {
   if(s[j] == ' ')
    break;
 }

 return i - j;
 }

connect next node of binary tree (not a complete binary tree)

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

 TreeLinkNode* nextFind(TreeLinkNode *root)
 {
  if(!root)
   return NULL;
  root = root->next;
  TreeLinkNode *retAdd = NULL;
  while(root)
  {
   if(root->left)
   {
    retAdd = root->left;
    break;
   }

   if(root->right)
   {
    retAdd = root->right;
    break;
   }


   root = root->next;
  }

  return retAdd;
 }


 void connectR(TreeLinkNode * root)
 {
  if(!root)
   return;

  if(root->left)
  {
   if(root->right)
   {
    root->left->next = root->right;
    root->right->next = nextFind(root);
    connectR(root->right);
   }
   else
   {
    // no right
    root->left->next = nextFind(root);
    connectR(root->right);
   }

   connectR(root->left);
  }

  else if(root->right)
  {
   root->right->next = nextFind(root);
   connectR(root->right);
  }

  else
  {
   connectR(nextFind(root));
  }
 }

 

 void connect(TreeLinkNode * root) {
  if(!root)
   return;

  root->next = NULL;
  connectR(root);
}