Facebook Interview Question Software Engineer / Developers
Country: United States
Literally, your description can be translated into Perl code as the following:
#! perl -w
#Paths may not exist!
$absolutePath = "/usr/bin/mail";
$relativePath = "../../../etc/xyz/../abc";
$myPath = $absolutePath ."/". $relativePath;
@myPath = split(/\//,$myPath);
@finalPath = ();
foreach (@myPath){
if (/\Q..\E/){ # go up 1 level
pop @finalPath || die "ERROR: Wrong inputs\n";
}
else{
push @finalPath, $_;
};
};
$res = join("/",@finalPath);
print $res ."\n";
public String pwd(String absolutePath, String relativePath) {
String path = absolutePath + "/" + relativePath;
String[] s = path.split("/");
Stack<String> st = new Stack<String>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length; i++) {
if (s[i].isEmpty() || s[i].equals("."))
continue;
else if (s[i].equals("..")){
if (st.isEmpty())
throw new NullPointerException("Invalid Path");
else
st.pop();
}else
st.push(s[i]);
}
while (!st.isEmpty())
sb.insert(0, "/" + st.pop());
return sb.toString();
}
//concatenate the two paths then..
stack<string> S;
//assume getNextLevel returns NULL after munging whole path
int i=0;
string x;
while( x=getNextLevel(concatenatedFullPath, i++) )
{
//we do nothing if "." or ".." inside root (i.e., empty stack)
if( !strcmp(x, ".") || ( !strcmp(x, "..") && S.empty() ) ) continue;
if( !strcmp(x, "..") ) S.pop(), continue;
S.push(x);
}
return S; //holds absolute path
@Snob, it's language independent pseudocode
The whole put of the "return S" is an excuse to point out, via a trailing comment, that it holds the absolute path at that point (i.e., extract that information as you deem necessary).
There isn't even a function or a function call in the above code.
No, fortunately my memory can remember things that go beyond the day I'm currently living, so this interview question was from some time ago.
And you forgot the answer so you want to refresh your brain by posting it now :)
Makes sense.
Nope, I remember the answer (which btw, is usually easier to remember the problem than the answer), I just wanted to share the problem with others so that any geek preparing for an interview or just wanting to have some fun solving technical problems has more material.
Does this make no sense now?
-11: Another failed attempt at cleverness.
Even assuming that such a solution is possible (i.e. we have a shell/unix based system etc), what it one of the directories does not even exist?
Seriously? Lol man remind me not to have a personality around other software developers. Humor apparently does not compute.
LOL. I was the first Anon.
I thought -11 would show the humor. Seems like it was too subtle for all y'all.
y'all found it so clever, y'all forgot that it does not work. Whatabunchofmorons.
Assumptions Assumptions. Why do you think I am a guy, and those aliases are the same person?
I guess it is beyond your comprehension, so I forgive you.
import java.util.ArrayList;
import java.util.Arrays;
public class main{
public static String findPath(String absolutePath, String relativePath) {
ArrayList<String> absolutePaths = new ArrayList<String>(Arrays.asList(absolutePath.split("/")));
String[] relativePaths = relativePath.split("/");
int lastIndex = absolutePaths.size()-1;
System.out.println(absolutePaths);
for (int i=0; i<relativePaths.length; i++) {
if (relativePaths[i].equals("..") && lastIndex>=0) {
absolutePaths.remove(lastIndex);
lastIndex--;
System.out.println("REMOVED "+absolutePaths);
} else {
absolutePaths.add(relativePaths[i]);
lastIndex++;
System.out.println("ADDED "+absolutePaths);
}
}
StringBuilder sb = new StringBuilder();
for (String s : absolutePaths)
{
sb.append(s);
sb.append("/");
}
return sb.toString();
}
public static void main(String []args){
System.out.println(findPath("/usr/bin/mail", "../../../etc/xyz/../abc"));
}
}
This can be solved with a simple stack implementation. The following code illustrates the output:
package com.kavitha.simulator;
import java.util.ArrayList;
import java.util.List;
public class ChangeDirectorySimulator {
List<String> pathElementsStack = null;
int top = 0;
public ChangeDirectorySimulator() {
pathElementsStack = new ArrayList<String>();
}
public void addPath( String path ) {
String givenPath = path.replaceAll("/","_");
String[] pathcomps = givenPath.split("_");
int i = 0;
for( i = 0; i < pathcomps.length; i ++) {
if( pathcomps[i].equals("..")) {
pathElementsStack.remove(--top);
} else {
pathElementsStack.add(top, pathcomps[i] );
top++;
}
}
return;
}
public String printPath() {
StringBuilder builder = new StringBuilder();
for( String s: pathElementsStack )
builder.append("/").append(s);
builder.deleteCharAt(0);
return builder.toString();
}
/**
* @param args
*/
public static void main(String[] args) {
if( args[0] == null || args[1] == null|| args[2] == null ) {
System.out.println( "Insufficient paramters provided" );
}
String absolutePath = args[0];
String relativePath1 = args[1];
String relativePath2 = args[2];
System.out.println( "Current path is " + absolutePath );
ChangeDirectorySimulator cd = new ChangeDirectorySimulator();
cd.addPath( absolutePath );
System.out.println( "Executing command: cd " + relativePath1 );
System.out.println( cd.printPath() );
cd.addPath(relativePath1);
System.out.println( "New path : " + cd.printPath() );
System.out.println( "Executing command: cd " + relativePath2 );
cd.addPath(relativePath2);
System.out.println( "Final output is " + cd.printPath() );
}
}
package com.kavitha.simulator;
import java.util.ArrayList;
import java.util.List;
public class ChangeDirectorySimulator {
List<String> pathElementsStack = null;
int top = 0;
public ChangeDirectorySimulator() {
pathElementsStack = new ArrayList<String>();
}
public void addPath( String path ) {
String givenPath = path.replaceAll("/","_");
String[] pathcomps = givenPath.split("_");
int i = 0;
for( i = 0; i < pathcomps.length; i ++) {
if( pathcomps[i].equals("..")) {
pathElementsStack.remove(--top);
} else {
pathElementsStack.add(top, pathcomps[i] );
top++;
}
}
return;
}
public String printPath() {
StringBuilder builder = new StringBuilder();
for( String s: pathElementsStack )
builder.append("/").append(s);
builder.deleteCharAt(0);
return builder.toString();
}
/**
* @param args
*/
public static void main(String[] args) {
if( args[0] == null || args[1] == null|| args[2] == null ) {
System.out.println( "Insufficient paramters provided" );
}
String absolutePath = args[0];
String relativePath1 = args[1];
String relativePath2 = args[2];
System.out.println( "Current path is " + absolutePath );
ChangeDirectorySimulator cd = new ChangeDirectorySimulator();
cd.addPath( absolutePath );
System.out.println( "Executing command: cd " + relativePath1 );
System.out.println( cd.printPath() );
cd.addPath(relativePath1);
System.out.println( "New path : " + cd.printPath() );
System.out.println( "Executing command: cd " + relativePath2 );
cd.addPath(relativePath2);
System.out.println( "Final output is " + cd.printPath() );
}
}
use a stack to track the folder names sequence.
#include <string>
#include <vector>
bool pushFolderName(const string &path, const int start,
const int length, vector<string> &path_buffer) {
string folder_name = path.substr(start, length);
if (folder_name == "..") {
// Pops a folder name from the stack, if stack is empty, return "".
if (path_buffer.empty()) return false;
path_buffer.pop_back();
} else if (folder_name != ".") {
path_buffer.push_back(folder_name);
}
return true;
};
bool getFolderNames(
const string &path, vector<string> &path_buffer) {
int start = 0;
int end = 0;
// Loops the input absolute path and push the folder names into stack.
while (true) {
end = path.find_first_of('/', end);
if (end == string::npos) break;
if (end > start + 1 &&
!pushFolderName(path, start, end - start, path_buffer)) {
return false;
}
++end;
start = end;
}
// The last folder name in absolute path may not contain '/'.
if (path.back() != '/' &&
!pushFolderName(path, start, end - start, path_buffer)) {
return false;
}
return true;
};
string &getAbsolutePath(
const string &absolute, const string &relative) {
// a stack to store the new absolute path's folder names.
vector<string> path_buffer;
// the return absolute path, default to empty.
string *path = new string();
if (!getFolderNames(absolute, path_buffer)) return *path;
if (!getFolderNames(relative, path_buffer)) return *path;
// Joins the new absolute path.
for (auto &folder_name : path_buffer) {
path->append("/");
path->append(folder_name);
}
return *path;
}
In Python using string.split and lists. Handles multiple slashes ex: //usr///bin
def join_path(absolute, relative):
path = [s for s in absolute.split("/") if s]
for item in relative.split("/"):
if item == ".":
continue
if item == "..":
path.pop()
else:
if item:
path.append(item)
return "/" + "/".join(path)
public static String getPath(String abs, String rel){
String result = "";
String []absArray = abs.split("/");
String []relArray = rel.split("/");
Stack<String> stack = new Stack<String>();
for (int j = 0; j < absArray.length;j++){
stack.push(absArray[j]);
}
for (int i = 0; i < relArray.length;i++){
if( relArray[i].equals("."))continue;
if( relArray[i].equals("..")){
stack.pop();
}else{
stack.push(relArray[i]);
}
}
while(!stack.empty()){
result = stack.pop() + "/"+ result;
}
return result;
}
public static String getAbsolutePath(String pwd, String relPath) {
Stack<String> stack = new Stack<String>();
String sep = String.valueOf(pwd.charAt(0));
String[] split = pwd.split(sep);
for(int i=1;i<split.length;i++){
stack.push(split[i]);
}
String[] exprSplit = relPath.split(sep);
for(int i=0;i<exprSplit.length;i++){
if(exprSplit[i].equals("..")){
if(stack.size() > 0){
stack.pop();
}
else{
throw new IllegalArgumentException(relPath);
}
}
else if(exprSplit[i].equals(".") || exprSplit[i].equals("")){
continue;
}
else{
stack.push(exprSplit[i]);
}
}
Iterator<String> iter = stack.iterator();
StringBuilder builder = new StringBuilder();
while(iter.hasNext()){
builder.append(sep+iter.next());
}
return builder.toString();
}
import java.util.Stack;
public class FindAbsolutePath {
public String getAbsolutePath(String basePath, String relativePath) throws Exception
{
Stack<String> stack = new Stack<String>();
String[] arr = basePath.split("/");
for(int i = 1 ; i < arr.length ; i++)
{
stack.push(arr[i]);
}
String[] relativeArr = relativePath.split("/");
boolean stackEmpty = false;
for(String relative : relativeArr)
{
if ("..".equals(relative))
{
if (stack.isEmpty())
{
throw new Exception("Invalid path");
}
else
{
stack.pop();
}
}
else
{
stack.push(relative);
}
}
String retVal = new String();
while (!stack.isEmpty())
{
String tmp = retVal;
retVal ="/"+stack.pop()+ tmp;
}
return retVal.toString();
}
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception
{
String str = new FindAbsolutePath().getAbsolutePath("/usr/bin/mail", "../../../etc/xyz/../abc");
System.out.println(str);
}
}
import java.util.Stack;
public class FindAbsolutePath {
public String getAbsolutePath(String basePath, String relativePath) throws Exception
{
Stack<String> stack = new Stack<String>();
String[] arr = basePath.split("/");
for(int i = 1 ; i < arr.length ; i++)
{
stack.push(arr[i]);
}
String[] relativeArr = relativePath.split("/");
boolean stackEmpty = false;
for(String relative : relativeArr)
{
if ("..".equals(relative))
{
if (stack.isEmpty())
{
throw new Exception("Invalid path");
}
else
{
stack.pop();
}
}
else
{
stack.push(relative);
}
}
String retVal = new String();
while (!stack.isEmpty())
{
String tmp = retVal;
retVal ="/"+stack.pop()+ tmp;
}
return retVal.toString();
}
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception
{
String str = new FindAbsolutePath().getAbsolutePath("/usr/bin/mail", "../../../etc/xyz/../abc");
System.out.println(str);
}
}
static void printPath()
{
string abs = "/usr/bin/mail";
string path = "../../../etc/xyz/../abc";
List<String> s = new List<string>();
char[] del = { '/' };
string[] splits = abs.Split(del);
foreach(string v in splits)
{
if(!v.Equals(""))
s.Add(v);
}
splits = path.Split(del);
string fullPath = "";
foreach(string v in splits)
{
if (v.Equals(".."))
{
if (s.Count > 0)
s.RemoveAt(s.Count - 1);
else
{
Console.Out.WriteLine("ERROR");
return;
}
}
else
{
s.Add(v);
}
}
foreach (string v in s)
fullPath += "/" + v;
Console.Out.WriteLine(fullPath);
}
#include "stdafx.h"
#include "string"
#include "stack"
#include "iostream"
#include "stdio.h"
using namespace std;
string Pathfind(string s1, string s2){
std::stack<string> ss;
string sbuffer = "";
for(int i = 0; i< s1.length(); i++){
if(s1[i] == '/'){
if(sbuffer!= ""){
ss.push(sbuffer);
sbuffer = "";
}
} else {
sbuffer += s1[i];
}
if(i == s1.length() -1){
ss.push(sbuffer);
sbuffer = "";
}
}
for(int i= 0; i<s2.length(); i++){
if(s2[i] == '/'){
if(sbuffer == ".."){
ss.pop();
} else {
if(sbuffer != ""){
ss.push(sbuffer);
}
}
sbuffer = "";
} else {
sbuffer += s2[i];
}
if(i == s2.length() -1){
ss.push(sbuffer);
}
}
string result = "";
while(!ss.empty()){
string buffer = "/";
buffer.append(ss.top());
ss.pop();
buffer.append(result);
result = buffer;
}
return result;
}
void main(void)
{
cout << Pathfind("/usr/bin/mail", "../../../etc/xyz/../abc")<< endl;
int i;
cin>>i;
}
static string GetAbsolutePath(string currentPath, string newRelativePath)
{
char seperator = '/';
string[] paths = newRelativePath.Split(seperator);
foreach (string path in paths)
{
if (path.Equals(".."))
{
int index = currentPath.LastIndexOf(seperator);
if (index != -1)
{
currentPath = currentPath.Remove(index);
}
else
{
throw new Exception("Invalid parameter");
}
}
else
{
currentPath += "/";
currentPath += path;
}
}
return currentPath;
}
public class RelativePath {
private static final String UP = "..";
/**
* Calculates absolute path by its relative
*
* @param relative relative path to calculate
* @param current current absolute path
* @return absolute path correspondent to relative
*/
public String absolute(String relative, String current) {
if (relative == null) throw new IllegalArgumentException("Null relative path is not allowed");
relative = relative.trim();
if ("".equals(relative)) throw new IllegalArgumentException("Empty relative path is not allowed");
LinkedList<String> relativeStack = pathStack(relative);
LinkedList<String> absoluteStack = pathStack(current);
while (!relativeStack.isEmpty()) {
String token = relativeStack.removeLast();
if (UP.equals(token)) {
boolean mismatch = false;
try {
// just remove from second stack
String el = absoluteStack.removeFirst();
mismatch = "".equals(el);
} catch (NoSuchElementException no) {
mismatch = true;
}
if (mismatch) {
// if no element in second stack - there is no such path
throw new IllegalArgumentException(
String.format("No matching absolute path for current [%s] and relative: [%s]",
current, relative));
}
} else {
absoluteStack.addFirst(token);
}
}
StringBuilder sb = new StringBuilder();
while (!absoluteStack.isEmpty()) {
sb.append(absoluteStack.removeLast()).append("/");
}
String path = sb.toString();
return path.substring(0, path.length() - 1);
}
private LinkedList<String> pathStack(String path) {
if (path == null) throw new IllegalArgumentException("Null path is not allowed");
path = path.trim();
if ("".equals(path)) throw new IllegalArgumentException("Empty path is not allowed");
String[] tokens = path.split("/");
LinkedList<String> stack = new LinkedList<String>();
for (String t : tokens) {
stack.addFirst(t);
}
return stack;
}
public static void main(String[] args) {
RelativePath rp = new RelativePath();
System.out.println(rp.absolute("../../../etc/xyz/../abc", "/usr/bin/mail"));
System.out.println(rp.absolute("../../etc/xyz/../abc", "/usr/bin/mail"));
System.out.println(rp.absolute("../../../../etc/xyz/../abc", "/usr/bin/mail"));
}
}
Objective-C:
NSString* appendPaths(NSString* path, NSString* relativePath)
{
path = [path stringByTrimmingCharactersInSet:[NSCharacterSet characterSetWithCharactersInString:@"/"]];
relativePath = [relativePath stringByTrimmingCharactersInSet:[NSCharacterSet characterSetWithCharactersInString:@"/"]];
NSMutableArray* pathInParts = [NSMutableArray arrayWithArray:[path componentsSeparatedByString:@"/"]];
for (NSString* part in [relativePath componentsSeparatedByString:@"/"])
{
if ([part isEqualToString:@"."])
{
continue;
}
else if ([part isEqualToString:@".."])
{
if (pathInParts.count == 0)
{
return nil;
}
[pathInParts removeLastObject];
}
else
{
[pathInParts addObject:part];
}
}
return [@"/" stringByAppendingString: [pathInParts componentsJoinedByString:@"/"]];
}
<code class=" language-java">
public static String wocao(String p1,String p2){
if(p1.charAt(0)=='/') p1=p1.substring(1);
String arr_p1[]=p1.split("/");
Stack<String> stack_p1=new Stack<String>();
for(int i=0;i<arr_p1.length;i++)
stack_p1.push(arr_p1[i]);
String arr_p2[]=p2.split("/");
for(int i=0;i<arr_p2.length;i++){
if(!arr_p2[i].equals("..")){
stack_p1.push(arr_p2[i]);
}
else{
stack_p1.pop();
}
}
StringBuilder sb=new StringBuilder();
while(!stack_p1.isEmpty()){
sb.insert(0,stack_p1.pop()+"/");
}
return sb.toString().substring(0,sb.toString().length()-1);
}
</code>
package facebook;
import org.junit.Test;
import java.util.*;
import static org.junit.Assert.*;
public class RelativePath {
@Test
public void test() {
assertEquals("/etc/abc", getAbsolutePath("/usr/bin/mail", "../../../etc/xyz/../abc"));
}
private static String getAbsolutePath(String startPath, String relativePath) {
LinkedList<String> stack = new LinkedList<String>();
Collections.addAll(stack, startPath.split("/"));
String[] rpDirs = relativePath.split("/");
for (String rpDir : rpDirs) {
if (rpDir.equals("..")) {
try {
stack.removeLast();
} catch (NoSuchElementException e) {
throw new IllegalArgumentException("Wrong relative path - unable to go to the parent directory from root.");
}
}
else {
stack.add(rpDir);
}
}
StringBuilder sb = new StringBuilder();
Iterator<String> dirsIt = stack.iterator();
while (dirsIt.hasNext()) {
sb.append(dirsIt.next());
if (dirsIt.hasNext()) {
sb.append('/');
}
}
return sb.toString();
}
}
public static void main(String[] args){
String ap="/usr/bin/mail";
String rp="../../../etc/xyz/../abc";
pwd(ap, rp);
}
static void pwd(String ap,String rp){
String result="";
String[] a=ap.split("/");
String[] r=rp.split("/");
Stack<String> s=new Stack<String>();
for(int i=0;i<a.length;i++){
s.push(a[i]);
}
for(int j=0;j<r.length;j++){
if(r[j].equals("."))
continue;
else if(r[j].equals(".."))
s.pop();
else
s.push(r[j]);
}
while(!s.isEmpty()){
result=s.pop()+"/"+result;
}
System.out.println(result);
}
public String printPath(String currentPath, String relativePath){
Stack<String> stack=new Stack<String>();
StringBuilder sb =new StringBuilder();
for(int i=0;i<currentPath.length();i++){
if(i==currentPath.length()-1){
sb.append(currentPath.charAt(i));
stack.push(sb.toString());
}
if(currentPath.charAt(i)=='/'){
if(i==0) continue;
stack.push(sb.toString());
sb =new StringBuilder();
} else {
sb.append(currentPath.charAt(i));
}
}
sb=new StringBuilder();
for(int i=0;i<relativePath.length();i++){
if(i==relativePath.length()-1){
sb.append(relativePath.charAt(i));
stack.push(sb.toString());
}
if(relativePath.charAt(i)=='/'){
String curr=sb.toString();
if(i==0) continue;
if(curr.equals("..")){
stack.pop();
}
else{
stack.push(curr);
System.out.println(curr);
}
sb =new StringBuilder();
} else {
sb.append(relativePath.charAt(i));
}
}
StringBuilder res=new StringBuilder();
List<String> list=new ArrayList<String>();
while(!stack.isEmpty())
list.add(stack.pop());
for(int i=list.size()-1;i>=0;i--){
res.append("/"+list.get(i));
}
return res.toString();
}
public string GenerateAbsolutePath(string currentPath, string relativePath)
{
var stack = new Stack<string>();
var arr = currentPath.Split('/');
foreach (var item in arr)
if (item != null && item.Length > 0)
stack.Push(item);
arr = relativePath.Split('/');
foreach (var item in arr)
{
if (item == null || item.Length == 0 || item.Equals("."))
continue;
if (item.Equals(".."))
{
Debug.Assert(stack.Count > 0);
if (stack.Count == 0)
throw new Exception();
stack.Pop();
}
else
stack.Push(item);
}
var sb = new StringBuilder();
while (stack.Count > 0)
{
var item = stack.Pop();
sb.Insert(0, item);
sb.Insert(0, '/');
}
return sb.Length != 0 ? sb.ToString() : "/";
}
Hold current absolute path in stack.
- krbchd March 24, 2014That is push for every encountered "/" form r to l.
Now for relative path pop for every ... and push for every "/" with non"..." substring after it.
If stack is empty and pop condition arises throw an exception
Finally print elements of stack in rev order delimited by "/"