Goldman Sachs Interview Question
Software Engineer / DevelopersCountry: Singapore
Interview Type: In-Person
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);
}
}
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));
}
}
}
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);
}
}
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);
}
}
/**
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);
}
}
}
}
/**
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);
}
}
}
}
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.
Output:
- havanagrawal November 13, 2017