CareerCup

To support any number of ".."s, a queue or list of valid path components will be required. This can be roughly completed in O(n) complexity and O(n) memory where n is the number of characters in the path:

public static String normalizePath(String path){
    if(path == null){
        throw new NullPointerException();
    }

    ArrayList<String> pathTokens = new ArrayList<String>();
    //build the set of valid path tokens
    StringBuilder tokenBuilder = new StringBuilder();
    for(int i = 0; i < path.length(); i++){
        char c = path.charAt(i);
        //if this is a distinct token, must handle it
        if(c == File.PATH_SEPARATOR){
            String token = tokenBuilder.toString();
            if(token.length() == 0){
                continue;
            }
            if(DOUBLE.equals(token)){
                if(pathTokens.size() == 0){
                    throw new IllegalArgumentException("invalid path");
                }
                pathTokens.removeLast();
            }
            else if(!SINGLE.equals(token)){
                pathTokens.add(token);
            }
            tokenBuilder.setLength(0);
        }
        else{
            tokenBuilder.append(c);
        }
    }
    String token = tokenBuilder.toString();
    if(token.length() > 0){
        if(DOUBLE.equals(toke)){
            if(pathTokens.size() == 0){
                throw new IllegalArgumentException("invalid path");
            }
            pathTokens.removeLast();
        }
        else if(!SINGLE.equals(token)){
            pathTokens.add(token);
        }
    }
    //rebuild the valid output
    tokenBuilder.setLength(0);
    for(String token : pathTokens){
        tokenBuilder.append(File.PATH_SEPARATOR);
        tokenBuilder.append(token);
    }
    return tokenBuilder.toString();
}

public String simplifyPath(String path) {
    Deque<String> stack = new LinkedList<>();
    Set<String> skip = new HashSet<>(Arrays.asList("..",".",""));
    for (String dir : path.split("/")) {
        if (dir.equals("..") && !stack.isEmpty()) stack.pop();
        else if (!skip.contains(dir)) stack.push(dir);
    }
    String res = "";
    for (String dir : stack) res = "/" + dir + res;
    return res.isEmpty() ? "/" : res;
}

I would simply use Stack.
First, get the list of token by splitting the string by '/'.
Iterate through the list and do the following,
If you see "..", pop the top element (unless stack is empty or the top element is ".." If stack is empty, just add "..". This case covers something like "../../c.txt")
Else, just add it to the stack.
When you are done iterating it, pop out the elements and build the path from the back.

public string NormalizePath(string path)
{
	Stack<string> stack = new Stack<string>();
	sting[] tokens = path.Split('/');
	foreach(string token in tokens)
	{
		if(token == "..")
		{
			if(stack.IsEmpty() || stack.Poll() == "..")
			{
				stack.Push(token);
			}
			else
			{
				stack.Pop();
			}
		}
		else
		{
			stack.Push(token);
		}
	}
	string normalizedPath = "";
	while(!stack.IsEmpty())
	{
		normalizedPath = stack.Pop() + normalizedPath;
	}
}

function normalize(inputs) {

  function isCurDir(part) {
    return part == '.';
  }

  function isPrevDir(part) {
    return part == '..';
  }

  var prevDir = 0;
  var normalized = [];
  var parts = inputs.split('\\');

  var i = parts.length;

  while (i) {
    var cur = parts[--i];
    if (!cur) continue;
    if (isCurDir(cur)) continue;
    else if (isPrevDir(cur)) {
      prevDir++;
    }
    else {
      if (prevDir)
        prevDir--;
      else normalized.push(cur);
    }
  }

  while (prevDir) {
    normalized.push('..');
    prevDir--;
  }

  return '\\' + normalized.reverse().join('\\');

}

public static String normalize(String path){
		String str[] = path.split("\\\\");
		return str[0]+"\\"+str[str.length-1];
	}

Am i missing something here?

public class PathNormalization {

	public static void main(String[] args) {
		String path = "\\a\\b\\..\\c\\.\\foo.txt";
        System.out.println(path);
        System.out.println(normalize(path));
	}

	public static String normalize(String path) {
		List<String> structure = new ArrayList<>();
		String[] splittedPath = path.split("\\\\");

		for (String dir : splittedPath) {
            dir = dir.trim();

            if (".".equals(dir) || dir.isEmpty()) {
                continue;
            }

			if ("..".equals(dir.trim())) {
				structure.remove(structure.size() - 1);
			} else {
				structure.add(dir.trim());
			}
		}

		StringBuilder sb = new StringBuilder();

		for (String s : structure) {
			sb.append("\\");
			sb.append(s);
		}

        return sb.toString();
	}
}

1. Split the path by '\' , put the splits into an array
eg. input: \a\b\..\foo.txt
Array = {"a" ,"b", "..", "foo.txt" }

2. start from last index of array , count number of instances of string == ".." and remove all the strings from indexes from last-i to last-i-count

3. generate path from array

String Normalize( String s ){
String[] arr = s.split("\");
int count = 0 ;
for( int i = arr.length-1; i >= 0 ; i-- ){
if( arr[i] == ".." )
count++;
else if(count >0){
arr[i] = "";
count--;
}
}
StringBuffer sb = new StringBuffer();
char c = '';
for( int i = 0 ; i < arr.length; i++ ){
if( arr[i] != "" ){
sb.append(c+arr[i]);
c = '\';
}
}
return sb.toString();
}

it use O(K) where k is the number of ".."

public class RelativePath {
    public String normalise(String path) {
        path = removeCurrentDirectorySign(path);
        return removeParentDirectorySign(path);
    }

    private String removeParentDirectorySign(String path) {
        String[] pathArray =path.split("\\\\.\\.");
        StringBuilder pathBuilder = new StringBuilder();
        for (String aPathArray : pathArray) {
            if (pathBuilder.length()>0) pathBuilder.delete(pathBuilder.lastIndexOf("\\"), pathBuilder.length());
            pathBuilder.append(aPathArray);
        }
        return pathBuilder.toString();
    }

    private String removeCurrentDirectorySign(String path) {
        return path.replace("\\.\\", "\\");
    }
}

http://git.io/vYvmv - source
http://git.io/vYvqW - test

O(n) implementation:

public static String ReducePath(String input, String sep) {
        if(input == null || sep == null) {
            return null;
        }

        String[] parts = input.split(sep);
        List<String> finalParts = new ArrayList<String>();
        boolean skipNext = false;
        for(int i = parts.length - 1; i > 0; i--) {
            if(skipNext == true) {
                skipNext = false;
                continue;
            }

            if(parts[i].isEmpty()) {
                continue;
            }

            if(parts[i].equals("..")) {
                skipNext = true;
                continue;
            }

            if(parts[i].equals(".")) {
                continue;
            }

            finalParts.add(parts[i]);
        }

        Collections.reverse(finalParts);
        return String.format("/%s", String.join(sep, finalParts));
    }

O(n) implementation:

public static String ReducePath(String input, String sep) {
        if(input == null || sep == null) {
            return null;
        }

        // Tokenize by specified seperator
        String[] parts = input.split(sep);
        List<String> finalParts = new ArrayList<String>();
        boolean skipNext = false;

        // Go through path in reverse order
        for(int i = parts.length - 1; i >= 0; i--) {

            // Skipping as result of a ".."
            if(skipNext == true) {
                skipNext = false;
                continue;
            }

            // Skipping as result of "//"
            if(parts[i].isEmpty()) {
                continue;
            }

            // Skipping ".." and setting marker for next iteration
            if(parts[i].equals("..")) {
                skipNext = true;
                continue;
            }

            // Ignoring...
            if(parts[i].equals(".")) {
                continue;
            }

            // Ok, hold on to this
            finalParts.add(parts[i]);
        }

        // Reverse the list
        Collections.reverse(finalParts);

        // Join the reversed list and prepend it with sep
        return String.format("%s%s", sep, String.join(sep, finalParts));
    }

public String computeRelativePath(String path) {
		String res = "";
		StringTokenizer st = new StringTokenizer(path, "\\");
		Stack<String> s = new Stack<String>();
		while (st.hasMoreTokens()) {
			String item = st.nextToken();
			if (item.equals("..")) {
				if (!s.isEmpty()) {
					s.pop();

				}
			} else {
				s.push(item);
			}
		}
		Stack<String> s1 = new Stack<String>();
		while(!s.empty()){
			s1.push(s.pop());
		}

		while(!s1.empty()){
			res += "\\" + s1.pop();
		}
		return res;
	}

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<map>
#include<climits>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    char str[100];
    scanf("%s",str);
   // printf("%s",str);
    char res[100];
    int j=0;
    int len = strlen(str);
    for(int i=0; i<len-1; i++)
    {
        if (str[i] == '.' && str[i+1] == '.') {
            if (j-2 > 0) {
                j-=2;
                while (res[j] != '\\') j--;
            }
            i++;
        } else {
            res[j++]=str[i];
        }
    }
    res[j++] = str[len-1];
    res[j]='\0';
    printf("%s",res);
    return 0;

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<map>
#include<climits>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    char str[100];
    scanf("%s",str);
   // printf("%s",str);
    char res[100];
    int j=0;
    int len = strlen(str);
    for(int i=0; i<len-1; i++)
    {
        if (str[i] == '.' && str[i+1] == '.') {
            if (j-2 > 0) {
                j-=2;
                while (res[j] != '\\') j--;
            }
            i++;
        } else {
            res[j++]=str[i];
        }
    }
    res[j++] = str[len-1];
    res[j]='\0';
    printf("%s",res);
    return 0;

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<map>
#include<climits>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    char str[100];
    scanf("%s",str);
   // printf("%s",str);
    char res[100];
    int j=0;
    int len = strlen(str);
    for(int i=0; i<len-1; i++)
    {
        if (str[i] == '.' && str[i+1] == '.') {
            if (j-2 > 0) {
                j-=2;
                while (res[j] != '\\') j--;
            }
            i++;
        } else {
            res[j++]=str[i];
        }
    }
    res[j++] = str[len-1];
    res[j]='\0';
    printf("%s",res);
    return 0;
}

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<map>
#include<climits>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    char str[100];
    scanf("%s",str);
   // printf("%s",str);
    char res[100];
    int j=0;
    int len = strlen(str);
    for(int i=0; i<len-1; i++)
    {
        if (str[i] == '.' && str[i+1] == '.') {
            if (j-2 > 0) {
                j-=2;
                while (res[j] != '\\') j--;
            }
            i++;
        } else {
            res[j++]=str[i];
        }
    }
    res[j++] = str[len-1];
    res[j]='\0';
    printf("%s",res);
    return 0;
}

for (int i  =0; i < input.length; i++) 
{
	if ( input[i] == '.' && input[i - 1] == '.')
	{
		input.removeAt(i + 1);
		input.removeAt(i);
		input.removeAt(i - 1);
		input.removeAt(i - 2);
		i = i - 3;
		while(i != '\' && i > 0)
		{
			input.removeAt(i);
			i--;
		}
	}
}
return input;

Solution in c++

string normalizePath(const string& path) {
  const string delim = "/";

  vector<string> args;
  boost::split(args, path, boost::is_any_of(delim));  

  vector<string> newArgs;

  // first dir/file
  if (args.size() > 0) {
    newArgs.push_back(args[0]);
  }

  // rest, except the last dir/file
  for (int i = 1; i < args.size() - 1; ++i) {

    if (args[i] == "" || args[i] == ".") {
      continue;
    } else if (args[i] == ".." && !newArgs.empty() && newArgs.back() != "..") {
      newArgs.pop_back();
    } else {
      newArgs.push_back(args[i]);
    }

  }

  // last dir/file
  if (args.back() != "" || args.back() != ".") {
    newArgs.push_back(args.back());
  }

  return boost::join(newArgs, delim);
}

Solution in C++

string normalizePath(const string& path) {
  const string delim = "/";

  vector<string> args;
  boost::split(args, path, boost::is_any_of(delim));  

  vector<string> newArgs;

  // first dir/file
  if (args.size() > 0) {
    newArgs.push_back(args[0]);
  }

  // rest, except the last dir/file
  for (int i = 1; i < args.size() - 1; ++i) {

    if (args[i] == "" || args[i] == ".") {
      continue;
    } else if (args[i] == ".." && !newArgs.empty() && newArgs.back() != "..") {
      newArgs.pop_back();
    } else {
      newArgs.push_back(args[i]);
    }

  }

  // last dir/file
  if (args.back() != "" || args.back() != ".") {
    newArgs.push_back(args.back());
  }

  return boost::join(newArgs, delim);
}

it would be much simpler if we start from right.
count++ if we encounter a ".."
count-- if we encounter a non ".." and count is greater than 0

No Stack

even split function can be avoided if we update the below code to process characters one by one to make it O(n) run time O(1) memory

{
            string path = @"\c\b\x\..\a\..\..\y\foo.txt";
            string newpath = string.Empty;
            int count = 0;
            string[] pathsegments = path.Split('\\');
            for (int i = pathsegments.Length - 1; i >= 0;i-- )
            {
                if (pathsegments[i].Equals(".."))
                {
                    count++;
                }
                else
                {
                    if (count > 0)
                        count--;
                    else
                        if (newpath == null)
                        {
                            newpath = pathsegments[i];
                        }
                        else
                        {
                            newpath = pathsegments[i] + "\\" + newpath;
                        }
                }
            }

in Node.js:

var relPath = "\\a\\b\\..\\foo.txt";
var tokens = relPath.split("\\");
while (tokens.length > 0) {
    var folder = tokens.shift();
    if (folder.length == 0) continue; // ignores blank
    if (tokens[0] == "..") {
        tokens.shift();
        continue;
    }
    process.stdout.write("\\" + folder); 
}
// \a\foo.txt

SEP = '\\'
PARENT = '..'
CURRENT = '.'


def normalize_path(input):
    stack = []

    if input.startswith(SEP):
        stack.append('')    # marker for the initial root directory
        input = input[1:]

    comps = input.split(SEP)
    for comp in comps:
        if comp == '':
            continue
        elif comp == CURRENT:
            continue
        elif comp == PARENT:
            discard = stack.pop()
            if discard == '':
                raise Exception('Cannot go back further than the root directory!')
        else:
            stack.append(comp)

    return SEP.join(stack)


if __name__ == '__main__':
    for path in [
            r'\a\b\..\foo.txt',
            r'a\b\..\foo.txt',
            r'\a\b\..\..\foo.txt',
            r'\a\b\c\..\d\..\..\foo.txt',
            r'\.\a\b\..\foo.txt',
            r'a\.\b\..\foo.txt',
            r'\a\b\.\..\..\foo.txt',
            r'\a\.\.\b\c\..\d\..\..\.\foo.txt',
            ]:
        print normalize_path(path)


"""
Output:

\a\foo.txt
a\foo.txt
\foo.txt
\a\foo.txt
\a\foo.txt
a\foo.txt
\foo.txt
\a\foo.txt

"""

void normPath(string &path) {
int pos, i;
while ((pos = path.find("/..")) != string::npos )
{
for ( i=pos-1; i>=0; i--){
if (path[i] == '/')
break;
}
path.erase(i, pos - i +3);
} ;
}