## Amazon Interview Question for Development Support Engineers

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

store in the stack array only the string between /and/.
Once u find .. pop the stack.
when u find . ignore it

At the end the stack can be read for the absolute path.

Comment hidden because of low score. Click to expand.
0

exactly

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

We can also use java strings with function lastindexOf() to attain the same.

-Sachin

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

Initially I told him one recursive solution then he asked me to implement using efficient algorithm so i implemented it using double linked list.

procedure:

1)get tokens of input string
2)create double linked list node for each token
3) parse the list if you find .. back track two positions and point to the next node of .. in list ,so we can get new list or if we have found . then backtrack one node and delete . node and pointer to next node

4)Repeat step3 for all nodes

5)Now traverse double linked list it will give u absolute path.

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

How about stack? The stack is simpler to handle than the doubly linked list. However the approach is the same.

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

are you given the relative path as a string ? well tahts the assumption my soln is based on.
1. initialize an output array of size equal to the input string, and maintain a counter, initialised to 0.
2. read the string in reverse order.. ie. keep a pointer pi for the input array, pointer po for the output array and progress them from back to front. initilaize both pi and po to len(i/p string)
4. when you come across a "\.", freeze po, but let pi continue
5. when you come across a "\..", , freeze po, increment the counter and let pi continue. Repeat (6.) for the number of times you see a continuos "\..", Once you encounter no more "\.."s, allow pi to continue beyond this for the number of times specified by the counter. po should remain frozen all this time. Now reset the counter and loop through 4,5,6.
6. if its any other character..write the character at pi to po and progress both (pi, po)
7. loop through 4,5,6.
8. the output string could be well shorter than the input,so the output string could contain a lot of blanks/gibberish before the actual answer but you can jus return the pointer po.. works well with strings !

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

what abt using unis subsitute .

just used reg ex /\/.*\//\/

Comment hidden because of low score. Click to expand.
0

Wrong!

For C:\Dir1\Dir2\..\Dir3\.\Dir4\helloworld.txt
you'll get C:\Dir1\Dir2\Dir3\Dir4\helloworld.txt
but the path should be C:\Dir1\Dir2\Dir4\helloworld.txt (No Dir3)

Comment hidden because of low score. Click to expand.
0

This is wrong I think !

The output should be
C:\Dir1\Dir3\Dir4\helloworld.txt

right?

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

How about using a stack and popping up the element when we encounter .. ?

Input . in the path string needs to be ignored in this case.

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

I have a simple tested program which uses a stack(AStack.java):

public class AStack
{
protected int pointer;
public AStack() {
pointer=-1;
}
public AStack(int capacity) {
pointer=-1;
}
public int size() {
return pointer;
}
public boolean isEmpty() {
return pointer==-1;
}
public void push(Object i) {
}
public Object pop() {
if(isEmpty())
return null;
}
}
The program is as follows(cd.java):
import java.util.*;
public class cd
{
public cd() {
}
public static void print(AStack stack) {
String str=new String((String)stack.pop());
if(str.equals("."))
return;
else
print(stack);
System.out.print("\\"+str);
}
public static void main(String[] args)
{
AStack stack=new AStack();
stack.push(".");
StringTokenizer tmp = new StringTokenizer(args[0],"\\");
while(tmp.hasMoreElements())
{ String str=new String((String)tmp.nextElement());
//if(str!= ".." && str!= ".")
if( str.equals(".."))
stack.pop();
else if(!str.equals("."))
stack.push(str);
else
continue;
}
cd.print(stack);
}
}
Program input:
>java cd C:\Dir1\Dir2\..\Dir3\.\Dir4\helloworld.txt
Program output:\C:\Dir1\Dir3\Dir4\helloworld.txt

The program expects correct data input as command line argument.

Always keen to hear suggestions and implement them..

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

here is the sample code(:-

public static void main(String args[])
{
String s= "C:\Dir1\Dir2\..\Dir3\.\Dir4\Dir5";
int i = s.indexOf("..",s);
while(i!=-1)
{
if(i==s.length()-2) \\incase .. is at end of string
s = s.substring(0,s.lastindexOf("\",i-2));
else
s = s.substring(0,s.lastindexOf("\",i-2)) + s.substring(i+2);
i = s.indexOf("..",s);
}

i = s.indexOf(".",s);
while(i!=-1)
{
if(i==s.length()-1) \\incase . is at end of string
s = s.substring(i-1);
else
s = s.substring(i-1) + s.substring(i+1);
i = s.indexOf(".",s);
}

System.out.println(s);
}

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

No need of any external datastructure i feel.. It wil simply complicate things. I have an algorithm that solves in O(n). Just parse this string from back. and when u encounter "." or ".." perform necessary actions. How about it guys.

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

Here is the code. Do the necessary modifcations.

#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#include <string.h>

void remove_char(char **string)
{
int count = 0;
//char *ptr1 = *string;
char *ptr2 = *string;
while((*string)[count] != '\0')
{
if((*string)[count] == '.')
{
if((*string)[count + 1] == '.')
{

}
else
{
while(*ptr2 != '/')
{
*ptr2 = ' ';
ptr2--;

}
}
ptr2 = (*string) + count;
}
ptr2++;
count++;
//(*string)++;
}
}

void remove_char_opposite(char **string)
{
int length = strlen(*string);
char *ptr = (*string) + length -1;

while(length != 0)
{
if((*string)[length] == '.')
{
if((*string)[length-1] == '.')
{
int countofslashfound = 0;

while(countofslashfound != 2)
{
if((*string)[length] == '/')
{
countofslashfound+=1;
}
(*string)[length] = ' ';
length--;
}
}
else if((*string)[length-1] == '/')
{
int countofslashfound = 0;

while(countofslashfound != 1)
{
if((*string)[length] == '/')
{
countofslashfound+=1;
}
(*string)[length] = ' ';
length--;
}
}
}
length--;
}
}

int main()
{

char *string = (char *)malloc(sizeof(char));
strcpy(string,"C:/Dir1/Dir2/../Dir3/./Dir4/helloworld.txt");

remove_char(&string);

printf("String after reversal = %s",string);

}

Comment hidden because of low score. Click to expand.
0

void absolutepath(char* path, int sizeOfPath)
{
std::deque<string> _dque;
char* ptr[100] = {NULL};
int count =0;
ptr[count++] =path;
char *p = path;
while(p && *p != '\0')
{
if(*p == '\\' || *p == '/')
{
ptr[count++] = p+1;
*p = '\0';
}
p++;
}

count=0;
while(ptr[count] != NULL)
{
char* p = ptr[count];
if(*p != '.')
{
_dque.push_back(p);
}
else if(*p == '.' && strlen(p) == 2)
{
_dque.pop_back();
}
count++;
}

count = 0;
memset(path,'\0',sizeOfPath);
int size = _dque.size();
for(int i=0; i<size ; i++)
{
count +=sprintf(path+count,"%s",((string)_dque[i]).c_str());
if(i != size -1)
count +=sprintf(path+count,"%c",'/');
}
}

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

Algo goes here:

AbsolutePath( string relativePath , string &absolutePath )
{
step 1: Maniuplate the string with / baais and start a loop.
step 2: do
step 3: switch ( dir )
step 4: case "..": pop from stack
step 5: defalut : push to stack
step 6: done
step 7: iterate the stack and form the string
step 8: if absolutePath.empty() then
step 9: absolutePath = s.pop();
step 10: else
step 11: absolutePath = s.pop() +"\" + absoultePath
}

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

how about just simple regexes? substitute <dirname>\.. with empty string and \. with empty string
which means c:\dir1\dir2\..\dir3\.\sometext.txt becomes c:\dir1\dir3\sometext.txt ? shouldnt that work?

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

Java program:
File temp = new File(str)
print temp.getAbsolutePath()

:D

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

scan the string token-wise (delimited by "/") from the right to the left; maintain a global variable the number of "..": incremental the global variable when visiting it and decrement it when a token is not ".." and the global variable is positive.

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

code in c++

``````main()
{
string str="C:/Dir1/../Dir2/../Dir3/./Dir4/./helloworld.txt";

int count=str.find("/..");

while( count != string::npos)
{
int b=str.find_last_of("/",count-1);
string s1=str.substr(0,b);
string s2=str.substr(count+3);
str= s1 + s2;
cout<<str<<"\n";
count=str.find("/..");
}
count=str.find("/./");

while( count != string::npos)
{
str.replace(count,3,"/");
count=str.find("/./");
}

cout<<str;

}``````

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

code in c++

``````main()
{
string str="C:/Dir1/../Dir2/../Dir3/./Dir4/./helloworld.txt";

int count=str.find("/..");

while( count != string::npos)
{
int b=str.find_last_of("/",count-1);
string s1=str.substr(0,b);
string s2=str.substr(count+3);
str= s1 + s2;
cout<<str<<"\n";
count=str.find("/..");
}
count=str.find("/./");

while( count != string::npos)
{
str.replace(count,3,"/");
count=str.find("/./");
}

cout<<str;

}``````

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

``````File temp = new File(input);
System.out.println( temp.getCanonicalPath());``````

Name:

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

### Books

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

### 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.