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 {

SalePeriod[] sales = new SalePeriod[t];

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

for (int i = 0; i < t; i++) {
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)``````

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}};

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);
}
}``````

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));
}
}``````

}

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){
return outputList;
}
else if(arr[start_time] != arr[end_time]){
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>();

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

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){
return outputList;
}
else if(arr[start_time] != arr[end_time]){
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>();

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

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);
}
}
}
}

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);
}
}
}
}

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.

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.