Goldman Sachs Interview Question for Software Engineer / Developers


Country: Singapore
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 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
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;

public class SalePrice {
    public static void main(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>();

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

        for ( int i = 0; i < 5; i++ ) {
            for ( int j = prices[i][0]; j <= prices[i][1]; j++ ) {
                if ( !map.containsKey(j) || (map.containsKey(j) && prices[i][2] < map.get(j))) {
                    map.put(j, prices[i][2]);
                }
            }
        }
        for ( int date : map.keySet() ) {
            System.out.println(date + ", " + map.get(date));
        }
    }

}

- shirish.nyc December 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.List;
import java.util.ArrayList;

class Interval{
    public int startTime;
    public int endTime;
    public int price;

  public Interval(int startTime, int endTime, int price){
    this.startTime = startTime;
    this.endTime = endTime;
    this.price = price;
  }
}

class Solution{
  
  private static List<Interval> minimumPriceIntervals(List<Interval> inputList){
  int max_time = 0, min_time = 25;
  for(Interval list : inputList){
    if(list.endTime > max_time)
      max_time = list.endTime;
    if(list.startTime < min_time)
      min_time = list.startTime;
  }
  
  // Creating a new array and intializing each elements with highest integer value
  int[] arr = new int[max_time - min_time];
  for(int i = 0; i < arr.length; i++)
    arr[i] = Integer.MAX_VALUE;
    
  // Filling the array with the price
  for(Interval list : inputList){
    int c = list.endTime - list.startTime;
    int i = list.startTime - 1;
    while(c > 0){
      if(list.price < arr[i])
        arr[i] = list.price;
      i++;
      c--;
    }
  }
  
  List<Interval> outputList = new ArrayList<Interval>();
    
  int start_time = 0;
  int end_time = 1;
  int item_price = 0;
  while(end_time < arr.length) {
    int start = end_time;
    while(end_time < arr.length && arr[start_time] == arr[end_time]){
      item_price = arr[start_time];
      start_time = start_time + 1;
      end_time = end_time + 1;
    }
    if(end_time == arr.length){
      outputList.add(new Interval(start, end_time+1, item_price));
      return outputList;
    }
    else if(arr[start_time] != arr[end_time]){
      outputList.add(new Interval(start, end_time+1, item_price));
      item_price = arr[end_time];
      start_time = end_time;
      end_time = end_time + 1;
    }
  }
  
  return outputList;
    
  }
    
  public static void main(String[] args) {
   List<Interval> inputList = new ArrayList<Interval>();
    inputList.add(new Interval(1, 4, 10));
    inputList.add(new Interval(3, 7, 12));
    inputList.add(new Interval(5, 9, 8));

    List<Interval> outputList = minimumPriceIntervals(inputList);
    for(Interval list : outputList)
      System.out.println(list.startTime+" "+list.endTime+" "+list.price);
  }
}

- Anonymous April 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.List;
import java.util.ArrayList;

class Interval{
    public int startTime;
    public int endTime;
    public int price;

  public Interval(int startTime, int endTime, int price){
    this.startTime = startTime;
    this.endTime = endTime;
    this.price = price;
  }
}

class Solution{
  
  private static List<Interval> minimumPriceIntervals(List<Interval> inputList){
  int max_time = 0, min_time = 25;
  for(Interval list : inputList){
    if(list.endTime > max_time)
      max_time = list.endTime;
    if(list.startTime < min_time)
      min_time = list.startTime;
  }
  
  // Creating a new array and intializing each elements with highest integer value
  int[] arr = new int[max_time - min_time];
  for(int i = 0; i < arr.length; i++)
    arr[i] = Integer.MAX_VALUE;
    
  // Filling the array with the price
  for(Interval list : inputList){
    int c = list.endTime - list.startTime;
    int i = list.startTime - 1;
    while(c > 0){
      if(list.price < arr[i])
        arr[i] = list.price;
      i++;
      c--;
    }
  }
  
  List<Interval> outputList = new ArrayList<Interval>();
    
  int start_time = 0;
  int end_time = 1;
  int item_price = 0;
  while(end_time < arr.length) {
    int start = end_time;
    while(end_time < arr.length && arr[start_time] == arr[end_time]){
      item_price = arr[start_time];
      start_time = start_time + 1;
      end_time = end_time + 1;
    }
    if(end_time == arr.length){
      outputList.add(new Interval(start, end_time+1, item_price));
      return outputList;
    }
    else if(arr[start_time] != arr[end_time]){
      outputList.add(new Interval(start, end_time+1, item_price));
      item_price = arr[end_time];
      start_time = end_time;
      end_time = end_time + 1;
    }
  }
  
  return outputList;
    
  }
    
  public static void main(String[] args) {
   List<Interval> inputList = new ArrayList<Interval>();
    inputList.add(new Interval(1, 4, 10));
    inputList.add(new Interval(3, 7, 12));
    inputList.add(new Interval(5, 9, 8));

    List<Interval> outputList = minimumPriceIntervals(inputList);
    for(Interval list : outputList)
      System.out.println(list.startTime+" "+list.endTime+" "+list.price);
  }
}

- Shubhendu Kumar April 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
There is going to be a sale during this month.
You are interested in a particular item and you found that different Vendors have different prices during different time periods.
You collected the following information:

Vendor => (start date, end date, price) both sides inclusive
A => (1, 5, $20)
B => (3, 6, $15)
C => (2, 8, $25)
D => (7, 12, $18)
E => (1, 31, $22)
As you can see, there are conflicting entries. You need to print out a non-conflicting schedule of prices, taking the best price from each period:

e.g.
(1, 2, $20), (3, 6, $15), (7, 12, $18), (13, 31, $22)

*/

/**
input.txt:
1, 5, $20
3, 6, $15
2, 8, $25
7, 12, $18
1, 30, $22

output:
1, 2, $20
3, 6, $15
7, 12, $18
13, 31, $22
*/

package com.dbs.tester;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class BestPrice {

public static void main(String [] args){
int [] bestPrice = new int[32];

try {
Scanner scanner = new Scanner(new File("input.txt"));
while (scanner.hasNextLine()) {
String line = scanner.nextLine();
String [] elements = line.split(",");
int startDate = Integer.parseInt(elements[0].trim());
int endDate = Integer.parseInt(elements[1].trim());
int price = Integer.parseInt(elements[2].trim().substring(1));

for (int i = startDate; i <= endDate; i++){
if (bestPrice[i] == 0 || price < bestPrice[i]){
bestPrice[i] = price;
}
}
//System.out.println(scanner.nextLine());
}
scanner.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
int previous = 0;
int start = 0;
for (int i = 0; i < bestPrice.length; i++){
if (bestPrice[i] != previous){
if (start > 0){
System.out.println(start + ", " + (i - 1) + ", $" + previous);
}
start = i;
previous = bestPrice[i];
}
if (i == 31 && bestPrice[i] != 0){
System.out.println(start + ", " + i + ", $" + previous);
}
}
}
}

- Guo Yu May 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
There is going to be a sale during this month.
You are interested in a particular item and you found that different Vendors have different prices during different time periods.
You collected the following information:

Vendor => (start date, end date, price) both sides inclusive
A => (1, 5, $20)
B => (3, 6, $15)
C => (2, 8, $25)
D => (7, 12, $18)
E => (1, 31, $22)
As you can see, there are conflicting entries. You need to print out a non-conflicting schedule of prices, taking the best price from each period:

e.g.
(1, 2, $20), (3, 6, $15), (7, 12, $18), (13, 31, $22)

*/

/**
input.txt:
1, 5, $20
3, 6, $15
2, 8, $25
7, 12, $18
1, 30, $22

output:
1, 2, $20
3, 6, $15
7, 12, $18
13, 31, $22
*/

package com.dbs.tester;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class BestPrice {

public static void main(String [] args){
int [] bestPrice = new int[32];

try {
Scanner scanner = new Scanner(new File("input.txt"));
while (scanner.hasNextLine()) {
String line = scanner.nextLine();
String [] elements = line.split(",");
int startDate = Integer.parseInt(elements[0].trim());
int endDate = Integer.parseInt(elements[1].trim());
int price = Integer.parseInt(elements[2].trim().substring(1));

for (int i = startDate; i <= endDate; i++){
if (bestPrice[i] == 0 || price < bestPrice[i]){
bestPrice[i] = price;
}
}
//System.out.println(scanner.nextLine());
}
scanner.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
int previous = 0;
int start = 0;
for (int i = 0; i < bestPrice.length; i++){
if (bestPrice[i] != previous){
if (start > 0){
System.out.println(start + ", " + (i - 1) + ", $" + previous);
}
start = i;
previous = bestPrice[i];
}
if (i == 31 && bestPrice[i] != 0){
System.out.println(start + ", " + i + ", $" + previous);
}
}
}
}

- Guo Yu May 09, 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