Google Interview Question Software Engineers
Country: United States
vector<int> GetRandomSublist(vector<int> A, int n)
{
default_random_engine seed((random_device())());
if (n < 0 || n >= A.size()) return {};
for (int i = 0; i < n; i++)
{
uniform_int_distribution<int> rand_gen(i, A.size() - 1);
int num = rand_gen(seed);
swap(A[i], A[num]);
}
vector<int> ret;
for (int i = 0; i < n; i++)
ret.emplace_back(A[i]);
sort(ret.begin(), ret.end());
return ret;
}
//make the ans, temp vector in main. v is the given vector
void func(vector<int> &temp, vector<int> v, int i, int m, vector<vector<int> > &ans) {
if(temp.size() == m) {
ans.emplace_back(temp);
return;
}
for(int j = i; j < v.size(); j++) {
temp.push_back(v[j]);
func(temp, v, j + 1, m, ans);
temp.pop_back();
}
}
import random
def GetSubArray(a, n):
diff_n = len(a) - n
if diff_n < 0:
return []
if diff_n == 0:
return a
index = 0
result = []
for i in range(0, n):
index = random.randint(index, diff_n + i)
result.append(a[index])
index = index + 1
return result
let ran = (set, size) => {
// if the size is greater than the range, theres nothing to see here
if (size >= set.length) {
return -1
}
const output = new Map();
// since the input is sorted, the first number will be the smallest
const [smallest] = set
// formula for determining the start rang
const range = (set.length - size) + 1;
const start = randomHelper(smallest,range);
// this will be our first number in the result set
output.set(start, true)
while (output.size < size) {
// get the next random number in the range
let nextRan = randomHelper(start, set.length)
// if it hasn't been included, go for it
if (!output.has(nextRan)) {
output.set(nextRan, true)
}
}
// return sorted set
return [...output.keys()].sort((a,b) => a -b);
}
function randomHelper(start, end) {
return Math.round(Math.random() * (end - start) + start)
}
let ran = (set, size) => {
// if the size is greater than the range, there's nothing to see here
if (size >= set.length) {
return -1
}
const output = new Map();
// since the input is sorted, the first number will be the smallest
const [smallest] = set
// formula for determining the start rang
const range = (set.length - size) + 1;
const start = randomHelper(smallest,range);
// this will be our first number in the result set
output.set(start, true)
while (output.size < size) {
// get the next random number in the range
let nextRan = randomHelper(start, set.length)
// if it hasn't been included, go for it
if (!output.has(nextRan)) {
output.set(nextRan, true)
}
}
// return sorted set
return [...output.keys()].sort((a,b) => a -b);
}
function randomHelper(start, end) {
return Math.round(Math.random() * (end - start) + start)
}
Knuth shuffle then order by original list. O(n + len(L))
import random
from copy import copy
def random_subset(original_list, n):
L = copy(original_list)
// Differentiate items which have the same value by adding a second "count" int
for i, val in enumerate(L):
if i == 0:
L[i] = (val, 1)
else:
prev_val, prev_count = L[i-1]
L[i] = (val, prev_count + 1) if val == prev_val else (val, 1)
// Hash each value to its index, so that we maintain the order at the end
val2i = {val: i for i, val in enumerate(L)}
// Choose items randomly, and move them to the end of the list so they don't get chosen twice.
for i in range(n):
rand_i = random.randint(0, len(L)-1-i)
L[rand_i], L[len(L)-1-i] = L[len(L)-1-i], L[rand_i]
// bucket sort the randomly selected items, now at the end of our list
bucket = [False] * len(L)
for val in L[len(L)-n:]:
bucket[val2i[val]] = True
subset = []
for i, inSubset in enumerate(bucket):
if inSubset:
subset.append(original_list[i])
return subset
package T11;
import java.util.ArrayList;
import java.util.Stack;
public class T11 {
static int[] L = { 1, 2, 3, 4, 5};
static int N = 3;
static ArrayList<Integer> input = new ArrayList<>();
static ArrayList<Object[]> output = new ArrayList<>();
static Stack<Integer> process = new Stack<>();
public static void main(String[] args) {
init();
process();
// find out the result
for(Object[] temp : output) {
System.out.print("[");
for(int i = 0 ; i < temp.length; i++) {
String t = temp[i].toString();
if(i != temp.length-1)
System.out.print(Integer.valueOf(t)+", ");
else
System.out.print(Integer.valueOf(t));
}
System.out.println("]");
}
}
private static void init() {
for (int i = 0; i < L.length; i++) {
input.add(L[i]);
}
// System.out.println(input);
}
private static void process() {
for (int i = 0; i < input.size() - N + 1; i++) {
process.removeAllElements();
process.push(input.get(i));
oneScan(i, i, false);
}
}
private static void oneScan(int index, int secondIndex, boolean last) {
int getIndex = index;
int getSecondIndex = secondIndex;
if (process.size() > 1) {
process.pop();
}
if (last == true)
return;
Object[] temp = null;
for (int i = index; i < input.size(); i++) {
if (process.size() == N) {
if (process.size() < N)
continue;
temp = (Object[]) process.toArray();
if(checkDup(temp) == true) continue;
output.add(temp);
process.pop();
getSecondIndex = findIndex(process.peek());
i--;
continue;
} else {
if (input.get(i) == input.get(getSecondIndex))
continue;
if (process.peek() >= input.get(i)) {
continue;
} else {
process.push(input.get(i));
}
}
} // end of for i
if (process.size() == N) {
temp = (Object[]) process.toArray();
if(checkDup(temp) == false) {
output.add(temp);
process.pop();
getSecondIndex = findIndex(process.peek());
}
}
getIndex = getIndex + 1;
if (getIndex == input.size())
oneScan(getIndex, getSecondIndex, true);
else
oneScan(getIndex, getSecondIndex, false);
}
private static int findIndex(int value) {
int retVal = 0;
for (int i = 0; i < input.size(); i++) {
if (value == input.get(i)) {
retVal = i;
break;
}
}
return retVal;
}
private static boolean checkDup(Object[] toCompare) {
boolean retVal = false;
for(Object[] getOutput : output) {
for(int i = 0 ; i < getOutput.length; i++) {
String getEachElement = getOutput[i].toString();
if(getEachElement.equalsIgnoreCase(toCompare[i].toString())) {
retVal = true;
}else {
retVal = false;
break;
}
}
if(retVal == true) return retVal;
}
return retVal;
}
}
public static List<Integer> sublist(final List<Integer> nums, final int size){
if(size == nums.size()) return nums;
else if( size == 0) return Collections.emptyList();
else if (size == 1) return Arrays.asList(nums.get(new Random().nextInt(nums.size())));
final List<Integer> sublist = new LinkedList<>();
final Random rand = new Random();
int selectIndex = -1;
while (sublist.size() < size){
int randomDelta = 0;
final int itemsRemaining = size - sublist.size();
final int lowestPos = nums.size() - itemsRemaining;
while (randomDelta == 0 || selectIndex + randomDelta > lowestPos)
randomDelta = rand.nextInt(nums.size() - selectIndex);
selectIndex += randomDelta;
sublist.add(nums.get(selectIndex));
}
return sublist;
}
import itertools
ll=[1,2,3,4,5]
n=3
mlist=n*[ll]
combinations = list(itertools.product(*mlist))
for value in combinations:
if(len(set(value)) == len(value) and list(value) == sorted(value)):
print(value)
It also takes care of condition with one of the element being zero. try with [1,2,3,4,0]
import itertools
ll=[1,2,3,4,5]
n=3
mlist=n*[ll]
combinations = list(itertools.product(*mlist))
for value in combinations:
if(len(set(value)) == len(value) and list(value) == sorted(value)):
print(value)
Above works fine with empty array [] and also if one of the elements is zero [1,2,3,4,0]
This is my solution with recursion. It works with any arrays and any N
mport java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
fun(7,new ArrayList<Integer>(), 0,3);
}
static void fun(int size, List<Integer> result, int i, int n) {
if(result.size() >= n)
printResult(result);
else {
findValue(size, result, i, n, i+1);
}
}
static void findValue(int size, List<Integer> result, int i, int n,int j) {
if(j <= size -n +i +1) {
List<Integer> newResult = new ArrayList<Integer>(result);
newResult.add(j);
fun(size, newResult, i+1, n);
findValue(size, result, i, n,j+1);
}
}
static void printResult(List<Integer> result) {
for(Integer value: result) {
System.out.print(value+ " ");
}
System.out.println();
}
}
#include <vector>
void generate(vector<int> & arr, int k, vector<vector<int>> & result, vector<int> & current, int index = 0){
int n = arr.size();
if(current.size() == k){
result.push_back(current);
return;
}
for(int i=index; i<n; i++){
current.push_back(arr[i]);
generate(arr, k, result, current, i+1);
current.pop_back();
}
}
vector<vector<int>> getAllCombinations(vector<int> arr, int k){
vector<vector<int>> result;
vector<int> current = {};
generate(arr, k, result, current);
return result;
}
void printResult(vector<vector<int>> matrix){
int n = matrix.size();
int m = matrix[0].size();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
int main() {
vector<int> arr = {1,2,3,4,5};
printResult(getAllCombinations(arr, 4));
}
Easy backtracking based solution c++
#include <iostream>
#include <vector>
using namespace std;
void generate(vector<int> & arr, int k, vector<vector<int>> & result, vector<int> & current, int index = 0){
int n = arr.size();
if(current.size() == k){
result.push_back(current);
return;
}
for(int i=index; i<n; i++){
current.push_back(arr[i]);
generate(arr, k, result, current, i+1);
current.pop_back();
}
}
vector<vector<int>> getAllCombinations(vector<int> arr, int k){
vector<vector<int>> result;
vector<int> current = {};
generate(arr, k, result, current);
return result;
}
void printResult(vector<vector<int>> matrix){
int n = matrix.size();
int m = matrix[0].size();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
int main() {
vector<int> arr = {1,2,3,4,5};
printResult(getAllCombinations(arr, 4));
}
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
std::vector<int> getRandomSublist(const std::vector<int>& L, int N) {
std::vector<int> sublist;
int remainingElements = N;
int availableChoices = L.size();
for (size_t i = 0; i < L.size() && remainingElements > 0; ++i) {
int randChoice = rand() % availableChoices;
if (randChoice < remainingElements) {
sublist.push_back(L[i]);
--remainingElements;
}
--availableChoices;
}
return sublist;
}
int main() {
srand(time(0)); // Seed for random number generation
std::vector<int> L = {1, 2, 3, 4, 5};
int N = 3;
auto sublist = getRandomSublist(L, N);
std::cout << "Random sublist of size " << N << ": [";
for (size_t i = 0; i < sublist.size(); ++i) {
std::cout << sublist[i];
if (i < sublist.size() - 1) std::cout << ", ";
}
std::cout << "]" << std::endl;
return 0;
}
import random
def generate_n_list(lst, n):
if n > len(lst):
return []
if n == len(lst):
return lst
res = []
for i in range(len(lst) - 1,-1,-1):
j = random.randrange(0,i + 1,1)
temp = lst[j]
lst[j] = lst[i]
lst[i] = temp
res.append(temp)
if len(res) == n:
break
return sorted(res)
- Anonymous July 30, 2019def get_increasing_list(l, n): q = [0, 1, 2] print l[:n] k = len(l) visited = [] while len(q) != 0: num = q.pop() for i in range(num+1, k): q.append(i) if len(q) >= n and q[:n] not in visited: res = map(lambda x: l[x], q) print res visited.append(q[:n])