## Expedia Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

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

Python Solution :

``````k = 3
a = [1,2,3,4,1]
bucket = []
for i in xrange(k):
bucket.append([])
currSum  = 0
for i,num in enumerate(a):
currSum += num
bucket[currSum%k].append(i)
total = 0
for i  in xrange(len(bucket)):
if i == 0:
total+= (len(bucket[0]) * (len(bucket[i]) +1))/2
else:
total += (len(bucket[i]) * (len(bucket[i]) -1) )/ 2
print total``````

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

what is the logic behind (len(bucket[0]) * (len(bucket[i]) +1))/2 and (len(bucket[i]) * (len(bucket[i]) -1) )/ 2

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

Implementation in Java.

``````void function(int[] arr, int k) {

int size = arr.length;
// list is used to print the pairs
Map<Integer, List<Integer>> hashMap = new HashMap<Integer, List<Integer>>();

int currentSum = 0;
for (int index = 0; index < size; index++) {
currentSum += arr[index];
List<Integer> list = hashMap.get(currentSum % k);
if (null != list) {

} else {
list = new ArrayList<Integer>();
}
hashMap.put(currentSum % k, list);
}

int noOfSubArray = 0;
for(Map.Entry<Integer, List<Integer>> entry : hashMap.entrySet()) {
Integer key = entry.getKey();
Integer listSize = entry.getValue().size();
if(key == 0) {
noOfSubArray += (listSize*(listSize+1))/2;
} else {
noOfSubArray += (listSize*(listSize-1))/2;
}
}

System.out.println("No of subArray in O(k+n) time complexity "+noOfSubArray);

}``````

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

``````function subkseq(arr, k){
var i = 0;
var j = 0;
var retArr = [];
do {
if(arr[j]%k === 0){
retArr.push(arr[j]);
}

if(Math.abs(arr[j-1]- arr[j]) === 1){
var temp = i;
var total = arr[j];

while(temp < j){
total += arr[temp];
temp++
}
if(total%k == 0){
retArr.push(arr.slice(i, j+1))
}
}
else {
while(i < j){
var temp2 = i;
var total2 = 0;
while(temp2 < j){
total2 += arr[temp2];
temp2++;
}
if(total2%k === 0){
retArr.push(arr.slice(i,j));
}
i++;
}
}
j++
}while(j < arr.length)

console.log(retArr);
return retArr

}``````

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

``````function subkseq(arr, k){
var i = 0;
var j = 0;
var retArr = [];
do {
if(arr[j]%k === 0){
retArr.push(arr[j]);
}

if(Math.abs(arr[j-1]- arr[j]) === 1){
var temp = i;
var total = arr[j];

while(temp < j){
total += arr[temp];
temp++
}
if(total%k == 0){
retArr.push(arr.slice(i, j+1))
}
}
else {
while(i < j){
var temp2 = i;
var total2 = 0;
while(temp2 < j){
total2 += arr[temp2];
temp2++;
}
if(total2%k === 0){
retArr.push(arr.slice(i,j));
}
i++;
}
}
j++
}while(j < arr.length)

console.log(retArr);
return retArr

}``````

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

C# implementation
Works for both positive and negative values
No overflows either

``````public static List<int[]> ModuloKSubsequence(int[] array, int k)
{
if (k == 0)
throw new ArgumentException("k==0");

List<int[]> result = new List<int[]>();

if (array == null || array.Length == 0)
return result;

for(int i = 0; i < array.Length; i++)
{
long sum = 0;
for(int j = i; j < array.Length; j++)
{
sum = (sum + array[j] % k) % k;
if(sum == 0)
{
int size = j - i + 1;
int[] sequence = new int[size];
Array.Copy(array,i,sequence,0,size);
}
}
}
return result;
}``````

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

``````var kSubsequence = function(array, k){
var start = 0; end = 0;
var seq = [];
var sum = 0;
for(var i = 0; i < array.length; i ++){
start = i;
while(start < array.length){
sum += array[start];
seq.push(array[start]);
if(sum % k === 0){
\$(seq);
}
start++;
}
seq = [];
sum = 0;
}
}

kSubsequence([1,2,3,4,1], 4)``````

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

``````private static void findSequenceDivisibleBy(int[] arr, int num) {

int count = 0;
for (int i = 0; i < arr.length; i++) {
ArrayList<Integer> temp = new ArrayList<Integer>();
int sum = 0;

for (int j = 0; j < arr.length - i; j++) {
sum += arr[i + j];

if (sum % num == 0) {
count++;
System.out.println(temp);
}
}
}

System.out.println("Count " + count);
}``````

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

``````private static void findSequenceDivisibleBy(int[] arr, int num) {

int count = 0;
for (int i = 0; i < arr.length; i++) {
ArrayList<Integer> temp = new ArrayList<Integer>();
int sum = 0;

for (int j = 0; j < arr.length - i; j++) {
sum += arr[i + j];

if (sum % num == 0) {
count++;
System.out.println(temp);
}
}
}

System.out.println("Count " + count);
}``````

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

``````k = 3
a = [1,2,3,4,5,6]
l=[]
for i in range(0,len(a)):
for j in range(i+1,len(a)):
if sum(a[i:j+1])%k == 0:
l.append(a[i:j+1])
temp = list(filter(lambda x: x%k == 0 and x not in l, a))
l.append(c for c in temp)
print(l)
print(len(l))``````

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

``````k = 3
a = [1,2,3,4,5,6]
l=[]
for i in range(0,len(a)):
for j in range(i+1,len(a)):
if sum(a[i:j+1])%k == 0:
l.append(a[i:j+1])
temp = list(filter(lambda x: x%k == 0 and x not in l, a))
l.append(c for c in temp)
print(l)
print(len(l))``````

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

``````//
public static int getSubsequence(int[] nums, int k) {

if (nums.length == 0 || k == 0)
return 0;

int sumOfSub, count = 0, end = 0, begin = end;
sumOfSub = nums[end];
while (begin < nums.length) {
if (sumOfSub % k == 0) {
count++;
}
end++;

if (end == nums.length) {
begin++;
if (begin < nums.length) {
end = begin;
sumOfSub = nums[end];
}
} else {

sumOfSub += nums[end];
}
}
return count;
}``````

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

function subsequence(arr){
var k=3, subSum = 0, subList = [],
outPutArray = [], arrayList = [];

for(let i=0; i<arr.length; i++){
for(let j=i; j<i+k; j++){
if(arr[j] || arr[j]===0){
subList.push(arr[j]);
var copy = subList.slice(0);
var subSum = 0;
copy.forEach(function(element) {
subSum +=element;
});
if(subSum%k==0) outPutArray.push(copy); }
}
}
subList = [];
arrayList = [];
}
return outPutArray;
};

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

``````function subsequence(arr){
var k=3, subSum = 0, subList = [],
outPutArray = [], arrayList = [];

for(let i=0; i<arr.length; i++){
for(let j=i; j<i+k; j++){
if(arr[j] || arr[j]===0){
subList.push(arr[j]);
var copy = subList.slice(0);
var subSum = 0;
copy.forEach(function(element) {
subSum +=element;
});
if(subSum%k==0) outPutArray.push(copy); }
}
}

subList = [];
arrayList = [];
}
return outPutArray;
};``````

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

``````function kSubsequence(arr){
var k=3, subSum = 0, subList = [],
outPutArray = [], arrayList = [];

for(let i=0; i<arr.length; i++){
for(let j=i; j<i+k; j++){
if(arr[j] || arr[j]===0){
subList.push(arr[j]);
var copy = subList.slice(0);
var subSum = 0;
copy.forEach(function(element) {
subSum +=element;
});
if(subSum%k==0) outPutArray.push(copy); }
}
}

subList = [];
arrayList = [];
}
return outPutArray;
};``````

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

//Sliding window solution O(n)

``````let kSubsequence = function(arr,k){

let final = [];
let start = 0;
let begin = 0;
let sub = [];
let sum = 0;
while(start<arr.length){

sub.push(arr[start]);
sum += arr[start];
if(sum%k===0){

final.push(sub.slice());
}
start++;
if(start===arr.length){
begin++;
start = begin;
sub = [];
sum =0;
}
}
return final;
}``````

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

``````let kSubsequence = function(arr,k){

let final = [];
let start = 0;
let begin = 0;
let sub = [];
let sum = 0;
while(start<arr.length){

sub.push(arr[start]);
sum += arr[start];
if(sum%k===0){

final.push(sub.slice());
}
start++;
if(start===arr.length){
begin++;
start = begin;
sub = [];
sum =0;
}
}
return final;
}``````

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

let kSubsequence = function(arr,k){

let final = [];
let start = 0;
let begin = 0;
let sub = [];
let sum = 0;
while(start<arr.length){

sub.push(arr[start]);
sum += arr[start];
if(sum%k===0){

final.push(sub.slice());
}
start++;
if(start===arr.length){
begin++;
start = begin;
sub = [];
sum =0;
}
}
return final;
}

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

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.