How to construct tree from preorder and inorder

Given pre-order and in-order traversals of a binary tree, write a function to reconstruct the tree.

For example, given the following preorder traversal:

[a, b, d, e, c, f, g]

And the following inorder traversal:

[d, b, e, a, f, c, g]

You should return the following tree:

    a
   / \
  b   c
 / \ / \
d  e f  g

Example:

Input: preorder = {'a', 'b', 'd', 'e', 'c', 'f', 'g'}, inorder = {'d', 'b', 'e', 'a', 'f', 'c', 'g'}
Output: [a,b,c,d,e,f,g]

Approach

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode

struct TreeNode
{
    char data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

int prestart;
TreeNode *buildTree(vector<char> &preorder, 
      vector<char> &inorder,
                    int instart, int inend)
{
    if (instart > inend)
        return NULL;
    TreeNode *root = new TreeNode(preorder[prestart++]);
    if (instart == inend)
        return root;
    int k = 0;
    for (int i = instart; i <= inend; i++)
    {
        if (inorder[i] == root->data)
        {
            k = i;
            break;
        }
    }

    root->left = buildTree(preorder, inorder, instart, k - 1);
    root->right = buildTree(preorder, inorder, k + 1, inend);
    return root;
}
TreeNode *buildTree(vector<char> &preorder, 
     vector<char> &inorder)
{
    prestart = 0;
    if (preorder.size() == 0)
        return NULL;
    return buildTree(preorder, inorder, 0, inorder.size() - 1);
}

void printTree(TreeNode *root)
{
    queue<TreeNode *> q;
    q.push(root);
    vector<string> vec;
    while (!q.empty())
    {
        root = q.front();
        q.pop();
        if (root == NULL)
            vec.push_back("null");
        else
            vec.push_back(string(1, root->data));
        if (root != NULL)
        {
            q.push(root->left);
            q.push(root->right);
        }
    }
    int j = vec.size() - 1;
    while (j > 0 && vec[j] == "null")
        j--;
    vec.resize(j);
    cout << "[";
    for (int i = 0; i < j; i++)
        cout << vec[i] << ",";
    cout << vec[j];

    cout << "]";
}
int main()
{
    vector<char> preorder = {'a', 'b', 'd', 'e', 'c', 'f', 'g'};
    vector<char> inorder = {'d', 'b', 'e', 'a', 'f', 'c', 'g'};
    TreeNode *root = buildTree(preorder, inorder);
    printTree(root);
    return 0;
}

Find Longest subarray with distinct integers

Given an array of elements, return the length of the longest subarray where all its elements are distinct.

For example, given the array [5, 1, 3, 5, 2, 3, 4, 1], return 5 as the longest subarray of distinct elements is [5, 2, 3, 4, 1].

Example:

Input:  arr = {5, 1, 3, 5, 2, 3, 4, 1}
Output: 5

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int longestSubarray(vector<int> &arr)
{

    int i = 0, j = 1;
    int max1 = 0, currLength = 1;
    max1 = max(max1, currLength);
    set<int> st;
    st.insert(arr[0]);

    while (i < arr.size() - 1 && j < arr.size())
    {
        if (st.find(arr[j]) == st.end())
        {
            currLength++;
            st.insert(arr[j++]);
        }
        else
        {
            st.erase(arr[i++]);
            currLength--;
        }
    }

    return max(currLength, max1);
}

int main()
{
    vector<int> arr = {5, 1, 3, 5, 2, 3, 4, 1};

    cout << longestSubarray(arr);

    return 0;
}

Implement LRU cache

Implement an LRU (Least Recently Used) cache. It should be able to be initialized with cache size, and contain the following methods:

• set(key, value): sets key to value. If there are already n items in the cache and we are adding a new item, then it should also remove the least recently used item.
• get(key): gets the value at key. If no such key exists, return null.

Each operation should run in O(1) time.

Example:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Approach:

C++

#include <bits/stdc++.h>
using namespace std;
class LRUCache
{
public:
    int cap;
    vector<int> v;
    unordered_map<int, int> mp;
    LRUCache(int capacity)
    {
        cap = capacity;
    }
    int get(int key)
    {
        auto pos = find(v.begin(), v.end(), key);
        if (pos != v.end())
        {
            v.erase(pos);
            v.push_back(key);
            return mp[key];
        }
        return -1;
    }
    void put(int key, int value)
    {
        auto pos = find(v.begin(), v.end(), key);
        if (pos != v.end())
            v.erase(pos);
        if (v.size() == cap)
        {
            mp[v[0]] = 0;
            v.erase(v.begin());
        }
        mp[key] = value;
        v.push_back(key);
    }
};
int main()
{
    LRUCache lRUCache(2);
    lRUCache.put(1, 1);
    lRUCache.put(2, 2);
    cout << "[";
    cout << lRUCache.get(1) << ", ";
    lRUCache.put(3, 3);
    cout << lRUCache.get(2) << ", ";
    lRUCache.put(4, 4);
    cout << lRUCache.get(1) << ", ";
    cout << lRUCache.get(3) << ", ";
    cout << lRUCache.get(4);
    cout << "]";
    return 0;
}

Construct BST from Post Order Traversal

Given the sequence of keys visited by a postorder traversal of a binary search tree, reconstruct the tree.

For example, given the sequence 2, 4, 3, 8, 7, 5, you should construct the following tree:

    5
   / \
  3   7
 / \   \
2   4   8

Example:

Input:  postorder = {2,4,3,8,7,5}
Output: [5,3,7,2,4,null,8]

Approach

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
int findLastSmaller(vector<int> &nodes,
                    int first, int last, int cut)
{

    if (last < first || nodes[first] > cut)
        return first - 1;

    int low = first, high = last, mid;

    while (low < high && nodes[high] > cut)
    {

        mid = low + (high - low + 1) / 2;

        if (nodes[mid] > cut)
        {

            high = mid - 1;
        }
        else
        {
            low = mid;
        }
    }

    return high;
}
TreeNode *recursiveFromPostOrder(vector<int> &nodes,
                                 int leftIndex, int rightIndex)
{

    if (rightIndex < leftIndex)
        return NULL;

    if (rightIndex == leftIndex)
        return new TreeNode(nodes[leftIndex]);

    int rootval = nodes[rightIndex];

    TreeNode *root = new TreeNode(rootval);

    int leftLast = findLastSmaller(nodes,
                                   leftIndex,
                                   rightIndex - 1, rootval);

    root->left = recursiveFromPostOrder(nodes, leftIndex,
                                        leftLast);

    root->right = recursiveFromPostOrder(nodes, leftLast + 1,
                                         rightIndex - 1);
    return root;
}
TreeNode *fromPostOrder(vector<int> &nodes)
{

    if (nodes.size() == 0)
        return NULL;
    return recursiveFromPostOrder(nodes, 0, nodes.size() - 1);
}

void printTree(TreeNode *root)
{
    queue<TreeNode *> q;
    q.push(root);
    vector<string> vec;
    while (!q.empty())
    {
        root = q.front();
        q.pop();
        if (root == NULL)
            vec.push_back("null");
        else
            vec.push_back(to_string(root->data));
        if (root != NULL)
        {
            q.push(root->left);
            q.push(root->right);
        }
    }
    int j = vec.size() - 1;
    while (j > 0 && vec[j] == "null")
        j--;
    vec.resize(j);
    cout << "[";
    for (int i = 0; i < j; i++)
        cout << vec[i] << ",";
    cout << vec[j];
    cout << "]";
}
int main()
{
    vector<int> postorder = {2, 4, 3, 8, 7, 5};

    TreeNode *root = fromPostOrder(postorder);

    printTree(root);

    return 0;
}

Shortest Possible Path in a Maze

You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on.

Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board.

For example, given the following board:

[[f, f, f, f],
[t, t, f, t],
[f, f, f, f],
[f, f, f, f]]

and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum number of steps required to reach the end is 7 since we would need to go through (1, 2) because there is a wall everywhere else on the second row.

Example:

Input:  board = {{1, 1, 1, 1}, {0, 0, 1, 0}, {1, 1, 1, 1}, {1, 1, 1, 1}}, srcX = 3, srcY = 0, destX = 0, destY = 0
Output: 7

Approach

C++

#include <bits/stdc++.h>
using namespace std;
bool isValid(vector<vector<bool>> &board,
             int M, int N,
             vector<vector<bool>> visited,
             int i, int j)
{
    return !(i < 0 || j < 0 || i >= M || j >= N ||
             !board[i][j] || visited[i][j]);
}

int ShortestPathInAMaze(vector<vector<bool>> &board,
                        int srcX, int srcY,
                        int destX, int destY)
{
    int M = board.size();
    int N = M > 0 ? board[0].size() : 0;

    vector<vector<bool>> visited(M, vector<bool>(N, false));

    queue<vector<int>> q;

    if (isValid(board, M, N, visited, srcX, srcY))
    {
        q.push({srcX, srcY, 0});
        visited[srcX][srcY] = true;
    }

    while (!q.empty())
    {
        vector<int> tempElement = q.front();
        q.pop();

        if (tempElement[0] == destX && tempElement[1] == destY)
        {
            return tempElement[2];
        }

        // checking if the 4 elements are valid or
        //not and pushing in the queue

        if (isValid(board, M, N,
                    visited, tempElement[0] + 1, tempElement[1]))
        {
            q.push({tempElement[0] + 1, tempElement[1],
                    tempElement[2] + 1});
        }

        if (isValid(board, M, N, visited,
                    tempElement[0] - 1, tempElement[1]))
        {
            q.push({tempElement[0] - 1, tempElement[1],
                    tempElement[2] + 1});
        }

        if (isValid(board, M, N, visited,
                    tempElement[0], tempElement[1] + 1))
        {
            q.push({tempElement[0], tempElement[1] + 1,
                    tempElement[2] + 1});
        }

        if (isValid(board, M, N, visited,
                    tempElement[0], tempElement[1] - 1))
        {
            q.push({tempElement[0], tempElement[1] - 1,
                    tempElement[2] + 1});
        }
    }

    // -1 indicates no path exists.
    return -1;
}

int main()
{
    vector<vector<bool>> board = {{1, 1, 1, 1},
                                  {0, 0, 1, 0},
                                  {1, 1, 1, 1},
                                  {1, 1, 1, 1}};

    int srcX = 3, srcY = 0;
    int destX = 0, destY = 0;
    cout << ShortestPathInAMaze(board, srcX, srcY, destX, destY);

    return 0;
}

Find the deepest node

Given the root of a binary tree, return the deepest node. For example, in the following tree, return d.

    a
   / \
  b   c
 /
d

Example:

Input:  tree = ['a','b','c','d']
Output: d

Approach

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    char data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
char deepesTreeNode(TreeNode *tree)
{

    queue<TreeNode *> q;
    TreeNode *temp = tree;
    TreeNode *prev = tree;
    while (temp != NULL)
    {
        prev = temp;
        if (temp->left != NULL)
        {
            q.push(temp->left);
        }
        if (temp->right != NULL)
        {
            q.push(temp->right);
        }
        temp = q.front();
        q.pop();
    }
    return prev->data;
}

int main()
{
    TreeNode *root = new TreeNode('a');
    root->left = new TreeNode('b');
    root->right = new TreeNode('c');
    root->left->left = new TreeNode('d');

    cout << deepesTreeNode(root);

    return 0;
}