C++ Leetcode

addNthlinklistNode.cpp

#include <iostream>
using namespace std;

/* Node Structure */
struct Node {
    int val;
    Node *next;
};

/* Create New Node */
Node *createNode(int data)
{
    Node *newNode = new Node();
    newNode->val = data;
    newNode->next = NULL;
    return newNode;
}


class InsertNthNode {
public:
    Node* _insertNthNode(Node* head, int pos, int data) {
        if (head != NULL) {
            Node* prev = nullptr;
            Node* curr = head;
            Node* btw = nullptr;
            for(int i=1; i<pos; i++) {
                if (curr->next != nullptr) {
                    prev=curr;
                    curr=curr->next;
                }
                else {
                    cout << "Value out of Bound!" << endl;
                    return nullptr;
                }
            }
            cout << "Current Position Value : " << prev->val << endl;
            cout << "Next Position Value : " << curr->val << endl;
            // insert a new node.
            btw = createNode(data);
            btw->val=data;
            btw->next=prev->next;
            prev->next=btw;
            return head;
        }
        else {
            cout << "Value out of Bound! : " << endl;
            return nullptr;
        }
    }
};

/* Insert Node in Binary Search Tree */
Node *insertNode(Node *root, int val)
{
    if (root == NULL)
        root = createNode(val);
    else
        root->next = insertNode(root->next, val);
    return root;
}

void traverse(Node *head) {
    if(head==NULL) {
        return;
    }
    else {
        cout << head->val << ",";
        traverse(head->next);
    }
}

Node* reverse(Node *head) {
    Node* prev;
    Node* curr;
    // Setting tail.
    prev = nullptr;
    while (head != nullptr) {
        curr = head;
        head = head->next;
        curr->next = prev;
        prev = curr;
    }
    return prev;
}

Node* deleteNode(Node* head, int val) {
    if (head != NULL) {
        if (head->val == val) return head = NULL;
        Node *curr = head;
        Node *prev = NULL;
        while(curr->val != val) {
            prev = curr;
            if (curr->next != NULL) curr=curr->next;
            else return head;
        }
        if (prev != NULL) prev->next = curr->next;
        else head = curr->next;
    }
    return head;
}

int main()
{
    Node *root = NULL;
    Node *head = NULL;
    Node *head2 = NULL;
    Node *root2 = NULL;
    /* Insert Node with Value */
    root = insertNode(root, 10);
    root = insertNode(root, 5);
    root = insertNode(root, 12);
    root = insertNode(root, 11);
    root = insertNode(root, 14);
    
    // Second Linklist for checking Intersection.
    root2 = insertNode(root2, 15);
    root2 = insertNode(root2, 19);
    root2 = insertNode(root2, 11);
    root2 = insertNode(root2, 20);
    root2 = insertNode(root2, 24);
  
    
    cout << "Insert Values to build linklist:" << endl;
    traverse(root);
    cout << endl;
    
    InsertNthNode obj;
    root = obj._insertNthNode(root, 2, 88);
    cout << "Insert nth Value to link list:" << endl;
    traverse(root);
    cout << endl;
    cout << "Reversed Linklist:" << endl;
    head = reverse(root);
    traverse(head);
    cout << endl;
    cout << "Delete a node with value from link list:" << endl;
    traverse(root2);
    cout << " => ";
    head2 = deleteNode(root2, 20);
    traverse(head2);
    cout << endl;
    return 0;
}

anagramSearch.cpp

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        // If any string s, p is empty.
        if (s.empty()|| p.empty()) {
            return result;
        }
        // Hashmap for pattern (p) matching.
        unordered_map<char,int>pattern_hash;
        for (const char c : p) {
            pattern_hash[c] += 1;
        }
        int left = 0, right = 0;
        auto count = p.length();
        while (right < s.length()) {
            // Move right everytime, if the character exists in p's hash, decrease the count.
            // Current hash value >= 1 means the character is existing in p.
            if (pattern_hash[s[right++]]-- >= 1) count--;
            // When the count is down to 0, means we found the right anagram.
            // Then add window's left to result list.
            if (count == 0) result.push_back(left);
            // If we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window.
            // ++ to reset the hash because we kicked out the left.
            // Only increase the count if the character is in p.
            // The count >= 0 indicate it was original in the pattern_hash, cuz it won't go below 0.
            if (right - left == p.length() && pattern_hash[s[left++]]++ >= 0) count++;
        }
        return result;
    }
};

int main()
{ 
    // Anagrams.
    string s = "abcab";
    string p = "cb";
    // Result.
    Solution obj;
    auto vec = obj.findAnagrams(s, p);
    // TODO: Remove temprory loop.
    int i;
    for (i=0; i<vec.size(); i++) {
        cout << vec[i] << ",";
    }
    return 0;
}

binarySearchTreeLCA.cpp

#include <iostream>
using namespace std;

/* BstNode Structure */
struct BstNode
{
    int data;
    BstNode *left;
    BstNode *right;
};

/* Create New BstNode */
BstNode *createNode(int data)
{
    BstNode *newNode = new BstNode();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

/* Insert Node in Binary Search Tree */
BstNode *insertNode(BstNode *root, int data)
{
    if (root == NULL)
        root = createNode(data);
    else if (data <= root->data)
        root->left = insertNode(root->left, data);
    else
        root->right = insertNode(root->right, data);
    return root;
}

// Code that goes into leetcode or hackarank.
class Solution {
public:
    BstNode* lowestCommonAncestor(BstNode* root, int p, int q) {
        if (!root || root->data == p || root->data == q) return root;
        BstNode* left = lowestCommonAncestor(root->left, p, q);
        BstNode* right = lowestCommonAncestor(root->right, p, q);
        return !left ? right : !right ? left : root;
    }
};

// Main Function.
int main()
{
    BstNode *root = NULL;
    /* Insert Node with Value */
    root = insertNode(root, 3);
    root = insertNode(root, 1);
    root = insertNode(root, 6);
    root = insertNode(root, 4);
    root = insertNode(root, 5);
    root = insertNode(root, 9);
    
    /* Lowest Common Ancestor*/
    Solution obj;
    root = obj.lowestCommonAncestor(root, 1, 9);
    cout << "the root is" << root->data;
    return 0;
}

cloneLinklistwithRandomPointer.cpp

#include <iostream>
using namespace std;


// Structure of linked list Node
struct Node
{
    int data;
    Node *next,*random;
    Node(int x)
    {
        data = x;
        next = random = nullptr;
    }
};

// Utility function to print the list.
void print(Node *start)
{
    Node *ptr = start;
    while (ptr)
    {
        cout << "Data = " << ptr->data << ", Random  = "
        << ptr->random->data << endl;
        ptr = ptr->next;
    }
}

// This function clones a given linked list
// in O(1) space
Node* clone(Node *start)
{
    Node* curr = start, *temp;
    
    // insert additional node after
    // every node of original list
    while (curr)
    {
        temp = curr->next;
        
        // Inserting node
        curr->next = new Node(curr->data);
        curr->next->next = temp;
        curr = temp;
    }
    
    curr = start;
    
    // adjust the random pointers of the
    // newly added nodes
    while (curr)
    {
        curr->next->random = curr->random->next;
        
        // move to the next newly added node by
        // skipping an original node
        curr = curr->next?curr->next->next:curr->next;
    }
    
    Node* original = start, *copy = start->next;
    
    // save the start of copied linked list
    temp = copy;
    
    // now separate the original list and copied list
    while (original && copy)
    {
        original->next = original->next? original->next->next : original->next;
        copy->next = copy->next?copy->next->next:copy->next;
        original = original->next;
        copy = copy->next;
    }
    
    return temp;
}

// Driver code
int main()
{
    Node* start = new Node(1);
    start->next = new Node(2);
    start->next->next = new Node(3);
    start->next->next->next = new Node(4);
    start->next->next->next->next = new Node(5);
    
    // 1's random points to 3
    start->random = start->next->next;
    
    // 2's random points to 1
    start->next->random = start;
    
    // 3's and 4's random points to 5
    start->next->next->random =
    start->next->next->next->next;
    start->next->next->next->random = start->next->next->next->next;
    
    // 5's random points to 2
    start->next->next->next->next->random = start->next;
    
    cout << "Original list : \n";
    print(start);
    
    cout << "\nCloned list : \n";
    Node *cloned_list = clone(start);
    print(cloned_list);
    
    return 0;
}

copyListWithRandomPointer.cpp

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head){
        if (head == nullptr) return head;
        RandomListNode* curr = head, *temp;
        
        while (curr)
        {
            temp = curr->next;
            curr->next = new RandomListNode(curr->label);
            curr->next->next = temp;
            curr = temp;
        }
        
        curr = head;
        while (curr)
        {
            if (curr->random != nullptr) curr->next->random = curr->random->next;
            else curr->next->random = nullptr;
            curr = curr->next?curr->next->next:curr->next;
        }
        if (head->next != nullptr) {
            RandomListNode* original = head, *copy = head->next;
            temp = copy;
            while (original && copy)
            {
                original->next = original->next? original->next->next : original->next;
                copy->next = copy->next?copy->next->next:copy->next;
                original = original->next;
                copy = copy->next;
            }
        }
        return temp;
    }

};

DeleteNode.cpp

Node* deleteNode(Node* head, int val) {
    if (head != NULL) {
        Node* curr = head;
        Node* prev = nullptr;
        while(curr->val != val) {
            prev = curr;
            if (curr->next != nullptr) curr=curr->next;
            else return nullptr;
        }
        if (prev != nullptr) prev->next = curr->next;
        else curr=nullptr;
    }
    return head;
}

isPalindrome.cpp

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return true;
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast->next!=NULL&&fast->next->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
        }
        slow->next=reverseList(slow->next);
        slow=slow->next;
        while(slow!=NULL){
            if(head->val!=slow->val)
                return false;
            head=head->next;
            slow=slow->next;
        }
        return true;
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* pre=NULL;
        ListNode* next=NULL;
        while(head!=NULL){
            next=head->next;
            head->next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
};

LRUCache.cpp

#include <unordered_map>
#include <list>
#include <iostream>
using namespace std;

// Time:  O(1), per operation.
// Space: O(k), k is the capacity of cache.

class LRUCache {
public:
    LRUCache(int capacity) : cache_capacity(capacity) {}
    int get(int key) {
        if (uhashmap_itr.find(key) != uhashmap_itr.end()) {
            // It key exists, update it.
            const auto value = uhashmap_itr[key]->second;
            update(key, value);
            return value;
        } else {
            return -1;
        }
    }
    void put(int key, int value) {
        // If cache is full while inserting, remove the last one.
        if (uhashmap_itr.find(key) == uhashmap_itr.end() && doublylist.size() == cache_capacity) {
            auto del = doublylist.back(); doublylist.pop_back();
            uhashmap_itr.erase(del.first);
        }
        update(key, value);
    }
private:
    list<pair<int, int>> doublylist; // key, value
    unordered_map<int, list<pair<int, int>>::iterator> uhashmap_itr; // key, list iterator
    int cache_capacity;
    void update(int key, int value) {
        auto it = uhashmap_itr.find(key); // Find if key in unordered_hashmap.
        if (it != uhashmap_itr.end()) { // If we found the key.
            doublylist.erase(it->second); //
        }
        doublylist.emplace_front(key, value); // Add key, value to front of list.
        uhashmap_itr[key] = doublylist.begin();
    }
};

int main() {
    //int capacity  = 3;
    LRUCache cache = LRUCache(2);
    //obj.LRUCache(capacity);
    //int param1 = obj.get(3);
    cache.put(1, 11);
    cache.put(2, 22);
    int out;
    out  = cache.get(1);       // returns 11
    cout << out << endl;
    cache.put(3, 33);    // evicts key 2
    out = cache.get(2);       // returns -1 (not found)
    cout << out << endl;
    cache.put(4, 44);    // evicts key 1
    out = cache.get(1);       // returns -1 (not found)
    cout << out << endl;
    out = cache.get(3);       // returns 33
    cout << out << endl;
    out = cache.get(4);       // returns 44
    cout << out << endl;
    //int param2 = obj.get(3);
    //cout << param2;
    return 0;
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

maze.cpp

#include<stdio.h>
#define N 4

bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);

void printSolution(int sol[N][N])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            printf(" %d ", sol[i][j]);
        printf("\n");
    }
}

bool isSafe(int maze[N][N], int x, int y)
{
    if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
        return true;
    return false;
}

bool solveMaze(int maze[N][N])
{
    int sol[N][N] = { {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };
    
    if(solveMazeUtil(maze, 0, 0, sol) == false)
    {
        printf("Solution doesn't exist");
        return false;
    }
    printSolution(sol);
    return true;
}

/* A recursive utility function to solve Maze problem */
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
    if(x == N-1 && y == N-1)
    {
        sol[x][y] = 1;
        return true;
    }
    
    if(isSafe(maze, x, y) == true)
    {
        // mark x,y as part of solution path
        sol[x][y] = 1;
        
        /* Move forward in x direction */
        if (solveMazeUtil(maze, x+1, y, sol) == true)
            return true;
        
        /* If moving in x direction doesn't give solution then
         Move down in y direction  */
        if (solveMazeUtil(maze, x, y+1, sol) == true)
            return true;
        
        /* If none of the above movements work then BACKTRACK:
         unmark x,y as part of solution path */
        sol[x][y] = 0;
        return false;
    }
    
    return false;
}

// driver program to test above function
int main()
{
    int maze[N][N]  =  {
        {1, 1, 0, 0},
        {1, 1, 1, 1},
        {0, 1, 0, 0},
        {1, 1, 1, 1}
    };
    
    solveMaze(maze);
    return 0;
}

reverseImage.py

# Python 
class Solution:
def rotate(self, A):
         A.reverse()
         for i in range(len(A)):
             for j in range(i):
                 A[i][j], A[j][i] = A[j][i], A[i][j]
                 
          
                
# C++ 50 times faster
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int a = 0;
        int b = n-1;
        while(a<b){
            for(int i=0;i<(b-a);++i){
                swap(matrix[a][a+i], matrix[a+i][b]);
                swap(matrix[a][a+i], matrix[b][b-i]);
                swap(matrix[a][a+i], matrix[b-i][a]);
            }
            ++a;
            --b;
        }
    }
};


# Python Slow
class Solution:
    def rotate(self, A):
        a = 0
        b = len(A)-1
        while(a<b):
            for i in range(b-a):
                A[a][a+i], A[a+i][b] = A[a+i][b], A[a][a+i]
                A[a][a+i], A[b][b-i] = A[b][b-i], A[a][a+i]
                A[a][a+i], A[b-i][a] = A[b-i][a], A[a][a+i]
            a=a+1
            b=b-1

reverselinklist.py

class Solution:
# @param {ListNode} head
# @return {ListNode}
def reverseList(self, head):
    prev = None
    while head:
        curr = head
        head = head.next
        curr.next = prev
        prev = curr
    return prev

serializeDeserialize.cpp

#include <iostream>
using namespace std;


/* Node Structure */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    // TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/* Create New Node */
TreeNode *createNode(int data)
{
    TreeNode *newNode = new TreeNode();
    newNode->val = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) return "#";
        return to_string(root->val)+","+serialize(root->left)+","+serialize(root->right);
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        return deserialize_handler(data);
    }
    TreeNode* deserialize_handler(string& data) {
        if (data[0]=='#') {
            if(data.size() > 1) data = data.substr(2);
            return nullptr;
        } else {
            auto pos = data.find(',');
            int val = stoi(data.substr(0,pos));
            data = data.substr(pos+1);
            TreeNode* node = createNode(val);
            node->left = deserialize_handler(data);
            node->right = deserialize_handler(data);
            return node;
        }
    }
};

/* Insert Node in Binary Search Tree */
TreeNode *insertNode(TreeNode *root, int val)
{
    if (root == NULL)
        root = createNode(val);
    else if (val <= root->val)
        root->left = insertNode(root->left, val);
    else
        root->right = insertNode(root->right, val);
    return root;
}

void traverse(TreeNode *root) {
    if(root==NULL) {
        return;
    }
    else {
        cout << root->val << ",";
        traverse(root->left);
        traverse(root->right);
    }
}

int main()
{
    TreeNode *root = NULL;
    /* Insert Node with Value */
    root = insertNode(root, 10);
    root = insertNode(root, 5);
    root = insertNode(root, 12);
    root = insertNode(root, 11);
    root = insertNode(root, 14);

    
    Codec obj;
    auto data = obj.serialize(root);
    TreeNode *myroot = NULL;
    myroot = obj.deserialize(data);
    traverse(myroot);
    return 0;
}

http://www.geeksforgeeks.org/clone-linked-list-next-random-pointer-o1-space/

class Solution(object):
def twoSum(self, nums, target):
lookup = {}
for i, num in enumerate(nums):
if target - num in lookup:
return [lookup[target - num], i]
lookup[num] = i
return []