1
\$\begingroup\$

I was trying to solve the following question:

You are given 2 arrays: one representing the time people arrive at a door and other representing the direction they want to go(in or out) You have to find at what time each person will use the door provided no 2 people can use the door at the same time. Constraints: the door starts with ‘in’ position, in case of a conflict(2 or more people trying to use the door at the same time), the direction previously used holds precedence. If there is no conflict whoever comes first uses the door. Also if no one uses the door, it reverts back to the starting ‘in’ position. Should be linear time complexity.

Is this a good approach? Can I get my code reviewed / refactored? Any advice regarding the following approach? Is there a better way to do this?

public class Doors {

        public class visitor {
                int time;
                String dir;

                public visitor(int time, String dir) {
                        this.time = time;
                        this.dir = dir;
                }
        }

        public String defaultDir = "In";
        public String lastDir = defaultDir;

        public static void main(String[] args) {
                int[] time = new int[] { 2, 3, 5, 1, 7, 4, 2 };
                String dir[] = new String[] { "In", "Out", "In", "Out", "Out", "In", "Out" };
                Doors obj = new Doors();
                obj.findTime(time, dir);
        }

        private void findTime(int[] time, String[] dir) {

                Map<Integer, Map<String, List<visitor>>> myMap = new TreeMap<>();
                for (int i = 0; i < time.length; i++) {
                        List<visitor> myList = new ArrayList<Doors.visitor>();
                        if (!myMap.containsKey(time[i])) {
                                Map<String, List<visitor>> visitorMap = new HashMap<String, List<visitor>>();
                                myList.add(new visitor(time[i], dir[i]));
                                visitorMap.put(dir[i], myList);
                                myMap.put(time[i], visitorMap);
                        } else {
                                Map<String, List<visitor>> visitorMap = myMap.get(time[i]);
                                if (!visitorMap.containsKey(dir[i])) {
                                        myList.add(new visitor(time[i], dir[i]));
                                        visitorMap.put(dir[i], myList);
                                } else {
                                        myList = visitorMap.get(dir[i]);
                                        myList.add(new visitor(time[i], dir[i]));
                                        visitorMap.put(dir[i], myList);
                                }
                        }
                }

                for (Entry<Integer, Map<String, List<visitor>>> entry : myMap.entrySet()) {
                        if (entry.getValue().size() > 1) { // now we know multiple people are trying to enter at the same time
                                List<visitor> visitors = entry.getValue().get(lastDir);
                                for (visitor v : visitors) {
                                        System.out.println(v.time + " : " + v.dir);
                                }
                                lastDir = lastDir.contentEquals("In") ? "Out" : "In";
                                visitors = entry.getValue().get(lastDir);
                                for (visitor v : visitors) {
                                        System.out.println(v.time + " : " + v.dir);
                                }

                        } else {
                                if (entry.getValue().containsKey("In")) {
                                        List<visitor> visitors = entry.getValue().get("In");
                                        for (visitor v : visitors) {
                                                System.out.println(v.time + " : " + v.dir);
                                        }
                                        lastDir = "In";
                                } else {
                                        List<visitor> visitors = entry.getValue().get("Out");
                                        for (visitor v : visitors) {
                                                System.out.println(v.time + " : " + v.dir);
                                        }
                                        lastDir = "Out";
                                }

                        }

                        entry.setValue(new HashMap<String, List<visitor>>());
                }
        }
}
\$\endgroup\$
  • \$\begingroup\$ I would have done it by sorting a List<Visitor>, but that's not linear time complexity. Oh well, I failed the interview. \$\endgroup\$ – Gilbert Le Blanc May 7 at 12:32
  • \$\begingroup\$ To be a bit more helpful, the question is basically "create a TreeMap that allows duplicate keys". A bit challenging for an interview question. And this comment is after 30 minutes or more of thought. \$\endgroup\$ – Gilbert Le Blanc May 7 at 12:44
2
\$\begingroup\$

I finally came up with an idea that might work.

I created a TreeMap<Integer, List<String>>.

Here's the output from my last test run. The first group is the TreeMap I created. The second group is a List<Visitor> that I created from the map. I just used the Visitor class toString method to output the List.

1 [Out]
2 [In, Out]
3 [Out]
4 [In]
5 [In]
7 [Out]

Visitor [time=1, direction=Out]
Visitor [time=2, direction=Out]
Visitor [time=2, direction=In]
Visitor [time=3, direction=Out]
Visitor [time=4, direction=In]
Visitor [time=5, direction=In]
Visitor [time=7, direction=Out]

Here's the code. It took me several hours to come up with this idea. I don't envy anyone trying to come up with this in an interview.

Edited to add: I'm not sure what comments the OP is looking for.

The createMap method checks to see if a key, value pair exists indirectly. If the value is null, the key, value pair doesn't exist. So I create an ArrayList<String> and add the key, value to the map. If the key, value pair exists, then I add the string to the value List. Since the value is a List, I maintain the order of the input people.

The createList method is a little more complicated. I iterate through the map keys, retrieving the List<String> value for each key. If there's only one element in the List (one person), I put them through the door and set the default direction of the door.

If there's more than one element in the List<String> value, I iterate through the List twice. Once with the default door direction, and once again with the opposite door direction. Since the List for one time value is likely to be small, the double iteration is pretty short.

Worst case, when everyone arrives at the door at the same time, the cost of creating the map, and iterating through the map value is 3n, which is effectively n.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class Doors {

    public static void main(String[] args) {
        int[] time = new int[] { 2, 3, 5, 1, 7, 4, 2 };
        String direction[] = new String[] { "In", "Out", 
                "In", "Out", "Out", "In", "Out" };
        Doors obj = new Doors();
        List<Visitor> visitors = 
                obj.findTime(time, direction);
        for (Visitor visitor : visitors) {
            System.out.println(visitor);
        }
    }

    public List<Visitor> findTime(int[] time, 
            String[] direction) {
        Map<Integer, List<String>> map =
                createMap(time, direction);
        printMap(map);
        return createList(map);
    }

    private void printMap(Map<Integer, List<String>> map) {
        Set<Integer> set = map.keySet();
        Iterator<Integer> iter = set.iterator();
        while (iter.hasNext()) {
            Integer key = iter.next();
            List<String> value = map.get(key);
            System.out.println(key + " " + value);
        }
        System.out.println();
    }

    private Map<Integer, List<String>> createMap(
            int[] time, String[] direction) {
        Map<Integer, List<String>> map = new TreeMap<>();
        for (int i = 0; i < time.length; i++) {
            Integer key = time[i];
            List<String> value = map.get(key);
            if (value == null) {
                value = new ArrayList<>();
            }
            value.add(direction[i]);
            map.put(key, value);
        }
        return map;
    }

    private List<Visitor> createList(
            Map<Integer, List<String>> map) {
        List<Visitor> visitors = new ArrayList<>();
        String defaultDirection = "In";
        Set<Integer> set = map.keySet();
        Iterator<Integer> iter = set.iterator();
        while (iter.hasNext()) {
            Integer key = iter.next();
            List<String> value = map.get(key);
            if (value.size() == 1) {
                String s = value.get(0);
                Visitor visitor = new Visitor(key, s);
                visitors.add(visitor);
                defaultDirection = s;
            } else {
                createVisitors(visitors, defaultDirection, 
                        key, value);
                defaultDirection = changeDefaultDirection(
                        defaultDirection);
                createVisitors(visitors, defaultDirection, 
                        key, value);
            }
        }
        return visitors;
    }

    private void createVisitors(List<Visitor> visitors, 
            String defaultDirection, Integer key, 
            List<String> value) {
        for (int i = 0; i < value.size(); i++) {
            String s = value.get(i);
            if (s.equals(defaultDirection)) {
                Visitor visitor = new Visitor(key, s);
                visitors.add(visitor);
            }
        }
    }

    private String changeDefaultDirection(
            String defaultDirection) {
        return defaultDirection.equals("In") ? "Out" : "In";
    }

    public class Visitor {

        private final Integer time;

        private final String direction;

        public Visitor(Integer time, String direction) {
            this.time = time;
            this.direction = direction;
        }

        public int getTime() {
            return time;
        }

        public String getDirection() {
            return direction;
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("Visitor [time=");
            builder.append(time);
            builder.append(", direction=");
            builder.append(direction);
            builder.append("]");
            return builder.toString();
        }

    }

}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hey @Gilbert Le Blanc I like this approach. Could you add some more comments to the code. Like for the methods createList and createMap? \$\endgroup\$ – coder1532 May 7 at 19:42
1
\$\begingroup\$

I tried a different approach to solve the problem based on the test of the question and obtaining the same output using what could be considered a brutal approach to the problem: the map I'm using is like @Gilbert Le Blanc's answer a Map<Integer, List<String>>; you can construct the values of the map of two types:

  1. a sequence ["In", "In", ... "In", "Out", "Out", ... "Out"]
  2. a sequence ["Out", "Out", ... "Out", "In", "In", ..., "In"]

So if you have your method findTime, you can create your map in the following way:

private void findTime(int[] times, String[] dirs) {
    //maxTime will be used after in the code while iterating over the map
    int maxTime = 0;

    Map<Integer, List<String>> map = new TreeMap<>();
    for (int i = 0; i < times.length; ++i) {
        int time = times[i];
        if (time > maxTime) { maxTime = time; } 
        String dir = dirs[i];
        if (map.containsKey(time)) {
            List<String> list = map.get(time);
            int index = list.indexOf(dir);
            if (index == -1) {
                list.add(dir);
            } else {
                list.add(index, dir);
            }
        } else {
            map.put(time, new ArrayList<>(Arrays.asList(dir)));
        }
    }

    //other lines of code 
}

So every value of the map will be a sequence of one of the two types ["In", "In", ... "In", "Out", "Out", ..., "Out"] or ["Out", "Out", ... "Out", "In", "In", ..., "In"]

Once you created your map you can iterate over it obtaining your same output:

String currentDir = "In";
for (int i = 0; i <= maxTime; ++i) {
    if (map.containsKey(i)) {
        List<String> list = map.get(i);
        if (!list.get(0).equals(currentDir)) {
            //reverse list so all elements equals to currentDir go in the first positions
            Collections.reverse(list); 
        }
        for (String s : list) {
            System.out.println(i + " : " + s);
        }
        int size = list.size();
        currentDir = list.get(size - 1);    
    } else {
        currentDir = "In"; //<-- no time, door everts back to the starting ‘in’ position
    }

Below the full code of the method findTime:

private void findTime(int[] times, String[] dirs) {
    int maxTime = 0;
    Map<Integer, List<String>> map = new TreeMap<>();
    for (int i = 0; i < times.length; ++i) {
        int time = times[i];
        if (time > maxTime) { maxTime = time; }
        String dir = dirs[i];
        if (map.containsKey(time)) {
            List<String> list = map.get(time);
            int index = list.indexOf(dir);
            if (index == -1) {
                list.add(dir);
            } else {
                list.add(index, dir);
            }
        } else {
            map.put(time, new ArrayList<>(Arrays.asList(dir)));
        }
    }


    String currentDir = "In";

    for (int i = 0; i <= maxTime; ++i) {
        if (map.containsKey(i)) {
            List<String> list = map.get(i);
            if (!list.get(0).equals(currentDir)) {
                Collections.reverse(list);
            }
            for (String s : list) {
                System.out.println(i + " : " + s);
            }
            int size = list.size();
            currentDir = list.get(size - 1);                
        } else {
            currentDir = "In";
        }
    }   
}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Since this site is not so much focused on clever solutions and algorithms but on code quality I'd like to give some comments on this.

Disclaimer this is my personal view and it might differ from what others may think. Never the less this would be my criteria if I'd be the interviewer. I'm also aware that some of my thoughts are easy to make when sitting on my couch having plenty of time.

Naming

I'm aware that an interview situation is quite stressing, but there are some basic rules violated in your code, that even a stress situation cannot excuse:

Conventions

  • Class names start upper case, so should your inner class visitor
  • Class names are singular form, so should your class Dors

For me this would be a major issue, worse then not finishing the task...

Similar is with the names of the input arrays. Since they are some kind of collection their names should have a plural 's'. I assume that this names where given my the interviewer, but I for myself would have renamed them even then.

Avoid technical name parts

What if you change your mind an visitorMap becomes some other kind of collection?

You might argue that this will not happen in an interview task, but the interviewer wants to find out how you usually code. Omitting good code criteria under pressure is not a benefit here.

Choose names from the problem domain

You have some variables with randomly picked names (obj, myMap, myList). This is a special case from the previous point and would show that you, when under pressure, create code that needs lots of refactoring afterwards.

Know the standard lib

When you initialize the map you use a rather complex if/else construct. But the computeIfAbsent() method was introduced long time ago with java-8, so that it should be known by any Java developer.

for (int i = 0; i < time.length; i++) {
    myMap.computeIfAbsent(time[i], HashMap::new)
         .computeIfAbsent(dir[i], ArrayList:new)
         .add(new Visitor(time[i], dir[i]));
}

Separate user interaction from processing

Your code outputs results in between the processing. I'd rather expect findTime() to return a List<Visitors> that has the desired order and have that that print out in main().

Mighty method

You do all the processing in a single method although is obviously consists of at least two blocks that your be extracted to separate private methods applying the Single Responsibility Pattern

Unnecessary special handling

In your methods second part you handle the case of only one person arrives differently then the case multiple persons arrive. The first case would be implicitly handled correctly by the latter.

Failed Requirements

I think this wouldn't be "NoGos" but bonuses, if done correctly...

  • Your code does not handle the case of

    Also if no one uses the door, it reverts back to the starting ‘in’ position.

    You simple ignore the time gaps.

  • The code is not of linear complexity

    I believe this is a trick question since the requirements involves sorting which simply cannot be done in linear complexity.


Finally: if you'd be interviewed by me and not writing unit tests you wouldn't get a call from me anyway...

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.