Expedia Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




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

Loop through the array once to find the product of all numbers.
For the output, loop through the array and divide the product / index to find the corresponding value in the index.

- sv May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 5 vote

private static int[] multiplyData(int[] data) {
		int[] newArray=new int[data.length];
		for(int i=0;i<newArray.length;i++)
		{
			int temp=1;
			for(int j=0;j<newArray.length;j++)
			{
				if(i!=j)
				{
					temp*=data[j];
				}
			}
			newArray[i]=temp;
			
		}
		return newArray;
	}

- Vir Pratap Uttam May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not minimizing mulitiplications.

- Vib May 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Assume this is inside a method/function/proc/subroutine/whatever...
# Assume input array is IN and output is OUT
# {In java, we can declare new arrays off heap are zero initialized... assume that or zero initialize it on creation somehow... }

int zeroIndex = -1;
double prod = 1;

# Find zeros in input while accumulating product of
# all non-zero elements
for( int i=0; i < IN.length ; i++ )
{	
	# Found zero element
	if( IN[i] == 0 )
	{
		# This is second one found, so return OUT as is
		if ( zeroIndex >= 0 ) { return OUT; }

		# Save spot of zero
		zeroIndex = i;
		continue;
	}
	prod *= IN[i];
}

# Case where there was 1 zero...
if ( zeroIndex >= 0) 
{
	OUT[zeroIndex] = prod;
	return OUT;
}

# Calculate output array (in this case, all elements of IN were nonzero)
for( int i=0; i < IN.length ; i++ )
{	
	OUT[i] = prod / IN[i];
}
return OUT;

Ping me for job opportunities in Toronto/Waterloo area.

- RecruitingForSandvineCanada May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n: no. of element in input array.
following function can have 2n complexity.

function multiArr(iptArr){
	var i=0; //counter
	var prdt=1; //product of elements in input array
	for(i=0;i<iptArr.length;i++){ //find product
		if(iptArr[i]!==0)	 //if not zero
			prdt*=iptArr[i]; 
	}
	var newArr=[]; //array to be returned
	for(i=0;i<iptArr.length;iptArr++){
		newArr[i]=prdt/iptArr[i];	//except index
	}
	return (newArr);
}

- MMI May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void mulExceptIndex(int iArr[])
{
	int resultArr[SIZE];
	int product=1;

	for(int i=0;i<SIZE;i++)
		product = product * iArr[i];
	
	for(int i=0;i<SIZE;i++)
	{
		if(iArr[i]!=0)
		resultArr[i] = product/iArr[i];
	}
}

- sv May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice try, but this wont work if one of the values is zero as the product will become zero

- Ganesh May 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

///
package Algo;

public class ArrayMultiplication {
//Assumption : the input array is not empty
//Assumption : the multiplication product does not exceed the integer max value

public static void main(String args[]) {

int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
int B[] = null;

int product = 1;
int i = 0;
int zerocounter = 0;

// Does input array have zero value?
while (i < A.length) {
if (A[i] == 0) {
zerocounter += 1; // if yes, how many zeroes?
} else {
product = product * A[i]; // multiply all non-zero inputs
}
i++;
}

if (zerocounter <= 1) { // Does the input array have less than two zeroes?

B = new int[A.length]; // output array initialization
i = 0;
while (i < A.length) {
if (A[i] == 0) {
B[i] = product; // product of all non-zeroes
}else{
B[i] = product/A[i]; // product / ith input = product of all non-ith elements
}
i++;
}
}

for (int k = 0; k < B.length; k++) {
System.out.println("Array" + B[k]);
}
}

}
\\\

- Shalini June 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Assumption : the input array is not empty
//Assumption : the multiplication product does not exceed the integer max value
		int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
		int B[] = null; 
		int product = 1;  
		int i = 0;
		int zerocounter = 0;

		while (i < A.length) { 		// Does input array have zero value? 
			if (A[i] == 0) {
				zerocounter += 1; // if yes, how many zeroes?
			} else {
				product = product * A[i]; // multiply all non-zero inputs
			}
			i++;
		}
		if (zerocounter <= 1) { // Does the input array have less than two zeroes?
			B = new int[A.length]; // output array initialization
			i = 0;
			while (i < A.length) { 
				if (A[i] == 0) {
					B[i] = product; // product of all non-zeroes
				}else{
					B[i] = product/A[i]; // product / ith input = product of all non-ith elements
				}
				i++;
			}
		}

- Anonymous June 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Assumption : the input array is not empty
		//Assumption : the multiplication product does not exceed the integer max value
		int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
		int B[] = null; 
		int product = 1;  
		int i = 0;
		int zerocounter = 0;

		while (i < A.length) { 		// Does input array have zero value? 
			if (A[i] == 0) {
				zerocounter += 1; // if yes, how many zeroes?
			} else {
				product = product * A[i]; // multiply all non-zero inputs
			}
			i++;
		}
		if (zerocounter <= 1) { // Does the input array have less than two zeroes?
			B = new int[A.length]; // output array initialization
			i = 0;
			while (i < A.length) { 
				if (A[i] == 0) {
					B[i] = product; // product of all non-zeroes
				}else{
					B[i] = product/A[i]; // product / ith input = product of all non-ith elements
				}
				i++;
			}
		}

- Anonymous June 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Assumption : the input array is not empty
		//Assumption : the multiplication product does not exceed the integer max value
		int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
		int B[] = null; 
		int product = 1;  
		int i = 0;
		int zerocounter = 0;

		while (i < A.length) { 		// Does input array have zero value? 
			if (A[i] == 0) {
				zerocounter += 1; // if yes, how many zeroes?
			} else {
				product = product * A[i]; // multiply all non-zero inputs
			}
			i++;
		}
		if (zerocounter <= 1) { // Does the input array have less than two zeroes?
			B = new int[A.length]; // output array initialization
			i = 0;
			while (i < A.length) { 
				if (A[i] == 0) {
					B[i] = product; // product of all non-zeroes
				}else{
					B[i] = product/A[i]; // product / ith input = product of all non-ith elements
				}
				i++;
			}
		}

- Shalini June 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Assumption : the input array is not empty
//Assumption : the multiplication product does not exceed the integer max value
int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
int B[] = null;
int product = 1;
int i = 0;
int zerocounter = 0;

while (i < A.length) { // Does input array have zero value?
if (A[i] == 0) {
zerocounter += 1; // if yes, how many zeroes?
} else {
product = product * A[i]; // multiply all other inputs
}
i++;
}
if (zerocounter <= 1) { // Does the input array have less than two zeroes?
B = new int[A.length]; // output array initialization
i = 0;
while (i < A.length) {
if (A[i] == 0) {
B[i] = product; // product of all non-zeroes
}else{
B[i] = product/A[i]; // product / ith input = product of all non-ith elements
}
i++;
}
}

- Anonymous June 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Assumption : the input array is not empty
//Assumption : the multiplication product does not exceed the integer max value
int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
int B[] = null;
int product = 1;
int i = 0;
int zerocounter = 0;

while (i < A.length) { // Does input array have zero value?
if (A[i] == 0) {
zerocounter += 1; // if yes, how many zeroes?
} else {
product = product * A[i]; // multiply all other inputs
}
i++;
}
if (zerocounter <= 1) { // Does the input array have less than two zeroes?
B = new int[A.length]; // output array initialization
i = 0;
while (i < A.length) {
if (A[i] == 0) {
B[i] = product; // product of all non-zeroes
}else{
B[i] = product/A[i]; // product / ith input = product of all non-ith elements
}
i++;
}
}

- Shalini June 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Assumption : the input array is not empty
//Assumption : the multiplication product does not exceed the integer max value
int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
int B[] = null;
int product = 1;
int i = 0;
int zerocounter = 0;

while (i < A.length) { // Does input array have zero value?
if (A[i] == 0) {
zerocounter += 1; // if yes, how many zeroes?
} else {
product = product * A[i]; // multiply all other inputs
}
i++;
}
if (zerocounter <= 1) { // Does the input array have less than two zeroes?
B = new int[A.length]; // output array initialization
i = 0;
while (i < A.length) {
if (A[i] == 0) {
B[i] = product; // product of all non-zeroes
}else{
B[i] = product/A[i]; // product / ith input = product of all non-ith elements
}
i++;
}
}

- shaliniselvaraj5 June 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
        int[] array = {1, 2, 3, 4};
        int size = array.length;
        int[] result = new int[size];
        int temp = 1;
        for(int i = 0; i < size ; i++){
            temp = 1;
            for(int j = size-1 ; j >=0; j--){
                temp = temp * array[j];
            }
            result[i] = temp / array[i];
        }

        for(int value : result){
            System.out.println(value);
        }

}

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

public static void main(String[] args) {
        int[] array = {1, 2, 3, 4};
        int size = array.length;
        int[] result = new int[size];
        int temp = 1;
        for(int i = 0; i < size ; i++){
            temp = 1;
            for(int j = size-1 ; j >=0; j--){
                temp = temp * array[j];
            }
            result[i] = temp / array[i];
        }

        for(int value : result){
            System.out.println(value);
        }
    }

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

public void printMultiply(int[] arr){
	int nozero = 0;
	double prod = 1;
	for(int i=0;i<arr.length;i++){
		if(arr[i]!=0){
			prod*=arr[i];
		}else{
			nozero++;
		}
		if(nozero>1){
			break;
		}
	}
	if(nozero>1){
		for(int i=0;i<arr.length;i++){
			System.out.print("0");
		}
	}else{
		for(int i=0;i<arr.length;i++){
			if(nozero>0&&arr[i]!=0){
				System.out.print("0");
			}else{
				if(arr[i]==0){
					System.out.print(prod);
				}else{
					System.out.print(prod/arr[i]);
				}
			}
		}
	}
}

- Ravi Kumar September 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] multiplyData(int[] data) {
		int[] newArray = new int[data.length];

		int zerothIndex = -1;
		int zero = 0;
		int pdt = 1;
		for (int i = 0; i < newArray.length; i++) {
			if (data[i] == 0) {
				zero++;
				zerothIndex = i;
			} else {
				pdt = pdt * data[i];
			}
		}
		if (zero >= 2) {
			return newArray; // everything will be 0
		}
		if (zero == 1) {
			newArray[zerothIndex] = pdt;
			return newArray;
		}
		for (int i = 0; i < newArray.length; i++) {
			newArray[i] = pdt / data[i];
		}

		return newArray;
	}

- A B January 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] multiplyData(int[] data) {
int[] newArray = new int[data.length];

int zerothIndex = -1;
int zero = 0;
int pdt = 1;
for (int i = 0; i < newArray.length; i++) {
if (data[i] == 0) {
zero++;
zerothIndex = i;
} else {
pdt = pdt * data[i];
}
}
if (zero >= 2) {
return newArray; // everything will be 0
}
if (zero == 1) {
newArray[zerothIndex] = pdt;
return newArray;
}
for (int i = 0; i < newArray.length; i++) {
newArray[i] = pdt / data[i];
}

return newArray;
}

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

int[] multiplyData(int[] data) {
int[] newArray = new int[data.length];

int zerothIndex = -1;
int zero = 0;
int pdt = 1;
for (int i = 0; i < newArray.length; i++) {
if (data[i] == 0) {
zero++;
zerothIndex = i;
} else {
pdt = pdt * data[i];
}
}
if (zero >= 2) {
return newArray; // everything will be 0
}
if (zero == 1) {
newArray[zerothIndex] = pdt;
return newArray;
}
for (int i = 0; i < newArray.length; i++) {
newArray[i] = pdt / data[i];
}

return newArray;
}

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

int[] multiplyData(int[] data) {
int[] newArray = new int[data.length];

int zerothIndex = -1;
int zero = 0;
int pdt = 1;
for (int i = 0; i < newArray.length; i++) {
if (data[i] == 0) {
zero++;
zerothIndex = i;
} else {
pdt = pdt * data[i];
}
}
if (zero >= 2) {
return newArray; // everything will be 0
}
if (zero == 1) {
newArray[zerothIndex] = pdt;
return newArray;
}
for (int i = 0; i < newArray.length; i++) {
newArray[i] = pdt / data[i];
}

return newArray;
}

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

int[] multiplyData(int[] data) {
int[] newArray = new int[data.length];

int zerothIndex = -1;
int zero = 0;
int pdt = 1;
for (int i = 0; i < newArray.length; i++) {
if (data[i] == 0) {
zero++;
zerothIndex = i;
} else {
pdt = pdt * data[i];
}
}
if (zero >= 2) {
return newArray; // everything will be 0
}
if (zero == 1) {
newArray[zerothIndex] = pdt;
return newArray;
}
for (int i = 0; i < newArray.length; i++) {
newArray[i] = pdt / data[i];
}

return newArray;
}

- Anonymous AB January 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_prod(a):
	n = len(a)
	zero_idx = -1
	zero_count = 0
	prod = 1
	for i in range(n):
		if a[i] is 0:
			if not zero_count:
				zero_idx = i
				zero_count += 1
			else:
				zero_count += 1
				prod = 0
		else:
			prod *= a[i]
			
	if zero_count > 1:
		return [0]*n
	elif zero_count is 1:
		return [prod if i is zero_idx else 0 for i in range(n)]
	else:
		return [prod/a[i] for i in range(n)]

- montu February 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Get the combinations of input array's indices, for example: (0, 1), (1, 2), (1, 2, 3), (0, 1, 2, 3, 4)....

2) Then multiply the elements pointed by the indices combination.

3) remove duplicates, ...

public class MultiplyAllNumbers {

	public static void main(String[] args) {

		int[] ip = { 1, 2, 3, 4 };
		Set<Integer> origins = new HashSet<Integer>();
		for(int i=0; i<ip.length; i++){
			origins.add(ip[i]);
		}
		
		Set<Integer> op = new HashSet<Integer>();

		int length = ip.length;
		
		for(int i=2; i<=length; i++){
			
			Set<Set<Integer>> set = getCombinationOfMNumbersFromN(i, length);
			Iterator<Set<Integer>> itr = set.iterator();
			while(itr.hasNext()){
				int product = 1;
				
				Set<Integer> subSet = itr.next();
				Iterator<Integer> subItr = subSet.iterator();
				while(subItr.hasNext()){
					product = product*ip[subItr.next()];
				}
				
				if(!origins.contains(product)){
					op.add(product);
				}
			}
			
		}

		System.out.println(op);
	}

	// get m different numbers from (0, 1, ..., (n-1)).
	public static Set<Set<Integer>> getCombinationOfMNumbersFromN(int m, int n) { 

		Set<Set<Integer>> resultSet = new HashSet<Set<Integer>>();
		getCombinationOfMNumbersFromN(m, n, 1, -1, resultSet, null);
		return resultSet;
	}

	/**
	 * 
	 * @param m
	 * @param n
	 * @param index
	 *            is the index of element in current set, from 1 to m.
	 * @param preNumber
	 *            is the previous number added to current set.
	 * @param resultSet
	 * @param currentSet
	 */
	private static void getCombinationOfMNumbersFromN(int m, int n, int index,
			int preNumber, Set<Set<Integer>> resultSet, Set<Integer> currentSet) {

		if (index == (m + 1)) {

			Set<Integer> set = new HashSet<Integer>(); // Java pass object by
														// reference, so need
														// create a new object
														// to store the data.
			set.addAll(currentSet);
			resultSet.add(set);

			return;
		}

		for (int i = preNumber + 1; i < (n - m + index); i++) {
			if (index == 1)
				currentSet = new HashSet<Integer>();
			currentSet.add(i);
			getCombinationOfMNumbersFromN(m, n, index + 1, i, resultSet,
					currentSet);
			currentSet.remove(i);
		}

	}

}

- yankeson2013 March 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// No of multiplication (n-1) where n is the size of matrix and time complexity is O(n) and space complexity is O(1)
        void function(int[] arr) {
                
                int multiply = 1;
                for(int index=0; index<arr.length; index++) {
                        multiply*=arr[index];
                }
                
                for(int index=0; index < arr.length; index++) {
                        System.out.print(multiply/arr[index] + " ");
                }
        }

- Kapil July 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] multiplyExceptIndex(int[] arr)
        {
            int product = 1;
            List<int> resultArray = new List<int>();
            
            foreach(int i in arr)
            {
                if(i!=0)
                {
                    product = product * i;
                }
            }

            for(int i=0;i<arr.Length;i++)
            {
                if(arr[i]!=0)
                {
                    resultArray.Add(product / arr[i]);
                }
                else
                {
                    resultArray.Add(0);
                }
            }
           return resultArray.ToArray();
        }

- gkr July 31, 2017 | 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