Goldman Sachs Interview Question for Software Engineer / Developers


Country: Singapore
Interview Type: In-Person




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

Time Complexity: O(n) if the problem is limited to the current month, otherwise O(mn), where m is the length of the longest period.
Space Complexity: O(n)

A little overkill with the SalePeriod class, but it makes the start and end times easier to handle. You could just as well do it with plain arrays.

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

class SalePeriod {
  public int startDay;
  public int endDay;
  public double price;

  public SalePeriod(int startDay, int endDay, double price) {
    this.startDay = startDay;
    this.endDay = endDay;
    this.price = price;
  }

  @Override
  public String toString() {
    return "(" + startDay + ", " + endDay + ", $" + price + ")";
  }
}

class SaleSchedule {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int t = Integer.parseInt(br.readLine());

    SalePeriod[] sales = new SalePeriod[t];

    int minStart = Integer.MAX_VALUE;
    int maxEnd = Integer.MIN_VALUE;

    for (int i = 0; i < t; i++) {
      String[] s = br.readLine().split(" ");
      int start = Integer.parseInt(s[0]);
      int end = Integer.parseInt(s[1]);
      double price = Integer.parseInt(s[2]);

      minStart = Math.min(minStart, start);
      maxEnd = Math.max(maxEnd, end);

      sales[i] = new SalePeriod(start, end, price);
    }

    List<SalePeriod> nonConflictingSchedule = getNonConflictingSchedule(sales, minStart, maxEnd);

    nonConflictingSchedule.forEach(System.out::println);
  }

  public static List<SalePeriod> getNonConflictingSchedule(SalePeriod[] sales, int minStart, int maxEnd) {
    // This will contain the minimum price on the ith day at the ith index
    double[] prices = new double[maxEnd + 1];

    for (int i = 0; i <= maxEnd; i++) {
      prices[i] = Integer.MAX_VALUE;
    }

    for (SalePeriod sp : sales) {
      for (int i = sp.startDay; i <= sp.endDay; i++) {
        prices[i] = Math.min(sp.price, prices[i]);
      }
    }

    List<SalePeriod> nonConflictingSchedule = new ArrayList<>();

    int i = minStart;
    while(i <= maxEnd) {
      int start = i;

      while (i <= maxEnd - 1 && prices[i + 1] == prices[i]) {
        i += 1;
      }

      int end = i;
      i += 1;

      nonConflictingSchedule.add(new SalePeriod(start, end, prices[i - 1]));
    }
    
    return nonConflictingSchedule;
  }
}

Output:

5
1 5 20
3 6 15
2 8 25
7 12 18
1 31 22
(1, 2, $20.0)
(3, 6, $15.0)
(7, 12, $18.0)
(13, 31, $22.0)

- havanagrawal November 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;
  

public class Sales {


        public static void main(String[] args) {

                int [][] data = {{1,5,20}, {3,6,15}, {2,8,25}, {7,12,18}, {1,31,22}};

                LinkedList<int[]> schedule = new LinkedList<int[]>();

                int[] currEntry=null;

                for(int i=1; i<= 31; i++) {
                        int todayPrice = getLowerPrice(i,data,0,-1);
                        if(todayPrice == -1) continue;
                        if(currEntry == null || todayPrice != currEntry[2]) {
                                currEntry = new int[3];
                                currEntry[0] = i;
                                currEntry[1] = i;
                                currEntry[2] = todayPrice;
                                schedule.offer(currEntry);

                        } else if (todayPrice == currEntry[2]) {
                                currEntry[1] = i;
                        }
                }
                int[] pop;
                while(schedule.size() >0 && (pop = schedule.removeFirst())!=null) System.out.println("("+pop[0]+", "+pop[1]+", "+pop[2]+")");
        }


        public static int getLowerPrice(int day,int[][] data,int index, int currLowPrice) {
                if(index == data.length) return currLowPrice;
                if(data[index][0]<=day && data[index][1]>=day) {
                        if(data[index][2] <currLowPrice || currLowPrice == -1) currLowPrice = data[index][2];
                }

                return getLowerPrice(day,data,++index,currLowPrice);
        }
}

- thatfernando@yahoo.com November 21, 2017 | 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