Expedia Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
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;
}
# 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.
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);
}
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];
}
}
///
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]);
}
}
}
\\\
//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++;
}
}
//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++;
}
}
//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++;
}
}
//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++;
}
}
//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++;
}
}
//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++;
}
}
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);
}
}
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);
}
}
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]);
}
}
}
}
}
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;
}
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;
}
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;
}
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;
}
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;
}
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)]
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);
}
}
}
// 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] + " ");
}
}
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();
}
Complexity is O(n + n) = O(n)
public static int[] solution(int[] a) {
if(a == null || a.length == 0) return a;
int[] res = new int[a.length];
int mul = a[0];
for(int i = 1; i < a.length; i++) {
if(a[i] != 0)
mul = mul * a[i];
}
for(int i = 0; i < res.length; i++) {
if(a[i] != 0)
res[i] = mul/a[i];
}
return res;
Loop through the array once to find the product of all numbers.
- sv May 23, 2015For the output, loop through the array and divide the product / index to find the corresponding value in the index.