Amazon Interview Question


Country: United States
Interview Type: Phone Interview


Comment hidden because of low score. Click to expand.
1
of 1 vote

Will the input always start with / and consist only of folder/file names or . or .. separated by slashes? If so, I can make a stack and every time I see a name, I push it on the stack, every time I see . I ignore that, and every time I see .., I will pop the top element off the stack. At the end I'll pop off all the stack elements into a list, reverse the list, and print out /element for each element, so I'll get /element1/element2/element3 and so on.

- eugene.yarovoi on June 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is the difference folder and file? It does not matter. the absolute path is important. I came up with stack too. actually path may contain ./ this too. It does not mean anything. We can skip it.

- kamoliddin on June 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I already mentioned that we can skip the dot (.) Agreed that it really doesn't matter whether something is a file or folder, or at least not based on how I'm understanding the question.

- eugene.yarovoi on June 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Split string with / e.g. Path.Split("/")
ignore leading and trailing /
for each string push to stack
for each .. pop from stack
e.g. windows/abs/../temp/new/.../

Push windows
Push abs
pop abs
push temp
push new
pop new

you will be left with windows/temp

- Anon on June 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think we can use a doubly linked list. Wheneever we get a path we create a new node and when we get .. we move to previous node and delete the next node
i.e for /windows/abs/../temp/new/.../
first you will get windows
windows -> null
now you got abs
windows -> abs
now .., which means move back and delete the node
windows
now you got temp
windows -> temp
now you got new
windows -> temp -> new
now you got ..
windows -> temp

So this is the absolute path

- Sandeep on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args)
    {
        String path = "/windows/abs/../temp/new/../";
        
        Stack<String> parts = new Stack<String>();
        
        String part;
        int start = 0;
        for(int i = start; i< path.length(); i++)
        {
            if(path.charAt(i) == '/')
            {
                part = path.substring(start, i);
                start = i + 1;
                
                if(part.isEmpty()) continue;
                
                if(part.equals(".."))
                {
                    if(parts.isEmpty())
                    {
                        throw new IllegalArgumentException();
                    }
                    else
                    {
                        parts.pop();
                    }
                }
                else
                {
                    parts.push(part);
                }
            }
        }
        
        Stack<String> result = new Stack<String>();
        while(!parts.isEmpty())
        {
            result.push(parts.pop());
        }

        if(result.isEmpty())
        {
            System.out.print("/");
        }
        else
        {
            while(!result.isEmpty())
            {
                System.out.print("/");
                System.out.print(result.pop());
            }
        }
    }

- Anonymous on June 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

String test = "/windows/abs/../temp/new/.../";
		String[] split = test.split("/");
		StringBuilder ans = new StringBuilder();
		for(int x = 0; x < split.length; x++) {
			System.out.println(ans);
			if(split[x].equals("..") | split[x].equals("..."))
				ans.replace(ans.lastIndexOf("/", ans.length() - 2), ans.length(), "/");
			else 
				ans.append(split[x] + "/");
		}
		System.out.println("Final:=" + ans);

- If you are going to write in Java... on June 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for the Ruby crowd

def absolute_path(path)
	abs_path = Array.new
	path.split("/").each do | f |
		if f.include?("..")
			abs_path.pop unless abs_path.empty?
		else
			abs_path.push(f)
		end
	end
	return abs_path.join("/")
end

- Brandon sislow on June 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my c++ based program. Using only stl: stack as helper.
No other stl or library is used (not even C++ string).
Hope it helps from-scratch implementation. Thanks @eugene.yarovoi for providing the idea. Though, I came up with the same logic but since u posted here earlier than me so I think acknowledgement is due :)

#include<iostream>
#include<cstring>
#include<stack>

using namespace std;

struct ll
{
	char *str;
	int len;
	// ll *next;
	
	ll(char* a=0, int l=0): str(a), len(l){}
};

void static clearStack(stack<ll*> &st)
{
	while(!st.empty())	
	{
		ll* temp = st.top();
		st.pop();
		delete(temp);
	}
	return;
}


void printStr(char* ptr, int len)
{ 
	if(!ptr || len == 0)
		return;
	for(int i=0; i<len; i++)
		cout << ptr[i];
}
void printPath(stack<ll*> &st)
{
	while(!st.empty())
	{
		ll* node = st.top();
		st.pop();
		printPath(st);
		printStr(node->str, node->len);
		delete(node);
		cout << "/";
	}
}
void relToAbs(char *rpath, int len)
{
	// STATE MACHINE TO PROCESS THE RELATIVE PATH STRING
	stack<ll*> st;
	char *aName = NULL;
	for(int  i=0; rpath[i] != '\0' && i<len; /* i++ */)
	{
		if(rpath[i] == '/')
		{
			i++;
		}
		else if(rpath[i] == '.')
		{
			if(rpath[++i] == '.')
			{
				if(!st.empty())
				{
					ll *aNode = st.top();
					st.pop();
					delete(aNode);
				}
				++i;
			}
		}
		else if(tolower(rpath[i]) >= 'a' && tolower(rpath[i]) <= 'z')// character is seen
		{
			aName = &rpath[i];
			int size = i;
			while(tolower(rpath[i]) >= 'a' && tolower(rpath[i]) <= 'z')
				i++;
			st.push(new ll(aName, i-size));
		}
		else
		{
			cout << "ill-formed path" << endl;
			clearStack(st);
			return ;
		}
	}
	//------------------------------------------------------
	
	return printPath(st);
	
}

void relToAbsDriver()
{
	char* str = "/windows/abs/../temp/new/../$";
	relToAbs(str, strlen(str));

	cout << endl << "--------------------------------" << endl;	
}

- pavi.8081 on July 09, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More