Amazon Interview Question
Software Engineer in TestsCountry: United States
import java.util.*;
public class Solution {
public String simplifyPath(String path) {
// Start typing your Java solution below
// DO NOT write main() function
Stack<String> stack = new Stack<String>();
String[] str = path.split("/");
for(int i = 0; i<str.length;i++){
String sw = str[i];
switch(sw){
case ".":
break;
case "..":
if(!stack.empty()){
stack.pop();
}
break;
case "":
break;
default:
stack.push(sw);
break;
}
}
String ret="";
while(!stack.empty()){
ret = "/" + stack.pop() + ret;
}
if(ret == ""){
return "/";
}
return ret;
}
public static void main(String[] args){
Solution sol = new Solution();
Scanner sc = new Scanner(System.in);
while(1==1){
String path = sc.nextLine();
String ret=sol.simplifyPath(path);
System.out.println(ret);
}
}
}
private static String getPath(String [] dirs) {
String path = "";
int ignore =0;
for(int i= dirs.length -1; i>=0 ; i--){
if("..".equals(dirs[i])) {
ignore++;
continue;
} else if(".".equals(dirs[i])) {
continue;
} else if (ignore > 0) {
ignore--;
continue;
} else {
path = dirs[i] + "/" + path;
}
}
return path.toString();
}
public static void main(String [] args) {
System.out.println(getPath("/home/abc/.././def/./ghi/../.".split("/")));
}
public class UnixPath {
public static String getPath(String inputPath) {
String outPath = "";
String[] dirs = inputPath.split("/");
int ignore = 0;
for(int index = dirs.length - 1; index >= 0 ; index--) {
if(dirs[index].equals("..")) ignore += 1;
else if(dirs[index].equals(".")) continue;
else {
if(ignore != 0) ignore -= 1;
else outPath = dirs[index] + "/" + outPath;
}
}
return outPath;
}
}
public class Main {
public static void main(String args[]) {
System.out.println(UnixPath.getPath("$/home/abc/.././def/./ghi/../."));
}
}
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<deque>
int main() {
std::stringstream ss("/home/abc/.././def/./ghi/../.");
std::string s;
std::vector<std::string> dirs;
while (getline(ss, s, '/')) {
dirs.push_back(s);
}
std::deque<std::string> dirstack;
for(std::vector<std::string>::iterator i = dirs.begin(); i != dirs.end(); ++i) {
if(*i == "..") {
dirstack.pop_back();
} else if (*i == ".") {
} else {
dirstack.push_back(*i);
}
}
for(std::deque<std::string>::iterator i = dirstack.begin(); i != dirstack.end(); ++i) {
std::cout << "/" << *i;
}
std::cout << std::endl;
return 0;
}
Here is the Java Solution
public static void main(String[] args) {
String input = "C:\\a\\b\\..\\.\\c\\d\\.";
char[] chars = input.toCharArray();
int length = chars.length;
int i = 0;
while (i < length) {
if (chars[i] == '.') {
if (i < length - 1 && chars[i + 1] == '.') {
int k = i - 2;
while (chars[k] != '\\') {
k--;
}
int temp = k;
for (int j = i + 2; j < length; j++) {
chars[k++] = chars[j];
}
length = k;
i = temp;
} else {
int k = i - 1;
for (int j = i + 1; j < length; j++) {
chars[k++] = chars[j];
}
length = k;
i --;
}
}
i++;
}
for (i = 0; i < length; i++) {
System.out.print(chars[i]);
}
}
public class Test {
public static void main (String [] args) {
String absolutePath = getAbsolutePath("$/home/abc/.././def/./ghi/../.");
System.out.println(absolutePath);
}
public static String getAbsolutePath(String path) {
if (path == null)
return null;
int length = path.length();
char[] pathArray = path.toCharArray();
int dotCount = 0;
StringBuilder absPath = new StringBuilder();
for (int i = length - 1; i >= 0; i--) {
if (pathArray[i] == '.') {
dotCount++;
}
if (dotCount == 0) {
absPath.insert(0, pathArray[i]);
}
if (pathArray[i] == '/') {
if (dotCount > 1) {
dotCount--;
} else {
dotCount = 0;
}
}
}
return absPath.toString();
}
}
// c++ code ,, use stringtokenizer in java
stringstream strin(dir_path);
string dir;
stack<string> s;
while ( getline(strin, dir, '/') )
{
if (dir == "." ) {}
else if (dir == "..") if (!s.empty()) s.pop();
else s.push(dir);
}
string ans;
while (!s.empty()) {
ans = "/" + s.top() + ans;
s.pop();
}
return ans.size() ? ans : "/";
You can do it using simple regex expression. As I see, there is no need of stacks. Sorry for my above post.
public class SimplifyUnixPath {
static String inppath;
public static void main(String[] args) {
String inputstring = "/home/abc/.././def/./ghi/../.";
//System.out.println(inputstring);
String toprint = simplifyPath(inputstring);
System.out.println(toprint);
// TODO Auto-generated method stub
}
public static String simplifyPath(String inp){
inppath = inp;
String splitexp = "/\\w*/\\.\\.|/\\.";
String output = "";
String[] outputarr;
outputarr = inppath.split(splitexp);
for(String s : outputarr){
//System.out.println(s);
output = output+s;
}
return output;
}
}
This is a version that doesn't use stacks and no extra memory. Probably a little inefficient.
var nextSegment = function(path, i) {
var end = i;
while(end < path.length) {
if(path[end] === '/') break;
end++;
}
return end;
}
var toAbsPath = function(path) {
var i = 0;
while(i < path.length) {
if(path[i] === '.') {
var segment = path.slice(i,i+3);
if(segment.match(/\.\.(\/)?/)) {
var end = nextSegment(path, i),
upDir = false;
i -= 2;
while(i > 0 && !upDir) {
if(path[i] === '/') {
path = path.slice(0,i) + path.slice(end);
upDir = true;
}
i--;
}
} else if(segment.match(/\.(\/[a-zA-Z0-9\.])?/)) {
var end = nextSegment(path, i);
path = path.slice(0,i) + path.slice(end + 1);
}
}
i++;
}
return path;
};
console.log(toAbsPath("$/home/abc/.././def/./ghi/../."));
package tree;
public class UnixPath {
public static void main(String[] args) {
String input = "$/home/abc/.././def/./ghi/../.";
String arr[] = input.split("/");
String out[] = new String[arr.length];
int i=-1;
for(String s: arr){
if(s.equals(".."))
i--;
else if(!s.equals("."))
out[++i] = s;
}
for(int j=0; j<=i; j++)
System.out.print(out[j]+"/");
}
}
Sorry it becomes:
- JSDUDE April 30, 2013$/home/def/