Linkedin Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
one can solve this problem in the following way
First Problem
public static int RandomElement(int[] inputArray)
{
if(inputArray == null || inputArray.Length ==0)
{
throw new ArgumentException()
}
else
{
return inputArray[(new Random()).Next(inputArray.Length)];
}
}
This is O(1) time and O(1) space complexity method.
For the second problem, we can do following.
public static int FindRandomElement(int[] inputArray, int[] feq)
{
if(inputArray == null || feq == null || inputArray.Length == 0 || feq;Length == 0 || inputArray.Length != feq.Length)
{
throw new ArgumentException()
}
else
{
int sum = 0;
for(int i = 0 ; i < feq.Length; i++)
{
sum = sum + feq[i];
}
int rand = (new Random()).Next(sum);
for(int i = 0; i < feq.Length;i++)
{
if(rand - feq[i] <= 0)
{
return inputArray[i];
}
else
{
rand = rand - feq[i];
}
}
}
}
The time complexity of this algorithm is O(N) and space complexity is O(1). But algorithm has interger overflow problem, which we can solve by following logic
public static int FindRandomElement(int[] inputArray, int[] feq)
{
if(inputArray == null || feq == null || inputArray.Length == 0 || feq;Length == 0 || inputArray.Length != feq.Length)
{
throw new ArgumentException()
}
else
{
int randsum = 0;
int j = 0;
for(int i = 0 ; i < feq.Length; i++)
{
randsum = randsum + (new Random()).Next(feq[i]);
while(j < feq.Length)
{
if(randsum - feq[j] > 0)
{
randsum = randsum - feq[j];
j++;
}
else
{
break;
}
}
}
while(j < feq.Length)
{
if(randsum - feq[j] > 0)
{
randsum = randsum - feq[j];
j++;
}
else
{
break;
}
}
return inputArray[j];
}
}
The time complexity of this algorithm is again O(N) and space complexity is O(1), and this does not have interger overflow problem.
int GetRandom(vector<int> const &a, vector<int> const &freq)
{
int idx = -1;
if (a.size() == freq.size()) {
int sum = 0;
for (int i = 0; i < freq.size(); ++i) {
if (rand() % (sum + freq[i]) >= sum) {
idx = i;
}
sum += freq[i];
}
}
return idx == -1 ? numeric_limits<int>::min() : a[idx];
}
This is a recent LinkedIn on-site question. It's a variant of another question that many have come across before - randomly select a linked list node based on the weights.
The open and follow-up questions are super trivial. Only the extra requirement takes a little probability trick.
public Integer random(int[] array, int[] freq) {
int totalFreq = 0;
Integer selected = null;
Random rand = new Random();
for(int i = 0; i < array.length; i++) {
int r = rand.nextInt() * (totalFreq + freq[i]);
if(r >= totalFreq) {
selected = array[i];
totalFreq += freq[i];
}
}
return selected;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews.
All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.
- kryzoo.m March 22, 2017