Google Interview Question
Software EngineersCountry: United States
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;
}
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() )
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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; }
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;
}
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;
}
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;
}
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)
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;
}
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;
}
#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;
}
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;
}
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
Then its about figure out
- interviewee April 28, 2017