Facebook Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
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.
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)));
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)
You can add all the values into a hashset.
Then iterate through the array and look for (CurrentValue + K) in the set.
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)));
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).
/*
* 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;
}
}
}
}
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
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++;
}
}
// 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;
}
}
}
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+")");
}
}
}
}
//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;
}
}
}
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]);
}
}
}
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;
}
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
}
}
}
}
#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;
}
#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;
}
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++;
}
}
}
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;
}
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;
}
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)
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]);
}
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);
}
}
}
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);
}
}
}
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);
}
}
}
}
}
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]);
}
}
}
}
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]);
}
}
}
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]);
}
}
}
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}
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));
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