Chris
BAN USERSWE
- 0of 0 votes
AnswersA new species has been discovered and we are trying to understand their form of communication. So, we start by identifying their alphabet. Tough Mr. Brown managed to steal a vocabulary that has words in it in ascending order and a team already identified the letters. So, we have now ordered words as sequences of numbers, print every letter once in ascending order.
- Chris in United States
[3,2]
[4,3,2]
[4,1,1]
[1, 2]
[1, 1]
alphabet: [3, 4, 2, 1]| Report Duplicate | Flag | PURGE
Software Engineer Data Structures
@Sivan:
when studying your code, I noticed
Integer hash = subList1.hashCode();
if(!solutionMap.containsKey(hash)) {
subList1.sort(Integer::compareTo);
solutionMap.put(subList1.hashCode(), subList1);
}
this doesn't only prevent adding duplicates but as well different lists that by chance result in the same hash value.You need to deep compare to ensure it's not the case (of course this happens only once in 2^31 cases ...) anyway I just noticed
further, I think [0,2] and [2,0] would produce different Hash codes but represent the same set.
When solving the problem I concluded best to avoid dublicate sets is to produce a set from the input values... (as well because the amount of entries go into the factorial for the O(n!) runtime)
how many time does an element occur at most in a set? ;-) once otherwise it's not a set, right? but I guess, he didn't really mean a set but a data set / array / what ever with the semantics that if you add 10 two times and delete it once, it's still once in there.
- mean: Sum/n (as long as no overflow danger exists...)
- median: Method with two heaps. To delete use the same structure as with mode below but instead of element count, use element value (a max heap and a min heap...)
- mode: heap of element'counts combined with a HT to the index of such an element into the heap (requires the heap to patch the HT when heapifying, bubbling up/down)
requires some memory... but the question didn't mention about usage. If you insert / delete most of the time, it might be more convenient to just insert/delete into a HT (value, count) and perform the queries in linear time which works for mean, median and mode.
@HarryT:
suppose n = 3, m = 30
the following log would be correct according to the problem statement
time | bot id |
30 | 1 |
30 | 2 |
31 | 1 |
32 | 1 |
50 | 2 |
60 | 2 |
but if you only go back 10 seconds, you miss bot 1, since the question didn't say anything about the distribution. I assumed it's a more or less uniform distribution
so:
time | bot id |
30 | 1 |
30 | 2 |
40 | 1 |
40 | 2 |
50 | 1 |
50 | 2 |
I would look at 50=2 and 50=1 and 40=2 and 40=1 and 30=2 and stop here, because 50-30 > 10.
but as soon you have a little jitter due to scheduling or what ever it might look like:
time | bot id |
29 | 1 |
32 | 2 |
42 | 1 |
43 | 2 |
49 | 1 |
49 | 2 |
61 | 2 |
so, you look at 61 = 2 and 49 = 2 and stop because 61-49 > 10 ... ooops
so a safety factor would extend the time frame you look at so you catch reasonable outliers on the "arrival time" ...
the question said nothing about the distribution within this n seconds. Assuming a perfect uniform distribution, knowing the context, is a bit naive, I thought ...
/*
like knapsack, the problem of finding a subset of a set that
sums up to a sum is a known NP-complete problem. There exists
a pseudo polynomial solution like with knapsack.
The recursion is
dp(i, k, target, result) = dp(i-1, k, target, result) ++ dp(i-1, k, target, result + {nums[i]}), if k > 0
return result, if k == 0 and target == 0
return {} if (k == 0 && target !=0) || target < 0 || i < 0
++: merge the list of sets returned by dp
this is O(n*(n-1)*(n-2)*..*(n-k)) = O(n!/(n-k)!) (if k = 1, its n...)
a common subproblem exists if the sum z of l<k elements of multiple subsets
in the range [o..n) exists, because then, all of those subsets would
lead to a solution if at least one subset of k-l elements in [0..o) would
sum up to target-z.
...
how to solve it now:
1) first thing we need to do is offset the target and all element values so
we get only positive values and 0s. we can here convert nums to a set to get
rid of ublicate values (because the result is supposed to be a set)
note: the target has k times the offset
reduced problem set: combinationSumPositive
2) create an empty sums hashtable where the sum is key and the values are all
subsets with size <= k that lead to this sum (only for sum <= target)
sums[0] = list with one empty set
iterate i from 0 to n
for each key in sums:
if key+nums[i] <= target:
for each set in sums[key]
if(set.size() < k)
nums.add(key+nums[i], set + {nums[i]}
3) sums[target] contains all results, but as well those with size < k, filter it
4) remove offset from elements, done.
5) time complexity is O(n*target*n*n) = O(n^3*target) ... hey, it's polinomial :-)
Space complexity is O(target*n^2)
of course, if you put this solution into Hackerrank or Leetcode it may produces
TLEs because it's relatively easy to construct special cases that will kill it.
To improve, you can either check up front if there is a solution without collecting
the sets, or better, mark the required subsums and element count that are needed
for a solution and later on only collect those subsums.
*/
// reduced problem, only positive nums and positive target
vector<vector<int>> combinationSumPositive(const unordered_set<int>& nums, int target, int k) {
unordered_map<int, vector<vector<int>>> sums;
sums[0] = vector<vector<int>>(1, vector<int>());
for (int a : nums) {
decltype(sums) newSums;
for (auto p : sums) {
if (p.first + a <= target) {
for (vector<int>& s : p.second) {
if (s.size() < k) {
vector<int> newSet = s;
newSet.push_back(a);
newSums[p.first + a].push_back(newSet);
}
}
}
}
// merge new sums into sums
for (auto pn : newSums) {
auto ps = sums.find(pn.first);
if (ps == sums.end()) {
sums.emplace(pn.first, move(pn.second));
} else {
for (vector<int>& ns : pn.second)
ps->second.emplace_back(move(ns));
}
}
}
vector<vector<int>> result;
for (vector<int>& r : sums[target]) {
if (r.size() == k) {
result.push_back(move(r));
}
}
return result;
}
vector<vector<int>> combinationSum(vector<int>& nums, int target, int k) {
int minA = min(0, target); // case of negative target
for (int a : nums) minA = min(a, minA);
if (minA < 0) {
for (int& a : nums) a -= minA; // TODO: overflow check
target -= k * minA; // TODO: overflow check
}
vector<vector<int>> result = combinationSumPositive(unordered_set<int>(nums.begin(), nums.end()), target, k);
for (vector<int>& r : result) {
for (int& v : r) {
v += minA;
}
}
return result;
}
ostream& operator << (ostream& o, vector<vector<int>> lofl) {
cout << "[" << endl;
for (auto& l : lofl) {
o << " [";
bool first = true;
for (int v : l) {
if (first) o << v;
else o << ", " << v;
first = false;
}
o << " ]" << endl;
}
cout << "]" << endl;
return o;
}
int main()
{
cout << combinationSum(vector<int>({1,6,12,2,-5,8}), 9, 3);
/* output
[
[1, 6, 2]
[12, 2, -5]
[6, -5, 8]
]
*/
}
scan the logs to figure out how many robots there are. I assume
the question is how to narrow down the time frame of logs scanned
(e.g. if they are on disc).
If the m/n frequency is without jitter, scan seiling(m/n) records is
sufficient. that's unrealistic due to scheduling, network latency etc.
I assume a safety factor of two would account for various
sources of errors and would scan too many entries by a factor
of two.
An other approach could be to scan the logfile until each robot-id
has been seen at least twice. Again this will fail eventually in extreme
cases with only two robots.
It's basically a probability experiment to maximize probability every
bot wrote a log in the time frame we are looking at (possion process)
something like this:
private final static int SAFETY_FACTOR = 2;
public HashSet<String> getBots(Log[] logs, int m, int n){
HashSet<String> bots = new HashSet<>();
if(logs == null || logs.length == 0) {
return bots;
}
long minTime = (long)logs[0].time -
((((long)n + (long)(m - 1)) / m) * (long)SAFETY_FACTOR);
for(int i = logs.length - 1; i >= 0 && logs[i].time >= minTime; i--) {
bots.add(logs[i].id);
}
return bots;
}
@Fernando: I agree. Concluded:
1) The best conceivable run-time is O(n) for the initial problem.(an informal "prove" is that you need to look at all elements because if you do not look at one element and if this one is the repeated element, there is no way to tell which element (value) repeats.
2) You can relax it in several ways:
a) define that adjacent elements differ by at most 1 (see my initial post), you can find the number of repeated elements then in O(1) and the element in O(lg(n))
b) you know the position of one element and thus need to find the end and start of the sequence as you pointed out
BUT, O(2*log(n)) is O(log(n) if "*" is a multiplication) because constant factors can be eliminated (if it was O(2^log(n)) where "^" being power then this is n because 2^log(n) = n, if log means the logarithm with base 2)
I don't agree with your recursion that's why the application of the master theorem turned out to be O(n): The recursion is T(n) = T(n/2). You do it twice for n, but not on every "recursion level" that's why you can't put the 2 in front of the T. They way you wrote it would be, in your binary search you had to either use recursion or introduce a stack so you can follow both path, the left and the right side which is clearly not the case, a T(n) = 2*T(n/2) recursion would look like:
def fun(s, e):
if s == e: return 1
m = (s + e + 1) // 2
return fun(s, m) + fun(m, e) # or max(fun(s, m), fun(m, e))
fun(0, n-1)
but you do clearly:
def fun(s, e):
if s == e: return 1
m = (s + e + 1) // 2
if (condition): fun(s, m)
else fun(m, e)
fun(0, n-1)
fun(0, n-1)
an other way to thin about is that doing a single binary search leads to O(lg(n)) why should two binary searches done after each other lead to O(n).
Even your prove might be wrong, I think it's important to remember interviewer and interviewee are humans with their own background in terms of professional experience, education and personal, cultural background. So whatever is said, is said from an implicit context, which is a bias. It can be, the person really thought he helped you, even if it wasn't the case for you since you didn't have his context...
@NoOne: Maybe I'm bit slow today, but let's take this example with only one repetition.
array = [5,9,13,15,20,20]
start = 0, end = 5, middle = 2 (value 13)
how to know it's in the interval (middle..end] when looking at 13 and maybe 9 and 15?
the array could be 5,5,13,15,17,20 and it would look the same at the first step of binary search, but in order to get the O(lg(n)) behavior one has to decide for interval [start..middle] or (middle..end]
...
if you could post the python/java/c code, that finds the single repeated element in a sorted array in less than O(N), that would be awesome ;-) for example with the array above.
actually, if it is sorted and if max-diference of two adjacent elements is 1, then the length of the repeated sequence is n-1-(array[n-1]-array[0]). If you want to know the elements value, you can binary search i:
#include <vector>
#include <iostream>
#include <utility>
using namespace std;
// vector a is sorted, max-diference of two adjacent elements is 1
pair<int,int> lengthOfRepeatedSeq(const vector<int>& a) {
if (a.size() = 0) return {0, 0};
int o = a[0];
int s = 0;
int e = a.size() - 1;
while (s < e) {
int m = (s + e) / 2;
if (a[m] >= m + o) s = m + 1; // if a[m] = m + o, there is no repeating character in [s..m]
else e = m; // if a[m] < m, there is a repeating character in [s..m]
}
return{ a[s], a.size() - (a[a.size() - 1] - o) };
}
ostream& operator << (ostream& o, pair<int, int> p) {
o << p.first << ", " << p.second;
return o;
}
int main()
{
cout << lengthOfRepeatedSeq({ 1,2,3,4,4,4,5,6 }) << endl;
cout << lengthOfRepeatedSeq({ 4,4,4,4,4 }) << endl;
cout << lengthOfRepeatedSeq({ 2 }) << endl; // not really a valid input
cout << lengthOfRepeatedSeq({ 6,7,8,9,10,10,11 }) << endl;
cout << lengthOfRepeatedSeq({ 6,7,8,9,10,10,10 }) << endl;
cout << lengthOfRepeatedSeq({ 5,5,6,7 }) << endl;
/* output:
4, 3
4, 5
2, 1
10, 2
10, 3
5, 2
*/
}
I would guess the question sais, you are given a set of pointers from multiple doubly linked lists and you need to determine how many doubly linked lists the pointers come from:
assuming that the first and last nodes are special in the list in a way their next and previous pointers are null, I can simply count the nodes that only have one incoming edge, which means I have the number of start and end nodes. Divide that by two should lead to the result.
int countNoOfLists(vector<void*> list) {
unordered_set<void*> set;
for (void* ptr : list) {
if (set.find(ptr) == set.end()) {
set.insert(ptr);
} else {
set.erase(ptr);
}
}
return set.size() / 2;
}
there are other interpretations of the question, but this one is particularly convenient :-)
- Chris May 28, 2017create the adjacency matrix from the given pairs, build all possible pairs (unidirectional) and add to result if no edge is present. In Java
public class RoadNetwork
{
public static int[][] RoadBuilder(int nCities, int[][] builtRoads) {
List<int[]> result = new ArrayList<>();
boolean[][] adjMatrix = new boolean[nCities][nCities];
for(int[] pair : builtRoads) {
adjMatrix[pair[0]][pair[1]] = true;
adjMatrix[pair[1]][pair[0]] = true;
}
for(int u = 0; u < nCities; u++) {
for(int v = u + 1; v < nCities; v++) {
if(!adjMatrix[u][v]) {
result.add(new int[]{u, v});
}
}
}
return result.toArray(new int[result.size()][2]);
}
public static void main(String[] args) {
int[][] test1 = new int[][]{{0, 1}, {1, 2}, {3, 2}};
System.out.println(
Arrays.deepToString(
RoadBuilder(4, test1))); // expected result should be {{0,2}, {0, 3}, {1, 3}}
}
}
my approach for a linear time (O(n)) solution
/*
1. brute force would be O(N^2) time and O(1) space (space for
the result not calculated)
2. there is a better approach in O(N) time and O(N) space,
comes from the following observation:
I start at an arbitrary point (e.g. index 0) with 0 gas:
i=0, totGas[0] = 0
to reach i+1 I get gas at i and use gas to go to i+1:
totGas[i+1] = totGas[i] + gas[i] - cost[i]:
note: I started at i with totGas[i] initial fuel
repeat this for i up to n-1, so, totGas is an array of n+1 length
if starting at i=0, if there is any value below totGas[0] on the right
side of the totGas-array, it means, at some point I will run out of gas.
This is, I can find out if I can reach station n-1 by looking at the
minimum value of totGas in [i+1..n].
But what happens with the stations [0..i] if i > 0?
pretty much the same, but i need to remove the start fuel from
totGas[i] and add totGas[n] to the min-Value in this range, since
initial calculation was done starting from 0 and because we had potentially
some fuel left when starting over at i=0...
I can do this by finding the min-values from the left and right
and pick the appropriate. If I do so, I need to offset the right-hand value
by totGas[i] as well since they were calculated forward assuming it had
totGas[i] gas in the tank initially.
complete in Java8, cleanup the indexes a bit
*/
public class GasStations {
static public List<Integer> canCompleteCircuit(int[] gas, int[] cost) {
assert(gas != null && cost != null && gas.length == cost.length);
int n = gas.length;
List<Integer> result = new ArrayList<>();
// totGas[i] is the amount of gas in tank at i when started with 0 at 0
// at totGas[n] is to get back to 0
int[] totGas = new int[n+1];
// minGas[i] is the minimum gas in tank at range [0..i-1] [i+1..n-1]
int[] minGas = new int[n+1];
for(int i = 0; i < n; i++) {
totGas[i+1] = totGas[i] + gas[i] - cost[i];
}
// get the minimum fuel found going towards the n-th station
for(int i = n-1, minG = Integer.MAX_VALUE; i >= 0; i--) {
minG = Math.min(minG, totGas[i+1]);
minGas[i] = minG - totGas[i];
}
// get the minimum fuel found coming from the 0-th station
for(int i = 1, minG = totGas[0] + totGas[n]; i < n; i++) {
minG = Math.min(minG, totGas[i] + totGas[n]);
minGas[i] = Math.min(minG - totGas[i], minGas[i]);
}
// see from which index i can start without running out of gas
for(int i = 0; i < n; i++) {
if(minGas[i] >= 0) result.add(i);
}
return result;
}
public static void main(String[] args) {
System.out.println(canCompleteCircuit(new int[]{10,2,3,5}, new int[]{5,6,2,6}));
System.out.println(canCompleteCircuit(new int[]{4,2,7,5}, new int[]{5,2,8,3}));
}
}
1) let's assume it's all integers so we can ignore negative exponents (e.g. 2^-1 = 1/2...) and there are no roots involved either
2) actually a negative exponent would be easy to do, just return a double and build the reciprocal 1/pow(base, -exp)
then it's about corner cases and overflow, try to be clean here
private static int power(int base, int exp) throws Exception{
if(exp < 0) throw new IllegalArgumentException("exponent must be >= 0"); // integer result, no reciprocal
if(exp == 0) return 1; // base^0 = 0 for all values of base
if(exp == 1) return base; // base^1 = base for all values of base
if(base == Integer.MIN_VALUE) throw new Exception("overflow"); // negative Min-Value has no positive counter part
if(base < 0) return (exp % 2 == 0) ? power(-base, exp) : -power(-base, exp); // negative base
if(base == 1) return 1; // no matter of the exponent, negative case already captured
int e = 1, r = 1;
while(true) {
if ((exp & e) > 0) r = savePosMul(r, base);
e <<= 1; // base overflows before the 1 is shifted out, except when base = 1, which is captured above
if(exp > e) base = savePosMul(base, base);
else break;
}
return r;
}
private static int savePosMul(int a, int b) throws Exception {
assert (a >= 0 && b >= 0);
if(Integer.MAX_VALUE / a < b) throw new Exception("overflow");
return a * b;
}
@all: time complexity won't change. It's O(n+m) because you need to look at each element at least once. That is, for 2*n data it takes double time, you wont achieve anything better unless you are magician ;-)
What can be improved is the constant factor. Fernando actually pointed that out. But if you are running on a single machine (threads, not processes) your bottleneck is disc I/O or memory access.
So, what we learn? distribute, shard your big data sets and use map/reduce. But Big-O is not changing, it's still O(n) by the way it's as well o(n) and Teta(n) since it's a quite tight bound
that's a tricky one, it looks like one of the cluster algorithms, such as k-mean should be applied, but if your study didn't cover that, I would assume you are lost in some way.
1. Start by picking a first arbitrary point from the list of points not assigned to a cluster.
2. Then search within R-distance of that point at least one second point. If found, estimate a sphere center by averaging all those points coordinates. Then around this center, add all points within R distance of the center. If not found, extend the search to 2R. If not found, put that single point into a single sphere and do not further consider that point. If found, average the two points, try to find more points that potentially go into this sphere...
3. Repeat until no points are left which gives an initial guess of spheres.
(initial center selection could be done by observing point density and guess centers from a group of dense points, e.g. by separating the space into R/2 cubes in order to get a space-based index etc.
or another approach would be to first separate the space into this cubes and start searching from outside in ...)
4. At this stage a number of spheres will probably overlap and points can be assigned to multiple spheres.
5. use the points in conflict and assign it to the sphere with more points in it
6. clean up spheres that are empty, recompute centers, repeat 4 until no changes happen *
* it's not clear it will converge, so maybe a upper limit of passes and/or error limit must be given
Think about problem as an array of integer with 1,2 or 3 in it that needs
to be sorted in-place, not stable.
1) Use a standard, in-place compare-sort technique that will run
with O(n*lg(n)) time and O1(1) space complexity.
2) implement something like radix sort in place with O(n) time and O(1)
space complexity.
For fun 2) in java
public class SortThreeRadixInPlace {
public static void sortSpecial(String[] array) {
if(array == null || array.length <= 1) return;
for(int p2s = 0, p3s = 0, i = 0; i < array.length; i++) {
// [0, p2s) marks the range for prio. 1.
// [p2s, p3s) marks the range for prio. 2.
// [p3s, i) marks the range for prio 3.
int prio = getPrio(array[i]); // here one would call the function to get the prio
if(prio == 1) {
swap(array, i, p2s);
swap(array, i, p3s);
p2s++;
p3s++;
} else if(prio == 2) {
swap(array, i, p3s);
p3s++;
}
}
}
and the boilerplate to compile and drive
static public void main(String[] args) {
String[] array = new String[]{"101", "302", "203", "104", "305", "106", "207", "208", "109", "310", "211"};
sortSpecial(array);
System.out.println(Arrays.toString(array));
// output: [101, 104, 106, 109, 207, 208, 203, 211, 305, 310, 302]
}
static private int getPrio(String code) {
// e.g. first character contains the prio 1,2,3
int prio = code.charAt(0) - '0';
if(prio >= 1 && prio <= 3) return prio;
return 3;
}
static private <T> void swap(T[] array, int i, int j) {
T tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
edited: changed recursion as Fernandoz pointed out
Analysis:
--
the cost of a single column depends on which color is on which row.
Which color can be painted on which row depends on the previous
column. No greedy choice is possible if optimal solution is wanted.
Solution (assuming no negative cost)
--
a) brute force, trying all potential combinations which are
roughly 3!^n = 6^n
b) look at all potential combinations per columns as adjacent nodes
from all the reachable combinations of the previous column. Thus build
a graph and find the shortest path. This can be done using Dijkstra's
shortest path algorithm. That's a bit a heavy tool for this problem.
There is a better alternative because in the DAC there are only edges from
Nodes in Column i to Column i + 1.
Every column can have 6 potential house-color combinations RGB, RBG, BGR, ...)
potentially each of those combinations can be reached by various paths, but
we are only interested in the cheapest path to a given combination. So, we
could just calculate the cost to go from each combination in column i to
each allowed combination in column i+1 and if multiple ways are allowed, we
pick the cheapest.
as recursion:
DP(col, comb) = Min(DP(col-1, prev_comb) + cost(comb))
for each prev_comb that leads to comb,
cost(comb) is the cost for the combination comb
if col = 0: DP(col, comb) = 0
The minimal cost then is: Min(DP(N, last_comb)) for each of the 6 color combinations
complete solution (iterative DP solution), time complexity O(n*8*8*3*6) = O(n), space: O(n)
public class PaintHouses {
static final String[] COLOR_COMBINATION_STR = new String[]{"RGB", "RBG", "GBR", "GRB", "BGR", "BRG" };
static public void printMinPaint(int n) {
int[][] cost = new int[n][COLOR_COMBINATION_STR.length]; // can optimize 1st dimension to 2
int[][] backTrack = new int[n][COLOR_COMBINATION_STR.length]; // previous combination
// initialize
for (int j = 0; j < COLOR_COMBINATION_STR.length; j++) {
cost[0][j] = getCost(0, j);
}
for(int i = 1; i < n; i++) {
for (int j = 0; j < COLOR_COMBINATION_STR.length; j++) {
cost[i][j] = Integer.MAX_VALUE;
}
}
// calculate cheapest cost
int min = 0; // keeps the cheapest last color combination
for(int i = 1; i < n; i++) {
int minCost = Integer.MAX_VALUE;
for(int l = 0; l < COLOR_COMBINATION_STR.length; l++) { // O(n*9)
for(int r = 0; r < COLOR_COMBINATION_STR.length; r++) { // O(n*9*9)
if(cost[i-1][l] < Integer.MAX_VALUE && isValidAdjacent(l, r)) {
int rc = cost[i-1][l] + getCost(i, r);
if(cost[i][r] > rc) {
cost[i][r] = rc;
backTrack[i][r] = l;
if(rc < minCost) {
min = r;
minCost = rc;
}
}
}
}
}
}
// backtrack to print (... print in reverse order, that's the same cost result)
for(int i = n-1; i >= 0; i--) {
System.out.println("Column: " + (n - i) + " Colors: " + COLOR_COMBINATION_STR[min]);
min = backTrack[i][min];
}
System.out.println("---");
}
// some arbitrary cost function to produce a "random" cost per column for
// a certain combination of house colors for the three rows
private static int getCost(int column, int rowColorCombination) {
return ((rowColorCombination * 17) * (column * 31)) % 11;
}
// can next column have this colors per row
// e.g. if left=0 and right=1:
// left right
// R R
// G B
// B G
// result false, because R and R in the first row
static private boolean isValidAdjacent(int left, int right) {
for(int i = 0; i < 3; i++)
if(COLOR_COMBINATION_STR[left].charAt(i) == COLOR_COMBINATION_STR[right].charAt(i))
return false;
return true;
}
static public void main(String[] args) {
printMinPaint(2);
printMinPaint(6);
printMinPaint(12);
}
}
@Michael.Karn.Ivanov
I'm not sure i understand what your desired property is: 6,5,7,9 gives me 5,6,7,9 with your code, which I'm not sure you would agree on being correct. If you did mean to create a[0]<a[1]>a[2]<a[3] and assume all distinct values, you might try this one:
static public int[] rearrange(int[] input) {
for(int i = 1; i < input.length - 1; i+=2) {
if(input[i] < input[i - 1]) {
swap(input, i, i - 1);
}
if(input[i] < input[i + 1]) {
swap(input, i, i+1);
}
}
return input;
}
that works because of any 3 distinct values at a[i-1],a[i],[a+1] it creates a[i-1]<a[i]>a[i+1] for odd i
then, if a[i+2] was smaller then a[i+1], a[i+1] would decrease and therefore still holding a[i]>a[i+1]. If a[i+2] is bigger than a[i+1] nothing changes and the chain is extended etc. etc.
This leaves room for interpretation, I assumed that every value at an odd
index should be greater than the value at an adjacent even index, e.g.
a[0] < a[1] > a[2] < a[3] > a[4] < a[5] > ...
e.g.
1,2,3,4,5 --> 1 < 4 > 2 < 5 > 3
1,1,1,3,3 --> 1 < 3 > 1 < 3 > 1
0,1,1,3,3 --> 0 < 3 > 1 < 3 > 1
0,1,2,2,3 --> 2 < 3 > 1 < 2 > 0
0,2,2,2,3 --> 2 < 3 > 2 < .... no solution
Idea:
--
If the array was sorted, pick greater and smaller values as needed. Best is,
if all elements are max distance away from their origin because this allows
for longest sequences of equal values:
1,2,3,4,5,6,7,8 --> 1 < 6 > 2 < 7 > 3 < 8 > 4 < 9 > 5
1,1,1,1,2,2,2,2 --> 1 < 2 > 1 < 2 > 1 < 2 > 1 < 2 > 1
we can rearrange this in a simple for loop in O(n)
==> sorting requires O(lg(n)), not quite there yet.
Optimize for O(n) average time complexity (O(n^2) worst case time complexity)
--
Since we do not really care about sorting but only need to separate bigger
and smaller values, it's okay to partition the array in such a way around the
median. This can be done in O(n) average time in various ways (I used the
quick-sort partition method).
It needs to be modified in a way that all elements that are equal to the
median are not seperated by other elements. The standard partition property
left <= median < right won't work here because we could create something
like 1,5,2,5,3,5,6,7,8 where it should be 1,2,3,5,5,5,6,7,8 in order to hold
the wanted properties after rearranging
(1 < 5 => 5 < 6 > 3 < 7 > 5 < 8 > 3 vs. 1 < 5 > 2 < 6 > 3 < 7 > 5 < 8 > 5)
maybe somebody finds a solution to re-arrange in place without additional
space...
public class OddGreaterEven {
public static int[] rearrange(int[] input) {
assert (input != null && input.length > 0);
// rearrange around median
int n = input.length;
int s = 0, e = n;
int medianIdx = n / 2;
while(true) {
// picks a pivot in [s, e) and rearranges around that pivot
// such that there exist three sub-arrays:
// [s..l) where all values are < pivot
// [l..m) where all values are = pivot
// [m..e) where all values are > pivot
// returns last pivot index in the range [s, e)
swap(input, (s + e) / 2, s); // move the pivot to the start
int l = s; // [s, l) < pivot
int m = l + 1; // [l, m) = pivot
int u = m; // [m, u) > pivot
while(u < e) {
if(input[u] > input[l]) {
u++; // the new element is already in the > pivot part
} else if(input[u] == input[l]) {
swap(input, m++, u++); // add the new element ot the = pivot part
} else {
swap(input, l++, u); // add the new element to the < pivot part
swap(input, m++, u++); // add element before to the = pivot part
}
}
if(l > medianIdx) e = l;
else if (m < medianIdx) s = m;
else break;
}
// rearrange
int[] result = input.clone();
for(int i = 1; i < n; i += 2) result[i] = input[(n + 1) / 2 + i / 2];
for(int i = 2; i < n; i += 2) result[i] = input[i / 2];
// TODO: check if the solution is valid or not,
return result;
}
// helper swap function
private static void swap(int[] input, int i, int j) {
int t = input[i];
input[i] = input[j];
input[j] = t;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(rearrange(new int[]{2,3,0,1})));
System.out.println(Arrays.toString(rearrange(new int[]{5,2,3,4,1})));
System.out.println(Arrays.toString(rearrange(new int[]{1,2,3,4,5})));
System.out.println(Arrays.toString(rearrange(new int[]{1,1,1,3,3})));
System.out.println(Arrays.toString(rearrange(new int[]{1,0,1,3,3})));
System.out.println(Arrays.toString(rearrange(new int[]{2,2,0,1,3})));
System.out.println(Arrays.toString(rearrange(new int[]{5,1,5,8,7,5,6,2,3})));
System.out.println(Arrays.toString(rearrange(new int[]{7,3,8,2,5,6,1,5,5})));
System.out.println(Arrays.toString(rearrange(new int[]{0,2,2,2,3}))); // should produce a wrong result, no solution
/* output
[0, 2, 1, 3]
[2, 4, 1, 5, 3]
[2, 4, 1, 5, 3]
[1, 3, 1, 3, 1]
[0, 3, 1, 3, 1]
[0, 2, 1, 3, 2]
[1, 5, 2, 6, 3, 7, 5, 8, 5]
[3, 5, 2, 8, 1, 7, 5, 6, 5]
[0, 2, 2, 3, 2]
*/
}
}
@majia: I saw you edited the question to include it's not a BST. In this case I assume, you mean, the Binary tree should keep it's complete property after insert. Interesting ;-)
I think one has to do a level order traversal and look for one of these:
- a Node that has either left or right but not both set. If that is met, add the new Node to id. done.
- if no such exists, keep the last node that had no children, that is the last node of the last level of the perfect tree
I think that should do it
TreeNode insert(TreeNode root, int val) {
Queue<TreeNode> queue = new LinkedList<>();
TreeNode candidate = null;
queue.add(root);
while(!queue.isEmpty()) {
TreeNode node = queue.pop();
if(node.left != null && node.right == null) (return node.right = new TreeNode(val));
if(node.left == null && node.right != null) (return node.left = new TreeNode(val));
if(node.left == null && node.right == null) candidate = node;
queue.add(node.left);
queue.add(node.right);
}
return (candidate.left = new TreeNode(val));
}
Q1. use a linked list to keep the order and a hashtable for lookup. place the list-element as value into the hash table, so O(1) from key to list-element to value (see code below)
Q2. Frequency is number of times accessed per time frame. Most simple way would be to use the time the service is running as time frame, so it's just the number of times accessed. It might be tempting to use a priority queue here, but it's not efficient. You can just move the accessed item in the queue up and down according to the Number of times it was accessed - there is a worst case scenario making this algorithm O(cachsize) when a cached item is accessed that I would fix using a skiplist or something the like). Priority queue removes worst case, but average case will be worse, further probably the priority queue must be re-implemented to allow priority change)
Q3. If the cache is occupied by items that were used in high frequency in the past, it might prevent new items from ever getting into the cache. That's tricky but important. Maybe we can give a new item a frequency offset, so it has chances to compete with items that have been used often in the past. This offset will increase over time and eventually overflow. An alternative could be to have two cache generations a current and a next and put new items into the next generation, and items from the current generation move to the next generation after being hit again. after a while, when freeing space we can consequently free space from the current generation... if it's empty, we can start over again, just like life ;-)
class LRUCache {
private:
std::list<std::pair<int, int>> list_;
std::unordered_map<int, decltype(list_)::iterator> map_;
int capacity_;
public:
LRUCache(int capacity) : capacity_(capacity) { }
int get(int key) { return getValueInFrontIfExists(key); }
void put(int key,int value) {
if (getValueInFrontIfExists(key) != -1) { // key existed, patch value
list_.front().second = value;
} else { // key does not exist, add to list and map
list_.push_front(std::pair<int,int>(key,value));
map_[key] = list_.begin();
if (list_.size() > capacity_) { // capacity exceeded, remove least used
map_.erase(list_.back().first); // patch map first
list_.pop_back(); // remove least used element
}
}
}
private:
// gets the value and moves value to front of list if exists otherwise returns -1
int getValueInFrontIfExists(int key) {
auto it = map_.find(key);
if (it != map_.end()) {
int value = it->second->second; // get the value
list_.splice(list_.begin(), list_, it->second);
return value;
}
return -1;
}
};
...if it's not a BST you can put it everywhere, just grab a node and insert it.
Therefore I assume the question aimed at inserting a node into a complete binary search tree (which is ordered). Complete means all levels except the last are full, how ever, it didn't say, the result must be a complete BST again.
So I assume, you need to find the node to insert and insert it. Finding the node to insert can be done using binary search which is only guaranteed to be efficient if the tree is balanced, a complete tree is balanced.
// assumed BST property left <= current <= right
TreeNode insert(TreeNode root, int val) {
if(val <= root.value) {
if(root.left == null) return (root.left = new TreeNode(val));
return insert(root.left, val);
}
if(root.right == null) return (root.right = new TreeNode(val));
return insert(root.right, val);
}
/*
I assume the question is, find the first moment in time when all balls
have fallen from the table (like max time).
--
First this is more of a physics than a C/S question, because we have
to understand what happens at collision very well. If the balls were
of volume lim->0 and it's an elastic collision as described and if we
couldn't distinguish balls we would just observe the balls moving "through"
each other. But if the balls get bigger, they would travel "through"
each other in "no time" or "bounce of" each other.
From the point of view of the ball, every time you hit a ball that
runs in opposite direction you travel "light speed" for the distance
of a balls diameter.
So, it's about choosing units we can easily calculate here. I would
suggest to use:
- ball diameter: d
- speed: 1d / time unit
- position: in d: 0, d, 2d, etc...
illustration (zero: zero volume case; even,odd: volume case with even
and odd distance)
case | zero | even | odd
---------------------------------
position| 12345 | 12345 | 12345
---------------------------------
| 1 |_.___._|_O___O_|_O__O__
t 1.5 | | |
i 2 |__._.__|__O_O__|__OO___
m 2.5 | | -*- |
e 3 |___.___|__O_O__|_O__O__
| 3.5 | | |
v 4 |__._.__|_O___O_|O____O_
having this definitions in place the table may look like this
(< left moving, >right moving)
12 15 26 30 34
| | | | |
____<__<__>__>___<___<__>___>___>_____
| | | | | |
5 9 11 19 23 40
table: 5..40
left moving: 9, 11, 19, 23
right moving: 12, 15, 26, 30, 34
t = time for a ball to reach table edge = distance to edge - #balls encountered
which ball takes the longest? either the most right left-running,
or the most left right-running (the ball 23 or 12 in the example)
O(n + m) solution (n number of left running, m number of right running)
1. traverse the two arrays to find the most left right-running and the most
right left-running
2. traverse the arrays again to find how many balls those will encounter
3. calculate, build the max, done
*/
public class TableOfBalls {
public static int lastBallFalling(int tableStart, int tableEnd,
List<Integer> leftRunningBallPos,
List<Integer> rightRunningBallPos) {
// TODO, verify corner cases for null, empty arrays, start > end,
// balls not in range etc.
int rightRunning = tableEnd - Collections.min(rightRunningBallPos) + 1;
int leftRunning = Collections.max(leftRunningBallPos) - tableStart + 1;
for(int rr : leftRunningBallPos) {
if(rr < leftRunning) leftRunning--;
}
for(int ll : rightRunningBallPos) {
if(ll > rightRunning) rightRunning--;
}
return Math.max(leftRunning, rightRunning);
}
public static void main(String[] args) {
System.out.println(lastBallFalling(5, 40,
Arrays.asList(9, 11, 19, 23),
Arrays.asList(12, 15, 26, 30, 34)));
// output 27: = max(40 - 12 + 1 - 2, 23 - 5 - 2)
}
}
@Venkat: no it isn't linear it's O(n*m) as it's implemented not efficient:
first string: "1111111111111"
pattern: "113"
the way it is imlemented
tries at index 0: 1 match, 1 match, 1,3 no match,
tries at index 1: 1 match, 1,match, 1,3 no match
etc.
roughly 3*n iterations instead of 13, if it was linear, the pattern couldn't influence that, so let's try pattern "13" ... roughly 2*n iterations
it's definitely not linear as it seldom is with nested for-loops ;-)
@IB, no, it will repeat already printed duplicates that's why you use a set and not a list ...
however, the approach is cool!!
int main()
{
std::vector<int> inp = {4, 2, 0, 5, 2, 0, 1} ;
//std::vector<int> inp = { 1, 2, 3, 0, 0, 1, 3, 6, 6 };
for (int i = 0; i < inp.size(); i++) {
if (inp[i] == i || inp[i] == -1) continue;
if (inp[inp[i]] == inp[i]) {
std::cout << inp[i] << " ";
inp[i] = -1;
} else {
std::swap(inp[inp[i]], inp[i]);
i--;
}
}
return 0;
}
with two passes:
1. iterate over all elements so that a[a[i]%n] = a[a[i]%n]%n + n
2. iterate a second time and if you face a[i] > n print i
note, n <= MAX_INT / 2, it's O(1) space and O(n) time, but there are two passes
it sais to do it with one pass:
1. iterate over all elements so that v=a[i], j=v%n
if a[j] < n: a[j] = a[j] + n
if n =< a[j] < 2n: a[j] = a[j] + n, print j
now n must be <= MAX_INT / 3 otherwise it won't work
Actually this O(1) space is a bit of a lie, while it is true in terms of bytes,
it uses unused bits to store occurrences.
in java:
public class RepeatingNumbers {
public List<Integer> findRepeat(int[] input) {
ArrayList<Integer> res = new ArrayList<>();
int n = input.length;
if(n > Integer.MAX_VALUE / 3) throw new IllegalArgumentException("input.length");
for(int i =0; i < input.length; i++) {
int j = input[i] % n;
if(input[j] < n) {
input[j] = input[j] + n;
} else if(input[j] >= n && input[j] < 2*n) {
input[j] = input[j] + n;
res.add(j);
}
}
return res;
}
public static void main(String[] args) {
System.out.println(new RepeatingNumbers().findRepeat(new int[]{4,2,0,5,2,0,1}));
System.out.println(new RepeatingNumbers().findRepeat(new int[]{1,2,3,0,0,1,3,6,6,6}));
/* Output
[2, 0]
[0, 1, 3, 6]
*/
}
}
the pointer passed to the template function is a pointer to Type "base" and by applying pointer arithmetic, you just add sizeof(base) as if there was only one member "int a". This c-style pointer arithmetic doesn't work in the second class where polymorphism comes into play. Therefore it would be better to pass an array of base pointers base** obj and invoke obj[i]->getA() ... or create a template function which fails again, if you pass it a true polymorphic array, since the trick about polymorphism is, it's not known at runtime... so template functions will not really solve it...
- Chris April 30, 2017edited: was a bit fast on the while condition
There are quite a few random generator questions asked by Google recently ;-)
1) I assume with a uniform distribution (every value has equal possibility to happen)
2) All adjacent digits are different, number is even and with 4-digit, is between 1013 and 9898, so roughly 4'000 values (assuming a leading 0 is not counted)
So how about this nonderteministic approach, that probably isn't totally
uniform (depends on Random.nextInt implmenetation):
public static int generate() {
Random rnd = new Random();
int value;
do {
value = 1013 + rnd.nextInt(9898 - 1013);
} while ((value & 1) == 1 ||
value % 10 == value % 100 / 10 ||
value % 100 / 10 == value % 1000 / 100 ||
value % 1000 / 100 == value % 10000 / 1000);
return value;
}
/*
Solution
--
I assume, the question draws towards doing many queries and few or no changes
on the matrix. You can prepare an array that will contain the # of ones in
the square (0,0,x,y). So, you need O(n*m) space and O(n*m) runtime to prepare
and O(1) to query.
Best is you draw it on a paper and then it's just like adding and subtracting
the area of squares:
[A][T][T][-][-]
[L][Q][Q][-][-]
[L][Q][Q][-][-]
[-][-][-][-][-]
let's assume we want to know how many 1's in Q: {x:1,y:1,w:2,h:2}
So, we take the value from {0,0,3,3} stored in mPreCalculated[3][3]
and subtract A,T,T and A,L,L from it and finally add A again.
in Java:
*/
public class MatrixCountOneFast {
private int[][] mSumMatrix;
private int mM;
private int mN;
public MatrixCountOneFast(int[][] input) {
mN = input.length;
mM = mN > 0 ? input[mN-1].length : 0;
mSumMatrix = input.clone();
for(int j = 0; j < mN; j++) {
int lineSum = 0;
for(int i = 0; i < mM; i++) {
lineSum += (input[j][i] > 0 ? 1 : 0);
mSumMatrix[j][i] = lineSum + ( j > 0 ? mSumMatrix[j-1][i] : 0);
}
}
}
public int queryNoOfOne(int x, int y, int height, int width) {
int x2 = x + width - 1;
int y2 = y + height - 1;
assert(x >= 0 && y >= 0 && x2 < mM && y2 < mN);
if(height <= 0 || width <= 0) return 0;
int sum = mSumMatrix[y2][x2];
if(y > 0) sum -= mSumMatrix[y - 1][x2];
if(x > 0) sum -= mSumMatrix[y2][x - 1];
if(x > 0 && y > 0) sum += mSumMatrix[y - 1][x - 1];
return sum;
}
public static void main(String[] args) {
MatrixCountOneFast m = new MatrixCountOneFast(new int[][]
{
{1,1,0,0,1,0,1},
{1,0,1,0,0,1,1},
{0,1,1,1,0,1,0},
{0,1,0,1,0,0,1}
});
System.out.println(m.queryNoOfOne(0,0,1,1) == 1);
System.out.println(m.queryNoOfOne(0,0,2,2) == 3);
System.out.println(m.queryNoOfOne(0,0,2,2) == 3);
System.out.println(m.queryNoOfOne(1,1,1,6) == 3);
System.out.println(m.queryNoOfOne(2,2,2,2) == 3);
}
}
Note that there is optimization for the O(N^2) pre calculation using a 2D segment tree, where changes in the matrix consume O(lg(N)lg(N)) and the same is true for querying. Then there is the addition to do something with lacy calculation by marking parts of the tree dirty and only calculate it when needed... this problem is pretty much open ended
- Chris April 28, 2017/*
Assumptions:
--
- for simplicity values in array must be > 0
- the sum must be > 0
- it said "sets of values" are looked for, for simplicity I assume,
if the input already contains a set, otherwise an additional
step would be required to create a set from the array.
- "find sets" I interpret as find all sets in the powerset of the
input whose elements sum up to sum
Brute force solution:
--
brute force, try all combinations which are 2^input-size
Improvement (inspired by the iterative solution of knap-sack):
--
This is complicated to explain. Therefore I simplify the problem
for explanation to only say "yes, sum can be reached" or "no...".
In this scenario what one can do is, keep a set of sums one can
reach. Now for each input value, we add it to all already
existing values in the set and put this values back into the
set. If we reach the sum, we are done. (...). Of course this starts
with the initial set that contains a single 0.
Since we need to tell which elements were in this sum, the set of
current reachable sums is not enough, we need to store the elements
as well, and since a given sum (or part sum) can be reached on
multiple ways and all solutions are wanted this is a bit messy.
I did it by creating an array of Hashtables. The array is basically
of size # of input-values + 1 (+1: start case 0). The Hashtable
contains as keys all the reachable sums and as values two flags:
- did I reach it by including the current value of index i
- did I reach it by not including the current value of index i
- both (therefore two flags)
This array of Hashtables is created iterative, easily, the ugly
part is backtracking to output all the combinations.
Note that the assumption about positive sum and positive element
values can be removed now, how ever, it's somewhat more comfortable
to keep it to define runtime and space:
time complexity: O(sum*n), where sum is the integer value of the desired sum
and n is the number of elements.
space complexity: O(sum*n)
*/
public class SetOfNumbers {
private static final int USE_CURRENT = 1;
private static final int USE_LAST = 2;
public static void printAllSums(int[] input, int sum) {
// initial step, create the array of hash tables
List<HashMap<Integer, Integer>> memo = new ArrayList<>(input.length + 1);
for(int i = 0; i < input.length + 1; i++) memo.add(new HashMap<>());
memo.get(0).put(0, 0); // start condition
for(int i = 0; i < input.length; i++) {
for(int currentSum : memo.get(i).keySet()) {
memo.get(i+1).compute(currentSum,
(k, v) -> v != null ? v | USE_LAST : USE_LAST);
if(currentSum + input[i] <= sum) { // since no negative inputs are allowed...
memo.get(i + 1).compute(currentSum + input[i],
(k, v) -> v != null ? v | USE_CURRENT : USE_CURRENT);
}
}
}
// backtrack and print results using Result Helper class (below)
if(!memo.get(memo.size()-1).containsKey(sum)) {
System.out.println("no solution found");
} else {
Stack<ResultHelper> solutionBuilder = new Stack<>();
solutionBuilder.push(new ResultHelper(sum, input.length - 1));
while (!solutionBuilder.empty()) {
ResultHelper solution = solutionBuilder.pop();
if (solution.InputIndex == -1) solution.print();
Integer memoEntry = memo.get(solution.InputIndex + 1).get(solution.RemainingSum);
if ((memoEntry & USE_CURRENT) > 0) {
solutionBuilder.push(solution.createNext(input[solution.InputIndex]));
}
if ((memoEntry & USE_LAST) > 0) {
solution.InputIndex--;
solutionBuilder.push(solution);
}
}
}
}
public static void main(String[] args) {
printAllSums(new int[]{1,2,3,4,5,6,7,8}, 12);
/* output
[5, 4, 2, 1]
[5, 4, 3]
[6, 3, 2, 1]
[6, 4, 2]
[6, 5, 1]
[7, 3, 2]
[7, 4, 1]
[7, 5]
[8, 3, 1]
[8, 4]
*/
}
// Helper class, to help backtracking and creating the results
private static class ResultHelper {
public ResultHelper(int remainingSum, int inputIndex) {
RemainingSum = remainingSum;
InputIndex = inputIndex;
}
public int RemainingSum;
public int InputIndex;
public ArrayList<Integer> SubArray = new ArrayList<>();
public ResultHelper createNext(int inputValue) {
ResultHelper newSol = new ResultHelper(RemainingSum - inputValue, InputIndex - 1);
newSol.SubArray = (ArrayList<Integer>)SubArray.clone();
newSol.SubArray.add(inputValue);
return newSol;
}
public void print() {
System.out.println(SubArray);
}
}
}
A generic and general solution is hard (billions of integers, large integers (e.g. 64 bit) and the desire to be exact and fast in all situations, extremes), but you may have some constraints you can leverage e.g.:
- integer size is only 10 or 16 bit: you could use counting sort technique
- do you know something about the distribution: can you tell a probability the median being within a certain range after seeing a few values?
- you might get away with less precision for the median? Maybe precise in a certain range and less if far away from expected?
- size of the stream, can it fit into memory?
- can you assume after you've seen a sample (e.g. 10'000 values) the median is reasonable stable?
The two classics are
- counting sort if median range can somehow be limited
let's assume you have 10 bit values, you count for each of the 1024 possible values
the number of occurences. you insert in O(1) and if you need to know the median,
it's in O(1), too --> easy
- two heaps if values fit in memory and integers are large
Min-heap (for values >= median) and Max-heap (for values < median)
if the next value from the stream is < Min-heap, insert it to the min heap otherwise to the max heap
if the two heap sizes differ by more than 1, take the top from the larger heap and put it to the smaller heap
to get the median: if both heaps are equal size, take the average of the bot tops otherwise take the top of the larger heap
--> insert O(lg(N)), get median: O(1)
maybe interesting could be, if you work with the two heaps but clean up memory from time to time by removing the tails on both heaps. You could for example say, when your heap exceeds 10'000 items, you purge 5'000 tail items, in the min heap this would mean for example to remove the 5'000 values (first quartile) or median of max-heap and do the symetrically the same with the min-heap (forth quartile) ...
depending on the nature of the distribution, chances are, your median never moves out the window and you get a O(1), O(1) solution since you limit N to a constant ...
/*
I'm not sure but the recursive implementation is given and
according to the comment in the question "need a better solution
so that we can store results by using hashmaps" there is some kind
of optimization looked for using memoization.
This is might be interesting if N is big, because prefixes with the
same sum and length have suffixes that can be re-used (are the same).
But then, if the prefixes produce the same sum with the same length, the
same results can be reused. So, a divide and conquer strategy with
memoization might be good.
Let's assume we divide N to reach S (the Sum), there are S ways to do so,
Left + Right = S: If we solved Left, we can reuse the solution for the Right
etc. Sum(S, N) returns a List where each element contains a List of integers
that sum up to S (actually comma separated strings in the implementation)
Sum(S, N) = Sum(s, N/2) ** Sum(S-s, N/2), if N > 1 AND for each 0 <= s <= S,
whereas the "**" indicates all permutations
of the two lists returned from Sum(...)
Below in Java8 with "Sum" being "recursiveSolve" and some inspection
counters to actually show the improvements over the just recursive
solution.
*/
package com.stackoverflow;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
public class Main {
public static class SumCreator {
private int mDigits, mSum;
private Hashtable<Long, List<String>> mMemo = new Hashtable<>();
private int mHitCounter = 0;
SumCreator(int digits, int sum) {
assert (digits > 0 && sum > 0);
mDigits = digits;
mSum = sum;
}
public void printAll() {
System.out.println("Solve it for Digits: " + mDigits + ", Sum: " + mSum);
List<String> results = recursiveSolve(mDigits, mSum);
for(String res : results) {
System.out.println(res.substring(0, res.length() - 2)); // remove last ", "
}
System.out.println("Memo HT size: " + mMemo.size() +
", Memo hit count: " + mHitCounter +
", #results: " + results.size() +
"\n\n\n");
}
List<String> recursiveSolve(int digits, int sum) {
List<String> result = mMemo.get(createKey(digits, sum));
if(result == null) {
result = new ArrayList<>();
if(digits == 1) {
result.add(sum + ", ");
} else {
for (int s = 0; s <= sum; s++) {
List<String> left = recursiveSolve(digits / 2, s);
List<String> right = recursiveSolve(digits - (digits / 2), sum - s);
for (String l : left) {
for (String r : right) {
result.add(l + r);
}
}
}
}
mMemo.put(createKey(digits, sum), result);
} else {
mHitCounter++;
}
return result;
}
static long createKey(int digits, int sum) {
return (long)digits * (long)Integer.MAX_VALUE + (long)sum;
}
}
public static void main(String[] args) {
new SumCreator(1, 16).printAll(); // Memo HT size: 1, Memo hit count: 0, #results: 1
new SumCreator(2, 16).printAll(); // Memo HT size: 18, Memo hit count: 17, #results: 17
new SumCreator(3, 16).printAll(); // Memo HT size: 35, Memo hit count: 306, #results: 153
new SumCreator(4, 16).printAll(); // Memo HT size: 35, Memo hit count: 306, #results: 969
new SumCreator(5, 16).printAll(); // Memo HT size: 52, Memo hit count: 595, #results: 4845
new SumCreator(6, 16).printAll(); // Memo HT size: 52, Memo hit count: 595, #results: 20349
}
}
if they are fixed size a reference to an array of array of array ...
if readonly a const reference
void methode(std::array<std::array<int, n>, m>& array)
if all dimensions are variable, vector of vector which has the issue that each vector has its own size, so it's not necessarily a multidimensional array as we are used to and it's hacky to access the dimension's size
For a matrix I wouldn't use a built in STL type because it will force you to a data representation which might not be what you want e.g. if you want to represent sparse matrix in a memory efficient way.
implementing your own matrix class would be the most effective way to go (except for a coding contest where implementation speed matters more). There you would keep the dimensions and the data seperated and implement a getElement and setElement method. don't get tricked into implementiong something like "[][]-operator" which is a pain due to referencing etc...
what you can do, if you want to provide syntactical sugar is "T& operator() (int row, int col)"
You can as well study the problems of vector<bool> which is a specialized vector (bit-vector) and provides something like:
bool_proxy& operator []
where bool proxy contains conversion to bool ... etc. etc.
- Chris March 21, 2017'''
Introduction:
- The sum can be made up of multiple terms
e.g. f[0]*nums[0] + f[1]*nums[1] + f[2]*nums[2] ... f[n-1]*nums[n-1]
note: 0 <= f[i] <= floor(target/nums[i])
- Find a solution that works for big numbers efficiently as well
Solution Brute Force:
try all f[i] and check if any combination would
lead to target. Of course one can stop trying if target is exceeded
runtime: O(target/nums[0]*target/nums[1]*..*target/nums[n-1])
Optimization Idea: keep calculated sums
Idea: keep intermediary sums and check every time if the value needed to
reach target has already been calculcated
--> this can accellerate to find a solution if one exists, but if none exists
it doesn't help
Optimization Idea: try to avoid double work
If we checked target - 14 and know it doesn work, we shouldn't retry if we get to "14" in an other way
Optimization Idea: Recursion with memoization could look like:
It's not neat, but I couldn't come up with something better within 30 Minutes:
- f(t, i) = f(t-k*nums[i], i - 1), as long as i >= 0 for each k between 0 and t >= k*nums[i]
Memoization I would use to avoid rechecking the same sub-problems again and again meaning, with nums in
the range from [0..k] I mark the values i can't construct with
'''
def factorSumRecursion(nums, target, i):
global memo
if target < 0 or i < 0 or target in memo[i]: return False
if target == 0: return True
if target >= nums[i] 0:
if factorSumRecursion(nums, target - nums[i], i): return True
else: memo[i].add(target - nums[i])
if factorSumRecursion(nums, target, i - 1): return True
else: memo[i-1].add(target)
return False
def factorSum(nums, target):
global memo
memo = [set() for i in range(len(nums))]
if len(nums) == 0: return target == 0
return factorSumRecursion(nums, target, len(nums)-1)
print(factorSum([6,9,20], 47)) #3*9 + 20
print(factorSum([6,9,20], 48)) #8*6
print(factorSum([6,9,20], 49)) #2*20 + 9
print(factorSum([6,9,20], 50)) #1*20 + 5*6
print(factorSum([6,9,20], 12)) #2*6
print(factorSum([6,9,20], 13)) #False
print(factorSum([6,9,20], 9)) #9
'''
Solution:
1) Sort each word's character set and remove dublicate characters => sorted character set of word
2) put into hashtable with sorted character set as key and original word as value
3) iterate over all keys and print words
runtime: O(n*m*lg(m)), whereas m is the max length of the words and n is the number of words
space: O(n*m)
'''
from collections import defaultdict
def getKey(word):
return ''.join(sorted(set(word.lower())))
def printUniqueCharacterSetWords(text):
words = text.split()
ht = defaultdict(list)
for word in words:
ht[getKey(word)].append(word)
for v in ht.values():
print(v)
printUniqueCharacterSetWords(
"May student students dog studentssess "
"god Cat act tab bat flow wolf lambs Amy "
"Yam balms looped poodle john alice"
)
'''
output:
['student', 'students', 'studentssess']
['looped', 'poodle']
['flow', 'wolf']
['dog', 'god']
['May', 'Amy', 'Yam']
['john']
['tab', 'bat']
['lambs', 'balms']
['Cat', 'act']
['alice']
'''
the idea is to learn from past subsets, if you increase the lower bound, the upper bound may stay the same or decrease... maybe be neatly expressed in a DP recursion as well, here the hands-on solution in O(n*log(n)) due to sort, O(n) if nums is passed already sorted (and nums.sort() is removed)
#
# 1) sort the array
# 2) start with i at 0 and j at n-1
# 3) repeat as long as nums[i] < target
# 4) try to find an upper bound which is smaller or equal than last j
# 5) add j - i + 1 or at least 1
# 6) increment goto 3)
#
# example with sorted input for simplicity:
# nums: [1, 4, 5, 7, 11, 14, 20]
# 1..11: 5 subsets: {1}, {1,4}, {1,4,5}, {1,4,5,7}, {1,4,5,7,11}
# 4..7: 3 subsets: {4}, {4,5}, {4,5,7}
# 5..7: 2 subsets: {5}, {5,7}
# 7: 1 subset: {7}
# 11: 1 subset: {11}
# total: 5+3+2+1+1 = 12 subsets
#
def countSubSet(nums, target):
nums.sort()
count = 0
j = len(nums) - 1
i = 0
while nums[i] < target:
while nums[i] + nums[j] >= target: j -= 1
count += max(j - i + 1, 1)
i += 1
return count
print(countSubSet([1, 4, 5, 7, 11, 14, 20], 14))
edited, added corner cases and updated recursion
@tryingtolearn: yes it's dp, but watch out your recursion, it has some flaws, did you verify with examples?
'''
Assumption: if all are negative, we select empty set,
sum 0 > anything negative
Solution:
---------
Recursion:
/ max(0, value(0)), for i = 0
dp(i) = | max(dp(0), value(1)), for i = 1
\ max(dp(i - 2) + value(i), dp(i - 1)), for i > 1
Optimization:
-------------
since the recursion only accesses dp(i-2) and dp(i-1) we can get around the dp-array
'''
def maxboxes(values):
if(len(values) == 0): return 0
dp = [0 for i in range(len(values))]
dp[0] = max(0, values[0])
if(len(values) == 1): return dp[0]
dp[1] = max(dp[0], values[1])
for i in range(2, len(values)):
dp[i] = max(dp[i-2] + values[i], dp[i-1])
return dp[len(values)-1]
# optimized to remove dp-array
def maxboxesOpt(values):
if(len(values) == 0): return 0
dp0 = max(0, values[0])
if(len(values) == 1): return dp0
dp1 = max(dp0, values[1])
for i in range(2, len(values)):
tmp = dp1
dp1 = max(dp0 + values[i], dp1)
dp0 = tmp
return dp1
print(maxboxesOpt([0,1,-2,3])) # should be 4
print(maxboxesOpt([8,1,-1,2,2,10])) # should be 20
print(maxboxesOpt([10,0,0,0,20])) # should be 30
print(maxboxesOpt([-1, -2, -3])) # should be 0
print(maxboxesOpt([])) # should be 0
print(maxboxesOpt([-2])) # should be 0
print(maxboxesOpt([99])) # should be 99
def remainder(binarystring, k):
r = 0
for c in binarystring:
r *= 2
if c == '1': r += 1
r %= k
return r
assume the large number is represented as a string "11" with the MSB first
assume further the divisor (k) is represented as integer
even if python is capable of nearly unlimitted sized integers, the
remainder operation is implemented manualy
just implement the manual (paper-style) division algorith but only keep remainder this is O(n) runetime and O(1) space where n is the number of bits I assume this is the best conceivable runtime since I can't imagine how to calculate a remainder withouth touching each bit. how ever, there might be a more optimized version, using fewer divisions.
complete python code
def remainder(binarystring, k):
r = 0
for c in binarystring:
r *= 2
if c == '1': r += 1
r %= k
return r
print(remainder("11", 3)) # 3%3 = 0
print(remainder("111", 3)) # 7%3 = 1
print(remainder("101", 3)) # 5%3 = 2
print(remainder("1111", 3)) #15%3 = 0
print(remainder("10000", 3)) #16%3 = 1
print(remainder("10001", 3)) #17%3 = 2
print(remainder("10010", 3)) #18%3 = 0
print(remainder("100010111100", 3)) #2236%3 = 1
edited, clarified points and added the check for usage error (post condition)
I assume c++, the code calls lock/unlock every time (so current code is not optimized for lockless which it probably should be, depending on usecase)
1) increment, decrement are not necessarily atomic, for example not if multi core, so it must be inside of lock or you should state that it doesn't run on multi core environment (which means today, it doesn't run on most smart phones, pcs, ...) not doing that is an error, you better don't guess on this.
2) returning the value of the variable outside of the lock, will eventually allow changing the value because the code may be interrupted between the unlock and the return and thus the return value is not deterministic. So you need to copy the value of the variable while in the critical section (locked)
3) the original code has no unlock when returning 0, assuming the "free" function unlocks the lock is very bad practice because it would mean very bad design: normaly, one creates thread safe methods to be used from outside the class but inside the class the methods assume a locked object, so you never need to call nested lock functions which eventually would unlock to early if not used properly... so, no, assuming free unlocks the lock, would be not a good sign.
4) what often happens is the code is not exception safe, one can argue, that the only place an exception can be thrown is in the "free" method and then it doesn't really matter because something really goes wrong. I would still want resources be unlocked to avoid further troubles, for example when logging etc...
5) one should really check if Release is called when m_refCounter is 0 because that would mean someone uses the referenc counting mechanism wrong, and that should be at least asserted.
Release()
{
m.lock(); // 1)
assert(m_refCounter > 0); // 5)
try //4)
{
m_refCount--;
int result = m_refCount; // 3)
if (m_refCount == 0)
{
free(this);
}
m.unlock(); // 3)
return result; // 2)
}
catch(...)
{
m.unlock(); // 4)
throw;
}
}
one intersting question is, how to optimize relatively expensive mutex lock / unlock if lots of "Realease" are called with m_refCount > 1 on multi core processors. While one can do something for single core, its realy hard to get it right on multi core due to caching because one can't assume memory access to be serialized between cores...
- Chris March 05, 2017@rganeyev
e.g. because Floyd-Warshall doesn't work with negative cycles as bellmann ford doesn't
an intuitive prove of this is that if you walk through the negative cycle once more, you will get an even "longer" path with the words of the question or a even "shorter path" in terms of the original algorithms.
Further, it has been shown that the problem can be deduced to a known NP complete problem.
but anyway, I don't agree it's a useless exercise, sometimes even an exponential algo is okay as long as you know it is exponential and if you can roughly prove it's in NP in an interview, I suppose some companies would love you ;-)
Repednaheeks, Android test engineer at Automated Traders Desk
I am Edna, a blogger . As an editor with a strong background in English and Hindi language. I enjoy writing ...
Rep
Rep
Repjudydschultz1234, Android test engineer at Eterno Infotech Pvt Ltd
Spent a weekend researching weebles in Nigeria. My current pet project is developing strategies for how to break someone's ...
RepAmber Van is the top rated company that offers friendly and professional removals services.Our featured services includes domestic moves ...
RepJames Gulledge, Dev Lead at ADP
Get you driving in comfort and class in Atlanta! Prestige Luxury Rentals offer a wide selection of premium vehicles Our ...
the question is ambiguous, even with that constraint of non-overlapping rectangles, the easiest solution is to print just all coordinates where a "1" occurs as 1x1 squares which are all non-overlapping rectangles.
- Chris June 05, 2017Now maybe the question was to minimize the number of non-overlapping rectangles, which seems a bit of an overkill for an interview question.