Amazon Interview Question
SDE1sCountry: United States
Java Version:
public class IdsGenerator {
static Set<String> idsSet = new TreeSet<>(new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
if(o1.length() <= o2.length())
return -1;
else
return 1;
}
});
static Queue<String> q = new LinkedList<String>();
public static void idGenerator(Set<Character> set, int m){
Set<String> dict = new HashSet<String>();
for(Character ch : set){
dict.add(String.valueOf(ch));
}
idsSet.addAll(makeUniqueIds(dict, m));
q.addAll(idsSet);
//System.out.println(idsSet);
}
public static Set<String> makeUniqueIds(Set<String> dict, int level){
Set<String> ids = new HashSet<String>();
for(int i = 1; i <= level; i++){
ids.addAll(makeIdsForLevel(dict, i));
}
return ids;
}
public static Set<String> makeIdsForLevel(Set<String> dict, int level){
if(level == 1)
return dict;
Set<String> mergedSet = new HashSet<String>();
for(String str : dict){
for(String ids : makeIdsForLevel(dict, level - 1)){
mergedSet.add(str + ids);
}
}
return mergedSet;
}
public static boolean hasNext(){
return q.size() > 0;
}
public static String next(){
return q.poll();
}
// To Do: DP
public static void main(String[] args) {
Set<Character> set = new HashSet<>();
set.add('1');
set.add('2');
set.add('3');
idGenerator(set,3);
while(hasNext()){
System.out.print(next() + " ");
}
}
}
Java DP Version:
public class IdsGenerator {
static Set<String> idsSet = new TreeSet<>(new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
if(o1.length() <= o2.length())
return -1;
else
return 1;
}
});
static Queue<String> q = new LinkedList<String>();
public static void idGenerator(Set<Character> set, int m){
Set<String> dict = new HashSet<String>();
Map<Integer, Set<String>> cache = new HashMap<Integer, Set<String>>();
for(Character ch : set){
dict.add(String.valueOf(ch));
}
cache.put(1, dict);
idsSet.addAll(makeUniqueIds(dict, m, cache));
q.addAll(idsSet);
}
public static Set<String> makeUniqueIds(Set<String> dict, int level, Map<Integer, Set<String>> cache){
Set<String> ids = new HashSet<String>();
for(int i = 1; i <= level; i++){
ids.addAll(makeIdsForLevel(dict, i, cache));
}
return ids;
}
public static Set<String> makeIdsForLevel(Set<String> dict, int level, Map<Integer, Set<String>> cache){
if(cache.containsKey(level)){
return cache.get(level);
}
Set<String> mergedSet = new HashSet<String>();
for(String str : dict){
for(String ids : makeIdsForLevel(dict, level - 1, cache)){
mergedSet.add(str + ids);
}
}
cache.put(level, mergedSet);
return mergedSet;
}
public static boolean hasNext(){
return q.size() > 0;
}
public static String next(){
return q.poll();
}
// To Do: DP
public static void main(String[] args) {
Set<Character> set = new HashSet<>();
set.add('1');
set.add('2');
set.add('3');
idGenerator(set,3);
while(hasNext()){
System.out.print(next() + " ");
}
}
}
# expandable counter - a generator of a number represented as an array of integers in given base
# Yields an array with incremented number on each next() call.
# Each position is an integer in [0..base-1] where the first item is the number LSB
# The number of digits is incremented by one when the counter rolls-over.
# For example for base 10 it yields: [0], [1],...,[9], [0,0], [1,0],...,[9,9], [0,0,0], ...
# (1 digits counter 0..9, 2 digits counter 00..99, 3 digits counter 000..999, etc.)
#
def xcounter(base):
counter = [0]
yield counter
while True:
for i in xrange(len(counter)):
counter[i] += 1
if counter[i] >= base:
counter[i] = 0
else:
break
if i == len(counter) - 1 and counter[-1] == 0:
counter.append(0)
yield counter
# A generator for id strings consisting fiven characters set were no character is repeated more than m times
# chars - a list of characters (e.g. ['0', '1', ... ,'9']
# m - maximum repetition of any character in yielded id
#
# Uses xcounter for generating expanded counter values and skip values which contain
# at least one consecutive appearance longest than m of any digit
#
def idgen(chars, m):
counter = xcounter(len(chars))
while True:
a = counter.next()
# skip counter with longer than m consecutive run of any digit
if longSubarray(a, m):
continue
# converts counter value into a string, reversing the value array for lexicograpical order
# (of same length ids)
id = ''.join([chars[x] for x in reversed(a)])
yield id
# Predicate for checking whether given list 'a' contains
# a consecutive repetition longer than given threshold of any value
#
def longSubarray(a, threshold):
if len(a) <= threshold:
return False
currLen = 1
for i in xrange(1, len(a)):
if a[i] == a[i-1]:
currLen += 1
if currLen > threshold:
return True
else:
currLen = 1
return False
# expandable counter - a generator of a number represented as an array of integers in given base
# Yields an array with incremented number on each next() call.
# Each position is an integer in [0..base-1] where the first item is the number LSB
# The number of digits is incremented by one when the counter rolls-over.
# For example for base 10 it yields: [0], [1],...,[9], [0,0], [1,0],...,[9,9], [0,0,0], ...
# (1 digits counter 0..9, 2 digits counter 00..99, 3 digits counter 000..999, etc.)
#
def xcounter(base):
counter = [0]
yield counter
while True:
for i in xrange(len(counter)):
counter[i] += 1
if counter[i] >= base:
counter[i] = 0
else:
break
if i == len(counter) - 1 and counter[-1] == 0:
counter.append(0)
yield counter
# A generator for id strings consisting fiven characters set were no character is repeated more than m times
# chars - a list of characters (e.g. ['0', '1', ... ,'9']
# m - maximum repetition of any character in yielded id
#
# Uses xcounter for generating expanded counter values and skip values which contain
# at least one consecutive appearance longest than m of any digit
#
def idgen(chars, m):
counter = xcounter(len(chars))
while True:
a = counter.next()
# skip counter with longer than m consecutive run of any digit
if longSubarray(a, m):
continue
# converts counter value into a string, reversing the value array for lexicograpical order
# (of same length ids)
id = ''.join([chars[x] for x in reversed(a)])
yield id
# Predicate for checking whether given list 'a' contains
# a consecutive repetition longer than given threshold of any value
#
def longSubarray(a, threshold):
if len(a) <= threshold:
return False
currLen = 1
for i in xrange(1, len(a)):
if a[i] == a[i-1]:
currLen += 1
if currLen > threshold:
return True
else:
currLen = 1
return False
Example:
>>> idg = idgen(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'], 3)
idg = idgen(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'], 3)
>>> ids = [idg.next() for _ in xrange(20)]
ids = [idg.next() for _ in xrange(20)]
>>> ids
ids
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '00', '01', '02', '03', '04', '05', '06', '07', '08', '09']
>>> idg = idgen(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'], 3)
idg = idgen(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'], 3)
>>> ids = [idg.next() for _ in xrange(2250)]
ids = [idg.next() for _ in xrange(2250)]
>>> ids[2218:2222]
ids[2218:2222]
['1109', '1110', '1112', '1113']
package com.harsha.cs;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
/**
* Harsha.H
*/
public class Subsets {
private static Set uniqueIds = new HashSet();
public void generateUniqueIds(int[] givenArray){
int[] subset = new int[givenArray.length];
helper(givenArray, subset, 0);
}
/**
* Get all the subsets for the given array.
* The algorithm goes like, if you pick or not pick the current item, how does it evolve.
* @param givenArray
* @param subset
* @param i
*/
private void helper(final int[] givenArray, int[] subset, int i) {
if(i == givenArray.length) {
addToSet(subset);
} else {
subset[i] = 0;
helper(givenArray, subset, i+1);
subset[i] = givenArray[i];
helper(givenArray, subset, i+1);
}
}
/**
* Remove dups from the string.
* @param subset
*/
private void addToSet(int[] subset) {
String str = Arrays.stream(subset).filter(x -> x != 0).mapToObj(a -> ((Integer)a).toString()).collect(Collectors.joining(","));
uniqueIds.add(str);
}
public static void main(String[] args){
Subsets subsets = new Subsets();
int[] arr = {1,2,3};
int m = 3;
int[] newArray = Arrays.stream(arr).flatMap(a -> IntStream.iterate(a, j -> j).limit(m)).toArray();
System.out.println(Arrays.toString(newArray)); // Create exploded array with elements of m times.
subsets.generateUniqueIds(newArray);
uniqueIds.stream().sorted(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if(((String)o1).length() < ((String)o2).length()) return -1;
else if(((String)o1).length() > ((String)o2).length()) return 1;
else return 0;
}
}).forEach(System.out::println);
}
}
C++ Solution.
Assumption: int m (level) is also the limit length for the key. If this assumption is not agreeable, it's easy to increase the level and filter strings that have more than m of the same character....
OUTPUT:
- Gabriel Feyer May 23, 2018Constructed Ids: [
3 2 1 33 32 31 23 22 21 13 12 11 333 332 331 323 322 321 313 312 311 233 232 231 223 222 221 213 212 211 133 132 131 123 122 121 113 112 111 ]
next id: 3
next id: 2
next id: 1
next id: 33
next id: 32
next id: 31
next id: 23
next id: 22
next id: 21
next id: 13
next id: 12
next id: 11
next id: 333
next id: 332
next id: 331
next id: 323
next id: 322
next id: 321
next id: 313
next id: 312
next id: 311
next id: 233
next id: 232
next id: 231
next id: 223
next id: 222
next id: 221
next id: 213
next id: 212
next id: 211
next id: 133
next id: 132
next id: 131
next id: 123
next id: 122
next id: 121
next id: 113
next id: 112
next id: 111
All IDs have been used.
Process returned 0 (0x0) execution time : 0.047 s
Press any key to continue.