Author Arunima Mandal

Trie (Insert and Search)

Arunima Mandal Leave a comment

Note: I have understood the concept of Trie from the following link- https://www.geeksforgeeks.org/trie-insert-and-search/
I have just modified the code according to my understanding and tried to make the code concise.

Code:

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

struct TrieNode
{
	TrieNode *child[26]={}; //if string contains alphabets only
	bool word=0;
};

void insert(struct TrieNode *root, string key)
{
	TrieNode *it = root;
	for (int i = 0; i < key.size(); i++)
	{
		int index = key[i] - 'a';
		if (!it->child[index]) it->child[index] = new TrieNode();
		it = it->child[index];
	}
	it->word = 1;
}

bool search(struct TrieNode *root, string key)
{
	TrieNode *it = root;
	for (int i = 0; i < key.size(); i++)
	{
		int index = key[i] - 'a';
		if (!it->child[index]) return false;
		it = it->child[index];
	}
	return (it->word);
}

// Driver
int main()
{
	// Input keys (use only 'a' through 'z' and lower case)
	vector<string> keys={"the", "a", "there", "answer", "any", "by", "bye", "their" };

	TrieNode *root = new TrieNode();

	// Construct trie
	for (int i = 0; i < keys.size(); i++)
		insert(root, keys[i]);

	// Search for different keys
	char output[][32] = {"Not present in trie", "Present in trie"};

	// Search for different keys
	cout<<"the"<<" --- "<<output[search(root, "the")]<<endl;
	cout<<"these"<<" --- "<<output[search(root, "these")]<<endl;
	cout<<"their"<<" --- "<<output[search(root, "their")]<<endl;
	cout<<"thaw"<<" --- "<<output[search(root, "thaw")]<<endl;
	return 0;
}

LeetCode 2115. Find All Possible Recipes from Given Supplies

Arunima Mandal Leave a comment

Problem Link: https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/description/

Note: Since the problem explicitly demands dependency, and the recipes are the ultimate nodes that have indegrees topological sort is the most intuitive thing that can come to mind if you know the idea of the topological sort well. I used Kahn’s algorithm here to do the topological sort.

  • Time complexity: O(n)
  • Space complexity: O(n)
class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_map<string, vector<string> > ump;
        unordered_map<string,int> indegree;
        vector<string> ans;
        for(int i=0; i<ingredients.size(); i++)
        {
            for(int j=0; j<ingredients[i].size(); j++)
            {
                 ump[ingredients[i][j]].push_back(recipes[i]);
                 indegree[recipes[i]]++;
            }
        }
        for(int i=0; i<supplies.size(); i++)
        {   
            for(int j=0; j<ump[supplies[i]].size(); j++)
            {
                string adj=ump[supplies[i]][j];
                indegree[adj]--;
                if(indegree[adj]==0)
                {
                    supplies.push_back(adj);
                    ans.push_back(adj);
                }
            }
        }
        return ans;
    }
};

Leetcode 729. My Calendar I

Arunima Mandal Leave a comment

Problem Link: https://leetcode.com/problems/my-calendar-i/description/

Note:

This problem is interesting to solve. It’s easy but again if you want to optimize, you will have to be careful about using data structure.

Approach 1: Using vector and Binary Search (O(N^2logN) time complexity)

In this approach, the time complexity is O(N^2 logN) because the sort() function takes O(NlogN) time. So for calling it N times, the time complexity will be O(N*NlogN) = O(N^2logN).

class MyCalendar {
public:
    vector<pair<int,int> > v;
    
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        pair<int,int> p{start,end};
        int l=lower_bound(v.begin(), v.end(), p)-v.begin();
        if(l<v.size() && (start==v[l].first || end>v[l].first) || (l>=1 && start<v[l-1].second)) return false;
        else if(l==v.size() && l>=1 && start<v[l-1].second) return false;   

        v.push_back({start,end});
        sort(v.begin(), v.end());
        return true; 
    }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(start,end);
 */

Approach 2: Using Set and Binary Search (O(NlogN) time complexity)

Here, the highest time is taken by the set insert which is logN. So for calling it N times, the time complexity will be O(N*logN) = O(NlogN).

class MyCalendar {
public:
    //vector<pair<int,int> > v;
    set<pair<int,int> >st;
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        pair<int,int> p{start,end};
        /*
        int l=lower_bound(v.begin(), v.end(), p)-v.begin();
        if(l<v.size() && (start==v[l].first || end>v[l].first) || (l>=1 && start<v[l-1].second)) return false;
        else if(l==v.size() && l>=1 && start<v[l-1].second) return false;   

        v.push_back({start,end});
        sort(v.begin(), v.end());
        */
        auto nextEvent=st.lower_bound(p);
        if(nextEvent!=st.end() && end>nextEvent->first) return false;
        if(nextEvent!=st.begin())
        {
            auto prevEvent=prev(nextEvent);
            if(start<prevEvent->second) return false;
        }
        st.insert(p);
        return true;
    }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(start,end);
 */

Absolute Path Of A Targeted File Where The Virus Is Not Present!!

Arunima Mandal Leave a comment

Problem: https://domjudge.cs.fsu.edu/public/problems/13/text

Note:

This problem intuitively resembles a tree structure. But it can be solved using a deque easily, though I think the first data structure that will come to mind is a stack, at least that was in my case. A stack would work, but eventually while accessing all the elements of the stack for length counting, then you will get how deque will serve in that case!

In the following code, there are two limiting criteria:

One is that the length of the level cannot be less than the size of the deque, if it is greater then we have already processed the subdirectory/file and we haven’t found our answer yet, so we can discard that from the deque.

And the second one is the case of checking the virus file. If the virus file is found once, then even if we get our targeted file in the same hierarchy level or in any deeper level of the same root directory, we’ll have to discard it. We have handled this checking using two variables vi and vi_level. One can use 1 variable only instead of these two to check this.

Code:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

    string target;
    cin>>target;
    string str,s,ss, ext;
    while(cin>>str)
    {
        s+=str;
        s+="\n";
    }
    int level=0, vi_level=0;
    bool flag=0, vi=0;
    deque<string> dq;

    for(int i=0; i<s.size(); i++)
    {
        if(s[i]=='\n')
        {
            dq.push_back(ss);
            if(flag)
            {
                if(ss==target)
                {
                    cout<<dq[0];
                    for(int i=1; i<dq.size(); i++) cout<<"/"<<dq[i];
                    return 0;
                }
                else if(ext=="virus")
                {
                    vi=1;
                    vi_level=level;
                }
            }
            ss.clear();
            level=0;
            flag=0;
            ext.clear();
        }
        else if(s[i]=='-') level++;
        else if(s[i]=='.')
        {
            if(vi && level>=vi_level) continue;
            ss+=s[i];
            flag=1;
        }
        else
        {
            if(level==0) vi=0;
            if(vi && level>=vi_level) continue;
            ss+=s[i];
            if(flag) ext+=s[i];
            while(level<dq.size()) dq.pop_back();
        }
    }
    return 0;
}

Print the Absolute File Path Of A Targeted File in C++

Arunima Mandal Leave a comment

Problem Statement: Given a file system(consisting of directories, sub-directories, and files) and a target file name, print the absolute path of that targeted file.

Input: Input would be a series of strings. The first line would be the target file name. From the next line onward, there will be multiple directories/sub-directories and file names separated by newlines. And “-” indicates the level hierarchy of each sub-directory or file. Assume that, the targeted file will always be present and will be unique in the input.

Output:

Print the path starting from the root directory name. Put a “/” in between directories, sub-directories, and files while printing the path.

Sample Input:

yes.cpp
Documents
-Homework
–DS.virus
–algo.docx
-yes.cpp
Downloads
-write.cpp
-yes.h

Sample Output:

Documents/yes.cpp

Code:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

    string target;
    cin>>target;
    string str,s,ss, ext;
    while(cin>>str)
    {
        s+=str;
        s+="\n";
    }
    int level=0;
    bool flag=0;
    deque<string> dq;

    for(int i=0; i<s.size(); i++)
    {
        if(s[i]=='\n')
        {
            dq.push_back(ss);
            if(flag && ss==target)
            {
                cout<<dq[0];
                for(int i=1; i<dq.size(); i++) cout<<"/"<<dq[i];
                return 0;
            }
            ss.clear();
            flag=0;
            level=0;
        }
        else if(s[i]=='-') level++;
        else if(s[i]=='.')
        {
            ss+=s[i];
            flag=1;
        }
        else
        {
            ss+=s[i];
            while(level<dq.size()) dq.pop_back();
        }
    }
    return 0;
}