Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
This is the basic idea, observe the nested functions ( ZoomBA ) :
def find_all_pic_dir(dir='.',
pic_extensions=set('.jpg', '.png' , '.gif') ){
// nest it
def recurse(cur_dir){
d = file ( cur_dir )
if ( !d.file.directory ) return
pic_dir = exists ( d ) :: { file($.o).extension.toLowerCase @ pic_extensions }
if ( pic_dir ){ dir_paths += cur_dir }
for ( child : d ){
recurse( child.canonicalPath )
}
}
// set up and call
dir_paths = set()
recurse( file(dir).file.canonicalPath )
// return
return dir_paths
}
dirs = find_all_pic_dir ( "/" )
println( dirs )
We don't need to keep track of multiple directories at the same level.
public List<String> getImageFilePaths(String fileName) throws Exception{
List<String> finalList = new ArrayList();
BufferedReader br = new BufferedReader(new FileReader(fileName));
String line = br.readLine();
Map<Integer, String> values = new HashMap();
while (line != null) {
int whitespaceCount = line.length() - line.trim().length();
if (whitespaceCount == 0) {
values = new HashMap();
values.put(0, line);
} else {
int tabCount = whitespaceCount/4;
line = line.trim();
if(line.startsWith("/")) {
values.put(tabCount, line);
} else if(line.endsWith(".gif") || line.endsWith(".jpg") || line.endsWith(".png")) {
StringBuilder sb = new StringBuilder();
for(int i=0;i<tabCount;i++) {
sb.append(values.get(i));
}
finalList.add(sb.toString());
}
}
line = br.readLine();
}
return finalList;
}
#TODO : Add validation for error scenarios
private static readonly int MaxPathsAllowed = 256;
private static readonly char PathSeparator = '/';
private static string[] directoryTokens = new string[MaxPathsAllowed];
private static int currentDirectoryIndex = -1;
private static void ProcessFile(string fileName)
{
foreach (var line in File.ReadAllLines(fileName))
{
ProcessLine(line);
}
}
private static void ProcessLine(string line)
{
int localTabCount = -1;
while (line[++localTabCount] == '\t') ;
var name = line.TrimStart('\t');
if (IsDirectory(name))
{
directoryTokens[localTabCount] = name;
currentDirectoryIndex = localTabCount;
} else if (IsImage(name))
{
PrintPath(name);
}
}
private static void PrintPath(string name)
{
PrintPath(name, directoryTokens, currentDirectoryIndex, PathSeparator);
}
private static void PrintPath(string name, string[] paramDirectoryTokens, int tabIndex, char separator)
{
var result = string.Empty;
for (int index = 0; index <= tabIndex; index++)
{
result += paramDirectoryTokens[index];
}
result += PathSeparator + name;
Console.WriteLine(result);
}
private static string[] imagePathExtensions = new string[] { ".img", ".png", ".jpg" };
private static bool IsImage(string name)
{
var result = false;
int index = name.LastIndexOf('.');
if (index != -1)
{
return imagePathExtensions.Contains(name.Substring(index));
}
return result;
}
private static bool IsDirectory(string name)
{
return name[0] == PathSeparator;
}
import java.util.*;
public class AbsolutePathImageDirectory {
HashSet<Node> set;
Node root;
public static void main(String[] args) {
AbsolutePathImageDirectory apid = new AbsolutePathImageDirectory();
System.out.println("(1) First approach using Brute Force");
apid.printAbsolutePath(new String[] {
"/usr",
" /local",
" profile.jpg",
" /bin",
" config.txt",
" dest.png",
" /rbin",
" img.gif",
"/sys",
" /re",
" /tmp",
" pic.jpg"
}
);
System.out.println("\n(2) Second approach using Trees");
apid.add(new String[] {
"/usr",
" /local",
" profile.jpg",
" /bin",
" config.txt",
" dest.png",
" /rbin",
" img.gif",
"/sys",
" /re",
" /tmp",
" pic.jpg"
}
);
System.out.println(Arrays.toString(apid.getAbsolutePath()));
}
public void printAbsolutePath(String[] inputs) {
for(int i = 0; i < inputs.length; i++) {
if(isImage(inputs[i])) {
int imageIndentCount = inputs[i].length()-inputs[i].replace(" ", "").length();
StringBuilder sb = new StringBuilder();
for(int j = i; j >= 0; j--) {
if(inputs[j].contains("/")) {
int indent = inputs[j].length()-inputs[j].replace(" ", "").length();
if(indent+2 == imageIndentCount) {
sb.insert(0,inputs[j].replace(" ",""));
imageIndentCount -= 2;
}
}
}
System.out.println(sb.toString());
}
}
}
public AbsolutePathImageDirectory() {
set = new HashSet<Node>();
root = new Node(null, "");
}
public void add(String[] inputs) {
// indent == 2 spaces
Node current = root;
int prevIndentCount = -2;
for(int i = 0; i < inputs.length; i++) {
int currentIndentCount = inputs[i].length()-inputs[i].replace(" ", "").length();
int difference = prevIndentCount-currentIndentCount+2;
System.out.println(inputs[i]+" "+currentIndentCount+" "+difference);
if(difference > 0) {
for(int j = 0; j < difference/2; j++) {
current = current.parent;
}
}
if(!isImage(inputs[i])) {
Node n = new Node(current, inputs[i].replace(" ", ""));
current.children.put(n.name, n);
current = n;
} else {
set.add(current);
currentIndentCount -= 2;
}
prevIndentCount = currentIndentCount;
}
}
public String[] getAbsolutePath() {
String[] result = new String[set.size()];
int index = 0;
for(Node n : set) {
StringBuilder sb = new StringBuilder();
while(n.parent != null) {
sb.insert(0, n.name);
n = n.parent;
}
result[index] = sb.toString();
index++;
}
return result;
}
public boolean isImage(String s) {
return s.contains(".png") ||
s.contains(".gif") ||
s.contains(".jpg") ||
s.contains(".jpeg");
}
public class Node {
HashMap<String, Node> children;
Node parent;
String name;
public Node(Node parent, String name) {
this.parent = parent;
this.children = new HashMap<>();
this.name = name;
}
}
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
- aonecoding January 15, 2017We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.