Google Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
8
of 10 vote

int mindistance(int Arr[], int arr_size, int num1, int num2)
{
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)

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

Perfect

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

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) );
}``````

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

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.

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

nice

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

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.

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

here is another good solution,

puddleofriddles.blogspot.com/2012/01/given-array-with-duplicates-find.html

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

``````int distance(int Arr[], int arr_size, int num1, int num2)
{
int dis = arr_size+1;
for(int i = 0; i<arr_size; i++)
{
if(Arr[i] == num1)
{
for(int j = 0; j<arr_size; j++)
{
if(Arr[j] == num2)
{
n_dis = MOD(i, j);
dis = min(dis, n_dis);
}
}
}
}
return dis;
}``````

Order = N Square

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

``````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

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

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.

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

Thanks Mayank ! You are right. I have fixed this.

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

Can you please post the corrected version of the code?

Thanks!

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

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)

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

<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>

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

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

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

great...........

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

Bingo! Even I thought of the exact same method. Works great.

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

One optimization that can be done is to stop once we find that the distance is 1

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

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 ??

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

That would work but you will have to use BFS for every occurrence of first or second element .That will make it O(n^2).

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

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 ??

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

is there less than O(n) solution exists?
n what is in worst case?

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

There cannot be a sublinear algorithm because you need to have a look at every element to check if it's one of the given numbers. You cannot skip any number.
One optimization that can be done is to stop once we find that the distance is 1.

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

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;
}

shashank7s dot blogspot dot com/2011/03/wap-to-find-minimum-distance-between dot html

Shashank

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

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;
}

shashank7s dot blogspot dot com/2011/03/wap-to-find-minimum-distance-between dot html

Shashank

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

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);
}

}

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

``````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};
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);
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);
}
}``````

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

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);
}``````

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

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;

}

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

There is a linear solution to this problem and it can be done in O(n) time

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

<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>

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

Sorry forgot to include my name while posting the code.

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

That's ok Ram. Posting a large piece of code without any explanation is worse than posting nothing at all.

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

Ashok, somewhere above, has given an elegant solution and yet people keep posting their 'code'.

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

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;
}

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

``````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;
}``````

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.