Max Amplitude -- Amazon

#include<iostream>
#include<fstream>
#include<sstream>
#include<vector>
#include<unordered_set>
#include<time.h>
#include<stdio.h>

using namespace std;

struct BTNode {
     int val;
     BTNode *left;
     BTNode *right;
     BTNode(int x) : val(x), left(NULL), right(NULL) {}
};

int computeAmp(vector<int> &path){
int min= INT_MAX, max=INT_MIN;
for(int i=0;i<path.size();++i){
if(min> path[i]){
min = path[i];
}
if(max < path[i]){
max = path[i];
}
}
return abs(max-min);
}

int returnMax(vector<int> &res){
int max=INT_MIN;
for(int i=0;i< res.size();++i){
if(max < res[i]){
max = res[i];
}
}
return max;
}

void maxAmpHelp(BTNode *root, vector<int> &path, vector<int> &res){
if(!root->left && !root->right){
path.push_back(root->val);
int v = computeAmp(path);
res.push_back(v);
}
else{
path.push_back(root->val);
if(root->left){
   maxAmpHelp(root->left,path,res);
path.pop_back();
}
if(root->right){
   maxAmpHelp(root->right,path,res);
path.pop_back();
}
}
return;
}

int maxAmplitude (BTNode *root){
vector<int> res, path;
maxAmpHelp(root, path, res);
int maxAmp = returnMax(res);
return maxAmp;
}


int main(){
 BTNode *root = new BTNode (1);
 root->left = new BTNode (2);
 root->right = new BTNode (6);
 root->left->left = new BTNode (10);
 root->left->right = new BTNode (-22);
 root->right->left = new BTNode (-36);
 root->right->right = new BTNode (8);
 root->left->left->left = new BTNode(5);
 root->left->right->right = new BTNode(56);

 int max = maxAmplitude(root);      //output == 78
 cout<<endl<<"Max Amplitude is:"<< max <<endl;
 getchar();
 return 0;
}

Delete Vowels -- Amazon

#include<iostream>
#include<fstream>
#include<sstream>
#include<vector>
#include<unordered_set>
#include<time.h>
#include<stdio.h>

using namespace std;

bool checkVowel (char c){
if(c>='A' && c<='Z'){
c = c - 'A' +'a';
}
if(c=='a' || c=='e' || c=='i' || c=='o' || c=='u'){
return true;
}
return false;
}
/*
void removeVowels(string &ori){
int len = ori.length();
if(len ==0)return;

int count = 0;
for(int i=0; i< len;++i){
if(checkVowel(ori[i]) == true){        //if ori[i] is a vowal character, 'count' slots ++, which should be deleted.
            count++;
}
else{
ori[i-count] = ori[i];             //left shift accumulated 'count' slots for an non-vowel character, modify ori string directly.
}
}
ori[len-count] = '\0';
for(int i= len-count;i< len;++i){
ori[i] = NULL;
}
}
*/
string removeVowels(string &ori){
string res = "";
int len = ori.length();
if(len ==0)return res;

for(int i=0;i<len;++i){
   if(checkVowel(ori[i])== false){         //if ori[i] is not a vowel character, insert it to res string's tail.
res.insert(res.end(),ori[i]);
}
}
return res;
}


int main(){
string original = "AbcdeFghijKiou123";
cout<<"Before : "<< original << endl;
string after = removeVowels(original);
cout<<"After : "<< after << endl;
getchar();
return 0;
}

atoi -- Java version

public int atoi(String str) {
 if (str == null || str.length() < 1)
  return 0;
 
 // trim white spaces
 str = str.trim();
 
 char flag = '+';
 
 // check negative or positive
 int i = 0;
 if (str.charAt(0) == '-') {
  flag = '-';
  i++;
 } else if (str.charAt(0) == '+') {
  i++;
 }
 // use double to store result
 double result = 0;
 
 // calculate value
 while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
  result = result * 10 + (str.charAt(i) - '0');
  i++;
 }
 
 if (flag == '-')
  result = -result;
 
 // handle max and min
 if (result > Integer.MAX_VALUE)
  return Integer.MAX_VALUE;
 
 if (result < Integer.MIN_VALUE)
  return Integer.MIN_VALUE;
 
 return (int) result;
}

Delete elements in Linked List

#include <stdio.h>

#include <iostream>

using namespace std;

struct ListNode{

int data;

ListNode *next;

ListNode(int d){

data = d;

next = NULL;

}

};

ListNode* deleteElement(ListNode* head , int elem){

ListNode* dummy = new ListNode(-1);

ListNode* prev=dummy;

ListNode* cur=head;

while(cur){

while(cur && cur->data!= elem){

prev = cur;

cur = cur->next;

}

prev->next = cur->next;     //

delete cur;                 //

cur = prev->next;           //

}

return dummy->next;

}

void print(ListNode* head){

ListNode *p = head;

while(p){

cout<<p->data<<" ";

p=p->next;

}

}

void main(int argc, char** argv){

ListNode *p1= new ListNode(1);

ListNode *p2 = new ListNode(2);

ListNode *p3 = new ListNode(3);

ListNode *p4 = new ListNode(1);

ListNode *p5 = new ListNode(1);

ListNode *p6 = new ListNode(6);

ListNode *p7 = new ListNode(1);

p1->next = p2;

p2->next = p3;

p3->next = p4;

p4->next = p5;

p5->next = p6;

p6->next = p7;

int deleteElem = 1;

ListNode *res = deleteElement(p1, deleteElem);

print(res);

getchar();

return;

}

Roman To Integer -- Leetcode

(1) Roman to Integer -- Leetcode
Given a roman numeral, convert it to an integer.

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

/* Romans:

I  V  X    L    C     D       M

1  5  10  50  100  500  1000

*/

Answer:
class Solution {
public:
    inline int c2n(char c) {
      switch(c) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return 0;      
      }
   }
   int romanToInt(string s) {
      // Start typing your C/C++ solution below
      // DO NOT write int main() function
      int result=0;
      for(int i =0; i< s.size(); i++)
      {
        if(i>0&& c2n(s[i]) > c2n(s[i-1]))
        {
          result +=(c2n(s[i]) - 2*c2n(s[i-1]));
        }
        else
        {
          result += c2n(s[i]);
        }
      }
      return result;
   }
};


(2)  Integer to Roman -- Leetcode

Given an integer, convert it to a roman numeral.

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

class Solution {
public:
    string intToRoman(int num) {
        string str;  
        string symbol[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};  
        int value[]=    {1000,900,500,400, 100, 90,  50, 40,  10, 9,   5,  4,   1};  
        for(int i=0;num!=0;++i)
        {
            while(num>=value[i])
            {
                num-=value[i];
                str+=symbol[i];
            }
        }
        return str;
    }
};

CopyList with Random Pointer -- Leetcode

Question:

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Answer:
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null)return null;
       
       
        HashMap<RandomListNode,RandomListNode> hmap = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode newListHead = new RandomListNode(head.label);
        hmap.put(head, newListHead);
       
        RandomListNode prevNew = newListHead, curOld = head.next, curNew=null;
       
        while(curOld!= null){                                                       //copy label and next
            curNew = new RandomListNode(curOld.label);
            hmap.put(curOld,curNew);
            prevNew.next = curNew;
            prevNew = curNew;
            curOld = curOld.next;
        }
        prevNew.next = null;
       
        curOld = head; curNew = newListHead;
        while(curOld!= null){                                                       //copy random
            curNew.random = hmap.get(curOld.random);
            curOld = curOld.next;
            curNew = curNew.next;
        }
       
        return newListHead;
    }
}

Divide two integers -- Leetcode

Question:
Divide two integers without using multiplication, division and mod operator.

Answer:
Method: Using Divide and Conquer method. Quickly!!!

class Solution {
public:
    int divide(int dividend, int divisor){      
       unsigned long dvd = dividend < 0 ? -dividend : dividend;
       unsigned long dvs = divisor < 0 ? -divisor : divisor;
       if (dvd < dvs) return 0;
     
       bool nega = (dividend > 0) ^ (divisor > 0);          //nega = true: -xxx; =false: +xxx.
     
       unsigned long originDvs = dvs;
       int power = 0;
       unsigned long result = 0;
     
       while (dvs < dvd){
            dvs = dvs << 1;
            power++;
       }                                    //dvd < dvs now
       while (dvd >= originDvs){
            if (dvd >= dvs){
                 dvd -= dvs;
                 result += (unsigned long) 1 << power;
            }
            while(dvd < dvs){                    //to get biggest dvs < dev everytime
                dvs = dvs >> 1;
                power--;
            }
       }
     
       return nega? -result : result;
   }
};

Remove duplicates in sorted array II -- Leetcode

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

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

Your function should return length = 5, and A is now [1,1,2,2,3].

Answer:

public class Solution {
    public int removeDuplicates(int[] A) {
        boolean flag=false;
        int count=0;
        for(int i=1;i<A.length;++i){
            if(A[i]==A[i-1] && flag==false){
                flag = true;                       //second same elem.
                A[i-count] = A[i];
            }
            else if(A[i]==A[i-1] && flag==true){
                count++;                        //elem. needed to be deleted.
            }
            else if(A[i]!=A[i-1]){
                flag = false;                  //flag initia to false for a new different elem.
                A[i-count] = A[i];
            }
        }
        return A.length - count;
    }
}

Remove duplicates in an array -- Java version

class RemoveDuplicates{
    public static int[] removeDuplicates (int[] a){
        HashMap<Integer,Boolean> hmap = new HashMap<Integer,Boolean>();
     
        int count = 0;
        for(int i=0;i<a.length;++i){
            if(hmap.containsKey(a[i])== false){
                hmap.put(a[i],true);
                a[i-count] = a[i];
            }
            else{
                count++;
            }
         
        }
        int[] res = java.util.Arrays.copyOfRange(a, 0, a.length-count);
        return res;
    }
 
    public static void main(String[] args) {
     
        int[] arr = {1,1,2,2,3,4,4,5,5,5,1,1,3,6};
        int[] res = removeDuplicates(arr);
        System.out.println(Arrays.toString(res));    
    }
}

Find a unique number in an array -- Amazon

Question:
Input:   int[] arr = {1,1,2,2,3,4,4,5,5,5,1,1,3,6};
Output: 6


Answer:
Java version:
import java.util.HashMap;

public class Uniquenum {
    public static int uniqueMy(int[] a){
        HashMap<Integer,Boolean> hmap = new HashMap<Integer,Boolean>();
        for(int i=0;i<a.length;++i){
            if(hmap.containsKey(a[i])== false){
                hmap.put(a[i],true);
            }
            else if(hmap.get(a[i])==true){
                hmap.put(a[i],false);
            }
        }
       
        for(int i=0;i<a.length;++i){
            if(hmap.get(a[i]) == true){
                return a[i];
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1,1,2,2,3,4,4,5,5,5,1,1,3,6};
        int uniquenum = uniqueMy(arr);
        System.out.println("Unique number is: " + uniquenum);
       
    }
}