Ebay Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
A good solution, only thing is that, it doesn't handle the case where last point can be considered as a dip (add '60' to the end of an array it wont be detected). Also I think time can be improved by scanning from both ends (although the code will become messier.
Also (seeing the condition that needs to be satisfied) I don't think it handles the case where dip spans for a period of time. E.g.
/\ _ _ _ / \
/ \
But I think this case should be discussed with the person giving an assignment during an interview. Also I think other guys should check their code against this conditions as I don't see their test data including it.
My ugly solution that could be improved many ( MANY ) ways, including the case I've mentioned would be
int[] y = { 0, 10, 20, 10, 30, 40, 50, 40, 30, 20, 10, 20, 30, 40, 50, 60, 50,50,50,50, 60, 70, 60, 60};
List<Integer> list = new LinkedList<Integer>();
List<Integer> tempList = new LinkedList<Integer>();
boolean dipFound = false;
for(int x=0; x <y.length; x++){
if(x+1== y.length){ //handles the last index
if(y[x]<=y[x-1]){
if(!tempList.isEmpty()){
list.addAll(tempList);//this could be improved
tempList.clear();
}
list.add(y[x]);
}
continue;
}
if(y[x]==y[x+1])
tempList.add(y[x]);
if(y[x+1]<y[x]){
dipFound=false;
tempList.clear();
}
if((y[x+1]>y[x]) && !dipFound){
dipFound = true;
if(!tempList.isEmpty()){
list.addAll(tempList); //this could be improved
tempList.clear();
}
list.add(y[x]);
}
}
System.out.println(list);
}
Linear, with test case.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
public class Main{
static public void main(String[] args){
Set<List<Integer>> testCases = new HashSet<List<Integer>>();
testCases.add(new ArrayList<Integer>(10){{
add(0);
add(10);
add(20);
add(10);
add(30);
add(40);
add(50);
add(40);
add(30);
add(20);
add(10);
add(20);
add(30);
add(40);
add(50);
add(60);
add(50);
add(60);
add(70);
}});
for(List<Integer> testCase : testCases){
publishDips(testCase);
}
}
static private void publishDips(List<Integer> nums){
Iterator<Integer> iter = nums.iterator();
boolean inDescent = true;
boolean first = true;
int lastNum = -1;
int num = -1;
while(iter.hasNext()){
lastNum = num;
num = iter.next();
if(first){
first = false;
}
else{
boolean inDescentPrior = inDescent;
inDescent = num < lastNum;
if(inDescentPrior && !inDescent){
System.out.print(lastNum + " ");
}
}
}
System.out.println();
}
}
if arr_0, if arr_1 > arr_0
add arr_0 to the results
for(arr_n (where n >= 1 && n < arr length)
if arr_n <= arr_n-1 && arr_n < arr_n+1
add arr_n to the results
if(arr_length < arr_length-1)
add arr_length to results
Complexity is O(n) and memory use is O(n) (storing results)
public static ArrayList<Integer> findMins(int[] arr){
if(arr == null){
throw new NullPointerException("\"arr\" may not be null");
}
ArrayList<Integer> results = new ArrayList<Integer>();
if(arr.length < 2){
return results;
}
//set to true to handle arr_0
boolean lastDown = true;
for(int i =0; i < arr.length-1; i++){
//count the first position of a plateau
boolean thisUpOrEqual = arr[i] <= arr[i+1];
if(lastDown && thisUp){
results.add(arr[i]);
}
// don't count subsequent plateau positions
lastDown = arr[i] > arr[i+1];
}
//check the last case. cannot be a plateau
if(arr[length-1] < arr[length -2]){
results.add(arr[length-1]);
}
return results;
}
Using R Program
lowestPoint <- function(list){
diff <- c()
total <- length(list)
if(length(list) > 2){
if(list[1] < list[2]){
diff <- c(diff, list[1])
}
for(i in seq(total)){
if(i + 1 <= total){
if(list[i+1] - list[i] < 0){
if(length(diff) > 0 && (diff[length(diff)] > list[i+1])){
diff[length(diff)]<- list[i+1]
}else{
diff <- c(diff, list[i+1])
}
}
}
}
}
print(diff)
}
> list <- lowestPoint(c(0, 10, 20, 10, 30, 40, 50, 40, 30, 20, 10, 20, 30, 40, 50, 60, 50, 60, 70))
[1] 0 10 10 50
> list <- lowestPoint(c(20, 0, 10, 20, 10, 30, 40, 50, 40, 30, 20, 10, 20, 30, 40, 50, 60, 50, 60, 70, 60))
[1] 0 10 10 50 60
> list <- lowestPoint(c(-20, 0, 10, 20, 10, 30, 40, 50, 40, 30, 20, 10, 20, 30, 40, 50, 60, 50, 60, 70, 60))
[1] -20 10 10 50 60
Now it's correct
lowestPoint <- function(list){
diff <- c()
total <- length(list)
lastNegative <- 0
if(total > 2){
if(list[1] < list[2]){
diff <- c(diff, list[1])
lastNegative <- 1
}
for(i in seq(total)){
if(i + 1 <= total){
if(list[i+1] - list[i] < 0){
diffLength <- length(diff)
if(diffLength > 0 && (lastNegative != i)){
diff <- c(diff, list[i+1])
}else{
diff[diffLength]<- list[i+1]
}
lastNegative <- i+1
}
}
}
}
print(diff)
}
> list <- lowestPoint(c(0, 10, 20, 10, 30, 40, 50, 40, 30, 20, 10, 20, 30, 40, 50, 60, 50, 60, 70,60,70,50,70,40))
[1] 0 10 10 50 60 50 40
Another R solution:
temp = scan()
0 10 20 10 30 40 50 40 30 20 10 20 30 40 50 60 50 60 70
plot(temp, type='b')
result <- c()
if(temp[1] < temp[2]) {
result[1] <- temp[1]
} else{
result <- c()
}
for(i in 2:(length(temp)-1)){
if(temp[i] < temp[i+1] & temp[i] < temp[i-1]){
result <- c(result, temp[i])
}
}
if(temp[length(temp)] < temp[length(temp)-1]) {
result = c(result, temp[length(temp)])
}
result
My solution, which accounts for edge cases as well as repeating local minimum values:
static void printDips(int[] points) {
System.out.println("Printing low points in the array");
if(points == null || points.length < 2) return;
int l1 = points.length;
int lastDifVal = points[0]; // initialize repeating value checker
if(points[0] < points[1]) // see if the first element is a min point
System.out.print(points[0] + " ");
for(int i = 1; i < l1 - 1; i++) {
// account for possible repeating local minimum:
lastDifVal = points[i] == points[i - 1] ? lastDifVal : points[i - 1];
if(points[i] < lastDifVal && points[i] < points[i + 1]) {
System.out.print(points[i] + " ");
}
}
if(points[l1 - 2] > points[l1 - 1]) // see if the last element is a min point
System.out.print(points[l1 - 1] + " ");
System.out.println();
}
Example input and output:
Intput array length(20)
80 87 5 28 12 98 23 96 17 17 17 17 76 23 22 18 22 92 42 70
Printing low points in the array
80 5 12 23 17 18 42
public class Dips {
public static List<Integer> findDips(int[] yCoordinates) {
List<Integer> output = new ArrayList<Integer>();
if (yCoordinates.length > 1) {
if (yCoordinates[0] <= yCoordinates[1]) {
output.add(yCoordinates[0]);
}
if (yCoordinates[yCoordinates.length - 1] < yCoordinates[yCoordinates.length - 2]) {
output.add(yCoordinates[yCoordinates.length - 1]);
}
}
for (int i = 1; i < yCoordinates.length - 1; i++) {
if (yCoordinates[i] < yCoordinates[i - 1]
&& yCoordinates[i] <= yCoordinates[i + 1]) {
output.add(yCoordinates[i]);
}
}
return output;
}
public static void main(String[] args) {
int[] Ys = {0, 10, 20, 10, 30, 40, 50, 40, 30, 20, 10, 20, 30, 40, 50, 60, 50, 60, 70};
List<Integer> output = findDips(Ys);
for (Integer i : output){
System.out.println(i);
}
}
}
public static void main(String[] args) {
int[] nums = {0, 10, 20, 10, 30, 40, 50, 40, 30, 20, 10, 20, 30, 40, 50, 60, 50, 60, 70};
System.out.println(findLowestPointGraph(nums));
}
private static List<Integer> findLowestPointGraph(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
if(nums == null || nums.length < 2) {
return result;
}
int prev = -1;
int curr = 0;
int next = 1;
if(nums[curr] < nums[next]) {
result.add(nums[curr]);
}
prev++;
curr++;
next++;
for(; next < nums.length; next++, prev++, curr++) {
if(nums[curr] < nums[prev] && nums[curr] < nums[next]) {
result.add(nums[curr]);
}
}
if(nums[curr] < nums[prev]) {
result.add(nums[curr]);
}
return result;
}
Here's my solution O(n) -
import java.util.ArrayList;
public class lowestDipsGraph {
public void getDips(){
int[] points={20,10,20,10,5,30,40,50,40,30,20,10,20,30,40,50,60,50,60,70,60};
boolean dip=false;
ArrayList<Integer> list = new ArrayList<Integer>(7);
for(int i=0;i<points.length;i++){
if(i==0){
if(points[i]<points[i+1]){
list.add(points[i]);
}
}
if(i==points.length-1){
if(points[i-1]>points[i]){
list.add(points[i]);
}
}
else{
if(points[i]>points[i+1]&&dip==false){
dip=true;
}
if(dip==true&&points[i+1]>points[i]){
list.add(points[i]);
dip=false;
}
}
}
System.out.println(list);
}
public static void main(String args[]){
lowestDipsGraph implementation=new lowestDipsGraph();
implementation.getDips();
}
}
- naren November 13, 2014