Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

here is O(N * #of primes) solution:

void num_generator() {
    int a[] = {2, 3, 7, 11};
    int as = sizeof(a) / sizeof(int);

    int *idx = new int[as];
    int *min_idx = new int[as];
    memset(idx, 0, sizeof(int)*as);
    
    int n = 100;
    int *x = new int[n];
    x[0] = 1;

    int i, j;
    for(i = 1; i < n; i++) {
        int min = x[idx[0]] * a[0], 
               nmins = 1; // # of primes giving the current minimal 
        min_idx[0] = 0;
        
        // iterate over prime factors: search for the minimal next number
        for(j = 1; j < as; j++) { 
            int xj = x[idx[j]] * a[j];
            if(xj <= min) {
                if(xj < min) {
                    min = xj;
                    nmins = 0;
                }
                // save a prime index giving the minimal next number
                min_idx[nmins++] = j;
            }
        }

        x[i] = min;
        for(j = 0; j < nmins; j++) {
            idx[min_idx[j]]++;
        }
        
        printf("x[%d] = %d\n", i, x[i]);
    }
    delete []x;
    delete []idx;
    delete []min_idx;
}

the output:

x[1] = 2
x[2] = 3
x[3] = 4
x[4] = 6
x[5] = 7
x[6] = 8
x[7] = 9
x[8] = 11
x[9] = 12
x[10] = 14
x[11] = 16
x[12] = 18
x[13] = 21
x[14] = 22
x[15] = 24
x[16] = 27
x[17] = 28
x[18] = 32
x[19] = 33
x[20] = 36
x[21] = 42
x[22] = 44
x[23] = 48
x[24] = 49
x[25] = 54
x[26] = 56
x[27] = 63
x[28] = 64
x[29] = 66
x[30] = 72
x[31] = 77
x[32] = 81
x[33] = 84
x[34] = 88
x[35] = 96
x[36] = 98
x[37] = 99
x[38] = 108
x[39] = 112
x[40] = 121
x[41] = 126
x[42] = 128
x[43] = 132
x[44] = 144
x[45] = 147
x[46] = 154
x[47] = 162
x[48] = 168
x[49] = 176
x[50] = 189
x[51] = 192
x[52] = 196
x[53] = 198
x[54] = 216
x[55] = 224
x[56] = 231
x[57] = 242
x[58] = 243
x[59] = 252
x[60] = 256
x[61] = 264
x[62] = 288
x[63] = 294
x[64] = 297
x[65] = 308
x[66] = 324
x[67] = 336
x[68] = 343
x[69] = 352
x[70] = 363
x[71] = 378
x[72] = 384
x[73] = 392
...

- pavel.em November 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

That's a correct and elegant solution with O(N*K). But that's really not so easy to understand the logic behind the scene without any explanations provided.

The logic here is that for every element in the prime set a[j] we track the element in the result array target[last_index[a[j]]] that we used to build a new element in the result array on the k-th step: target[k] = target[last_index[a[j]]] * a[j]. Therefore we imply, that on the next (k+1)-th iteration for an element a[j] of the prime set, it's enough to check only the following product: target[last_index[a[j]] + 1] * a[j], since target[last_index[a[j]]] was previously processed and target[last_index[a[j]] + 2] is evidently bigger than target[last_index[a[j]] + 1].

And a minor comment - x[0] is missing in the output.

- Alex M. November 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

yes, you are right. This solution is based on Dijkstra's algorithm from "a discipline of programming".

Here is a basic version for 2 primes to help understanding the idea:

void print23() {
	// print 2^i*3^j increasing order
	int a[100];
	a[0] = 1;

  int i2 = 0, i3 = 0;
  for(int i = 1; i < 100; i++) {
    int a2 = a[i2] * 2, a3 = a[i3] * 3;
    if(a2 < a3) {
        a[i] = a2;
        i2++;
    } else {
        a[i] = a3;
        i3++;
        if(a2 == a3)
            i2++; // inc both indices in case of a tie
    }
    printf("%d ", a[i]);
  }
}

- pavel.em November 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

How is this based on Dijkstra's algorithm? That would require a heap.

- Anonymous November 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

An easier solution would be to store the value in a Tree Map and then remove them one by one till we reach Nth number. That code is way easier. Java Code below:

* 
 * @author shivam.maharshi
 */
public class NthSmallestMulFromSet {

	// O(n*log(m)). M is size of set.
	public static int get(int[] set, int n) {
		TreeMap<Integer, Integer> map = new TreeMap<>();
		for (int a : set) {
			map.put(a, a);
		}
		int num = 0;
		while (n > 0) {
			num = map.firstKey();
			int value = map.get(num);
			map.remove(num);
			if (!map.containsKey(num + value)) {
				map.put(num + value, value);
			} else {
				map.put(num + 2 * value, value);
			}
			n--;
		}
		System.out.println(num);
		return num;
	}

	public static void main(String[] args) {
		int[] set = { 2, 3 };
		get(set, 6);
	}

}

- Shivam Maharshi January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looks like ugly numbers but not sure how would it work with primes around 10^4 and N around 10^6?

- Yola July 03, 2019 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 vote

MinHeap can be used here. Initially put all prime number into the heap, in each iteration, pop up the minimum, multiply all prime numbers in the initial array to it and add them into the queue. Need to check duplicates so the previous number is kept. Output when the nth largest number is found.

- Anonymous October 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

could you please elaborate? you have a min-heap and a queue?

- koosha.nejad November 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Implemented this solution using PriorityQueue in Java:

public int findNum(int k, int[] primes) {
	PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
	Set<Integer> checkedSet = new HashSet<Integer>();
	queue.add(1);
	int i = 0;
	int e = 1;
	while (i < k) {
		e = queue.poll();
		for (int x = 0; x < primes.length; x++) {
			int newElement = e * primes[x];
			if (!checkedSet.contains(newElement)) {
				checkedSet.add(newElement);
				queue.add(newElement);
			}
		}
		i++;
	}

	return e;
}

- Maxim December 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have one question. You said, you take out the minimum and then multiply n numbers of the array and push them into heap after checking for duplicates. That would keep on increasing the size of the heap, right ?

- Shivam Maharshi January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

var frontNumbers = new MinHeap<int>();
frontNumbers.Add(1)
for (i=0; i<n; i++)
{
   var head = frontNumbers.Pop();
   foreach (var prime in primes)
   {
      frontNumbers.Add(head*prime);
   }
}
return frontNumbers.Pop();

- ilya November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I fixed previous code, multiplication is used instead of addition.

{2, 3, 5, 7, 11, 23, 97}, 3 => 3
{2, 3, 5, 7, 11, 23, 97}, 1000000 => 37812219101007120
{99991}, 3 => 9998200081
{99991}, 1000000 => 0

c++, O(n * n * log n)

typedef unsigned long long UINT64;

const UINT64 LIMIT = 18446744073709551615UL;

UINT64 getNthNumber(vector<int>& primes, int n) {
    set<UINT64> nums;
    set<UINT64>::iterator it;
    set<UINT64>::reverse_iterator rit;
    UINT64 limit;
    unsigned int i;
    
    nums.insert(1);
    for (i = 0; i < primes.size(); i++) {
        it = nums.begin();
        limit = LIMIT / primes[i];
        while (it != nums.end()) {
            if (*it > limit) break;
            nums.insert(*it * primes[i]);
            if (nums.size() == n * 2) break;
            it++;
        }
        
        while (nums.size() > n) {
            rit = nums.rbegin();
            nums.erase(next(rit).base());
        }
    }
    
    if (nums.size() < n) return 0;
    
    return *nums.rbegin();
}

- kyduke October 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

{2, 103}, n=3 - what will you return? Should return 4.
For sure there's something about the numbers being prime that can be used

- IAR November 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

my solution below works in O(N * #of primes) time

- pavel.em November 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

import Queue
import heapq
def prime_set(prime_set, n):
  prime_set = list(prime_set)
  print prime_set
  prime_set.sort()

  queue_list = []
  ret_list = []
  for i in prime_set:
    tmp_queue = Queue.Queue()
    queue_list.append(tmp_queue)
  heap = []
  ret_list.append(1)
  for j in range(0,len(queue_list)):
    queue_list[j].put(1*prime_set[j])
    heapq.heappush(heap, (queue_list[j].get(),j))
  while len(ret_list) < n:
    v = heapq.heappop(heap)
    ret_list.append(v[0])
    for j in range(v[1], len(queue_list)):
      val = (prime_set[j]*v[0])
      queue_list[j].put(val)
    heapq.heappush(heap,(queue_list[v[1]].get(), v[1]))
  print ret_list
if __name__ == '__main__':
  primes = {2,3,5,7, 11}
  prime_set(primes, 100)

- PradeepN October 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sort isn't actually necessary, I was just testing it.

- PradeepN October 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your code needs small change - 1 cannot be obtained.

- infinity October 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity:- O(n*logk*k), where k= no. of prime nos. & n= req. nos. ??

- Anonymous November 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not sure
Just a prototype ::

{2,5} -->

Consider 2^x < 5
so x=3

So the nth number would be -- 2^((n-1)%3). 5^(n/3)

You can guess for more numbers

- raghu.aok October 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry 5< 2^x

minimum value of x

- raghu.aok October 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain the logic? Why would that be the nth number?

- IAR November 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ solution running in O(n log n)

uint64_t find_expressible(vector<int>& prime_set, int pos)
{
  set<uint64_t> result;
  list<uint64_t>queue;
  queue.push_back(1);
  while(queue.size()> 0)
  {
    uint64_t cur  = queue.front();
    queue.pop_front();

    if (cur != 1 && result.find(cur) == result.end())
    {
      result.insert(cur);
      cout<<cur<<","<<endl;
    }
    for (int i = 0; i < prime_set.size(); i++)
    {
      int next = cur*prime_set[i];
      if (result.size() < pos*2)
      {
        queue.push_back(next);
      }
      else
        break;
    }
    if (result.size() >= pos*2)
      break;
  }
  //put numbers in the heap
  MinHeap heap(result);
  uint64_t found =0;
  //remove last big numbers as many as pos
  for (int i = 0; i < pos; i++)
      found = heap.extract();;
  return found;
}

- hankm2004 November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Multiway tree with data containing the number and last multiplier , and with a condition that next multiplier <= last multiplier to avoid duplication like abc , bca ,cba to only cba

1. Start root with value = 1 , LastMultiplier =1
2. Insert all prime elements
3. Insert all prime elements in circular loop till the Value <= BigN
1
a (Insert a)
b (Insert b)
c (Insert c)
aa ba ca (Insert a)
bb cb (Insert b)
cc (Insert c)
aaa baa bba caa cba cca (Insert a)
bbb cbb ccb (Insert b)
ccc (Insert c)
...

- Ankush Bindlish November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Multiway tree with data containing Value and LastMultiplier. Proceed with node only if currentValue is less than equal to LastMultiplier.

- ankushbindlish November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sequence I observed in above problem. I think 250 is max value
1
2 3
4 6 9
8 12 18 27
16 24 36 54 81
32 48 72 108 162 243
64 96 144 216 324 486 729
128 192 288 432 648 972 1458

In above sequence I stop writing next line because it is starting with 256 greater than 250. Now we will filter data
by starting with 128
128/2=64*3=192/2=96*3=288/2=144*3=432/2=216*3=648/2=324/2=162
324*3=972/2=486/2=243
we get
128 144 162 192 216 243
which is greater than 128 less than 250
243 is nearer to it

- anudeep November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

only for prime set {2,3}
time complexity is O(n+log n)
I am trying to find solution in generic way by satisfying it for all prime sets

- anudeep November 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node
 {
        public long val;
        public long par;
        public int index;
        public Node(long val,long par,int index)
        {
            this.val=val;
            this.par=par;
            this.index=index;
        }
    }
class NodeHeap
    {
        public List<Node> h = new List<Node>();
        void swap(int i, int j)
        {
            Node n = h[i];
            h[i] = h[j];
            h[j] = n;
        }
        public void push(Node n)
        {
            h.Add(n);
            int i = h.Count - 1;
            int p;
            while (i != 0)
            {
                p = (i - 1) / 2;
                if (h[p].val > h[i].val)
                {
                    swap(i, p);
                    i = p;
                }
                else
                    break;
            }
        }
        public Node pop()
        {
            swap(0, h.Count - 1);
            Node ret = h[h.Count - 1];
            h.RemoveAt(h.Count - 1);
            int i = 0;
            while (2 * i + 1 < h.Count)
            {
                int l = 2 * i + 1;
                int r = 2 * i + 2;
                int min=l;
                if (r < h.Count && h[r].val < h[l].val)
                    min = r;
                if (h[min].val < h[i].val)
                {
                    swap(i, min);
                    i = min;
                }
                else
                    break;
            }
            return ret;
        }
    }

static long findNth(long[] f, int n)
        {
            if (n == 1)
                return 1;
            NodeHeap h = new NodeHeap();
            h.push(new Node(f[0], 1, 0));
            int c = 1;
            while (c < n)
            {
                Node node = h.pop();
                c++;
                if (c == n)
                    return node.val;
                Node child = new Node(node.val * f[node.index], node.val, node.index);
                h.push(child);
                if (node.index < f.Length - 1)
                {
                    Node sibling = new Node(node.par * f[node.index + 1], node.par, node.index + 1);
                    h.push(sibling);
                }
            }
            return -1;
        }

- Anonymous November 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Something has to do with the fact the numbers are primary...

- IAR November 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For sure the fact that these are prime numbers means something.
Maybe that it can be calculated without going over the list multiple times

- IAR November 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Input:{3,5,7,11};
Maximumvalue N;

ArrayList al;
Queue q;
q.enqueue(3);
q.enqueue(5);
q.enqueue(7);
q.enqueue(11);

al.add(3);
al.add(5);
al.add(7);
al.add(11);
int maxvalue=3;
while(!q.isempty())
{
int x=q.dequeue();
if(x>=maxvalue && x<=N)
maxvalue=x;
Iterator list= al.iterator();
while (list.hasNext()) {
y=list.next()*x;
if(!q.contains(y))
{
q.enqueue(y);
al.add(y);
}
}

al.remove(x);

}


It is similar to BFS

- Anudeep November 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def division(number,primediv):
    a=0
    nondiv=0
    s=0
    quotient=0
    b=number
    while quotient!=1:
        for i in primediv:
            a=number%i
            if number/i==1:
                nondiv=0
                s=number
                quotient=1
            if a==0:
                nondiv=0
                number=number/i
                break
            else:
                nondiv+=1
                if nondiv==len(primediv):
                    b=0
                    quotient=1
    return b          
def prime_expressible(n,primeset):
    mas=[]
    numb=1
    while len(mas)<n:
        if division(numb,primeset)!=0:
            mas.append(numb)
        numb+=1
    print(mas)
    return(mas[len(mas)-1])
print(prime_expressible(73,[2, 3, 5, 7]))

output:

[2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 50, 54, 56, 60, 63, 64, 70, 72, 75, 80, 81, 84, 90, 96, 98, 100, 105, 108, 112, 120, 125, 126, 128, 135, 140, 144, 147, 150, 160, 162, 168, 175, 180, 189, 192, 196, 200, 210, 216, 224, 225, 240, 243, 245]
245

- intainer7 November 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a solution in JavaScript. Note, I only tested it with the given test input, so it might have bugs:

// var set = [2, 3], n = 8;

// expect: results.exp = [1, 2, 3, 4, 6, 8, 9, 12]
// expect: results.non = [5, 7, 10, 11]
// expect: results.result = 12

var primeExpressibles = function (set, n) {
  if (n < 1) return {exp: [], non: [], result: null};
  if (n === 1) return {exp: [1], non: [], result: 1};
  var results = {exp: [1], non: [], result: 1};
  iteration:
  for (var i = 2; i < set[0] * n; i++) {
    var num = i, j = 0;
    while (set[j] !== undefined) {
      if (!Number.isInteger(num / set[j])) {
        j++; continue; // continue while loop
      }
      num /= set[j];
      if (num === 1) {
        results.exp.push(i);
        if (results.exp.length === n) {
          results.result = i;
          return results;
        }
        continue iteration; // break out of while loop, continue iteration
      }
    }
    results.non.push(i);
  }
  return results; // should never reach this point, in theory...
};

- Jeff November 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <algorithm>
#include <queue>
#include <limits>
#include <iostream>

using namespace std;

class Solution {
public:
struct Val{
Val(int v, int c):val(v), cnt(c){}
bool operator < (const Val& other)const{
return val*cnt > other.val*other.cnt;
}

bool operator > (const Val& other)const{
return val*cnt < other.val*other.cnt;
}

bool operator != (const Val& other)const{
return val*cnt != other.val*other.cnt;
}

int val;
int cnt;
};

int nthUglyNumber(int n) {
if(n < 6 ){
return n;
}

int maxInt = numeric_limits<int>::max();
priority_queue<Val> q;
q.push(Val(2,1));
q.push(Val(3,1));
q.push(Val(5,1));
int counter = 1;
Val result(0, 0);
Val pred = result;
while( counter < n ){
result = q.top();
q.pop();
if( result != pred){
std::cout << result.cnt*result.val << " " << std::endl;
}

pred = result;
result.cnt++;
q.push(result);
counter++;
}

return result.cnt*result.val;
}
};

int main(int argc, char** argv){
Solution sol;
sol.nthUglyNumber(150);
return 0;
}

- O(n) solution with prio q November 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <algorithm>
#include <queue>
#include <limits>
#include <iostream>

using namespace std;

class Solution {
public:
   struct Val{
     Val(int v, int c):val(v), cnt(c){}
     bool operator < (const Val& other)const{
       return val*cnt > other.val*other.cnt;
     }
     
     bool operator > (const Val& other)const{
       return val*cnt < other.val*other.cnt;
     }      
     
     bool operator != (const Val& other)const{
   return val*cnt != other.val*other.cnt;
     }
     
     int val;
     int cnt;
   };

   int nthUglyNumber(int n) {
       if(n < 6 ){
           return n;
       }

       int maxInt = numeric_limits<int>::max();
       priority_queue<Val> q;
       q.push(Val(2,1));
       q.push(Val(3,1));
       q.push(Val(5,1));
       int counter = 1;
       Val result(0, 0);
Val pred = result;
       while( counter < n ){
           result = q.top();
           q.pop();
       if( result != pred){
         std::cout << result.cnt*result.val << " " << std::endl; 
       }
       
       pred = result;
       result.cnt++;
           q.push(result);
       counter++;
       }
       
       return result.cnt*result.val;
   }
};

int main(int argc, char** argv){
 Solution sol;
 sol.nthUglyNumber(150);
 return 0;
}

Similar problem is located in leetcode.

- O(n) solution with prio q November 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <algorithm>
#include <queue>
#include <limits>
#include <iostream>

using namespace std;

class Solution {
public:
   struct Val{
     Val(int v, int c):val(v), cnt(c){}
     bool operator < (const Val& other)const{
       return val*cnt > other.val*other.cnt;
     }
     
     bool operator > (const Val& other)const{
       return val*cnt < other.val*other.cnt;
     }      
     
     bool operator != (const Val& other)const{
   return val*cnt != other.val*other.cnt;
     }
     
     int val;
     int cnt;
   };

   int nthUglyNumber(int n) {
       if(n < 6 ){
           return n;
       }

       int maxInt = numeric_limits<int>::max();
       priority_queue<Val> q;
       q.push(Val(2,1));
       q.push(Val(3,1));
       q.push(Val(5,1));
       int counter = 1;
       Val result(0, 0);
Val pred = result;
       while( counter < n ){
           result = q.top();
           q.pop();
       if( result != pred){
         std::cout << result.cnt*result.val << " " << std::endl; 
       }
       
       pred = result;
       result.cnt++;
           q.push(result);
       counter++;
       }
       
       return result.cnt*result.val;
   }
};

int main(int argc, char** argv){
 Solution sol;
 sol.nthUglyNumber(150);
 return 0;
}

- O(n) solution with prio q November 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a solution in JavaScript:

// var set = [2, 3], n = 8;

// expect: results.exp = [1, 2, 3, 4, 6, 8, 9, 12]
// expect: results.non = [5, 7, 10, 11]
// expect: results.result = 12

var primeExpressibles = function (set, n) {
  if (n < 1) return {exp: [], non: [], result: null};
  if (n === 1) return {exp: [1], non: [], result: 1};
  var results = {exp: [1], non: [], result: 1};
  iteration:
  for (var i = 2; i < set[0] * n; i++) {
    var num = i, j = 0;
    while (set[j] !== undefined) {
      if (!Number.isInteger(num / set[j])) {
        j++; continue; // continue while loop
      }
      num /= set[j];
      if (num === 1) {
        results.exp.push(i);
        if (results.exp.length === n) {
          results.result = i;
          return results;
        }
        continue iteration; // break out of while loop, continue iteration
      }
    }
    results.non.push(i);
  }
  return results; // should never reach this point, in theory...
};

- jeffwtribble November 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Whoops! Just saw that I posted this twice..

- jeffwtribble November 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

L - A set of linked lists with each prime number with one liked list
MH - A min heap to take the head values of L
Pseudo-code:
- If N is ranged in [1, m+1], return from {1, P1, ..., Pm}
- Otherwise,
- Initialize Nth = 1
- Starting with {P1}, {P2}, ..., {Pm} for L.
- Find the smallest value, Es, of the min heap, MH, that is made of the head of L.
As MH - {P1, P2, ..., Pm} at the start.
- Find the corresponding prime number against which linked list Es comes from, Px and Lx
- Append Es*Px into Lx, Es*Px+1 into Lx+1, ..., Ex*Pm into Lm
- Remove Es from Lx and increment the Nth
- Repeat above 4 steps until Nth reaches N.

Details: cpluspluslearning-petert.blogspot.co.uk/2015/12/find-nth-expressible-number-of-given.html

Test:

void TestFindNthExpressibleNum()
{
    std::vector<unsigned long> sortedPrimes;
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 5) == 0);

    sortedPrimes.push_back(2);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 1);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 2) == 2);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 3) == 4);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 4) == 8);

    sortedPrimes.push_back(3);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 1);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 2) == 2);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 3) == 3);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 4) == 4);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 5) == 6);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 6) == 8);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 7) == 9);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 8) == 12);

    sortedPrimes = {3, 5, 7};
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 1);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 2) == 3);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 3) == 5);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 4) == 7);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 5) == 9);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 6) == 15);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 7) == 21);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 8) == 25);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 9) == 27);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 10) == 35);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 11) == 45);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 12) == 49);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 13) == 63);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 14) == 75);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 15) == 81);
}

- peter tang December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Store values in a Tree Map with value as keys, and the prime number with which they are made as values. Since Tree Map is already sorted on the basis of keys, you can simply remove the first key and add its next multiple. Put / Get / Delete / Contains are Log(n) in Tree Map. Hence the complexity of this solution would be : O(n * log(m)). Where M is the size of the subset.

Java Code Below:

/* 
 * @author shivam.maharshi
 */
public class NthSmallestMulFromSet {

	// O(n*log(m)). M is size of set.
	public static int get(int[] set, int n) {
		TreeMap<Integer, Integer> map = new TreeMap<>();
		for (int a : set) {
			map.put(a, a);
		}
		int num = 0;
		while (n > 0) {
			num = map.firstKey();
			int value = map.get(num);
			map.remove(num);
			if (!map.containsKey(num + value)) {
				map.put(num + value, value);
			} else {
				map.put(num + 2 * value, value);
			}
			n--;
		}
		System.out.println(num);
		return num;
	}

	public static void main(String[] args) {
		int[] set = { 2, 3 };
		get(set, 6);
	}

}

- Shivam Maharshi January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using namespace std;

typedef vector<int> TVI;
TVI  g = {2,3};

  TVI v = {1}; // add new numbers to this vector, assume it is always sorted ascending strict
  TVI idx(g.size(), 0); // to store next possible generated number using each input number in generator list

  while (v.size() < 100) // while we still want to generate more numbers
    {
      TVI tg (g.size());
      for (int i(0); i < g.size();++i)
        {
          tg[i] = g[i] * v[idx[i]]; // generate next minimum for each item in generator set
        }
     size_t cidx = distance(tg.begin(), min_element(tg.begin(), tg.end()));
      if (tg[cidx] > v.back())
        v.push_back(tg[cidx]);
      ++idx[cidx];
    }

  std::cout << "is sorted " << is_sorted(v.begin(), v.end()) << "\n";

- nawap February 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The algorithm is $O(n)$. Note every time it the size of list is increased by one and it stops when the size is equal to $n$ (well, it may generate duplicate values, but every duplicate value is not generated more than twice --> still O(n))

int myExpressibleInsert(vector<int>& R, int val)
{
int i=0;
while (i < R.size() && R[i] < val) i++;
if (i < R.size())
{
if (R[i] != val)
R.insert(R.begin() + i - 1, val);
}
else
R.push_back(val);
return i;
}

int prime_expressible(const vector<int> S, int n)
{
vector<int> result;
int i;
result.push_back(1);
int startindex = 0;
while (result.size() < n)
{
int stopindex=n;
for (i = startindex; i < stopindex; i++)
{
for (int j = 0; j < S.size(); j++)
{
int temp = myExpressibleInsert(result, result[i] * S[j]);
if (stopindex == n && temp < n)
stopindex = temp;
}
if (result.size() >= n) return result[n];
}
startindex = stopindex;
}
return result[n];
/* main body
vector<int> S = { 2, 3 };
cout << prime_expressible(S, 7);
*/
}

- Abolfazl Asudeh February 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <iostream>
#include <set>

using namespace std;


int main()
{
	int arr [] = {2,3,7,11};
	int size = sizeof(arr)/sizeof(int);
	set<int>multiples1(arr,arr + size);
	set<int>multiples2(arr,arr + size);

	typedef set<int>::iterator itr;

	while( multiples1.size() < 100 )
	{		
		for(itr n = multiples1.begin(); n != multiples1.end(); n++)
		{
			for(itr m = multiples1.begin(); m != multiples1.end(); m++)
			{
				multiples2.insert( *n * *m );
			}
		}

		for(itr n = multiples2.begin(); n != multiples2.end(); n++)
		{
			for(itr m = multiples2.begin(); m != multiples2.end(); m++)
			{
				multiples1.insert( *n * *m );
			}
		}
	}

	int m = 0;
	for(itr n = multiples2.begin(); n != multiples2.end() && m < 100; n++)
	{
		cout << m << " " << *n << endl;
		m++;
	}


	return 0;

}

- Anonymous May 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <iostream>
#include <set>

using namespace std;


int main()
{
	int arr [] = {2,3,7,11};
	int size = sizeof(arr)/sizeof(int);
	set<int>multiples1(arr,arr + size);
	set<int>multiples2(arr,arr + size);

	typedef set<int>::iterator itr;

	while( multiples1.size() < 100 )
	{		
		for(itr n = multiples1.begin(); n != multiples1.end(); n++)
		{
			for(itr m = multiples1.begin(); m != multiples1.end(); m++)
			{
				multiples2.insert( *n * *m );
			}
		}

		for(itr n = multiples2.begin(); n != multiples2.end(); n++)
		{
			for(itr m = multiples2.begin(); m != multiples2.end(); m++)
			{
				multiples1.insert( *n * *m );
			}
		}
	}

	int m = 0;
	for(itr n = multiples2.begin(); n != multiples2.end() && m < 100; n++)
	{
		cout << m << " " << *n << endl;
		m++;
	}


	return 0;
}

- cm May 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's the version in Python

def nth_prime_factor(prime_set):
    found = [1]
    index = {prime:0 for prime in prime_set}
    while True:
        next_primes = {prime:found[index[prime]]*prime for prime in prime_set}
        min_next_prime = float('inf')
        for k,v in next_primes.items():
            if v <= min_next_prime:
                min_next_prime = v
        found.append(min_next_prime)
        yield found[-1]
        for prime, next_prime in next_primes.items():
            if next_prime == min_next_prime:
                index[prime] += 1

and the driver is:

prime_set = [2, 3, 7, 11]
n = 25
nth_prime_factor_generator = nth_prime_factor(prime_set)
for x in range(n):
    result = next(nth_prime_factor_generator)
	
print result

- Justin Tervala June 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python 3.5

def generate_prime_factors(n):
    i = 2
    while i**2 <= n:
        if n % i:
            i += 1
        else:
            n //= i
            if i:
                yield i
    if n > 1:
        yield n

def is_prime_expressible_given_prime_set(i, ps):
    expressable = (p for p in generate_prime_factors(i) if p in ps)
    non_expressable = (p for p in generate_prime_factors(i) if p not in ps)
    return len(list(expressable)) > 0 and len(list(non_expressable)) == 0

def generate_prime_expressibles(ps):
    i = 1
    while True:
        if is_prime_expressible_given_prime_set(i, ps):
            yield i
        i += 1

def find_nth_expressible(n, ps):
    prime_expressibles = []
    for i, pe in enumerate(generate_prime_expressibles(prime_set)):
        if i == n:
            break
        prime_expressibles.append(pe)
    return max(prime_expressibles)

if __name__ == "__main__":
    prime_set = [2, 3]
    n = 7
    print(str(find_nth_expressible(n, prime_set)))   #12

- clint@datanavigator.ca July 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

{2, 3, 5, 7, 11, 23, 97}, 3 => 3
{2, 3, 5, 7, 11, 23, 97}, 1000000 => 1244877
{99991}, 1000000 => 99990900009

c++, Sieve of Eratosthenes, O(n^2)? O(n log n)?

typedef unsigned long long UINT64;

UINT64 getNthNumber(vector<int>& primes, int n) {
    set<UINT64> nums;
    set<UINT64>::reverse_iterator rit;
    UINT64 num;
    unsigned int i;
    
    nums.insert(1);
    for (i = 0; i < primes.size(); i++) {
        num = 0;
        while (true) {
            num += primes[i];
            nums.insert(num);
            if (nums.size() >= n && *nums.rbegin() == num) {
                while (nums.size() > n) {
                    rit = nums.rbegin();
                    nums.erase(next(rit).base());
                }
                break;
            }
        }
    }
    
    return *nums.rbegin();
}

- kyduke October 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your code is incorrect for case primes = {4441}, n = 2, it outputs 8882, but expected output is 19722481
hxxp://ideone.com/2uaTys

- emb October 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

emb, you are right. It is not correct answer. I must use multiplication, not addition.

- kyduke October 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I have a solution that is O(n*log(n*k)), k:number of elements in the prime set

-First insert "1" to the set
-in each iteration, get the ith element of the set ( i is the iterator ) and multiply it by each element in the prime set and add it to the set
-perform n iteration

Time Complexity: we are adding at most k elements in each iterations, so the size of the set is less than or equal to (n*k), and we have n iterations, so it can be done in O(n*log(n*k)), order O(n*log(n)) is also achievable, but it's a bit complcated

c++ Code:

int getNthNumber(vector<int>& primes, int n) 
{
   set<int> nums;
   set<int>::iterator it;
   nums.insert( 1 );

   // PRINTING--------------------------------------------------------
   std::vector<int>::iterator iter;
   std::set<int>::iterator iter2;

   std::cout << "INPUT:{";
   for ( iter = primes.begin() ; iter != primes.end() ; ++iter )
   {
      std::cout << *iter << ", ";
   }
   std::cout << "} N = " << n <<"\n\n";
   //-----------------------------------------------------------------

   //Now we start from the beginning of the set, every time we see a number
   //We multiply it by every element in the original prime set and add it to our set

   int new_number;

   iter2 = nums.begin();

   int counter = 1;

   while (1)
   {
      if ( counter == n )
      {
         break;
      }

      std::cout <<  "Iteration " << counter++ << ", Current number is "<< (*iter2) << "\n" ;

      for ( iter = primes.begin() ; iter != primes.end() ; ++iter )
      {
         new_number = (*iter)*(*iter2);
         
         std::cout <<  "   Adding number " << new_number << "\n" ;

         nums.insert( new_number );
      }

      ++iter2;
   }

   std::cout << "\nPrinting the result\n";
   std::cout << nums.size() << " numbers in the set\n";
   counter = 0;
   for ( iter2 = nums.begin() ; counter < n ; ++iter2 )
   {
      std::cout << ++counter << ": " << (*iter2) << "\n";
   }
   return 0;
}

Sample Output:

INPUT:{2, 5, 7, 11, } N = 10

Iteration 1, Current number is 1
Adding number 2
Adding number 5
Adding number 7
Adding number 11
Iteration 2, Current number is 2
Adding number 4
Adding number 10
Adding number 14
Adding number 22
Iteration 3, Current number is 4
Adding number 8
Adding number 20
Adding number 28
Adding number 44
Iteration 4, Current number is 5
Adding number 10
Adding number 25
Adding number 35
Adding number 55
Iteration 5, Current number is 7
Adding number 14
Adding number 35
Adding number 49
Adding number 77
Iteration 6, Current number is 8
Adding number 16
Adding number 40
Adding number 56
Adding number 88
Iteration 7, Current number is 10
Adding number 20
Adding number 50
Adding number 70
Adding number 110
Iteration 8, Current number is 11
Adding number 22
Adding number 55
Adding number 77
Adding number 121
Iteration 9, Current number is 14
Adding number 28
Adding number 70
Adding number 98
Adding number 154

Printing the result
28 numbers in the set
1: 1
2: 2
3: 4
4: 5
5: 7
6: 8
7: 10
8: 11
9: 14
10: 16

- koosha.nejad November 03, 2015 | Flag Reply


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