## 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
of 0 votes

``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
of 0 votes

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

}``````

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;
sublist.add(nums.get(selectIndex));
}

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

}

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.
-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
of 0 votes

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
}

Add a Comment
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.

Learn More

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

Learn More

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

Learn More

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

Learn More