Google Interview Question for Software Engineers


Country: United States




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

It can boil down to getting the list of integers between 1000 and 9999 (including) that have adjacent digits as different.
To do that we can apply memoization on the following function

List(d, s) 
		Lists = []

                if d = 1
                	for i = 0 to 9 and i != s
                        	Lists.add(i)
			return Lists
		for i in 0 to 9 and i != s
                	Lists.addAll(List(d-1, i))
                for i in 0 to Lists.length
                        Lists[i] = (10 ^ d * s) + Lists[i]
                return Lists

          Call Lists(4, 1..9)

Then its about figure out

Lists[random() * (Lists.length - 1)]

- interviewee April 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

function getRN() {
  var rnumber = Math.floor(Math.random() * 9000 + 1000);
  for(let i = 1; i < rnumber.toString().length; i++) {
    if (rnumber.toString()[i] === rnumber.toString()[i-1]) {
      return getRN();
    }
  }
  return rnumber;
}

console.log(getRN());

- Vladimir April 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

edited: was a bit fast on the while condition
There are quite a few random generator questions asked by Google recently ;-)
1) I assume with a uniform distribution (every value has equal possibility to happen)
2) All adjacent digits are different, number is even and with 4-digit, is between 1013 and 9898, so roughly 4'000 values (assuming a leading 0 is not counted)

So how about this nonderteministic approach, that probably isn't totally
uniform (depends on Random.nextInt implmenetation):

public static int generate() {
        Random rnd = new Random();
        int value;
        do {
            value = 1013 + rnd.nextInt(9898 - 1013);
        } while ((value & 1) == 1 ||
                value % 10 == value % 100 / 10  ||
                value % 100 / 10 == value % 1000 / 100 ||
                value % 1000 / 100 == value % 10000 / 1000);
        return value;
    }

- Chris April 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I abhor code so.. what these guys said, they are going to get exactly that:

/* 
4 digit Even.
That gives :
A | B | C | D = [0 2 4 6 8]
Such that D  != C etc etc.
*/
__digits__ = list ( [0:10] )  
__l_digits__ = list ( [1:10] )  

def four_digit_even_unopt(){
  D = random( [0,2,4,6,8] )
  C = random( __digits__ - D )
  B = random( __digits__ - C )
  A = random( __l_digits__ - B )
  1000 * A + 100 * B + 10 * C + D 
}
println( four_digit_even_unopt() )

- NoOne April 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int random() {
int random = ((int) (Math.random() * 499)) * 2;
int thousandth = (int) ( 1+ (Math.random() * 8));
random = (thousandth * 1000) + random;
if(!checkAjancentDigits(random)) {
random = random();
}
return random;
}

public boolean checkAjancentDigits(int random) {
int middleTwo = random % 1000;
middleTwo = middleTwo / 10;
int secondTwo = random % 100; //4455 -> 55
int firstTwo = (random - secondTwo) / 100;
if(firstTwo % 11 == 0 || secondTwo % 11 == 0 || middleTwo % 11 == 0) {
System.out.println("Failed " + random);
return false;
}
return true;
}

- Hiren Parmar April 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int random() {
		int random = ((int) (Math.random() * 499)) * 2;
		int thousandth = (int) ( 1+ (Math.random() * 8));
		random = (thousandth * 1000) + random;
		if(!checkAjancentDigits(random)) {
			random = random();
		}
		return random;
	}
	
	public boolean checkAjancentDigits(int random) {
		int middleTwo = random % 1000;
		middleTwo = middleTwo / 10;
		int secondTwo = random % 100; //4455 -> 55
		int firstTwo = (random - secondTwo) / 100;
		if(firstTwo % 11 == 0 || secondTwo % 11 == 0 || middleTwo % 11 == 0) {
			System.out.println("Failed " + random);
			return false;
		}
		return true;

}

- Hiren Parmar April 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int random() {
		int random = ((int) (Math.random() * 499)) * 2;
		int thousandth = (int) ( 1+ (Math.random() * 8));
		random = (thousandth * 1000) + random;
		if(!checkAjancentDigits(random)) {
			random = random();
		}
		return random;
	}
	
	public boolean checkAjancentDigits(int random) {
		int middleTwo = random % 1000;
		middleTwo = middleTwo / 10;
		int secondTwo = random % 100; //4455 -> 55
		int firstTwo = (random - secondTwo) / 100;
		if(firstTwo % 11 == 0 || secondTwo % 11 == 0 || middleTwo % 11 == 0) {
			System.out.println("Failed " + random);
			return false;
		}
		return true;
	}

- Hiren Parmar April 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int getNumber(){

		int index1, index2 = 11, index3= 11, index4 = 11;
		int[] numbersArray = {1,2,3,4,5,6,7,8,9};
		int[] evennumberArray = {0,2,4,6,8};
		Random generator = new Random();
		index1 = generator.nextInt(9);
		index2 = getDifferentRandomNumber(index1, index2, 10, generator);
		index3 = getDifferentRandomNumber(index2,index3, 10, generator);
		if((index3%2) ==0){
			index4 = getDifferentRandomNumber((index3/2), index4, 5, generator);
		}else{
			index4 = generator.nextInt(5);
		}

		StringBuffer sBuffer = new StringBuffer();
		sBuffer.append(numbersArray[index1]);
		sBuffer.append(index2);
		sBuffer.append(index3);
		sBuffer.append(evennumberArray[index4]);
		return Integer.parseInt(sBuffer.toString());
	}
	private int getDifferentRandomNumber(int firstIndex, int secondIndex, int upperLimit, Random generator){
		secondIndex = generator.nextInt(upperLimit);
		while(firstIndex==secondIndex){
			secondIndex = generator.nextInt(upperLimit);
		}
		return secondIndex;
	}

- Rashmin Dave April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int getNumber(){

		int index1, index2 = 11, index3= 11, index4 = 11;
		int[] numbersArray = {1,2,3,4,5,6,7,8,9};
		int[] evennumberArray = {0,2,4,6,8};
		Random generator = new Random();
		index1 = generator.nextInt(9);
		index2 = getDifferentRandomNumber(index1, index2, 10, generator);
		index3 = getDifferentRandomNumber(index2,index3, 10, generator);
		if((index3%2) ==0){
			index4 = getDifferentRandomNumber((index3/2), index4, 5, generator);
		}else{
			index4 = generator.nextInt(5);
		}

		StringBuffer sBuffer = new StringBuffer();
		sBuffer.append(numbersArray[index1]);
		sBuffer.append(index2);
		sBuffer.append(index3);
		sBuffer.append(evennumberArray[index4]);
		return Integer.parseInt(sBuffer.toString());
	}
	private int getDifferentRandomNumber(int firstIndex, int secondIndex, int upperLimit, Random generator){
		secondIndex = generator.nextInt(upperLimit);
		while(firstIndex==secondIndex){
			secondIndex = generator.nextInt(upperLimit);
		}
		return secondIndex;
	}

- Rashmin Dave April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int getNumber(){

		int index1, index2 = 11, index3= 11, index4 = 11;
		int[] numbersArray = {1,2,3,4,5,6,7,8,9};
		int[] evennumberArray = {0,2,4,6,8};
		Random generator = new Random();
		index1 = generator.nextInt(9);
		index2 = getDifferentRandomNumber(index1, index2, 10, generator);
		index3 = getDifferentRandomNumber(index2,index3, 10, generator);
		if((index3%2) ==0){
			index4 = getDifferentRandomNumber((index3/2), index4, 5, generator);
		}else{
			index4 = generator.nextInt(5);
		}

		StringBuffer sBuffer = new StringBuffer();
		sBuffer.append(numbersArray[index1]);
		sBuffer.append(index2);
		sBuffer.append(index3);
		sBuffer.append(evennumberArray[index4]);
		return Integer.parseInt(sBuffer.toString());
	}
	private int getDifferentRandomNumber(int firstIndex, int secondIndex, int upperLimit, Random generator){
		secondIndex = generator.nextInt(upperLimit);
		while(firstIndex==secondIndex){
			secondIndex = generator.nextInt(upperLimit);
		}
		return secondIndex;
	}

- Rashmin Dave April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int getNumber(){

int index1, index2 = 11, index3= 11, index4 = 11;
int[] numbersArray = {1,2,3,4,5,6,7,8,9};
int[] evennumberArray = {0,2,4,6,8};
Random generator = new Random();
index1 = generator.nextInt(9);
index2 = getDifferentRandomNumber(index1, index2, 10, generator);
index3 = getDifferentRandomNumber(index2,index3, 10, generator);
if((index3%2) ==0){
index4 = getDifferentRandomNumber((index3/2), index4, 5, generator);
}else{
index4 = generator.nextInt(5);
}

StringBuffer sBuffer = new StringBuffer();
sBuffer.append(numbersArray[index1]);
sBuffer.append(index2);
sBuffer.append(index3);
sBuffer.append(evennumberArray[index4]);
return Integer.parseInt(sBuffer.toString());
}
private int getDifferentRandomNumber(int firstIndex, int secondIndex, int upperLimit, Random generator){
secondIndex = generator.nextInt(upperLimit);
while(firstIndex==secondIndex){
secondIndex = generator.nextInt(upperLimit);
}
return secondIndex;
}

- Rashmin Dave April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int getNumber(){

		int index1, index2 = 11, index3= 11, index4 = 11;
		int[] numbersArray = {1,2,3,4,5,6,7,8,9};
		int[] evennumberArray = {0,2,4,6,8};
		Random generator = new Random();
		index1 = generator.nextInt(9);
		index2 = getDifferentRandomNumber(index1, index2, 10, generator);
		index3 = getDifferentRandomNumber(index2,index3, 10, generator);
		if((index3%2) ==0){
			index4 = getDifferentRandomNumber((index3/2), index4, 5, generator);
		}else{
			index4 = generator.nextInt(5);
		}

		StringBuffer sBuffer = new StringBuffer();
		sBuffer.append(numbersArray[index1]);
		sBuffer.append(index2);
		sBuffer.append(index3);
		sBuffer.append(evennumberArray[index4]);
		return Integer.parseInt(sBuffer.toString());
	}
	private int getDifferentRandomNumber(int firstIndex, int secondIndex, int upperLimit, Random generator){
		secondIndex = generator.nextInt(upperLimit);
		while(firstIndex==secondIndex){
			secondIndex = generator.nextInt(upperLimit);
		}
		return secondIndex;

}

- Rashmin Dave April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int getNumber(){

		int index1, index2 = 11, index3= 11, index4 = 11;
		int[] numbersArray = {1,2,3,4,5,6,7,8,9};
		int[] evennumberArray = {0,2,4,6,8};
		Random generator = new Random();
		index1 = generator.nextInt(9);
		index2 = getDifferentRandomNumber(index1, index2, 10, generator);
		index3 = getDifferentRandomNumber(index2,index3, 10, generator);
		if((index3%2) ==0){
			index4 = getDifferentRandomNumber((index3/2), index4, 5, generator);
		}else{
			index4 = generator.nextInt(5);
		}

		StringBuffer sBuffer = new StringBuffer();
		sBuffer.append(numbersArray[index1]);
		sBuffer.append(index2);
		sBuffer.append(index3);
		sBuffer.append(evennumberArray[index4]);
		return Integer.parseInt(sBuffer.toString());
	}
	private int getDifferentRandomNumber(int firstIndex, int secondIndex, int upperLimit, Random generator){
		secondIndex = generator.nextInt(upperLimit);
		while(firstIndex==secondIndex){
			secondIndex = generator.nextInt(upperLimit);
		}
		return secondIndex; }

- Rashmin Dave April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int getNumber(){

int index1, index2 = 11, index3= 11, index4 = 11;

int[] numbersArray = {1,2,3,4,5,6,7,8,9};

int[] evennumberArray = {0,2,4,6,8};

Random generator = new Random();

index1 = generator.nextInt(9);

index2 = getDifferentRandomNumber(index1, index2, 10, generator);

index3 = getDifferentRandomNumber(index2,index3, 10, generator);

if((index3%2) ==0){

index4 = getDifferentRandomNumber((index3/2), index4, 5, generator);

}else{

index4 = generator.nextInt(5);

}

StringBuffer sBuffer = new StringBuffer();

sBuffer.append(numbersArray[index1]);

sBuffer.append(index2);

sBuffer.append(index3);

sBuffer.append(evennumberArray[index4]);

return Integer.parseInt(sBuffer.toString());

}

private int getDifferentRandomNumber(int firstIndex, int secondIndex, int upperLimit, Random generator){

secondIndex = generator.nextInt(upperLimit);

while(firstIndex==secondIndex){

secondIndex = generator.nextInt(upperLimit);

}

return secondIndex;

}

- Rashmin Dave April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int getNumber(){

int index1, index2 = 11, index3= 11, index4 = 11;
int[] numbersArray = {1,2,3,4,5,6,7,8,9};
int[] evennumberArray = {0,2,4,6,8};
Random generator = new Random();
index1 = generator.nextInt(9);
index2 = getDifferentRandomNumber(index1, index2, 10, generator);
index3 = getDifferentRandomNumber(index2,index3, 10, generator);
if((index3%2) ==0){
index4 = getDifferentRandomNumber((index3/2), index4, 5, generator);
}else{
index4 = generator.nextInt(5);
}

StringBuffer sBuffer = new StringBuffer();
sBuffer.append(numbersArray[index1]);
sBuffer.append(index2);
sBuffer.append(index3);
sBuffer.append(evennumberArray[index4]);
return Integer.parseInt(sBuffer.toString());
}
private int getDifferentRandomNumber(int firstIndex, int secondIndex, int upperLimit, Random generator){
secondIndex = generator.nextInt(upperLimit);
while(firstIndex==secondIndex){
secondIndex = generator.nextInt(upperLimit);
}
return secondIndex;
}

- Rashmin Dave April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int getNumber(){

		int index1, index2 = 11, index3= 11, index4 = 11;
		int[] numbersArray = {1,2,3,4,5,6,7,8,9};
		int[] evennumberArray = {0,2,4,6,8};
		Random generator = new Random();
		index1 = generator.nextInt(9);
		index2 = getDifferentRandomNumber(index1, index2, 10, generator);
		index3 = getDifferentRandomNumber(index2,index3, 10, generator);
		if((index3%2) ==0){
			index4 = getDifferentRandomNumber((index3/2), index4, 5, generator);
		}else{
			index4 = generator.nextInt(5);
		}

		StringBuffer sBuffer = new StringBuffer();
		sBuffer.append(numbersArray[index1]);
		sBuffer.append(index2);
		sBuffer.append(index3);
		sBuffer.append(evennumberArray[index4]);
		return Integer.parseInt(sBuffer.toString());
	}
	private int getDifferentRandomNumber(int firstIndex, int secondIndex, int upperLimit, Random generator){
		secondIndex = generator.nextInt(upperLimit);
		while(firstIndex==secondIndex){
			secondIndex = generator.nextInt(upperLimit);
		}
		return secondIndex;
	}

- Anonymous April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
public int getNumber(){{{ int index1, index2 = 11, index3= 11, index4 = 11; int[] numbersArray = {1,2,3,4,5,6,7,8,9}; int[] evennumberArray = {0,2,4,6,8}; Random generator = new Random(); index1 = generator.nextInt(9); index2 = getDifferentRandomNumber(index1, index2, 10, generator); index3 = getDifferentRandomNumber(index2,index3, 10, generator); if((index3%2) ==0){{{ index4 = getDifferentRandomNumber((index3/2), index4, 5, generator); }}}else{{{ index4 = generator.nextInt(5); }}} StringBuffer sBuffer = new StringBuffer(); sBuffer.append(numbersArray[index1]); sBuffer.append(index2); sBuffer.append(index3); sBuffer.append(evennumberArray[index4]); return Integer.parseInt(sBuffer.toString()); }}} private int getDifferentRandomNumber(int firstIndex, int secondIndex, int upperLimit, Random generator){{{ secondIndex = generator.nextInt(upperLimit); while(firstIndex==secondIndex){{{ secondIndex = generator.nextInt(upperLimit); }}} return secondIndex; }}} - Rashmin Dave April 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Solution:

import random

def randnum(n):
    x = random.randint(0,9)
    if x==n:
        return randnum(n)
    return x
curr = 0
num = 0
for a in xrange(0,4):
    randomNum = randnum(curr)
    curr = randomNum
    num = num*10+randomNum
print num

- Naman Dasot May 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int getNumber() {
		String s = "";
		int prev = 0;
		int n = 0;
		for(int i = 1; i<=4;i++) {
			while (prev==n) {
				 n = (int) (Math.random()*10);
			}
			prev = n;
			if(i == 4) {
				while (n%2 ==1) {
					n = (int) (Math.random()*10);
				}
			}
			s+=n;
		}
		return Integer.parseInt(s);
	}

- xyz May 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import random
def getNumber():
    mynum = ""
    while True:
        if len(mynum) == 4:
            return int(mynum)
        rnum = random.randint(0,9)
        if (len(mynum)!=0 and mynum[-1] == str(rnum)) or (len(mynum) == 0 and rnum == 0):
            #if prev digit is not equal to current digit or first digit is 0,skip
            continue
        if len(mynum) ==3 and rnum % 2 != 0 :
            #odd num out
            continue
        mynum += str(rnum)

- ankitpatel2100 May 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getNumber() {
	Random r = new Random();
	int random = 1000 + r.nextInt(4499);
	random *= 2;
	System.out.println(random);
	int prev = getNum(random, 1);
	for (int i = 2; i <= 4; i++) {
		int digit = getNum(random, i);
		if (prev == digit) {
			int pow = (int) Math.pow(10, i - 1);
			if (digit != 9) {
				random += pow;
			} else {
				random -= pow * 9;
			}
		}
		prev = digit;
	}
	if (random / 1000 == 0) {
		random += 1000;
	}
	return random;
}

public static int getNum(int num, int index) {
	int divider = (int) Math.pow(10, index - 1);
	return (num / divider) % 10;
}

- Max July 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static long generateNDigitRandomNumber(int n) {
		long result = 0;
		List<Integer> randomDigits = new ArrayList<>();
		Random r = new Random();
		int digit = 0;
		for (int i = 0; i < n; i++) {
			if (i == 0) {
				while ((digit = r.nextInt(10)) == 0)
					;
				randomDigits.add(digit);
				continue;
			}
			if (i != n - 1) {
				while ((digit = r.nextInt(10)) == randomDigits.get(i - 1))
					;
				randomDigits.add(digit);
			} else {
				while (((digit = r.nextInt(10)) % 2) == 1
						|| digit == randomDigits.get(i - 1))
					;
				randomDigits.add(digit);
			}
		}
		for (int i = 0; i < randomDigits.size(); i++) {
			result += randomDigits.get(i) * Math.pow(10, n - 1 - i);
		}
		return result;

}

- Ahmed.Ebaid August 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <vector>
#include <algorithm>

int getRundom19();  // returns random number from 1 till 9
int getRundom18();  // returns random number from 1 till 8
int getRundomEven08();  // returns rundom even number from 0 till 8

int getNumber() {
  std::vector<int> digits(10);
  std::iota(digits.begin(), digits.end(), 0);

  int dig = getRundomEven08();
  int num = dig;  // lowest even digit from 0 till 8

  for (int mul = 10; mul <= 100; mul *= 10) {
    std::swap(digits[0], digits[dig]);  // digits[0] contains adjacent digit
    int d = digits[getRundom19()];      // random digit of digits[1] till digits[9]
    num += d * mul;
    std::swap(digits[0], digits[dig]);  // digits again is {0 .. 9}
    dig = d;
  }
  std::swap(digits[9], digits[dig]); // digits[9] contains adjacent digit, digits[0] contains useless 0
  dig = digits[getRundom18()];
  num += dig * 1000;
  return num;
}

- S.M. January 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(k) time. Where k is amount of digits.

#include <vector>
#include <iostream>

using namespace std;

int GetNumber(int k)
{
    if (k <= 0)
    {
        return numeric_limits<int>::min();
    }
    int n = (rand() % 5) * 2;
    int prev = n;
    int denom = 10;
    vector<int> digits;
    for (int i = 1; i < k; ++i)
    {
        digits.clear();
        for (int i = 0; i < 10; ++i)
        {
            if (i != prev)
            {
                digits.push_back(i);
            }
        }
        int digit = digits[rand() % digits.size()];
        n += digit * denom;
        denom *= 10;
        prev = digit;
    }
    return n;
}

int main()
{
    srand(time(NULL));
    for (int i = 0; i < 10; ++i)
    {
        cout << GetNumber(4) << ", ";
    }
    cout << "\n";
    return 0;
}

- Alex November 11, 2018 | 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