Interview Question for Jr. Software Engineers


Team: Python development
Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

I realize this says Python, but did this in Java for kicks.,

package com.ezraepstein.careercup;

import java.io.InputStream;
import java.util.*;

public class Main implements Runnable {

  private static String[] reverseStringArray(final String[] a) {
    final int l = a.length;
    String tmp;
    for (int i=0; i<(l>>1); ++i) {
      tmp = a[l-1-i];
      a[l-1-i] = a[i];
      a[i] = tmp;
    }
    return a;
  }

  static class Path implements Comparable<Path>{
    final String[] stops;
    final Integer distance;

    String getOrigin() {
      return stops[0];
    }
    String getDestination() {
      return stops[stops.length - 1];
    }

    Path(Integer distance, String... stops) {
      if (distance == null || distance < 0) {
        throw new IllegalArgumentException("distance must not be null or negative");
      }

      this.distance = distance;
      this.stops = (stops.length < 2 || stops[0].compareTo(stops[stops.length-1]) <= 0) ? stops : reverseStringArray(stops);

      if (getOrigin() == null || getDestination() == null || getOrigin().equals(getDestination())) {
        throw new IllegalArgumentException("origin and destination must be non-null and distinct");
      }
    }

    Path(final String origin, final String destination, final Integer distance) {
      this(distance, origin, destination);
    }

    static Path makePath(Path s1, Path s2) {
      final int dist = s1.distance + s2.distance;
      if (s1.getOrigin().equals(s2.getOrigin())) {
        return new Path(dist, s1.getDestination(), s1.getOrigin(), s2.getDestination());
      } else if (s1.getOrigin().equals(s2.getDestination())) {
        return new Path(dist, s1.getDestination(), s1.getOrigin(), s2.getOrigin());
      } else if (s1.getDestination().equals(s2.getOrigin())) {
        return new Path(dist, s1.getOrigin(), s1.getDestination(), s2.getDestination());
      } else if (s1.getDestination().equals(s2.getDestination())) {
        return new Path(dist, s1.getOrigin(), s1.getDestination(), s2.getOrigin());
      } else {
        return null;
      }
    }

    @Override
    public String toString() {
      final StringJoiner sj = new StringJoiner(":", "", "")
              .add(distance.toString());
      for (String s : stops) {
        sj.add(s);
      }
      return sj.toString();
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      final Path path = (Path) o;
      return Arrays.equals(stops, path.stops) &&
              Objects.equals(distance, path.distance);
    }

    @Override
    public int hashCode() {
      return Objects.hash(stops, distance);
    }

    @Override
    public int compareTo(Path o) {
      return o.distance.compareTo(distance); // longest first
    }
  }

  private final Scanner scanner;

  private final Map<String, TreeSet<Path>> segmentMap;

  private Path longestPath = null;


  private Path readLine() {
    return new Path(scanner.next().trim().toUpperCase(), scanner.next().trim().toUpperCase(), scanner.nextInt());
  }

  private void addSegmentForLocation(final Path s, final String location) {
    TreeSet<Path> result;
    if (!segmentMap.containsKey(location)) {
      result = new TreeSet<>();
      segmentMap.put(location, result);
    } else {
      result = segmentMap.get(location);
    }
    result.add(s);
  }

  private Path longestForSegmentAndLocation(final Path s, final boolean origin) {
    Path p = null;
    final TreeSet<Path> fromLoc = segmentMap.get((origin ? s.getOrigin() : s.getDestination()));
    if (fromLoc != null) {
      long d = s.distance;

      final Iterator<Path> itr = fromLoc.iterator();
      // given our sorting, the first item is the longest
      Path s2 = itr.next();
      if (s2.equals(s)) {
        // handle edge case where Path s is already in the map.
        s2 = itr.next();
      }
      if (longestPath == null || (d+s2.distance > longestPath.distance)) {
        // origin sorts before destination, so construct the path accordingly to keep lexicographic ordering
        p = Path.makePath(s, s2);
      }

    }
    return p;
  }

  private void computeLongestPath(final Path s, final boolean origin) {
    final Path p = longestForSegmentAndLocation(s, origin);
    if (longestPath == null || (p != null && p.distance > longestPath.distance)) {
      longestPath = p;
    }
  }

  private void addSegment(final Path s) {
    if (!segmentMap.isEmpty()) {
      computeLongestPath(s, true);
      computeLongestPath(s, false);
    }
    addSegmentForLocation(s, s.getOrigin());
    addSegmentForLocation(s, s.getDestination());
  }

  @Override
  public void run() {
    for (;;) {
      addSegment(readLine());
      if (longestPath != null) {
        System.out.println(longestPath);
      }
    }
  }

  private Main(final InputStream ins) {
    this.scanner = new Scanner(ins).useDelimiter("[:\\n]");
    this.segmentMap = new HashMap<>();
  }

  public static void main(String[] args) {
    new Main(System.in).run();
  }

}

- e2 November 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1

- arachni_name"'`-- November 14, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1"'`--

- arachni_name November 14, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1)

- arachni_name November 14, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1

- arachni_name November 14, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1

- arachni_name) November 14, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Java rather than Python, a simple impl is :

package com.ezraepstein.careercup;

import java.io.InputStream;
import java.util.*;

public class Main implements Runnable {

  private static String[] reverseStringArray(final String[] a) {
    final int l = a.length;
    String tmp;
    for (int i=0; i<(l>>1); ++i) {
      tmp = a[l-1-i];
      a[l-1-i] = a[i];
      a[i] = tmp;
    }
    return a;
  }

  static class Path implements Comparable<Path>{
    final String[] stops;
    final Integer distance;

    String getOrigin() {
      return stops[0];
    }
    String getDestination() {
      return stops[stops.length - 1];
    }

    Path(Integer distance, String... stops) {
      if (distance == null || distance < 0) {
        throw new IllegalArgumentException("distance must not be null or negative");
      }

      this.distance = distance;
      this.stops = (stops.length < 2 || stops[0].compareTo(stops[stops.length-1]) <= 0) ? stops : reverseStringArray(stops);

      if (getOrigin() == null || getDestination() == null || getOrigin().equals(getDestination())) {
        throw new IllegalArgumentException("origin and destination must be non-null and distinct");
      }
    }

    Path(final String origin, final String destination, final Integer distance) {
      this(distance, origin, destination);
    }

    static Path makePath(Path s1, Path s2) {
      final int dist = s1.distance + s2.distance;
      if (s1.getOrigin().equals(s2.getOrigin())) {
        return new Path(dist, s1.getDestination(), s1.getOrigin(), s2.getDestination());
      } else if (s1.getOrigin().equals(s2.getDestination())) {
        return new Path(dist, s1.getDestination(), s1.getOrigin(), s2.getOrigin());
      } else if (s1.getDestination().equals(s2.getOrigin())) {
        return new Path(dist, s1.getOrigin(), s1.getDestination(), s2.getDestination());
      } else if (s1.getDestination().equals(s2.getDestination())) {
        return new Path(dist, s1.getOrigin(), s1.getDestination(), s2.getOrigin());
      } else {
        return null;
      }
    }

    @Override
    public String toString() {
      final StringJoiner sj = new StringJoiner(":", "", "")
              .add(distance.toString());
      for (String s : stops) {
        sj.add(s);
      }
      return sj.toString();
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      final Path path = (Path) o;
      return Arrays.equals(stops, path.stops) &&
              Objects.equals(distance, path.distance);
    }

    @Override
    public int hashCode() {
      return Objects.hash(stops, distance);
    }

    @Override
    public int compareTo(Path o) {
      return o.distance.compareTo(distance); // longest first
    }
  }

  private final Scanner scanner;

  private final Map<String, TreeSet<Path>> segmentMap;

  private Path longestPath = null;


  private Path readLine() {
    return new Path(scanner.next().trim().toUpperCase(), scanner.next().trim().toUpperCase(), scanner.nextInt());
  }

  private void addSegmentForLocation(final Path s, final String location) {
    TreeSet<Path> result;
    if (!segmentMap.containsKey(location)) {
      result = new TreeSet<>();
      segmentMap.put(location, result);
    } else {
      result = segmentMap.get(location);
    }
    result.add(s);
  }

  private Path longestForSegmentAndLocation(final Path s, final boolean origin) {
    Path p = null;
    final TreeSet<Path> fromLoc = segmentMap.get((origin ? s.getOrigin() : s.getDestination()));
    if (fromLoc != null) {
      long d = s.distance;

      final Iterator<Path> itr = fromLoc.iterator();
      // given our sorting, the first item is the longest
      Path s2 = itr.next();
      if (s2.equals(s)) {
        // handle edge case where Path s is already in the map.
        s2 = itr.next();
      }
      if (longestPath == null || (d+s2.distance > longestPath.distance)) {
        // origin sorts before destination, so construct the path accordingly to keep lexicographic ordering
        p = Path.makePath(s, s2);
      }

    }
    return p;
  }

  private void computeLongestPath(final Path s, final boolean origin) {
    final Path p = longestForSegmentAndLocation(s, origin);
    if (longestPath == null || (p != null && p.distance > longestPath.distance)) {
      longestPath = p;
    }
  }

  private void addSegment(final Path s) {
    if (!segmentMap.isEmpty()) {
      computeLongestPath(s, true);
      computeLongestPath(s, false);
    }
    addSegmentForLocation(s, s.getOrigin());
    addSegmentForLocation(s, s.getDestination());
  }

  @Override
  public void run() {
    for (;;) {
      addSegment(readLine());
      if (longestPath != null) {
        System.out.println(longestPath);
      }
    }
  }

  private Main(final InputStream ins) {
    this.scanner = new Scanner(ins).useDelimiter("[:\\n]");
    this.segmentMap = new HashMap<>();
  }

  public static void main(String[] args) {
    new Main(System.in).run();
  }

}

- ezra.epstein November 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Observations:
- Transit Station Memory Needs
-- For every transit station, we need to remember only top two items (because of two tickets)
-- Ex: For NYC, NYC-HAWAI, NYC-SEATTLE are top two and rest such as NYC-LA, NYC-CHI can be forgotten with NYC as transit station. However, we should not forget the same with NYC station as start/end station

- We can't forget anything other than transit related stuff. Otherwise, issues would occur. For example, in the given input example;
let's say fifth row input is CHI:WA is 8192, then longest route is 8911:NYC:CHI:WA
At this row, can we forget NYC:SEATTLE?
let's say sixth row input is SEATTLE:WA is 9100, then longest route is 11558:NYC:SEATTLE:WA which requires NYC:SEATTLE to be remembered

Algorithm:

- Route is of type (String Station1, String Station2, int Distance)
- There is a NONE(String.EMPTY, String.EMPTY, 0) route to indicate no route
- Longest Route is of type (String startStation, String transitStation, String endStation, int totalDistance) 
  Initialized as (String.EMPTY, String.EMPTY, String.EMPTY, 0)
- Hash Table with Key as Transit Station, Value as Pair<Route, Route>
  Where, Pair contains two stations with longest distance from this station
  If there is only one route, other route would be NONE route
  
- For every input received,
  Create a record
  Add record to Hash Table twice - with key as station1 and station2
  If hash already has an entry for a station, update the value (pair of routes) appropriately such that top two routes are retained
  
- Get entries from hash using two stations of input route
  We will get four routes at the max
  Compute longest two-ticket distance using these four routes
  If newly computed longest route is longer than stored longest route
  { update stored longest route }
  Print stored longest route

- Laxmi Narsimha Rao Oruganti November 26, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More