Category Tree

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;
}

LeetCode 388. Longest Absolute File Path

Arunima Mandal 1 Comment

Problem Link: https://leetcode.com/problems/longest-absolute-file-path/

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, one limiting criterion 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. 

class Solution {
public:
    int lengthLongestPath(string input) {
        deque<int> dq;
        int len=0, level=0, res=0;
        bool flag=0;
        for(int i=0; i<input.size(); i++)
        {
            if(input[i]=='\n')
            {
                dq.push_back(len);
                len=0;
                level=0;
                flag=0; 
            }
            else if(input[i]=='\t') level++;
            else if(input[i]=='.')
            {
                flag=1;
                len++;
            }
            else
            {
                len++;
                if(flag)
                {
                    int sum=0;
                    for(int i=0; i<dq.size(); i++)
                    {
                        sum+=dq[i];
                    }
                    res=max(res, sum+len+level);
                }
                while(level<dq.size()) dq.pop_back();
            }
        }
        return res;
    }
};

In-order Successor of any Binary Tree

Arunima Mandal Leave a comment

1. Binary tree:

The successor of a node p is the node with the smallest key greater than p.val.

So there can be three cases to find the successor of a node:

  1. If the node has the right child, the successor must reside in its right subtree. If not, go to case 2. Note that, I didn’t mention the right “child”, I mentioned “subtree”. Because the node’s right child may not have the smallest value greater than p.value. In that case, the smallest value would be the leftmost child of the right child.
  2. If the node has no right child, then in the inorder traversal process, the successor node to be traversed would be this(node p’s) subtree’s parent node, which is the immediate node in the stack. If the stack is empty already, then go to case 3.
  3. If case 1 and 2 fails, that means node p has no successor.

We can use this process to find the inorder successor of a BST(Binary Search Tree) too. But in that case, we are not using the properties of BST, so that won’t be optimized. That is, this code’s time and space complexity is O(N), N being the number of nodes. In the case of BST, if we use the BST properties, then this problem can be solved in O(N) time and O(1) space.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        stack<TreeNode*> st;
        TreeNode *node=root;
        bool c=0;
        while(!st.empty() || node)
        {
            while(node)
            {
                st.push(node);
                node=node->left;
            }
            node=st.top();
            st.pop();
            if(c==1) return node;
            if(node==p) 
            {
                c=1;
                if(!node->right)
                {
                    if(!st.empty()) return st.top();
                    else return NULL;
                }
            }
            node=node->right;
        }
        return NULL;  
    }
};

2. Binary Search Tree:

Here using the BST properties, each time, we will discard half of the tree. Thus our usual time complexity for a balanced binary tree would be logarithmic instead of linear i.e. O(log(N)), and our space complexity would be constant i.e O(1) as we are not using any extra data structure to store the tree. Though in case the BST is not balanced, so we will get a skewed tree, in that worst-case scenario, the time complexity would be O(N).

Here, all the above 3 cases are taken care of at once.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode *node=root;
        TreeNode *successor=NULL;
        while(node)
        {
            if(node->val > p->val)
            {
                successor=node;
                node=node->left;
            }
            else if(node->val <= p->val)
            {
                node=node->right;
            }
        }
        return successor;  
    }
};