## 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] ) )
}

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

Comment hidden because of low score. Click to expand.
0

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

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()){
tempList.clear();
}
}
continue;
}

if(y[x]==y[x+1])

if(y[x+1]<y[x]){
dipFound=false;
tempList.clear();
}

if((y[x+1]>y[x]) && !dipFound){
dipFound = true;
if(!tempList.isEmpty()){
tempList.clear();
}
}
}

System.out.println(list);
}``````

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

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

}

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

if arr_0, if arr_1 > arr_0
for(arr_n (where n >= 1 && n < arr length)
if arr_n <= arr_n-1 && arr_n < arr_n+1
if(arr_length < arr_length-1)

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){
}
// 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]){
}
return results;
}``````

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``````

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``````

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``````

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

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]) {
}

if (yCoordinates[yCoordinates.length - 1] < yCoordinates[yCoordinates.length - 2]) {
}
}

for (int i = 1; i < yCoordinates.length - 1; i++) {
if (yCoordinates[i] < yCoordinates[i - 1]
&& yCoordinates[i] <= yCoordinates[i + 1]) {
}
}

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

}
}``````

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]) {
}

prev++;
curr++;
next++;

for(; next < nums.length; next++, prev++, curr++) {

if(nums[curr] < nums[prev] && nums[curr] < nums[next]) {
}
}

if(nums[curr] < nums[prev]) {
}

return result;

}``````

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``````

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]){
}
}
if(i==points.length-1){
if(points[i-1]>points[i]){
}
}
else{
if(points[i]>points[i+1]&&dip==false){
dip=true;
}
if(dip==true&&points[i+1]>points[i]){
dip=false;
}
}
}
System.out.println(list);

}
public static void main(String args[]){
lowestDipsGraph implementation=new lowestDipsGraph();
implementation.getDips();
}
}``````

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.

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.