Ebay Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

//You have to find Y[i] which satisifies this: Y[i-1]>Y[i] < Y[i+1]. Check for edge conditions
//Linear scan through array O(N)

    public static List<Integer> getLowDips(int [] y) {
    	List<Integer> returnList = new ArrayList<Integer>();
    	for(int i =0;i<y.length;i++) {
    		if((i==0 || y[i] < y[i-1] ) && (i==y.length-1 || y[i] < y[i+1] ) )
    			returnList.add(y[i]);
    	}
    	
    	return returnList;
    }

    public static void main (String [] args) {
    	int [] y = new int[] {0 ,10 ,20 ,10 ,30 ,40 ,50 ,40 ,30 ,20 ,10 ,20 ,30 ,40 ,50 ,60 ,50 ,60,70 };
    	System.out.println(getLowDips(y));
    }

- naren November 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vi.ramanauskas November 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- cubed November 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- zortlord November 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Sponch November 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Sponch November 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Mr.JoshuaGordon November 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- MD January 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- mk January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

    }

- PK February 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python:

dips = []
falling = False
dips.append(graph[0])
for i in range(1, len(graph)):
	if falling and graph[i] > graph[i - 1]:
		dips.append(graph[i - 1])
		falling = False
	elif not falling and graph[i] < graph[i - 1]:
		falling = True
if falling:
	dips.append(graph[len(graph) - 1])

print dips

- Egor July 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Saikrishnan January 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You should get this by O(lgN). The key is how you merge the values.

- Use divide and conquer June 19, 2016 | 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