Google Interview Question
Country: United States
multiples of 4 give sequence:
4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, ...
multiples of 6 give sequence:
6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, ...
Combine 2 sequences (but eliminate duplicates):
4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 44, 48, 52, 54, 56, 60, 64, 66, 68, 72, ...
The task is to get the Nth element from combined sequence.
c++, implementation, O(n log n)
int nthMultipleNumber(vector<int> arr, int n) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int i, ret;
if (arr.size() == 0 || n <= 0) return 0;
for (i = 0;i < arr.size(); i++) {
q.push(make_pair(arr[i], i));
}
ret = 0;
while (n) {
if (ret != q.top().first) n--;
ret = q.top().first;
i = q.top().second;
q.pop();
q.push(make_pair(ret + arr[i], i));
}
return ret;
}
I think thar time complexity is nlog(k) where the k is set cardinality. Could this be improved with fibonachhi heap?
That's right.
It can be improved with sorted data structures. I used sorted hashmap.
The time complexity is O(n + k).
c#.
Time: O(n*logm + m), where m - arr.Length.
Space: O(m).
static private int GetNthSmallestMultiple( int[] arr, int n ) {
var sortedHash = new SortedList<int, int>();
for ( int i = 0; i < arr.Length; i++ ) {
sortedHash.Add( arr[ i ], i );
}
int current = 0;
while( n > 0 ) {
n--;
current = sortedHash.Keys[ 0 ];
var i = sortedHash[ current ];
var key = current + arr[ i ];
sortedHash.RemoveAt( 0 );
if ( sortedHash.ContainsKey( key ) ) {
key += arr[ i ];
}
sortedHash.Add( key, i );
}
return current;
}
According to the question we have to print n smallest multiples of 4 or 6.
For example : input set is {2, 5, 7} and k is 6 then
multiples of 2 are 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, .......
multiples of 5 are 5, 10, 15 ,20, 25, 30, 35, 40, 25, .......
multiples of 7 are 7, 14, 21, 28, 35, 42, 49, 56, 63, .......
Combine these sequences sort them and print first 6 element
2, 4, 5, 6, 7, 8
This solution does some optimization to avoid unnecessary computations, but I don't believe it improves the worst case time. For example, it only continues adding multiples of a number so long as the length of the selection is < n, or the number to be added is less than the current item in position n. To do this I keep the selection sorted in real time, though I'm using a dumb approach to do so. Performance could be improved by using a smart search on the selection, or a priority queue (so long as the queue was able to get an item at position n in O(1) time).
public static Integer findSmallestNthMultiple(int[] set, int n) {
if (set == null || set.length == 0) {
return null;
}
List<Integer> list = new LinkedList<>();
for (int i : set) {
list.add(i);
}
Collections.sort(list);
List<Integer> prime = Lists.newArrayList(list);
for (Integer m : list) {
if (m == 0) continue;
Integer mP = m;
int insertIndex = 1;
while ((prime.size() < n || mP + m < prime.get(n - 1))) {
mP += m;
while (insertIndex < prime.size() && mP > prime.get(insertIndex)) {
insertIndex++;
}
if (insertIndex != prime.size() && prime.get(insertIndex).intValue() == mP.intValue()) {
continue;
}
prime.add(insertIndex++, mP);
}
}
return prime.get(n - 1);
}
#!/usr/bin/python
import sys
def nth_mul(a, b, n):
c = 1
m = 2
# Extract common multipler, leave co-prime quotients
while m < a and m < b:
if a % m == 0 and b % m == 0:
c *= m
a /= m
b /= m
else:
m += 1
print "A = %d * %d" % (c, a)
print "B = %d * %d" % (c, b)
# For each A candidates generated from B and B canditates
# generated from A exactly one (the last) is duplicated.
# The formula below returns the searched value in case it
# hits to duplicated element.
v = n * c * a * b / (a + b - 1)
print "V = %d (tentetively)" % v
# Otherwise, we adjust it to the next value in sequence.
if v % (a * c) != 0 and v % (b * c) != 0:
v = min(v + a * c - v % (a * c), v + b * c - v % (b * c))
print "V = %d" % v
nth_mul(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]))
#!/usr/bin/python
import sys
def nth_mul(a, b, n):
c = 1
m = 2
# Extract common multipler, leave co-prime quotients
while m < a and m < b:
if a % m == 0 and b % m == 0:
c *= m
a /= m
b /= m
else:
m += 1
print "A = %d * %d" % (c, a)
print "B = %d * %d" % (c, b)
# For each A candidates generated from B and B canditates
# generated from A exactly one (the last) is duplicated.
# The formula below returns the searched value in case it
# hits to duplicated element.
v = n * c * a * b / (a + b - 1)
print "V = %d (tentetively)" % v
# Otherwise, we adjust it to the next value in sequence.
if v % (a * c) != 0 and v % (b * c) != 0:
v = min(v + a * c - v % (a * c), v + b * c - v % (b * c))
print "V = %d" % v
nth_mul(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]))
Apart from extracting the common multiplier, the rest is constant time.
Can be done in constant space. The time does not depend on N:
#!/usr/bin/python
import sys
def nth_mul(a, b, n):
c = 1
m = 2
# Extract common multipler, leave co-prime quotients
while m < a and m < b:
if a % m == 0 and b % m == 0:
c *= m
a /= m
b /= m
else:
m += 1
print "A = %d * %d" % (c, a)
print "B = %d * %d" % (c, b)
# For each a candidates generated from b and b canditates
# generated from a exactly one (the last) is duplicated.
# The formula below returns the searched value in case it
# hits the duplicated element.
v = n * c * a * b / (a + b - 1)
print "V = %d (tentetively)" % v
# Otherwise, we adjust it to the next value in sequence.
if v % (a * c) != 0 and v % (b * c) != 0:
v = min(v + a * c - v % (a * c), v + b * c - v % (b * c))
print "V = %d" % v
nth_mul(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]))
./nth_mul.py 6 4 6
A = 2 * 3
B = 2 * 2
V = 18 (tentetively)
V = 18
./nth_mul.py 6 4 7
A = 2 * 3
B = 2 * 2
V = 21 (tentetively)
V = 24
import java.util.ArrayList;
import java.util.Arrays;
public class Question1
{
public int nthSmallest(int[] nums, int n)
{
int[] indexes = new int[nums.length];
Arrays.fill(indexes,1);
int ret = 0;
for(int i=0; i<n; i++)
{
ret=chooseAndIncSmallest(indexes, nums);
System.out.print(ret + " ");
}
return ret;
}
public int chooseAndIncSmallest(int[] indexes, int[] nums)
{
int smallest = Integer.MAX_VALUE;
ArrayList<Integer> indx = new ArrayList<Integer>();
for(int i=0; i<indexes.length; i++)
{
if (nums[i]*indexes[i] < smallest)
{
smallest=nums[i]*indexes[i];
indx= new ArrayList<Integer>();
indx.add(i);
}
else if (nums[i]*indexes[i] == smallest)
{
indx.add(i);
}
}
for (int i=0; i<indx.size();i++)
indexes[indx.get(i)]++;
return smallest;
}
public static void main(String[] args)
{
System.out.println("\n"+new Question1().nthSmallest(new int[]{3,4,6},12));
}
}
Simple question. The idea is to use a min-priority-heap to track the top of the 3 sequence based on each element. Each time squeeze out one number. And skip counting the top of the min-priority-heap is equal to last value (it means that this value is a common divider of at least of two elements in the given set). Keep doing this until reach Nth.
Details: cpluspluslearning-petert.blogspot.co.uk/2015/12/find-nth-multiple-given-set.html
Test
void TestFindNthMultipleNum()
{
std::vector<unsigned long> sortedPrimes;
assert(FindNthMultipleNumGivenSet(sortedPrimes, 0) == 0);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 1) == 0);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 5) == 0);
sortedPrimes.push_back(4);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 0) == 0);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 1) == 4);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 5) == 20);
sortedPrimes.push_back(6);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 0) == 0);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 1) == 4);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 2) == 6);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 3) == 8);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 4) == 12);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 5) == 16);
assert(FindNthMultipleNumGivenSet(sortedPrimes, 6) == 18);
}
public class MultipleSequenceNthElement {
//Time complexity O(m + nlogm) - first addition to the queue and then logm iteration of the queue n times.
public int getNthElement(int[] arr, int n) {
Set<Integer> uniqueAnswers = new HashSet<Integer>();
int max = -1;
Queue<Pair> pairPriorityQ = new PriorityQueue<Pair>(new PairComparator());
for (int i = 0; i < arr.length; i++) {
pairPriorityQ.add(new Pair(arr[i], i));
}
while (uniqueAnswers.size() < n) {
int candidate = getCandidate(pairPriorityQ, arr);
if (!uniqueAnswers.contains(candidate)) {
uniqueAnswers.add(candidate);
max = Math.max(max, candidate);
}
}
return max;
}
private int getCandidate(Queue<Pair> pairPriorityQ, int[] arr) {
Pair minPair = pairPriorityQ.poll();
Pair newPair = new Pair(minPair.multipleVal + arr[minPair.arrPos], minPair.arrPos);
pairPriorityQ.offer(newPair);
return minPair.multipleVal;
}
class Pair {
public int multipleVal;
public int arrPos;
public Pair(int multipleVal, int arrPos) {
this.multipleVal = multipleVal;
this.arrPos = arrPos;
}
}
class PairComparator implements Comparator<Pair> {
public int compare(Pair o1, Pair o2) {
if (o1.multipleVal != o2.multipleVal) {
return o1.multipleVal - o2.multipleVal;
}
return o1.arrPos - o2.arrPos;
}
}
public static void main(String[] args) {
MultipleSequenceNthElement multipleSequenceNthElement = new MultipleSequenceNthElement();
int[] arr = {3, 4, 6};
int n = 6;
System.out.println("the " + n + " th element of sequence is " + multipleSequenceNthElement.getNthElement(arr, n));
}
}
Here is my simple solution in Python:
{def series(x,y, n):
if x == y:
print(x*n)
return
if y < x :
(x,y) = (y,x)
xi = 0
yj = 0
count = 0
xChange = True
yChange = True
last_item = 0
while count < n:
if xChange: xi += x
if yChange: yj += y
if xi == yj:
last_item = xi
iChange = True
jChange = True
elif xi < yj:
last_item = xi
iChange = True
jChange = False
else:
lase_item = yj
iChange = False
jChange = True
count += 1
print(last_item, end = ' :: ')
series(4,6,6)
print('\n')
series(4,6,2)
print('\n')
series(6,3,5)
print('\n')
series(4,4,6)
}
Simple Python implementation
def series(x,y, n):
if x == y:
print(x*n)
return
if y < x :
(x,y) = (y,x)
xi = 0
yj = 0
count = 0
xChange = True
yChange = True
last_item = 0
while count < n:
if xChange: xi += x
if yChange: yj += y
if xi == yj:
last_item = xi
iChange = True
jChange = True
elif xi < yj:
last_item = xi
iChange = True
jChange = False
else:
lase_item = yj
iChange = False
jChange = True
count += 1
print(last_item, end = ' :: ')
series(4,6,6)
print('\n')
series(4,6,2)
print('\n')
series(6,3,5)
print('\n')
series(4,4,6)
def series(x,y, n):
if x == y:
print(x*n)
return
if y < x :
(x,y) = (y,x)
xi = 0
yj = 0
count = 0
xChange = True
yChange = True
last_item = 0
while count < n:
if xChange: xi += x
if yChange: yj += y
if xi == yj:
last_item = xi
iChange = True
jChange = True
elif xi < yj:
last_item = xi
iChange = True
jChange = False
else:
lase_item = yj
iChange = False
jChange = True
count += 1
print(last_item, end = ' :: ')
series(4,6,6)
print('\n')
series(4,6,2)
print('\n')
series(6,3,5)
print('\n')
series(4,4,6)
This can be done in log(n) using binary search.
We need the n-th item of the combined sequence A[n], so we start with a range between l=0 and some number h which is the k-th item in the combined sequence, such that m>=A[n]. This can be satisified by choosing h=i[0]*n where i[0] is one the numbers on the input list. Since h=i[0]*n is the n-th number of the multiplication sequence of i[0], it will be some k-th item on the combined sequence where k>=n, so h=A[k]>=A[n].
Now all we need is to perform binary search by repeatedly choosing a middle value m=(l+h)/2 and computing the position "p" of its closest item the combined sequence such that A[p]<=m, and then comparing p to n. If p<n we recursively search from m to h, otherwise we search from l to m.
To compute the position p of a number m such that A[p]<=m, we simply use the formula p=floor(m/i[0])+floor(m/i[1])-floor(m/lcm(i[0],i[1])). lcm is the lowest common multiple of a pair of numbers. If there are more than two numbers in the input, the we expand this formula for each of the number and the lcm of each pair.
For example, lets take the values from the question i={4,6} n=6. We compute lcm(4,6)=12.
Initially we search from 0 to 4*6=24. So we choose 12, which is the 4-th item in the combined sequence: p=floor(12/4)+floor(12/6)-floor(12/12)=3+2-1=4.
Since we need the 6-th item (n=6), we now search from 12 to 24. We choose 18, which is the p=floor(18/4)+floor(18/6)-floor(18/12)=4+3-1=6. So we found the 6-th item. Done.
The question doesn't make any sense. How does the set { 4,6} lead to the given pattern? If anything, its should start from the LCM of the two numbers. Something is not mentioned here.
- Codingguest December 12, 2015