Expedia Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
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) {
list.add(index);
} else {
list = new ArrayList<Integer>();
list.add(index);
}
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);
}
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
}
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
}
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);
result.Add(sequence);
}
}
}
return result;
}
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)
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];
temp.add(arr[i + j]);
if (sum % num == 0) {
count++;
System.out.println(temp);
}
}
}
System.out.println("Count " + count);
}
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];
temp.add(arr[i + j]);
if (sum % num == 0) {
count++;
System.out.println(temp);
}
}
}
System.out.println("Count " + count);
}
//
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;
}
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;
};
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;
};
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;
};
//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;
}
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;
}
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;
}
Python Solution :
- Naman Dasot April 20, 2017