Interview Questions – Implement linux change directory command

Problem

Given an absolute path of the directory that may contain special symbols like .(Current directory), ..(Patent directory) & actual directory name. Write an effecient algorithm to get the actual path where the cd will land.

Example

Input: /com/./../working/../example/./interview

output: /example/interview

[1] . Will keep us in the current direction

[2] .. Will take the current directory to the parent directory

[3] Identifier would be a valid name containing characters, numbers, _, -.

Constraints

[1] 100 > identifier length > 0.

[2] Input will only contain valid symbols.

Before going forward try it yourself. Think about what data structure we can use.

Solution and Implementation

If you think a bit about the main operation that are going on here is

• We need to make a decision every step whether we need to in the current direction or move back to parent.

Does this ring a bell, how can we move back to parent easily and keep the parsed directory so far intact. You guessed it right! it Stack that we have to use here to solve this. But before we start coding we also need  a way to distinguish between “.” and “..”.

package working.example.tech.InterviewQuestions;
import working.example.tech.interfaces.TestCaseRunner;
import java.util.Stack;
public class ChangeDirectory implements TestCaseRunner {
    private Stack<Character> mStk;
    public ChangeDirectory() {
        mStk = new Stack<>();
    }

    private void changeDirectory(String in) {
        char prevChar = '*';
        for (char ch : in.toCharArray()) {
            switch (ch) {
                case '.':
                    if (prevChar == '.') {
                        do {
                            mStk.pop();
                        } while(mStk.peek() != '/');
                    }
                    break;
                case '/':
                    if (!(prevChar == '/' || (!mStk.empty() && mStk.peek() == '/'))) {
                        mStk.push('/');
                    }
                    break;
                default:
                    mStk.push(ch);
                    break;
            }
            prevChar = ch;
        }
    }
    @Override
    public void RunTest() {
        changeDirectory("/working//exmaple/../././../is//blog");
        showOut();
    }

    @Override
    public void showOut() {
        StringBuilder stringBuilder = new StringBuilder();
        while(!mStk.empty()) {
            stringBuilder.append(mStk.peek());
            mStk.pop();
        }
        System.out.println("cd " + stringBuilder.reverse());
    }
}

Output

cd /is/blog

Complexity

Auxiliary Space complexity: O(m)

Time Complexity:  O(m)

Where m is the length of the input.