Qualcomm Interview Question Software Engineer in Tests
Country: United States
Interview Type: In-Person
* Program to fill in values for a 10 X 10 array.
The function should fill the array with random,
non-repeated values every time the function is called
input -> 100 numbers using 2x2 matrix.
output -> 84 87 78 16 94 36 100 93 50 22 63 28 91 60 64 27 41 100 73 37
12 69 68 30 83 31 100 24 100 100 100 3 23 59 70 100 100 57 100
43 100 74 100 20 85 38 99 25 100 71 14 100 92 81 100 100 100 100
97 82 6 26 100 100 100 100 47 100 100 58 100 96 100 46 15 100 35
65 44 51 88 9 77 79 89 100 4 52 55 100 33 61 100 100 40 13 100 100 95 100
*/
#include<stdio.h>
static int size;
int rval;
int pool[100];
int generaterRandom(int s);
int main()
{
int i,j;
int arr[10][10];
for(i = 0; i < 100 ; i++)
{
pool[i] = i+1;
}
for(i = 0; i < 10 ; i++)
{
for(j = 0; j < 10 ; j++)
arr[i][j] = generaterRandom(100);
}
for(i = 0; i < 10 ; i++)
{
for(j = 0; j < 10 ; j++)
printf("%d ", arr[i][j]);
}
}
int generaterRandom(size)
{
if (size < 1)
return -1;
int idx = rand()%size;
size--;
rval = pool[idx];
pool[idx] = pool[size];
return rval;
}
int pool[100];
int main()
{
int generaterRandom(int s);
int arr[10][10];
//int n = ;
//cout<<n;
for(int i = 0; i < 100 ; i++)
{
pool[i] = i+1;
}
for(int i = 0; i < 10 ; i++)
{
for(int j = 0; j < 10 ; j++)
arr[i][j] = generaterRandom(100);
}
for(int i = 0; i < 10 ; i++)
{
for(int j = 0; j < 10 ; j++)
cout << arr[i][j]<<", ";
cout<<endl;
}
}
int generaterRandom(int s)
{
static int size = s;
if (size < 1)
return -1;
int idx = rand()%size;
size--;
int rval = pool[idx];
pool[idx] = pool[size];
return rval;
}
import java.util.*;
public class RandomMatrix
{
public static void main (String [] args)
{
Random rn = new Random();
int no = 0;
//int no = rn.nextInt(100);
//System.out.println(no);
//Scanner sc = new Scanner(System.in);
int array [] [] = new int[10][10];
int array1 [] = new int[1000];
for(int i = 0 ; i<10 ; i++)
{
for(int j = 0 ; j< 10 ; j++)
{
no = rn.nextInt(1000);
System.out.println(no);
if(array1[no] == no)
{
System.out.println("inside");
continue;
}
else
{
array[i][j] = no;
no = 0;
}
}
}
for(int i = 0 ; i<10 ; i++)
{
for(int j = 0 ; j< 10 ; j++)
{
System.out.print(array[i][j]);
System.out.print("\t");
}
System.out.print("\n");
}
}
}
This problem can be solved by standard technique of selecting a random permutation of k numbers from n given unique numbers.
Every time our required function is called do the following
1. select a random range of n numbers (unique)
2. here k=10*10
3. n >> k (preferably)
4. copy 1st k numbers to matrix (assume the matrix is an array of 100 elements now)
5. at each step generate a random number between 1 to i, where i varies from k+1 to n.
6. if generated value is between 1 to k, then replace val[k] by val[i]. Else continue
7. Convert array into matrix and display
5.
for (i = 0; i < 100; i++) {
list[i] = i;
}
for (i = 0; i < 100; i++) {
int j = i + rand() % (100 - i);
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
for (i = 0; i < 100; i++) {
a[i/10][i%10] = list[i];
}
public static void set_random_no_repeated(int[][] test,int maxValue){
- Chengyun Zuo August 16, 2012if(maxValue<test.length*test[0].length){
System.out.println("No way!");
return;
}
HashMap<Integer,Boolean> map=new HashMap<Integer,Boolean>();
for(int i=0;i!=test.length;i++){
for(int j=0;j!=test[0].length;j++){
int setValue=0;
do{
setValue=(int)(Math.random()*maxValue);
}
while(map.containsKey(setValue));
map.put(setValue, true);
test[i][j]=setValue;
}
}
}