Implement Trie (Prefix Tree)

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example :

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Approach:

C++

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

struct Node
{
    char val = '\0';
    struct Node *child[26];
    bool isword = false;
};
Node *root = new Node();

//funtion to insert word
//into the trie
void insert(string word)
{
    Node *node = root;
    for (int i = 0; i < word.size(); i++)
    {
        char c = word[i];
        int index = c - 'a';
        if (node->child[index])
        {
            node = node->child[index];
            continue;
        }
        node->child[index] = new Node();
        node->child[index]->val = c;
        node = node->child[index];
    }
    node->isword = true;
}

//check if word is present in the
//trie
bool search(string word)
{
    struct Node *node = root;
    for (int i = 0; i < word.size(); i++)
    {
        char c = word[i];
        int index = c - 'a';
        if (!node->child[index])
            return false;
        node = node->child[index];
    }
    if (node->isword)
        return true;
    return false;
}

bool startsWith(string prefix)
{
    Node *node = root;
    for (int i = 0; i < prefix.size(); i++)
    {
        char c = prefix[i];
        int index = c - 'a';
        if (!node->child[index])
            return false;
        node = node->child[index];
    }
    return true;
}

int main()
{

    cout << "[";
    insert("apple");
    if (search("apple"))
        cout << "true, ";
    else
        cout << "false, ";
    if (search("app"))
        cout << "true, ";
    else
        cout << "false, ";
    if (startsWith("app"))
        cout << "true, ";
    else
        cout << "false, ";
    insert("app");
    if (search("app"))
        cout << "true";
    else
        cout << "false";

    cout << "]";

    return 0;
}

Implement Power Set

The power set of a set is the set of all its subsets. Write a function that, given a set, generates its power set.

For example, given the set {1, 2, 3}, it should return {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

You may also use a list or array to represent a set.

Example:

Input:  arr = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Approach

C++

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

vector<vector<int>> subsets(vector<int> &nums)
{
    vector<vector<int>> res;
    int n = nums.size();
    if (n == 0)
        return res;
    vector<int> x;
    res.push_back(x);
    for (int i = 0; i < pow(2, n); i++)
    {
        vector<int> y;
        for (int j = 0; j < n; j++)
        {
            if ((i & (1 << j)))
                y.push_back(nums[j]);
        }
        if (find(res.begin(), res.end(), y) == res.end())
            res.push_back(y);
    }
    return res;
}
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> sub = subsets(nums);

    cout << "[";
    for (int i = 0; i < sub.size(); i++)
    {
        cout << "[";
        for (int j = 0; j < sub[i].size(); j++)
        {
            cout << sub[i][j];
            if (j != sub[i].size() - 1)
                cout << ",";
        }
        cout << "]";
        if (i != sub.size() - 1)
            cout << ",";
    }
    cout << "]";

    return 0;
}

Running median of a sequence

Compute the running median of a sequence of numbers. That is, given a stream of numbers, print out the median of the list so far on each new element.

Recall that the median of an even-numbered list is the average of the two middle numbers.

For example, given the sequence [2, 1, 5, 7, 2, 0, 5], your algorithm should print out:

Example:

Input:  arr = [2,1,5,7,2,0,5]
Output: [2, 1.5, 2, 3.5, 2, 2, 2]

Approach

C++

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

//maximum priority queue
priority_queue<double> max1;

//minimum priority queue
priority_queue<double, vector<double>, greater<double>> min1;

//variable to hold the median
double median = 0;

//add numner into the priority
//queues
void addNum(int num)
{

    //if both are of equal size

    if (max1.size() == min1.size())
    {

        //if current element is
        //greter than median then
        //push into minimum priority
        //queue and set meadin as top
        //of min priority queue
        if (num > median)
        {
            min1.push(num);
            median = min1.top();
        }

        //else push into the max  queue
        //and set median as top of max queue
        else
        {
            max1.push(num);
            median = max1.top();
        }
    }

    //if min size is more
    else if (min1.size() > max1.size())
    {

        //if element is more than median
        //then push the top of min into max
        //and current element into the min
        if (num > median)
        {
            max1.push(min1.top());
            min1.pop();
            min1.push(num);
        }
        //else push into the max
        else
            max1.push(num);

        //set median as average of
        //min top and max top elements
        median = (min1.top() + max1.top()) / 2;
    }
    //if max size if greater
    else
    {
        //if current is more than then
        //median then push into the min
        //queue
        if (num > median)
        {
            min1.push(num);
        }

        //else push the top of max into
        //the min and current into the max
        else
        {
            min1.push(max1.top());
            max1.pop();
            max1.push(num);
        }
        //set the median as average of
        //top of min and max
        median = (min1.top() + max1.top()) / 2;
    }
}

//function to find the meadin of running
//stream
double findMedian()
{
    return median;
}
int main()
{
    int arr[] = {2, 1, 5, 7, 2, 0, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "[";
    for (int i = 0; i < n; i++)
    {
        addNum(arr[i]);
        cout << findMedian();
        if (i != n - 1)
            cout << ", ";
    }
    cout << "]";
    return 0;
}

Find the edit distance

The edit distance between two strings refers to the minimum number of character insertions, deletions, and substitutions required to change one string to the other. For example, the edit distance between “kitten” and “sitting” is three: substitute the “k” for “s”, substitute the “e” for “i”, and append a “g”.

Given two strings, compute the edit distance between them.

Example:

Input:  word1 = "kitten", word2 = "sitting"
Output: 3

Approach

C++

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

int minDistance(string word1, string word2)
{
    int m = word1.size(), n = word2.size();

    //create a 2D array of size (m+1)*(n+1)
    int dp[m + 1][n + 1];
    for (int i = 0; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {

            //if first is empty
            if (i == 0)
                dp[i][j] = j;

            //if second is empty
            else if (j == 0)
                dp[i][j] = i;
            //if both are same
            else if (word1[i - 1] == word2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];

            //else min of insert,delete and replace
            else
                dp[i][j] = 1 + min(dp[i - 1][j],
                                   min(dp[i][j - 1],
                                       dp[i - 1][j - 1]));
        }
    }
    return dp[m][n];
}
int main()
{
    string word1 = "kitten", word2 = "sitting";
    cout << minDistance(word1, word2);
    return 0;
}

Square the elements of sorted array and give the output in sorted

Given a sorted list of integers, square the elements and give the output in sorted order.

For example, given [-9, -2, 0, 2, 3], return [0, 4, 4, 9, 81].

Example:

Input:  arr = [-9,-2,0,2,3]
Output: [0, 4, 4, 9, 81]

Approach

C++

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

vector<int> sortedSquares(vector<int> &nums)
{
    vector<int> res;
    int p = 0;
    bool flag = false;
    for (int i = 0; i < nums.size(); i++)
    {
        if (nums[i] >= 0)
        {
            flag = true;
            p = i;
            break;
        }
    }
    int i = p;
    int j = p - 1;
    if (flag == false)
        j = nums.size() - 1;
    while (j >= 0 && i < nums.size())
    {
        if (nums[i] * nums[i] < nums[j] * nums[j])
        {
            res.push_back(nums[i] * nums[i]);
            i++;
        }
        else
        {
            res.push_back(nums[j] * nums[j]);
            j--;
        }
    }
    while (j >= 0)
    {
        res.push_back(nums[j] * nums[j]);
        j--;
    }
    while (i < nums.size() && flag)
    {
        res.push_back(nums[i] * nums[i]);
        i++;
    }
    return res;
}
int main()
{
    vector<int> nums = {-9, -2, 0, 2, 3};

    vector<int> res = sortedSquares(nums);

    cout << "[";

    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i];
        if (i != res.size() - 1)
            cout << ", ";
    }
    cout << "]";

    return 0;
}

Implement run-length encoding and decoding

Run-length encoding is a fast and simple method of encoding strings. The basic idea is to represent repeated successive characters as a single count and character. For example, the string "AAAABBBCCDAA" would be encoded as "4A3B2C1D2A".

Implement run-length encoding and decoding. You can assume the string to be encoded have no digits and consists solely of alphabetic characters. You can assume the string to be decoded is valid.

Example:

Input:  str = "AAAABBBCCDAA"
Output: 4A3B2C1D2A

Approach

C++

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

int main()
{

    string str = "AAAABBBCCDAA";
    char t = str[0];

    int i = 0;
    int cnt = 1;
    int n = str.size();
    string res = "";
    while (i < n)
    {
        cnt = 1;
        i++;
        while (i < n && str[i] == str[i - 1])
        {
            i++;
            cnt++;
        }
        res += to_string(cnt);
        res += str[i-1];
    }
    cout << res << "\n";
    return 0;
}