Google Interview Question SDE1s
Country: United States
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;
}
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;
}
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;
}
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;
}
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;
}
#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 ;
}
#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 ;
}
#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 ;
}
#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 ;
}
#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 ;
}
#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 ;
}
#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;
}
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);
}
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);
}
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);
}
}
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);
}
}
{ public static int genRand() { int random = (int)(Math.random()*9000)+1000; if(random%2 == 0) return random; else return genRand(); }}
- Amit April 13, 2017