Best Time to Buy and Sell Stock

/*
Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit
*/
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = prices.size();
        if(size<=1) return 0;
        int minv = 0;
       
        int maxProfit = 0;
       
        int i;
        for(i=1; i<size; i++){
          if(prices[i]<prices[minv]) minv = i;
          if(prices[i]-prices[minv]>=maxProfit) maxProfit = max(prices[i]-prices[minv], maxProfit);
        }
       
        return maxProfit;
    }
};

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i, j;
        int maxProfit = 0;
        int profit;
        int days = prices.size();
        for(i=0;i<days-1;i++){
         for(j=i+1;j<days;j++){
           profit = prices[j] - prices[i];
           if (profit > maxProfit){
           maxProfit = profit;
           }
         }   
        }
        return maxProfit; 
    }
};

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int maxProfit = 0;
        int size = prices.size();
        findMaxProfit(prices, 0, 1, maxProfit, size);
        return maxProfit;
    }
    void findMaxProfit(vector<int> &prices, int i, int j, int & maxProfit, int const size){
       if(i>=j||i>size-2||j>size-1) return;
       int profit = prices[j] - prices[i];
       if(profit > maxProfit) maxProfit = profit;
       findMaxProfit(prices, i+1, j, maxProfit, size);
       findMaxProfit(prices, i, j+1, maxProfit, size);
    }
};

Binary Tree Maximum Path

/*
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

*/

void findMaxPath(Node<int>* curr, int & cSum, int & maxSum){

if(curr==NULL){



cSum = 0;

return;



}

int lsum = 0;

int rsum = 0;



findMaxPath(curr->Left, lsum, maxSum);

findMaxPath(curr->Right, rsum, maxSum);

cSum = max(curr->Value, max(curr->Value+lsum, curr->Value+rsum));

maxSum = max(maxSum, max(cSum, curr->Value+lsum+rsum));

}

Flatten Binary Tree to Linked List

---Flatten the binary tree

ListNode* listHead = new ListNode(0);



ListNode* prep = listHead;

findNextNode(root, prep);

ListNode* currListHead = listHead->next;
  while(currListHead != NULL){

if(currListHead->next != NULL)

cout << currListHead->val << "->";

else cout << currListHead->val;



currListHead = currListHead->next;

void findNextNode (Node<int>* curr, ListNode* & prep){

if(curr == NULL) {

return;



}

ListNode* currNode = new ListNode(curr->Value);

if (prep != NULL) prep->next = currNode;


prep = currNode;

findNextNode(curr->Left, prep);

findNextNode(curr->Right, prep);

}

Add two numbers

/**
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

**/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        //case 1: l1 or l2 is empty
        if (l1==NULL) return l2;
        if (l2==NULL) return l1;
    
        //normal case
        ListNode* newHead = NULL;
        ListNode* prep = NULL;
        ListNode* curr = NULL;
        int sum;
        int reminder;
        bool plus;
       
        newHead = new ListNode(l1->val+l2->val);
        if(newHead->val >= 10){
        newHead->val = newHead->val - 10;
        plus = true;
        }
        else{
        plus = false;
        }
        prep = newHead;
        l1=l1->next;
        l2=l2->next;
       
        while((l1!=NULL)&&(l2!=NULL)){
         sum = l1->val+l2->val;
         if(plus) sum++;
        
         if(sum>=10){
         sum = sum - 10;
         plus = true;
         }
         else {
         plus = false;
         }
        
         curr = new ListNode(sum);
         prep->next = curr;        
         prep = curr;
         l1=l1->next;
         l2=l2->next;
        }
       
        curr = NULL;
       
        if(l1!=NULL){
        curr = l1;
        }
       
        if(l2!=NULL){
        curr = l2;
        }
       
        if((l1==NULL)&&(l2==NULL)&&plus){
        curr = new ListNode(1);
        plus = false;
        }
       
        while(curr!=NULL){
        if(plus) curr->val++;
        if(curr->val >= 10){
        curr->val = curr->val-10;
        plus = true;
        }
        else{
        plus = false;
        }
        prep->next = curr;
        prep = curr;
        curr = curr->next;
        }
       
        if(plus){
        curr = new ListNode(1);
        prep->next = curr;
        }
       
        return newHead;
    }
};

Remove Nth Node From End

/*Given a linked list, remove the nth 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.

*/

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

*/    

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

// Start typing your C/C++ solution below

// DO NOT write int main() function

if(n<=1){

cout << "invalid input" << endl;

return head;



}

ListNode* prep = NULL;

ListNode* curr = head;

ListNode* next = head->next;

int count = n-1;

while (count > 0 && next != NULL){



next = next->next;

count--;

}

if(count>0){

cout << "The linked list is not long enough" << endl;

return head;



}

while (next != NULL){



prep = curr;

curr = curr->next;

next = next->next;

}

if(prep == NULL) {

return head->next;



}

else{



prep->next = curr->next;

return head;



}

}

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 isPalindrome(string s) {

// Start typing your C/C++ solution below

// DO NOT write int main() function

if (s.empty()){

cout << "empty string is palindrome." << endl;

return true;



}

string::iterator front = s.begin();

string::iterator behind = s.end() - 1;

while(front < behind){

while(!isValidLetter(*front)) front++;

while(!isValidLetter(*behind)) behind--;





if(toLowerCase(*front)==toLowerCase(*behind)){



front++;

behind--;

} else {

cout << "found non-palindrome chars." << endl;

return false;



}

}

return true;



}

Recursive Function

#include <iostream>
#include "Node.h";
using namespace std;

//factorial number
int factoria(int num){
//initial value
if (num == 0){
return 1;
} else {
return num * factoria(num-1);
}
}

//find the largest in a array
int FindLargest(int* listArray, int lowerIndex, int upperIndex){
//base class
if(lowerIndex == upperIndex){
return listArray[lowerIndex];
}

//recursive call
int currMax = FindLargest(listArray, lowerIndex+1, upperIndex);

if(currMax > listArray[lowerIndex]){
return currMax;
} else {
return listArray[lowerIndex];
}
}

void printRevertLinkedList(Node* node){
//base case
if(node->next == NULL){
cout << node->value << ",";
return;
}

printRevertLinkedList(node->next);
cout << node->value << ",";
}

void printRevertedLinkedListSimp(Node* node){
if(node != NULL){
printRevertLinkedList(node->next);
cout << node->value << ",";
}
}

int Fabonacci(int number){
//validate the input parameters
if(number <= 0){
cout << "invalid input." << endl;
return 0;
}

//base class
if (number == 1 || number == 2){
return 1;
}

return Fabonacci(number-1)+Fabonacci(number-2);
}

//tower of hanoi
void moveTower(int count, int node1, int node2, int node3){
if (count <= 0){
//cout << "the end of round from " << node1 << " to " << node2 << endl;
return;
}

moveTower(count-1, node1, node3, node2);
cout << "move the single one from " << node1 << " to " << node2 << endl;
moveTower(count-1, node3, node2, node1);
}


//change from decimal to binary -- positive integer
void decimalToBinary(int number, int base){
//validate input parameter
if (number < 0){
cout << "Negative input is invalid. " << endl;
}

//base case
if (number == 0){
return;
}

decimalToBinary(number/base, base);
cout << number%base;
}