## Goldman Sachs Interview Question

Software Engineer / Developers**Country:**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);
}
}
```

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