Facebook Interview Question for Software Developers


Country: United States
Interview Type: Phone Interview




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

Use two pointers. Start one at array[1] and one at array[0]. If difference between the two is greater than 3, move the back pointer up(unless they're one away, then iterate first pointer up). If it's less than 3, move the back pointer up (unless once again they're next to each other). If they're 3 away, output that value.

- Matt October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

By the way, here is a proof that this works. It's then easy to understand how to move window bounds. (suppose elements are unique)

for(int i = 0; i < n - 1; ++i) {
    int j = bin_search(arr, i + 1, n, arr[i] + K); // find index of element in arr[i+1:n] whose differenec with current is K
 if(j!=-1) total++
}
   print total

Pseudocode above is obvious and now we think - can we do better? Yep, we observe that we don't need to do bin_search - if we increase i, then j will only increase.
The same technique helped me to understand what to do in all similar questions where we move bounds of window.

- emb October 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

var a = [1, 2, 3, 5, 6, 8, 9, 11, 12, 13];

function differByK(arr, k) {
	if(!arr || !arr.length) {
        throw 'Invalid array input';
    }
    if(k<0) {
    	throw 'Invalid k input';
    }
    
    var i = 0, j = 1, results = [];
    while(j<arr.length) {
    	var diff = arr[j] - arr[i];
        if(diff < k) {
            j++;
        } else if(diff > k) {
            i++;
        } else{
            results.push([arr[i], arr[j]]);
            j++;
        }
    }
    return results;
}

console.log(JSON.stringify(differByK(a, 3)));

- Aslan October 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@emb Can you explain more about what do you mean by that ' if we increase i, then j will only increase.'?

- Roger October 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

public static void computeDifference(int[] arr, int k){
		for(int i = 0,j = 1; j < arr.length && i < j; ){
			if((arr[j] - arr[i]) == k){
				System.out.println(arr[j]+" "+arr[i]);
				j++;
			}else if((arr[j] - arr[i]) > k){
				i++;
			}else if((arr[j] - arr[i]) < k){
				j++;
				
			}
		}
	}

The above code produces the result in O(n)

- Kathirvelu October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

You can add all the values into a hashset.
Then iterate through the array and look for (CurrentValue + K) in the set.

- Anonymous October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Space is O(n). See below for same runtime but O(1) space.

- mdallman October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

var A = [1, 2, 3, 5, 6, 8, 9, 11, 12, 13];
var K = 3;

function getPairs(A, K) {
    var pairDictionary = {};
    var length = A.length;
    var key;
    var retArray = [];
    for (var i = 0; i < length; i++) {
        key = A[i] + K;
        pairDictionary[key] = A[i];
    }
    var pair;
    for (var x = length - 1; x >= 0; x--) {
        pair = pairDictionary[A[x]];
        if (pair) {
            retArray.unshift([pair, A[x]]);
        }
    }
    return retArray;
}
console.log(JSON.stringify(getPairs(A, K)));

- joebm08 December 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use two variables. Start one equal to array[1] and the other at array[0]. If the difference between the two values is greater than K, increment the back pointer to the next array value. If the difference is less than K, increment the front pointer. If the two are right next to each other, always increment the front pointer. If the values are exactly K apart, output value, and increment back pointer. Runtime is O(n).

- mdallman October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* runtime = 2N
*/
public void findPairs(int[] a, int k){

    if(a.length < 2 ){
     return; //No result
    }
    int previous= 1;
    
    for(int i = 0; i < a.length; i++){
        for(int j = previous; j < a.length; j++){
            previous = j;
            if(a[j] - a[i] > k ){
                break;
            }else if(a[j] - a[i] == k){
                System.out.println(a[i] +", "+a[j]);
                break;
            }
        }
    }

}

- simplysou October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def diffByK(array, K):
	dict = {}
	output = []

	for i in array:
		dict[i] = 1

		if dict[i - K] in dict:
			tmp = [dict[i - K] , i]
			output.append(tmp]

	return output

- hiuhchan October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

runtime = n where n is the array size

- hiuhchan October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void find_pair(int *array, int len, int diff)
{
int i = 0, j = 0, k, l;

while (i < len)
{
k = i + 1;
if (k < len && array[i] == array[k])
{
i++;
continue;
}

for (j = i + 1; j < len; j++)
{
l = j + 1;
if (l < len && array[j] == array[l])
continue;


if ( array[j] == array[i] + diff)
{
printf("Pair (%d, %d)\n", array[i], array[j]);
}
}
i++;
}
}

// Another approach
void find_pair2(int *array, int len, int diff)
{
int count = 0;
int l = 0;
int r = 0;
while (r < len)
{
if (array[r] - array[l] == diff)
{
printf("pair (%d, %d)\n", array[l], array[r]);
r++;
l++;
}
else if (array[r] - array[l] > diff)
{
l++;
}
else
r++;
}
}

- rsl October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The hash map approach runs in O(n) time but O(n) space.
If space is a problem we can use binary search.

Basically for element Ai we need to look if element Ai-3 is in A[0..i-1] using binary search
The time complexity is O(nlogn)

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

// O(k*n) - recall that the list is increasing, so there are no duplicates
void OutPairs(Integer[] list, int k){
	for(int i = 0; i < list.length; i++){			//Runs max O(n)
		for(int j = i+1; j < list.length; j++){		//Runs max O(k)
			int low = list[i];
			int high = list[j];
			if(high-low==k)
				print(high,low);
			else if(high-low>k)
				j = list.length;
		}
	}
}

- dannyflax October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void computeDifference(int[] arr, int k){
		for(int i = 0,j = 1; j < arr.length && i < j; ){
			if((arr[j] - arr[i]) == k){
				System.out.println(arr[j]+" "+arr[i]);
				j++;
			}else if((arr[j] - arr[i]) > k){
				i++;
			}else if((arr[j] - arr[i]) < k){
				j++;
				
			}
		}

}

- Kathirvelu October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void computeDifference(int[] arr, int k){
		for(int i = 0,j = 1; j < arr.length && i < j; ){
			if((arr[j] - arr[i]) == k){
				System.out.println(arr[j]+" "+arr[i]);
				j++;
			}else if((arr[j] - arr[i]) > k){
				i++;
			}else if((arr[j] - arr[i]) < k){
				j++;
				
			}
		}
	}

- kathirvelu October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class findingpairs {
 public static void main(String args[]){

       //given array
	 Integer arr[]={1,2,3,5,6,8,9,11,12,13};
	 @SuppressWarnings("unchecked")
	 Set <Integer>set = new HashSet<Integer>();
	 Collections.addAll(set, arr);
	 //the diff between the pairs 
	 int element=3;
	 for(int value:arr){
		 int target=value+element;
		
		 if(set.contains(target)){
			 System.out.println("("+value+","+target+")");
		 }
		
	 }
 }

}

- surajimmanuel October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Run time  = O(N)
	public void findDiff(int[] a, int k){
		
	    if(a.length < 2 ){
		     return; //No result
		    }
		int lPtr = 0;
		int rPtr = 1;
		while(lPtr < a.length-1 && rPtr < a.length){
			if(a[rPtr] - a[lPtr] < k){
				rPtr++;
			}else if(a[rPtr] - a[lPtr] > k){
				lPtr++;
				rPtr = lPtr + 1;
			}else{
				System.out.println(a[lPtr] + ", " + a[rPtr]);
				lPtr++;
				rPtr = lPtr + 1;
			}
		}
	}

- simplysou October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Run time: O(n*k) - note Omega is the same. Not the best implementation in terms of runtime, but concise.

def find_k_diff(array, k):                                    
    return [ (i, j) for (x,i) in enumerate(array) for j in array[x:(x+k)] if (j - i)\
 == k]

- Denys.N.K October 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) using extra memory : -

import java.util.HashSet;
import java.util.Set;

public class AllPairs {

public static void main(String[] args) {
int k = 3;
int arr[] = {1,2,3,5,6,8,9,11,12,13};
findPairs(arr,k);
}


public static void findPairs(int arr[],int k){
if(!(arr.length > 0))return;
Set<Integer> set = new HashSet<Integer>();
set.add(arr[0]);

for (int i = 1; i < arr.length; i++) {
if(set.contains(arr[i]-k)){
System.out.println(arr[i]-k + " , "+arr[i]);
}
set.add(arr[i]);
}

}

}

- Infinite Possibilities October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) solution:

size_t diffpairs(set<long>& numbers, long diff)
{
	size_t count = 0;
	long tmp;
	set<long>::iterator srcIt;
	for (set<long>::const_iterator it = numbers.begin(); it != numbers.end(); it++)
	{
		tmp = diff + *it;
		srcIt = numbers.find(tmp);
		if (srcIt != numbers.end())
		{
			count++;
			cout << *it << ", " << *srcIt << endl;
		}
	}
	return count;
}

- Teh Kok How October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Because the array is unique, positive and increased sorted, therefore, given a k, for one element, we just need to check k element a head (suppose the difference between two consecutive item is minimum 1)

public static void main (String[] args) throws java.lang.Exception
	{
		int k = 3;
		int arr[] = {1,2,3,5,6,8,9,11,12,13};
		findPairs(arr,k);
	}
	
	public static void findPairs(int[] arr,int k) {
		for(int idx = 0; idx < arr.length; idx++) {
			for (int distance = 1; distance <= k && ((idx+distance) < arr.length); distance++) {
				if((arr[idx + distance] - arr[idx]) == k) {
					System.out.println(arr[idx] + ", " + arr[idx + distance]);
					break; // Skip inner loop
				}
			}
		}
	}

- Tai Le October 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could not modify :). Running time will be O(k*n)

- Tai Le October 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def k_seperate(numbers, k):
k_seperate_numbers = []
dict_numbers = {}
for num in numbers:
dict_numbers[num] = num
for num in numbers:
wanted = num + k
if wanted in dict_numbers:
k_seperate_numbers.append((num, wanted))
return k_seperate_numbers

- rizTaak October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def k_seperate(numbers, k):
    k_seperate_numbers = []
    dict_numbers = {}
    for num in numbers:
        dict_numbers[num] = num
    for num in numbers:
        wanted = num + k
        if wanted in dict_numbers:
            k_seperate_numbers.append((num, wanted))
    return k_seperate_numbers

- rizTaak October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

void PrintPair(int num[], int n, int k)
{
int i = 0, j = 1;
while(j<n)
{
if(num[j] - num[i] < k)
{
j++;
}
if(num[j] - num[i] > k)
{
i++;
}
if(num[j] - num[i] == k)
{
cout << "\nPair:" << num[i] << "," << num[j];
j++;
}
else
{
i++;
j++;
}
}
}
int main(int argc, char** argv) {
int num[]={1,2,3,5,6,8,9,11,12,13};
int k = 3;
int size = sizeof(num)/sizeof(num[0]);
PrintPair(num, size, k);
return 0;
}

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

#include <iostream>
using namespace std;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

void PrintPair(int num[], int n, int k)
{
	int i = 0, j = 1;
	while(j<n)
	{
		if(num[j] - num[i] < k)
		{
			j++;
		}
		if(num[j] - num[i] > k)
		{
			i++;
		}
		if(num[j] - num[i] == k)
		{
			cout << "\nPair:" << num[i] << "," << num[j];
			j++;
		}
		else
		{
			i++;
			j++;
		}
	}
}
int main(int argc, char** argv) {
	int num[]={1,2,3,5,6,8,9,11,12,13};
	int k = 3;
	int size = sizeof(num)/sizeof(num[0]);
	PrintPair(num, size, k);
	return 0;
}

- Anonymous October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please run your code by remove 2 from the array.
3 and 6 pair will be missed due to small bug in your code.
I am pasting my code at the end , you can see it just in case if you cannot make it.
But I am sure you can fix it.

- venkatesh.duggirala December 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following is a spin-off of the Kadane algorithm. It runs in O(n) time, and uses O(1) space.

public static void findPairs(int[] arr, int k) {
		//This implementation will be similar to the Kadane algorithm
		//If there is only one element, return
		if (arr.length < 2) return;
		//Otherwise, initialize two indices to positions 0 and 1
		int lefti = 0;
		int righti = 1;
		
		//As long as we haven't reached the end yet
		while (lefti < arr.length && righti < arr.length) {
			
			//Find the difference (since it's sorted, this will
			//always be positive.
			int diff = arr[righti] - arr[lefti];
			
			//If the difference is k, this is a pair, so print it out.
			//Then increment both indices by one.
			//The reason for this is because if you only incremented the
			//left index, the next difference will ALWAYS be smaller
			//and if you only incremented the right index, the next
			//difference would ALWAYS be larger (because the array
			//is sorted) So we increment both.
			if (diff == k) {
				System.out.println(arr[lefti] + ", " + arr[righti]);
				lefti++;
				righti++;
			}
			//If the difference is smaller, increment the right
			//index (because it's sorted, we know doing that will
			//increase the difference)
			else if (diff < k) righti++;
			
			//Otherwise (meaning the difference is smaller) increment
			//the left index (because it's sorted, we know doing that
			//will decrease the difference)
			else {
				lefti++;
				//The next line is because we never want the two indices
				//pointing to the same spot
				if (lefti == righti) righti++;
			}
		}
	}

- effy October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution with running time of O(N)

#include <list>
#include <iostream>

using namespace std;

void find_pairs(int * input, int len, int k)
{
	int s = 0;
	int e = 0;

	while(e < len)
	{
		int diff = input[e] - input[s];
		if (diff < k)
		{
			e++;
		} else if (diff > k)
		{
			s++;
			if (s == e) e++;
		}else 
		{
			cout <<"( "<<input[s]<<", "<<input[e]<<")"<<endl;
			s++;
			e++;
		}	
	}
}


int main()
{
	int input[10] = {1,2,3,5,6,8,9,11,12,13};		

	find_pairs(input, 10, 3);
	return 1;
}

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

Here is C++ version of solution with running time of O (N)

#include <list>
#include <iostream>

using namespace std;

void find_pairs(int * input, int len, int k)
{
	int s = 0;
	int e = 0;

	while(e < len)
	{
		int diff = input[e] - input[s];
		if (diff < k)
		{
			e++;
		} else if (diff > k)
		{
			s++;
			if (s == e) e++;
		}else 
		{
			cout <<"( "<<input[s]<<", "<<input[e]<<")"<<endl;
			s++;
			e++;
		}	
	}
}


int main()
{
	int input[10] = {1,2,3,5,6,8,9,11,12,13};		

	find_pairs(input, 10, 3);
	return 1;
}

- hankm2004 October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The list is already sorted so we just need two pointers, initially they both start from the first element in the array. If at any point of time we meet the criteria where abs(arr[r] - arr[l]) == K, then we add that pair of numbers (arr[l], arr[r]) to the list of results. If the absolute difference is less than K then we update the r pointer, otherwise the l pointer. We use the builtin set DS to store unique pairs

def findAllPairs(arr, K):
    if arr == None or len(arr) <= 1:
        return 0
    
    l = r = 0
    pairs = set()
    
    while r < len(arr):
        if abs(arr[r] - arr[l]) == K:
            l = l + 1
            r = r + 1
            pairs.add((arr[l], arr[r]))
        elif abs(arr[r] - arr[l] < K):
            r = r  + 1
        else:
            l = l + 1
    
    
    return list(pairs)

- sauravmaximus October 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void find_subarray2(int a[], int& s, int& e, int target, int size) {
    s = e = 0;
    int dif;
    while ((s<size)&&(e<size)) {
        dif = a[e] - a[s];
        if (dif == target) {
            cout << s << " " << e << endl;
            s++;
            e++;
        }
        else if (dif > target) {
            s++;
        }
        else {
            e++;
        }
    }
}

- jk October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void find_pair(int a[], int& s, int& e, int target, int size) {
    s = e = 0;
    int dif;
    while ((s<size)&&(e<size)) {
        dif = a[e] - a[s];
        if (dif == target) {
            cout << s << " " << e << endl;
            s++;
            e++;
        }
        else if (dif > target) {
            s++;
        }
        else {
            e++;
        }
    }
}

- jk October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] numbers = new int[]{ 1, 2, 3, 5, 6, 8, 9, 11, 12, 13 };
    int K = 3;
    int startIndex = 0;
    for(int i = 0; i < numbers.length; i++){
      int diff = numbers[i] - numbers[startIndex];
      while(diff > K){
        startIndex++;
        diff = numbers[i] - numbers[startIndex];
      }
      if(diff == K) System.out.println(numbers[startIndex] + " " + numbers[i]);
    }

- Meow October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def differs(A, k):
    l = []
    d = {}
    for i in range(len(A)):
        d[A[i]] = i
    for j in range(len(A)):
        temp = k + A[j]
        if temp in d:
            l.append((A[j], temp))
            del d[A[j]]
    return l

z = differs([1, 2, 3, 5, 6, 8, 9, 11, 12, 13], 3)
print(z)

- anish531213 November 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printPairs(int a[], int len, int givenDiff)
{
    int i=0, j=1;
    while (j <len)
    {
      if (a[j] - a[i] == givenDiff)
        printf("Pairs : [ %d %d ]\n", a[i++], a[j++]);
      else if (a[j] - a[i] < givenDiff)
        j++;
      else
        i++;
    }
}

- venkatesh.duggirala December 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package dir;

import java.util.Vector;

public class main {

int lastElement, currentElement, diff, lastIndex = 0;
Vector<String> pairs = new Vector<>();

public main(int[] arr, int k) {
for (int i = 1; i < arr.length; i++) {
currentElement = arr[i];
for (int j = i - 1; j >= lastIndex; j--) {
lastElement = arr[j];
if (currentElement - lastElement == k) {
pairs.add(lastElement + "," + currentElement);
lastIndex=j+1;
}
}
}
for (String pair : pairs) {
System.out.print(pair+" ");
}
System.out.println("");
}

public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3, 5, 6, 8, 9, 11, 12, 13};
for (int i = 0; i < arr[arr.length-1]; i++) {
new main(arr, i);
}
}
}

- sach March 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package dir;

import java.util.Vector;

public class main {

int lastElement, currentElement, diff, lastIndex = 0;
Vector<String> pairs = new Vector<>();

public main(int[] arr, int k) {
for (int i = 1; i < arr.length; i++) {
currentElement = arr[i];
for (int j = i - 1; j >= lastIndex; j--) {
lastElement = arr[j];
if (currentElement - lastElement == k) {
pairs.add(lastElement + "," + currentElement);
lastIndex=j+1;
}
}
}
for (String pair : pairs) {
System.out.print(pair+" ");
}
System.out.println("");
}

public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3, 5, 6, 8, 9, 11, 12, 13};
for (int i = 0; i < arr[arr.length-1]; i++) {
new main(arr, i);
}
}
}

- sachin March 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my Java approach with 2 pointers

class Solution {
  static int[] valuesA = new int[]{1,2,3,5,6,8,9,11,12,13};
  static int valueK = 5;
  public static void main(String[] args) {
    retrievePairs(valuesA, valueK);
  }
  
  static void retrievePairs(int[] valuesA, int valueK){
    for (int i=0; i < valuesA.length; i++){
      for (int j = 0; j < valuesA.length; j++){
        if (((valuesA[i] - valuesA[j]) == valueK) && (valuesA[i] != valuesA[j])){
          System.out.println("["+valuesA[i]+"-"+valuesA[j]+"] = "+ valueK);
        }
      }
    }
  }
  
  
}

- eliel.development March 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In C#

static void Main(string[] args)
        {
            int[] A = { 1, 2, 3, 5, 6, 8, 9, 11, 12, 13 };
            int K = 3;

            getDiffered (A, K);
            Console.ReadKey(); // Optional
        }

        public static void getDiffered(int[] A, int K)
        {
            for (int x = 0; x < A.Length; x++)
            {
                for (int y = 0; y < A.Length; y++)
                {
                    if (A[x] + K == A[y])
                    {
                        Console.WriteLine(A[x] + ", " + A[y]);
                    }
                }
            }
        }

- borisous April 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
           int k = 3;
           List<int> lista = new List<int>(){1,2,3,5,6,8,9,11,12,13};
           DifbyK(lista,k);
           Console.ReadLine();
        }

   static void DifbyK(List<int> lista, int k)
        {
            for (int i =0; i<= lista.Count - k; i++)
            {
                int index=lista.IndexOf(lista[i]+k);
                if ( index>= 0)
                {
                    Console.WriteLine(lista[i] + " & " + lista[index]);
                }
            }
        }

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

static void DifbyK(List<int> lista, int k)
        {
            for (int i =0; i<= lista.Count - k; i++)
            {
                int index=lista.IndexOf(lista[i]+k);
                if ( index>= 0)
                {
                    Console.WriteLine(lista[i] + " y " + lista[index]);
                }
            }
        }

- Aldo Macias April 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In C#

Runtime N-K = O(N)

static void Main(string[] args)
        {
           int k = 3;
           List<int> lista = new List<int>(){1,2,3,5,6,8,9,11,12,13};
           DifbyK(lista,k);
           Console.ReadLine();
        }
   
static void DifbyK(List<int> lista, int k)
        {
            for (int i =0; i<= lista.Count - k; i++)
            {
                int index=lista.IndexOf(lista[i]+k);
                if ( index>= 0)
                {
                    Console.WriteLine(lista[i] + " & " + lista[index]);
                }
            }
        }

- aldojm April 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;

public class NumDiff {
    public static void main(String[] args) {
        Integer arr[]={1,2,3,5,6,8,9,11,12,13, 4};
        int k = 3;
        HashSet<Integer> set = new HashSet<Integer>();
        for (Integer i : arr) {
            set.add(i);
        }
        for (int i = 0; i < arr.length; i++) {
            int diff = arr[i] - k;
            if (set.contains(diff)) {
                System.out.println("{" + arr[i] + "," + diff + "}");
            }
        }
    }
}

OUTPUT:
{5,2}
{6,3}
{8,5}
{9,6}
{11,8}
{12,9}
{4,1}

- anand June 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Most of the solutions had a bug. In the case that two consecutive numbers with diff larger than k.
for example: 1 6 7 10 k: 3
i = 0, j = 1: a[j] - a[i] = 5 > 3 so i++.
now i == j and the loop stops.
This is my solution that handle that case:

function findDiff(arr, k) {
    if (arr.length === 0) {
        return [];
    }
    let res   = [];
    let start = 0, end = 1;
    while (start < end) {
        let first = arr[start], second = arr[end], sum = second - first;
        if (sum === k) {
            res.push([first, second]);
            start++;
            second++;
        } else if (sum < k) {
            end++;

        }else{
            start++;
            if(start === end){
                end++;
            }
        }

        if (end === arr.length) {
            break;
        }

    }
    return res;
}

console.log(findDiff([1,2,3,5,6,8,9,11,12,13],3));

- benmeiri84 January 04, 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