## Google Interview Question for Software Engineers

Country: United States

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

``````def 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])``````

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

``q = list(range(n))``

for any n. The above code code works well for only n=3.

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

``````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;

}``````

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

public static int[] getSubArray(int [] array, int n){
Random random = new Random();
int[] result = new int[n];
int index = 0;
for(int i = 0;i<n;i++){
index = random.nextInt((array.length-n+i-index)+1)+index;
result[i]=array[index++];
}
return result;
}

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

``````public static int[] getSubArray(int [] array, int n){
Random random = new Random();
int[] result = new int[n];
int index = 0;
for(int i = 0;i<n;i++){
index = random.nextInt((array.length-n+i-index)+1)+index;
result[i]=array[index++];
}
return result;
}``````

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

def 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])

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

``````def get_perm(nums, k):
if k == 1 :
for n in nums:
yield [n]
else:
for i,n in enumerate(nums):
for x in get_perm(nums[i+1:],k-1):
yield [n] + x

def main(nums,k):
if len(nums) < k:
return []
return list(get_perm(nums,k))

main([1,2,3,4,5], 3)``````

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

//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();
}
}

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

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 < 5; j++){
temp.push_back(v[j]);
func(temp, v, j + 1, m, ans);
temp.pop_back();
}
}

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

``````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``````

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

The numbers don't all have an equal chance of getting in the subset.

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

``````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``````

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

``````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)
}``````

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

``````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)
}``````

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

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``````

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

``````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++) {
}

//		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;

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) {
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;
}

}``````

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

``````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;
}

return sublist;
}``````

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

``````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]

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

``````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]

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

import random

def random_sublist(n,k):
sublist=[]
offset=0
var = k
while var > 0 :
ind = random.randint(1,n-var-offset+1)+offset
sublist.append(ind)
offset=ind
var=var-1
return sublist

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

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);
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();
}

}

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

``````#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));
}``````

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

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));
}``````

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

``````#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;
}``````

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

``````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)``````

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

it seems to not respect the requirements: this solution allows to have descending order

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

public void sublist(int[] L, int n) {
for (int i=0; i <5; i++){
for (int j=i+1; j < 5; j++ ){
for (int k=j+1; k < 5; k++){
if (L[i] <L[j] && L[j]<L[k]){
System.out.println(L[i] +"," + L[j] + " ," + L[k] + "");
}
}
}
}
}

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

public void sublist(int[] L, int n) {
for (int i=0; i <5; i++){
for (int j=i+1; j < 5; j++ ){
for (int k=j+1; k < 5; k++){
if (L[i] <L[j] && L[j]<L[k]){
System.out.println(L[i] +"," + L[j] + " ," + L[k] + "");
}
}
}
}
}

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

{
my name is varma
}

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.

### 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.

### 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.