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);
}