Google Interview Question Software Engineer / Developers
Or even shorter:
pos1 = pos2 = dis = INT_MAX;
for(int i = 0; i < n; i++)
{
if (a[i] == num1) pos1 = i ;
if (a[i] == num2) pos2 = i ;
if (pos1 < INT_MAX && pos2 < INT_MAX)
dis = min (dis, abs(pos1-pos2) );
}
Nice.
Why is there no rating system at CareerCup ?
Up/Down voting would save a lot of time to people trying to figure
out various solutions to find out the correct one.
What if both the numbers are same, for e.g.
1, 2, 3, 4, 5, 4, 6
and user wants to find the distance between 2 4's
Above algo will return 0 when the distance is 2.
I think once we have found a number, we should only look for the other number. So, we should have a flag that would tell us which number are we looking currently and only match against that.
int distance(int Arr[], int arr_size, int num1, int num2)
{
int dis = arr_size+1;
int n1 = -1;
for(int i = 0; i<arr_size && dis > 1; i++)
{
if(Arr[i] == num1 || Arr[i] == num2)
{
if(n1>0 && Arr[n1] != Arr[i])
dis = min(dis, i-n1);
n1 = i;
}
}
return dis;
}
Order N
I dont think this is going to wok for the below example:
Arr[] = {3,2,1,4,3,5,6,7,8,4}
and the numbers are 3 and 4
the minimum distance is 1 however your algo will give 3
I think algo should be, do the scan and get all indexes for these two numbers and then find the minimum distances between indexes.
Start from the left most <a, b> or <b, a> pair, which does not contain other <a, b> or <b, a> pairs.
min_dist[0...i] = min_dist[0...i-1] if array[i]!=a && array[i]!=b
min_dist[0...i] = min(|i-index(right_most_b)|, min_dist[0..i-1]) if array[i]=a
min_dist[0...i] = min(|i-index(right_most_a)|, min_dist[0..i-1]) if array[i]=b
O(n)
<pre lang="" line="1" title="CodeMonkey7635" class="run-this">int getTwoNumberDistance(int *arr, int nLength, int num1, int num2)
{
if (NULL == arr)
return -1;
int i = 0;
int min = nLength+1;
while (i < nLength)
{
if (arr[i] == num1)
{
int begin = (i - min) < 0 ? 0 : i - min;
int end = (i + min) > nLength ? nLength : (i + min);
for (int j = begin;j < end;j++)
{
int tmp;
if (j > i)
tmp = j-i;
else
tmp = i-j;
if (num2 == arr[j] && min > tmp)
min = tmp;
}
}
i++;
}
return min;
}
</pre><pre title="CodeMonkey7635" input="yes">
</pre>
search the first occurence of any of the two numbers.call that position i num1 is found .continue search for second number and if we get the first number again update i with this position,now if second number is found store the distance in a variable.now take it as first number and continue search in same way .update minimum if distance less the previous one
We can consider the distinct array elements as nodes of graph and then compute the minimum distance from 1st to another by BFS O(V+E) ..... Will That work ??
Algorithm:take variables current=-1 & min=INT_Max
so we start from last element say its index is last which is array size -1 & check it with a & b if its equal to any of these then check current !=- && a[current]!=a[last] if its true then compare min with min & current-last & update the min e.g min=minimum(min,current-last)
set current=n; repeat until we run out of loop
#include <stdio.h>
#include <limits.h>
int min(int a,int b)
{ if( a<b)
return a;
else
return b;
}
int minDist(int a[], int n, int b, int c) {
int ret = INT_MAX, cur = -1;
while(n--) {
if(a[n] == b || a[n] == c) {
if(cur != -1 && a[cur] != a[n]) {
ret = min(ret, cur - n);
}
cur = n;
printf("n=%d , cur=%d ,ret=%d \n ",n,cur,ret);
}
}
return ret;
}
More Info. can be found here
shashank7s dot blogspot dot com/2011/03/wap-to-find-minimum-distance-between dot html
Shashank
Algorithm:take variables current=-1 & min=INT_Max
so we start from last element say its index is last which is array size -1 & check it with a & b if its equal to any of these then check current !=- && a[current]!=a[last] if its true then compare min with min & current-last & update the min e.g min=minimum(min,current-last)
set current=n; repeat until we run out of loop
#include <stdio.h>
#include <limits.h>
int min(int a,int b)
{ if( a<b)
return a;
else
return b;
}
int minDist(int a[], int n, int b, int c) {
int ret = INT_MAX, cur = -1;
while(n--) {
if(a[n] == b || a[n] == c) {
if(cur != -1 && a[cur] != a[n]) {
ret = min(ret, cur - n);
}
cur = n;
printf("n=%d , cur=%d ,ret=%d \n ",n,cur,ret);
}
}
return ret;
}
More Info. can be found here
shashank7s dot blogspot dot com/2011/03/wap-to-find-minimum-distance-between dot html
Shashank
public class MinimumDistance {
public static void main(String[] args) {
int [] numbers = {1,3,4,5,6,8,9,4,2,32,1,4,6,3,4,2,1};
int number1[] = new int[10];
int number2[] = new int[10];
int n2=0;
int n1=0;
int diff = 100;
int tempDiff = 100;
for(int i =0;i<numbers.length;i++){
if(numbers[i]==1){
number1[n1++]=i;
System.out.println("1 @ : "+i);
}else if(numbers[i]==2){
number2[n2++]=i;
System.out.println("2 @ : "+i);
}
}
for(int i=0;i<n1;i++){
for (int j=0;j<n2;j++){
tempDiff = number1[i]-number2[j];
if(tempDiff<0){
tempDiff=-(tempDiff);
}
if(diff>tempDiff){
diff=tempDiff;
}
}
}
System.out.println(diff);
}
}
import java.util.*;
public class unsingNegation {
static int flag=0;
public static void main(String args[]){
int a[]={5,6,2,1,3,6,1,5,5,2};
List<Integer> dis=new LinkedList<Integer>();
int pos1=0;
int pos2=0;
int num1=1;
int num2=2;
int min=0;
int flag1=0;
for(int i=0;i<a.length;i++){
if(a[i]==num1){
pos1=i;
//System.out.println("pos1= "+pos1);
unsingNegation.flag=1;
}
//System.out.println(unsingNegation.flag);
if(a[i]==num2&&unsingNegation.flag==1){
pos2=i;
//System.out.println("pos2= "+pos2);
dis.add(pos2-pos1);
unsingNegation.flag=0;
}
}
System.out.println(dis);
for(int i=0; i<dis.size();i++){
if(dis.get(i)<min){
min=dis.get(i);
flag1=1;
}
}
if(flag1==0){
min=dis.get(0);
}
System.out.println(min);
}
}
Check this :
int findmindistanceab(int A[], int n, int a, int b) {
int i = 0,val=0,min=9999,curr=-1,index[2];
for (i = 0; i < n; i++) {
if (A[i] == a)
val = 0;
else if (A[i] == b)
val = 1;
else
continue;
if (curr == (!val) && (i - index[curr] - 1) < min)
min = i - index[curr] - 1;
curr = val;
index[curr] = i;
}
return min;
}
int main(int argc, char** argv) {
int a[]={7,5,5,2,1,6,3,3,2,1,5,5,1,2,3,10};
int n=sizeof(a)/sizeof(int);
printf(" %d ",findmindistanceab(a,n,3,5));
return (EXIT_SUCCESS);
}
int minDiff(int arr[],int a,int b,int n)
{
int i;
int last=-1;
int last2=-1;
int diff=32767;
if(a==b)
{
for(i=0;i<=n-1;i++)
{
if(arr[i]==b)
{
if(last!=-1)
{diff=min(diff,abs(i-last));
last=i;}
else
{
last=i;
}
}
}
}
else
{
for(i=0;i<=n-1;i++)
{
if(arr[i]==a)
last=i;
if(arr[i]==b)
last1=i;
if(last!=-1 && last1!=-1)
diff=min(diff,abs(last-last1))
}
}
return diff;
}
<pre lang="" line="1" title="CodeMonkey62748" class="run-this">public class MinDistance {
public void findMinDistance(int[] array, int num1, int num2) {
if (array == null || array.length == 0) {
System.out.println("Invalid Arguments.......");
return;
}
int idx1 = -1;
int minDistance = -1;
int distCounter = 0;
boolean foundNum = false;
for(int i = 0;i < array.length;i++) {
if (!foundNum) {
if (array[i] == num1 || array[i] == num2) {
idx1 = i;
foundNum = true;
}
} else if (array[i] == num1) {
if (array[idx1] == num2) {
if (minDistance == -1 || distCounter < minDistance) {
minDistance = distCounter;
}
distCounter = 0;
idx1 = i;
} else if (array[idx1] == num1) {
idx1 = i;
distCounter = 0;
}
} else if (array[i] == num2) {
if (array[idx1] == num1) {
if (minDistance == -1 || distCounter < minDistance) {
minDistance = distCounter;
}
distCounter = 0;
idx1 = i;
} else if (array[idx1] == num2) {
idx1 = i;
distCounter = 0;
}
} else {
if (foundNum) {
distCounter++;
}
}
}
if (minDistance != -1) {
System.out.println("Min Distance between nos "+num1+" and "+num2+" is "+minDistance);
}
}
public static void main(String[] args) {
MinDistance m = new MinDistance();
m.findMinDistance(new int[] {3,2,1,4,3,5,6,7,8,4}, 3, 4);
}</pre><pre title="CodeMonkey62748" input="yes">
</pre>
int srarray(){
int a[11] = {1,4,2,7,4,7,2,8,9,3,4};
int pos1 = -1, pos2 = -1,dist, bpos1 = 0, bpos2 = 0, bdist = 100;
int i, m = 4, n=9;
for(i=0;i<11;i++){
if(m == a[i]){
pos1 = i;
if(pos2 != -1){
dist = pos2 - pos1; if (dist < 0) dist *=-1;
if (dist < bdist){
bdist = dist;
bpos1 = pos1;
bpos2 = pos2;
}
}
}
if(n == a[i]){
pos2 = i;
if(pos2 != -1){
dist = pos1 - pos2; if (dist < 0) dist *=-1;
if (dist < bdist){
bdist = dist;
bpos1 = pos1;
bpos2 = pos2;
}
}
}
}
printf("Pos1 = %d\nPos2 = %d\nDistance = %d\n",bpos1+1,bpos2+1,bdist+1);
return 0;
}
int srarray(){
int a[11] = {1,4,2,7,4,7,2,8,9,3,4};
int pos1 = -1, pos2 = -1,dist, bpos1 = 0, bpos2 = 0, bdist = 100;
int i, m = 4, n=9;
for(i=0;i<11;i++){
if(m == a[i]){
pos1 = i;
if(pos2 != -1){
dist = pos2 - pos1; if (dist < 0) dist *=-1;
if (dist < bdist){
bdist = dist;
bpos1 = pos1;
bpos2 = pos2;
}
}
}
if(n == a[i]){
pos2 = i;
if(pos2 != -1){
dist = pos1 - pos2; if (dist < 0) dist *=-1;
if (dist < bdist){
bdist = dist;
bpos1 = pos1;
bpos2 = pos2;
}
}
}
}
printf("Pos1 = %d\nPos2 = %d\nDistance = %d\n",bpos1+1,bpos2+1,bdist+1);
return 0;
}
int mindistance(int Arr[], int arr_size, int num1, int num2)
- li June 23, 2011{
int dis = arr_size+1;
int lastLocN1 = -1;
int lastLocN2 = -1;
for(int i = 0; i<arr_size; i++)
{
if(Arr[i] == num1)
{
lastLocN1 = i;
if (lastLocN2 > 0 && (lastLocN1 - lastN2) < dis)
{
dis = lastLocN1 - lastN2;
}
}
if (Arr[i] == num2)
{
lastLocN2 = i;
if (lastLocN1 > 0 && (lastLocN2 - lastLocN1) < dis)
{
dis = lastLocN2 - lastLocN1;
}
}
}
return dis;
}
O(n)