## Google Interview Question for SDE1s

Country: United States

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

``````{
public static int genRand() {
int random =  (int)(Math.random()*9000)+1000;
if(random%2 == 0)
return random;
else
return genRand();
}``````

}

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

``````var num = Math.floor((500 + Math.random()*4500) * 2);

console.log(num);``````

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

A working C++11 O(1) in time and O(N) in space solution with test program. I assumed that we work with unsigned numbers, but implementing negative ones would not be a problem wither.

``````#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

class ValueGenerator{
public:
ValueGenerator() : vals_(4500), left_(4500), rd_(), rg_(rd_()) {
for(int i = 0; i < vals_.size(); ++i)
vals_[i] = 1000 + 2*i;
}

int generate() {
if(0 == left_) {
return 0;
} else {
int index = std::uniform_int_distribution<>{0, left_ - 1}(rg_);
std::swap(vals_[index], vals_[left_-1]);
--left_;
return vals_[left_];
}
}

private:
std::vector<int> vals_;
int left_;
std::random_device rd_;
std::mt19937 rg_;
};

int main() {
ValueGenerator vg1;

// generate some number to see if they are random
for(int i = 0; i < 10; ++i)
std::cout << vg1.generate() << std::endl;

// check if no number was repeated
ValueGenerator vg2;
std::vector<bool> check(10000, false);
for(int i = 0; i < 1000; ++i) check[i] = true;
for(int i = 1001; i < 10000; i += 2) check[i] = true;

for(int i = 0; i < 4500; ++i) {
int val = vg2.generate();
if(check[val]) {
std::cout << "Problem with: " << val << std::endl;
i = 4500;
}
check[val] = true;
}

//check if all values are now set to true
for(int i = 0; i < 10000; ++i)
if(!check[i]) std::cout << "Number " << i << "was not set" << std::endl;

return 0;
}``````

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

A working C++11 O(1) in time and O(N) in space solution with test program. I assumed that we work with unsigned numbers, but implementing negative ones would not be a problem wither.

``````#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

class ValueGenerator{
public:
ValueGenerator() : vals_(4500), left_(4500), rd_(), rg_(rd_()) {
for(int i = 0; i < vals_.size(); ++i)
vals_[i] = 1000 + 2*i;
}

int generate() {
if(0 == left_) {
return 0;
} else {
int index = std::uniform_int_distribution<>{0, left_ - 1}(rg_);
std::swap(vals_[index], vals_[left_-1]);
--left_;
return vals_[left_];
}
}

private:
std::vector<int> vals_;
int left_;
std::random_device rd_;
std::mt19937 rg_;
};

int main() {
ValueGenerator vg1;

// generate some number to see if they are random
for(int i = 0; i < 10; ++i)
std::cout << vg1.generate() << std::endl;

// check if no number was repeated
ValueGenerator vg2;
std::vector<bool> check(10000, false);
for(int i = 0; i < 1000; ++i) check[i] = true;
for(int i = 1001; i < 10000; i += 2) check[i] = true;

for(int i = 0; i < 4500; ++i) {
int val = vg2.generate();
if(check[val]) {
std::cout << "Problem with: " << val << std::endl;
i = 4500;
}
check[val] = true;
}

//check if all values are now set to true
for(int i = 0; i < 10000; ++i)
if(!check[i]) std::cout << "Number " << i << "was not set" << std::endl;

return 0;
}``````

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

I will try a didactic approach using JavaScript.
The main idea is that will generate an array with the digits from 0 to 9... then we'll shuffle the array by swapping elements on random positions.
With this array, we will then go ahead and collect the first elements that meet the criteria. See code for more details:

``````console.log( getRandomDigits() );

// Generate a random 4 digit unique number...
function getRandomDigits() {
var ar = new Array(10)

// generates an array with all the digits 0 ... 9
for(var i = 0; i <= 9; i++) {
ar[i] = i;
}

// ... then shuffle the array
shuffleArray(ar);

// If 0 is on the first position of the array... then start at the next position
var i = ar[0] == 0 ? 1 : 0;

return ar[i] * 1000 + ar[i+1] * 100 + ar[i+2] * 10 + getNextEven(ar, i+3);
}

// Returns the next even number in the array on or after position i
function getNextEven(ar, i)
{
while(ar[i] % 2 != 0) {
i++;

if (i >= ar.length)
i = 0;
}

return ar[i];
}

// Shuffle entire array
function shuffleArray(ar) {
var n = ar.length;
for(var i = 0; i < n; i++) {
var i2 = getRandomIntInclusive(0, n - 1);
var t = ar[i];
ar[i] = ar[i2];
ar[i2] = t;
}
}

// Getting a random integer between two values, inclusive
function getRandomIntInclusive(min, max) {
min = Math.ceil(min);
max = Math.floor(max);

return Math.floor(Math.random() * (max - min + 1)) + min;
}``````

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

``````console.log( getRandomDigits() );

// Generate a random 4 digit unique number...
function getRandomDigits() {
var ar = new Array(10)

// generates an array with all the digits 0 ... 9
for(var i = 0; i <= 9; i++) {
ar[i] = i;
}

// ... then shuffle the array
shuffleArray(ar);

// If 0 is on the first position of the array... then start at the next position
var i = ar[0] == 0 ? 1 : 0;

return ar[i] * 1000 + ar[i+1] * 100 + ar[i+2] * 10 + getNextEven(ar, i+3);
}

// Returns the next even number in the array on or after position i
function getNextEven(ar, i)
{
while(ar[i] % 2 != 0) {
i++;

if (i >= ar.length)
i = 0;
}

return ar[i];
}

// Shuffle entire array
function shuffleArray(ar) {
var n = ar.length;
for(var i = 0; i < n; i++) {
var i2 = getRandomIntInclusive(0, n - 1);
var t = ar[i];
ar[i] = ar[i2];
ar[i2] = t;
}
}

// Getting a random integer between two values, inclusive
function getRandomIntInclusive(min, max) {
min = Math.ceil(min);
max = Math.floor(max);

return Math.floor(Math.random() * (max - min + 1)) + min;
}``````

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

A much better approach is to use a sieve. Have all the available digits in an array and as you pick them, we'll remove them from the original array:

``````console.log( getRandomDigits() );

function getRandomDigits() {
var ar = new Array(10);

// generates an array with all the digits 0 ... 9
// then implement a sieve with these numbers
for(var i = 0; i <= 9; i++) {
ar[i] = i;
}

// pick first digit... avoiding 0 as first digit
var i = getRandomIntInclusive(1, ar.length - 1);
var n1 = ar[i];
ar.splice(i, 1);    // remove the number from the sieve
// to avoid being picked up later

// pick second digit...
i = getRandomIntInclusive(0, ar.length - 1);
var n2 = ar[i];
ar.splice(i, 1);

// pick third digit...
i = getRandomIntInclusive(0, ar.length - 1);
var n3 = ar[i];
ar.splice(i, 1);

// eliminate odd numbers from array
// to ensure picking an even number as last digit
eliminateOdd(ar);

i = getRandomIntInclusive(0, ar.length - 1);
var n4 = ar[i];

return n1 * 1000 + n2 * 100 + n3 * 10 + n4;
}

// eliminate odd numbers from array
function eliminateOdd(ar)
{
for(var i = ar.length - 1; i >= 0; i--) {
if(ar[i] % 2 != 0) {
ar.splice(i, 1);
}
}
}

// Getting a random integer between two values, inclusive
function getRandomIntInclusive(min, max) {
min = Math.ceil(min);
max = Math.floor(max);

return Math.floor(Math.random() * (max - min + 1)) + min;
}``````

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

``````#include <iostream>
#include <vector>
#include <cstdlib>
#include <chrono>
using namespace std ;
int main()
{

srand(time(0)) ;

vector<bool> v(10) ;

int x = 0 ;

while (x < 1000) {
int y = rand() % 10 ;
if (v[y] == false) {
if (x < 100) x = 10*x + y ;
else if (y % 2 == 0) x = 10*x + y ;
v[y] = true ;
}
}

cout << x ;

}``````

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

``````#include <iostream>
#include <vector>
#include <cstdlib>
#include <chrono>
using namespace std ;
int main()
{

srand(time(0)) ;

vector<bool> v(10) ;

int x = 0 ;

while (x < 1000) {
int y = rand() % 10 ;
if (v[y] == false) {
if (x < 100) x = 10*x + y ;
else if (y % 2 == 0) x = 10*x + y ;
v[y] = true ;
}
}

cout << x ;

}``````

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

``````#include <iostream>
#include <vector>
#include <cstdlib>
#include <chrono>
using namespace std ;
int main()
{

srand(time(0)) ;

vector<bool> v(10) ;

int x = 0 ;

while (x < 1000) {
int y = rand() % 10 ;
if (v[y] == false) {
if (x < 100) x = 10*x + y ;
else if (y % 2 == 0) x = 10*x + y ;
v[y] = true ;
}
}

cout << x ;

}``````

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

``````#include <iostream>
#include <vector>
#include <cstdlib>
#include <chrono>
using namespace std ;
int main()
{

srand(time(0)) ;

vector<bool> v(10) ;

int x = 0 ;

while (x < 1000) {
int y = rand() % 10 ;
if (v[y] == false) {
if (x < 100) x = 10*x + y ;
else if (y % 2 == 0) x = 10*x + y ;
v[y] = true ;
}
}

cout << x ;``````

}

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

#include <iostream>
#include <vector>
#include <cstdlib>
#include <chrono>
using namespace std ;
int main()
{

srand(time(0)) ;

vector<bool> v(10) ;

int x = 0 ;

while (x < 1000) {
int y = rand() % 10 ;
if (v[y] == false) {
if (x < 100) x = 10*x + y ;
else if (y % 2 == 0) x = 10*x + y ;
v[y] = true ;
}
}

cout << x ;

}

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

``````#include <iostream>
#include <vector>
#include <cstdlib>
#include <chrono>
using namespace std ;
int main()
{

srand(time(0)) ;

vector<bool> v(10) ;

int x = 0 ;

while (x < 1000) {
int y = rand() % 10 ;
if (v[y] == false) {
if (x < 100) x = 10*x + y ;
else if (y % 2 == 0) x = 10*x + y ;
v[y] = true ;
}
}

cout << x ;

}``````

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

int rand4DigitNumber() {
boolean[] used = new boolean[10];

Random rand = new Random();
int res = 0;

for (int i = 0; i < 4; i++) {
int val = rand.nextInt(10);
while ((i == 0 && val == 0) || used[val]) {
val = rand.nextInt(10);
}
res = res * 10 + val;
used[val] = true;
}
return res;
}

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

``````#include<iostream>
#include<vector>
#include<unordered_set>
#include<random>

using namespace std;

int range_random(int i, int j, const unordered_set<int>& excluded){
int n = j-i - (int)excluded.size();

random_device rd;
default_random_engine gen(rd());

uniform_int_distribution<> dis(0, n);

int idx = dis(gen);

for(int k = i; k<j+1; k++){
if(excluded.find(k) == excluded.end()){
idx --;
}

if(idx == -1){
return k;
}
}

throw "there is not any free value which has not excluded";
}

int main(){
unordered_set<int> excluded {};

int first_digit = range_random(1, 9, excluded);
excluded.insert(first_digit);
int second_digit = range_random(0, 9, excluded);
excluded.insert(second_digit);
int third_digit = range_random(0, 9, excluded);
excluded.insert(third_digit);

for(int i = 1; i<10 ; i+=2){
excluded.insert(i);
}

int forth_digit = range_random(0, 9, excluded);

cout << first_digit << second_digit << third_digit << forth_digit << endl;
}``````

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

Sorry can't comment. @Marcello Ghali, let say your random function returns 2146 and after adding 1000, it becomes 2246, which is wrong i guess.

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

public static void getFourDigitNumber() {

List<Integer> intList = new ArrayList<>(Arrays.asList(1 ,2 ,3, 4));
Random random = new Random();
int randomNum = 0;
int multiplyNumber = 1000;
while(!intList.isEmpty()) {
int randomIndex = random.nextInt(intList.size());
randomNum+=intList.get(randomIndex) * multiplyNumber;
multiplyNumber/=10;
intList.remove(randomIndex);
}
System.out.println(randomNum);
}

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

``````public static void getFourDigitNumber() {

List<Integer> intList = new ArrayList<>(Arrays.asList(1 ,2 ,3, 4));
Random random = new Random();
int randomNum = 0;
int multiplyNumber = 1000;
while(!intList.isEmpty()) {
int randomIndex = random.nextInt(intList.size());
randomNum+=intList.get(randomIndex) * multiplyNumber;
multiplyNumber/=10;
intList.remove(randomIndex);
}
System.out.println(randomNum);
}``````

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

``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class FourDigitNumber {

public static void main(String[] args) {

getFourDigitNumber();

}

public static void getFourDigitNumber() {

List<Integer> intList = new ArrayList<>(Arrays.asList(1 ,2 ,3, 4));
Random random = new Random();
int randomNum = 0;
int multiplyNumber = 1000;
while(!intList.isEmpty()) {
int randomIndex = random.nextInt(intList.size());
randomNum+=intList.get(randomIndex) * multiplyNumber;
multiplyNumber/=10;
intList.remove(randomIndex);
}
System.out.println(randomNum);
}

}``````

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

``````public static void getFourDigitNumber() {

List<Integer> EvenList = new ArrayList<>(Arrays.asList(2 ,4 ,6, 8));
List<Integer> intList = new ArrayList<>(Arrays.asList(1 ,2 ,3, 4 ,5, 6,7, 8 ,9));
Random random = new Random();
int randomFourDigitNum = 0;
int multiplyNumber = 1000;
int count = 0;
while(count < 3) {
int randomIndex = random.nextInt(intList.size());
randomFourDigitNum+=intList.get(randomIndex) * multiplyNumber;
EvenList.remove(new Integer(intList.get(randomIndex)));
multiplyNumber/=10;
intList.remove(randomIndex);
count++;
}
int randomIndex = random.nextInt(EvenList.size());
randomFourDigitNum+=EvenList.get(randomIndex) * multiplyNumber;
System.out.println(randomFourDigitNum);
}
}``````

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

brute force solution is randomly generate a 4 digit number until you get an even one. then maintain hashmap so that you don't return the same number again.
acecodinginterview.com

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

``````func genEvenFourDigitNumber(r *rand.Rand) int {
for true {
n := r.Intn(9000) + 1000
if n%2 == 0 {
return n
}
}

return -1
}``````

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.