Docker does not support including a Dockerfile in another Dockerfile, luckily the Dockerfile plus project comes to the rescue.
Simply setup your Dockerfile with:
# syntax = edrevo/dockerfile-plus:0.1.0
INCLUDE+ someDockerfile
FROM someimage
You might need to enable Docker buildkit in order to use this extension, simply set the environment variable:
DOCKER_BUILDKIT=1
When running applications in containers, we might have log files that are relevant to monitor but are not automatically printed with the container output.
A workaround for this is to force the redirect in our Dockerfile by adding a symbolic link:
RUN ln -sf /dev/stdout /path/to/logfile.log
Can also be applied to /dev/stderr of course
Sometimes a Java based app running in a container requires UTF8 encoding. Not all available images enable that by default, this can be fixed by adding one line to your Dockerfile setting the JAVA_TOOL_OPTIONS environment variable:
ENV JAVA_TOOL_OPTIONS -Dfile.encoding=UTF8
This also works outside containers of course.
I recently needed to make a script automatable, meaning I had to provide all inputs to it from the CLI command used to execute it, rather than wait for it to prompt me during execution.
Turns out Python has a nice module dedicated to this: argparse
The usage is very simple and will also create the help menu automatically for us:
import argparse
parser = argparse.ArgumentParser("myScript")
parser.add_argument("-a_flag_input", help="This is a true/false flag", action='store_true')
parser.add_argument("-a_string_input", help="This is a string input", type=str)
args = parser.parse_args()
options = vars(args)
print(args)
if options["a_flag_input"]:
print("a_string_input")
Basically, we define each input parameter along with its type, if the input is a flag (true/false) we can specify an action on it to determine the value it would receive if set.
The inputs will be collected in a Namespace object, which we can convert to dictionary and get easy access to the inputs from the code.
I've been recently introduced to a nice Docker feature: multi-stage builds.
The idea is simple, if the build is containerized as well, the build itself is a developer responsability as well and the operations team need only provide a build server with docker installed on all worker nodes.
To achieve the result, we use a simple Dockerfile where we specify multiple FROM statements and tag each layer as necessary. The last layer will be the one responsible to run the application, while the previous layers are only used for the build. A sample file for a SpringBoot app looks like this:
# syntax=docker/dockerfile:1
# build layer
FROM adoptopenjdk/openjdk11:latest as build
WORKDIR /app
# copy project files into container workdir
COPY . .
# build jar, skip tests, avoid daemon
RUN ./gradlew build -x test --no-daemon
# run layer
FROM adoptopenjdk/openjdk11:latest as prod
WORKDIR /app
#copy fat jar from previous layer into current workdir and rename it
COPY --from=build /app/build/libs/*.jar ./myApp.jar
# not mandatory, must use -p 8080:8080 later anyway
EXPOSE 8080
# start the spring boot app
CMD ["java", "-jar", "myApp.jar"]
Then it can be placed in the project directory and we can trigger the build with:
docker build -t TAG .
Finally run it with (binding for example port 8080 and executing it in background):
docker run -p 8080:8080 -d TAG
We can also see the container output with (find container name with docker ps first):
docker logs -f CONTAINER_NAME
A scenario that popped up recently was to login a user via Java code to Kerberos and retrieve a GSSCredential object containing the Kerberos ticket. I used Java 8, but this works since Java 7 onwards.
Java offers a Krb5LoginModule class which can be used in conjuction with a LoginContext to achieve this.
The flow is quite simple (once you have read all the Kerberos documentation):
This procedure allows handling multiple login mechanisms in the application and even multiple Kerberos realms.
return null;
Unless it's an analog clock, in which case:
The hour hand makes a 360 degree turn every 12 hours or 12*60 = 720 minutes, therefore each minute the hand moves 360/720 = 0.5 degrees
The minute hand makes a 360 degree turn every hour or 60 minutes, therefore each minute the hand moves 360/60 = 6 degrees
Setting 12 as the 0 position, to calculate the angle of each hand we can:
We now have the position of both hand with respect to the 12 o'clock, the angle between them will simply be the difference, between the two positions (absolute value!)
If the difference is more than 180 degrees, the angle is a reflex angle and since we want the smallest angle between the hands, we take its complement by subtracting it from 360 (again, absolute value unless we did a modulo before to account for 24 hour format)
You can check my implementation of clockAngle on my Gist along with some tests in ClockAngleJTests.
Something simple which comes up often when problems require some sort of item distribution.
Given an amount of items N and K buckets, distribute the items in the buckets as uniformly as possible.
Amount of items each bucket would hold in perfect distribution: N/K (integer division)
Amount of remaining items which could make some buckets hold extra items compared to others: N%K
Therefore simply place N/K items in each bucket, then calculate the remainder N%K and place 1 item in each bucket until remainder is 0.
Of course if K is bigger than N, some buckets will be empty.
Given a number N, return the amount of trailing zeroes in its factorial.
Example:
4! = 24, no trailing zeroes
10! = 3628800, two trailing zeroes
100! = something big with 24 trailing zeroes
We could compute the factorial then count the zeroes, which is O(N) time and might work for small values of N, however multiplication can be indeed expensive.
Generate the K-th number made only of primes 3, 5, 7.
Expected results up to K = 15: 1, 3, 5, 7, 9, 15, 21, 25, 27, 35, 45, 49, 63, 75, 81
This exercise is one of those that once the solution is known it's extremely easy but getting to the optimal solution requires work.
An initial suboptimal idea could be to start with a queue and placing only 1 in it.
Then execute some iterations where the top of the queue is polled, multiplied by 3,5,7 and then all results are added back to the queue, including the polled value.
We need to track generated values to avoid duplicating them. After some iterations, sort the queue, then poll until the k-th value is reached.
However the numbers generated this way quickly stray from the natural ordering so we end up generating more numbers that we need to get the actual solution.
After a long examination and paper examples (try drawing a matrix that expands with each new generated value and keep generating until the solution is reached), we notice that the emerging pattern is:
This uses O(N) time and space and most importantly stops as soon as a result is reached.
You can check my implementation of generateKth357 on my Gist along with some tests in GenerateKth357JTests.
Given an array of positive integers and a target K, determine whether it's possible to partition the array in K subsets of equal sum.
Example:
1,1,1,1 k = 2
it's possible to have two sets, each with a total sum of 2
1,1,1,1 k = 3
it's not possible to have 3 sets of equal sum
We first determine if this is generally feasible by looking at the total sum of elements in our array and comparing with K. If possible, each set should sum up to total / K, which means K must be a divisor of our total sum.
We then need to explore all possibilities to generate each subset, this is evident in this sample:
1,1,1,2,2,2 k = 3
The only solution is to pair each 1 with a 2, we cannot apply a greedy approach as we might miss this solution.
A bit similar to the house painting problem, we need to recursively explore our options keeping track of:
We start with no subset existing and all elements available and try an add each available element to a set until we reach the target sum. Everytime we use an element, we mark it as unavailable.
When a set reaches the target sum, we increase the number of "full" subsets and start creating a new subset repeating this logic.
When we have no more available elements, if the amount of "full" subsets is reached, we have our answer, otherwise we need to backtrack and explore a different configuration.
When we backtrack we simply mark the current element as available again, remove it from the current subset sum and proceed on the next element.
This approach gives us a (N * 2^N) time complexity as for each element we explore the option of choosing it or not for the current subset and worst case we repeat this process for each element in our array before we realize no solution exists. Not sure whether sorting the array would have a significant impact on the runtime since there can exist a configuration where the total sum is divisible by K but no arrangement of elements is possible, maybe sorting descending can on average be faster but not in worst case.
We use O(N) space instead for the recursion stack (can't have more than N calls as we pick each element once in a branch) and the array tracking the available elements.
You can check my implementation of canPartitionInKSubsetsOfEqualSum on my Gist along with some tests in CanPartitionInKSubsetsOfEqualSumJTests.
A sample 3D shooter game made with Unity.
Get the code from the repo or play online.
The animals have gone mad, defend your farm from their rage.
Controls:
AD - move left/right
SPACE - shoot
R - restart level
Q - quit
Interesting notes:
Given a MxN matrix of 0s and 1s where 1 is an obstacle, find the shortest path from 0,0 to M-1,N-1 (top left to bottom right) deleting at most K obstacles.
We for sure need a BFS, but need to tweak it a bit so we prefer fast paths that use as many deletions as other paths or fewer.
We therefore track for each cell the amount of deletions we have left when we reach it. If another path reached that cell before us AND had MORE deletions left, then the current path is not an optimal solution and we can discard it. This is because some faster (shorter) path exists that has higher chances of deleting obstacles down the road, so we should explore that path instead.
We use a queue of Integer[] to track the data we need: i, j, current path length, deletions left.
This gives us a O(MN) space and time solution.
You can check my implementation of shortestPathWithMaxKDeletions on my Gist, this time without tests because I am lazy so you can simply run leetcode instead.
A sample 3D plane flying project made with Unity.
Get the code from the repo or play online.
Much anticipated sequel to the exciting Fury Roads, it's time to elevate your rage to the skies.
Controls:
WS - pitch (up/down)
SPACE - turbo
X - invert pitch controls (down/up)
R - restart level
Q - quit
PrintScreen - take a screenshot of that beauty in action
Alt+F4 - close your browser and go take a walk with your mask on
CapsLock - bring that rage to the comments section
Interesting notes:
A sample 3D car driving project made with Unity.
Get the code from the repo or play online.
How to play is in readme or in game menu. Hit the barrier, avoid the boulder, be fast, release the rage.
Interesting notes:
Given a list of strings, group all anagrams together.
Example:
asd, lol, dsa
return:
[lol], [asd,dsa]
Anagrams are words of the exact same length with the exact same characters, potentially in different places.
We can use this to our advantage to easily determine whether two strings are anagrams of each other using an idea similar to a basic string compression algorithm. We create a fixed size array with a slot for each character in the alphabet (26 total, 0 = 'a' and 25 = 'z') and we process each string counting how many times each character appears in it.
We then create a string from that array using a fixed format: Xchar1...YcharN
We can now use this string as key for a map, which will quickly determine whether two strings are anagrams of not. All strings that are anagrams are added as values to the same map bucket, we then simply collect all values in an output list.
This uses O(N) time as we process all strings once and do constant work for each (alphabet size is fixed at 26) and O(N) space as we store all strings in our map.
You can check my implementation of groupAnagrams on my Gist along with some tests in GroupAnagramsJTests.
Given two strings, check whether the first can be rotated any number of times to match the second.
Example:
asd, lol: not possible
asd, sda: yes with one rotation
The key insight to solve this problem is to realize that a string concatenated with itself will contain all possible strings resulting from all its rotations:
asd becomes asdasd
All rotations of asd are: asd, sda, das and we can see that asdasd contains all of them.
Then the problem becomes a search for substring, after having checked that both strings have same length.
We can use KMP algorithm to do a N+N search using N space, stopping as soon as we find the first match, if there is none, then the string can't be rotated in the other one.
You can check my implementation of isRotation on my Gist along with some tests in IsRotationJTests.
Given a list of integers, combine them to form the biggest number possible using all given numbers. Example:
500,60 return 60500
1,2,3 return 321
We can cheat a bit and get the input as array of strings, but the approach is the same. The idea is we need to sort this input in a way that provides us with the highest numbers first.
However, it is not enough to simply compare numbers since the example shows that approach would lead to the wrong result: 500,60 the biggest number is 60500 and not 50060 even though 500 is bigger than 60.
This example does show the solution though: given two numbers we want to order them based on the resulting number, since 60500 is bigger than 50060, the order is then 60,500
To solve our problem in O(N logN) time and O(logN) space (use Arrays.sort()) we simply need to provide a comparator that does what we want, then take each number and combine it in the result.
You can check my implementation of makeBiggestNumber on my Gist along with some tests in MakeBiggestNumberJTests.
Given an array of integers return true if it is possible to reorder its elements in pairs so that arr[2 * i + 1] = 2 * arr[2 * i] for all i up to length/2
In other words, given an array of integers allowing negatives and duplicates, find if it is possible to use each element in a pair where the first element in the pair is half the value of the second element of that pair. Elements cannot be reused among different pairs.
Given a series of equality and inequality equations, determine whether they can be satisfied.
Equations are in the form:
a==b
a!=b
where a,b are the two variables involved.
Example:
a==b, b==c, c==a: OK
a==b, b==c, c!=a: KO
Similar to the graph coloring we saw before, we can apply the same method here but expand it to more colors.
We create an adjacency list from all equality equations, the linked variables (connected components) must all have the same color, we proceed by starting with a color and then assigning it to all variables connected to each other, we repeat this process for all variables without color, each time using a different color.
Then we parse all inequality equations and verify if any conflict arises.
This algorithm runs in O(V) space and O(E) time as we explore all edges (equations) once. We use V space for the stack when coloring as at most we can add each vertex only once (we only add if vertex has no color).
You can check my implementation of equationsPossible on my Gist along with some tests in EquationsPossibleJTests.
Given a graph, return a possible 2 coloring of it.
The algorithm is simple, for each node in the graph, if it doesn't yet have a color, run a DFS from it.
The DFS will assign a default color (eg; 1) to the node, if it doesn't already have one, then for each neighbor:
In the end, if we stopped early it means the graph can't be colored with only 2 colors (there is no possible bipartition), otherwise we will have a possible 2 coloring or our graph as output.
This algorithm runs in O(V) space and O(E) time as for each node we explore all its neighbors once (we don't invoke DFS again unless neighbor had no color) and at most we can put V nodes on the callstack for recursion.
You can check my implementation of twoColor on my Gist along with some tests in TwoColorBipartitionJTests.
Given a 32 bit integer, reverse it.
Example:
123 becomes 321
The initial thought was to treat the integer as a bit array, swapping each from left to right.
This would have some tricks in the implementation, especially since Java uses 2's complement for negative representation, but could be done and has a complexity of O(32) at most as we consider each bit in the number.
However, turns out there is a much better approach that uses divide and conquer logic to achieve the same result:
public static int reverseBits(int n){
//take half of the bits from MSB to mid portion
//take half of the bits from mid to LSB portion
//swap them
//repeat the process with always smaller masks and portions
//mask is always 32 bit in size
//initial swap, throw away 16 LSB and 16 MSB, combine them together
//now we have the two halves reversed
n = n >>> 16 | n << 16;
//mask for left portion: 1111 1111 0000 0000 1111 1111 0000 0000
//mask for right portion: 0000 0000 1111 1111 0000 0000 1111 1111
//then shift by half of previous size (8 bit)
n = (n & 0xff00ff00) >>> 8 | (n & 0x00ff00ff) << 8;
//mask for left portion: 1111 0000 1111 0000 1111 0000 1111 0000
//mask for right portion: 0000 1111 0000 1111 0000 1111 0000 1111
//then shift by half of previous size (4 bit)
n = (n & 0xf0f0f0f0) >>> 4 | (n & 0x0f0f0f0f) << 4;
//mask for left portion: 1100 1100 1100 1100 1100 1100 1100 1100
//mask for right portion: 0011 0011 0011 0011 0011 0011 0011 0011
//then shift by half of previous size (2 bit)
n = (n & 0xcccccccc) >>> 2 | (n & 0x33333333) << 2;
//mask for left portion: 1010 1010 1010 1010 1010 1010 1010 1010
//mask for right portion: 0101 0101 0101 0101 0101 0101 0101 0101
//then shift by half of previous size (1 bit)
n = (n & 0xaaaaaaaa) >>> 1 | (n & 0x55555555) << 1;
//now all the bits have been moved around in the reverse place
return n;
}
The idea is to split the integer in two halves, shift them by half the size of the integer, and combine them back.
Repeating this process on each half will in the end give the desired result.
Given an array of length N of unique positive integers in range 0..N both inclusive, find the missing one.
We have two linear approaches, one uses a mathematical formula, the other some bit magic.
Math:
all numbers in range 0..N summed up can be calculated with the formula:
N * (N + 1) / 2
If we sum up all elements in the array, our missing number is the expected sum minus the actual sum
Bit:
if the array was of size N + 1 and all integers in range 0 .. N were present and sorted, each would sit at the index same as the number itself, for example:
idx: 0 1 2
num: 0 1 2
Since we know only one number is missing, there must be some index where the value doesn't match the index.
Since N + 1 is NOT a valid index in the array, we can initialize a variable to that, then XOR that variable with all values and indices in the array.
All repeated elements (index and value) would cancel out, leaving only the missing one as result.
You can check my implementation of findMissingNumber on my Gist (math) and Gist (bit) along with some tests in FindMissingNumberJTests (math) and FindMissingNumberJTests (bit).
Given a positive integer N, find for each integer in range 0..N inclusive, how many bits are set to 1.
We could for each integer in range 0..N consider its binary representation and pick off all bits set to 1 counting them.
This would make us do at most 32 operations for each number, being 32 a constant we'd have linear time but performance is still impacted.
We can however reuse information we stored earlier (especially in this case it's part of our answer anyway)
Drawing the binary sequence for 0..8 gives us:
And we notice that N and N*2 have exactly the same amount of bits set, just shifted left one position, example:
What is left out is odd numbers like 5 and 7. But in that case, it's just about setting the lsb to 1 from the previous number, example:
so to create an odd N, we can simply start from N/2, shift it up one position AND check if we should set the lsb to 1 in this new number.
If we know how many bits are set in N/2, we skip all of this process and just reuse that value adding one to it if the lsb should be 1. We know if it should be 1 by checking N & 1.
This is also equal to saying number of bits set in N is N/2 + N mod 2 as anything modulo 2 will always be either 0 or 1, specifically 0 if N is even and 1 if N is odd.
We repeat this process for all numbers in our range and we have the solution.
Since the output is part of the solution, our space complexity is O(1) and our time is O(N).
All operations we use are division by 2 and modulo by 2, which are a right bit shift and a bitwise AND.
You can check my implementation of countOnes on my Gist along with some tests in CountOnesJTests.
Given two integers, return a + b without using sum operator.
Seems like it's time for more bit magic.
We process our numbers bit by bit starting from LSB, we track a carry, a position in the result sum, and the result sum.
Getting the LSB can be done by:
n & 1
If 1 the bit was set to 1
Then we can calculate the result of the sum:
it will be a 1 only if there is an odd number of ones between lsbA, lsbB and carry:
res = lsbA ^ lsbB ^ carry
Then we can push that bit in the correct place in the final result:
res = res << position
And set it in the final sum:
sum |= res
Also we need to increase position for the next iteration, but we can't use sum operator:
position = -(~position)
We can then calculate the carry for the next iteration:
it will be a 1 if there were at least two ones between lsbA, lsbB, carry:
carry = (lsbA & lsbB) | (lsbA & carry) | (lsbB & carry)
we then drop the lsb from both a and b WITHOUT preserving sign (we need it come to us for processing, we can't leave it set in MSB):
a = a >>> 1
b = b >>> 1
and repeat this process until both a and b are 0
One last thing to do after all of this, if there was still a carry left AND we are not trying to set it in position 32 (MSB), set it in the final sum.
You can check my implementation of sum on my Gist along with some tests in SumJTests.
Here's another piece of bit magic that works on those systems where numbers are stored using 2's complement.
Since a negative number is stored using that form, and that form is obtainable by inverting all the bits then adding one, we can get the number + 1 by inverting all bits first and then flipping its sign:
n = -(~n)
This works for both negatives and positives.
Given a DAG, find all paths from source to target.
Since it is a DAG, there are no cycles, therefore we can't go back to an already visited vertex during a visit.
We can therefore add the source to a stack, then use recursion to find all paths from source to target.
In the recursive function, we look at the current node (top of stack) and for each one of its edges, we add the destination to the stack and call recursion on that destination.
When the top of stack is the target, we scan the scan and track all elements as a solution, they will be in inverted order from last vertex to first. However, a foreach loop on a Stack (in Java) gives element in order from bottom to top, so there is no need to invert them in our result.
When we get back from a recursive call, we remove ourselves from the stack as we have fully explored our subgraph.
This code works in O(V) space as that's how deep the recursion could go, and our stack also matches the recursion in size.
For time complexity, I assumed we would get a O((V+E)^2) upper bound as without cycles we cannot go back to previously visited vertices but some paths might overlap and we would walk down the same edge multiple times.
This might not be the case if we look for ALL paths from ALL vertices, however we only consider ONE start vertex in this case.
I think it made sense as a similar problem which is topological sorting is linear and in this case we're looking at all paths between the two farthest nodes.
Turns out it's exponential in reality: If all vertices are connected (without cycles) for each new node excluding start and end, we have a choice of either including it in a path or not, which would give a O(2^V) upper bound.
You can check my implementation of findAllPathsFromSourceToDestInDAG on my Gist along with some tests in FindAllPathsFromSourceToDestInDAGJTests.
The title is actually a simplification of the following problem:
given a car with unlimited fuel capacity, an array indicating the amount of fuel that can be put in the car at a specific city i and another array indicating the amount of fuel necessary to travel from city i to the next, return the index of any city that allows making a round trip passing through all other cities in the order they appear.
Example:
gasAtCity = 1,1
gasForNextCity = 1,1
Any index is correct, start at city 0 we will the tank with 1 unit of fuel, we spend 1 unit of fuel and reach city 1 with 0 fuel left. We fill the tank there with 1 unit of fuel, spend 1 unit of fuel to go to the next city which bring us back to the start and end our journey.
gasAtCity = 1,1
gasForNextCity = 2,2
No city is correct since no matter where we start, we won't ever have enough fuel in the tank to reach the next city.
gasAtCity = 1,1,2
gasForNextCity = 1,2,1
Start from last city is the only possible choice as starting from earlier places will leave us at some point with not enough fuel to continue the trip.
We've seen how to search for an element in a sorted array of unique element, which was rotated an unknown amount of times.
Now we want to find the minimum element in that array.
The approach is the same, however the minimum element can be in two places:
We can therefore do a binary search testing for this condition: which adjacent elements are such that the first is bigger than the second. When we find that pair, the second element will be the smallest.
This is because the array has unique elements and was sorted, therefore there is only one place where this pair exists and it's where the last and first meet.
If we view the array as a circle, a sorted array as last and first meeting at the very borders.
At each iteration of the search we have the following cases:
This code runs in O(logN) time and constant space.
You can check my implementation of minimumRotatedSortedArray on my Gist along with some tests in MinimumRotatedSortedArrayJTests.
Given an array of integers, find the maximum subarray product. The product of all elements in the array is guaranteed to fit in an integer.
Example:
-2,0: return 0
-2,20,-1: return 40
1,2,3: return 6
Given a list of flight tickets and a start airport, find if possible an itinerary that uses all tickets. If there are more such itineraries, return the earliest lexicographically sorted one.
Example:
a,b - c,d start at a: there is no path
a,b - a,c - b,c - c,a start at a: return a,b,c,a,c since it's alphabetically earlier than a,c,a,b,c
This exercise is a bit simpler since we are given the start vertex and it's asking us to find a Eulerian path for the given directed graph.
The complexity for that would be O(E) where E is number of edges as we tray to visit each at most once and either we'll find a path or not.
However we are asked to return the earliest lexicographically sorted path, therefore when choosing a next vertex to visit, we can't pick any edge as we would normally do, but need to choose the earliest one.
This can be done by sorting the edges first, bringing the total time to O(E log E). Using an adjacency list, we could replace the list with a PriorityQueue instead to have this done for us while building the graph.
We can then have a map with key = vertex, value = priority queue to track our graph.
The idea then is to do a DFS and start from the source and:
When the queue of destinations for a vertex is empty, we can't progress further from that vertex, so we add it as HEAD of our result path
When we return from the initial call, we have one check to do: the adjacency list of all vertices must be empty (we were removing edges while doing DFS) as we want to have visited all edges.
If that is not the case, there was no path, we return an empty list.
You can check my implementation of eulerianPath on my Gist along with some tests in EulerianPathJTests.
I have also added optional code that would perform the check whether a path exists and would help in finding a potential start and end vertices in case they were not given.
Given an array of integers, find the longest increasing subsequence. If there are more, find any.
Given a number, calculate the nth root within a certain precision epsilon.
Without using square functions, we need to approximate the result ourselves.
We could start from epsilon, calculate the nth power of it, then verify whether it differs from the given number by at most the given epsilon.
If yes, we have our result, otherwise, we increase our start value by epsilon and repeat.
This can be done iteratively in constant space but has a terrible time complexity O(all possible numbers between epsilon and N with precision epsilon).
We can improve on this by using binary search as in the end we're looking for a value within a range.
We set our floor to 0 and our ceil to N, then our mid point is at each time the candidate for our nth root.
We multiply mid with itself to calculate the nth power, and verify if we're within epsilon of the given number, which means we have found the root.
If not, we check whether we overshot or undershot and set ceil or floor respectively to mid. We do NOT use mid plus or minus something since we're dealing with doubles and any fluctuation might lead to a wrong result.
Additionally mid is the midpoint between floor and ceil, and since we're dealing with floating point values it's guaranteed it will never be equal to either bound (unless we have reached the minimum possible precision of the double type).
The complexity now is O(log all possible numbers between 0 and N with precision epsilon) which is much better than before.
Space complexity stays the same since we're doing the iterative approach.
You can check my implementation of nRoot on my Gist along with some tests in NRootJTests.
Given array of positive integers including zeros and duplicates, partition it in portions left and right such that every element in left is smaller than every element in right. Keep left as small as possible.
Example:
1,2,3 partition 1 - 2,3
3,2,1 partition 3,2,1 - empty
1,1,0,3,2 partition 1,1,0 - 3,2
1,1,3,2 partition 1 - 1,3,2
Looking at our examples, we can solve this in O(N) time and space by keeping track of the following information:
This is because we can notice that for each position from left to right we want to break there (and therefore generate the smallest partition) only if max at that position is less than or equal to min at the next position.
In that case, every element BEFORE us (including us) will be less than or equal to every element AFTER us, satisfying the given condition.
We can improve slightly on space by noticing we don't need to remember max values, but only need the last one, so we can replace the max array with a variable.
We still need the min array though, for example:
5,0,3,8,6
if we tracked only 0 as min, we would break at the end of the array since max until there is never less than 0.
By checking against the min value at the next position though, we break on 3, which is the correct answer.
You can check my implementation of disjointPartition on my Gist along with some tests in DisjointPartitionJTests.
Given a simple regex that allows characters, dots and stars, find if a given text matches a given pattern.
dot '.' = any character
star '*' = 0 or more repetitions of previous character
We have already seen a slightly more complex regular expression matcher which does a similar thing but I realized that matcher did NOT use caching.
The complexity becomes exponential due to the behavior of star, since "0 or more" means we have a choice: match on this char and continue with same pattern or keep this char and continue with next piece of pattern.
For example:
text = abbbb
pattern = ab*b
Due to this possible choice, our complexity is O(2^N) for both time and space.
We can cache however the pairs (index of text char, index of pattern char) where failed to find a match, so that for repeated patterns example:
text = abbbb
pattern = ab*b*b*.*.*b
When we reach a portion that we already investigated in the past, we skip it and continue
This uses O(N^2) space and O(N^2) time as we check each pair once.
We have to be very careful in our base cases:
text = "", pattern = "" is a match
text = "", pattern = ".*" or any char followed by star or any sequence of chars followed by stars (.*b*n*), is a match
text = "", pattern = "." or any sequence, is not a match
text = anything, pattern = "", is not a match
We therefore find the following cases:
If we encounter a failure when doing any of these inspections, we cache it
If at any point we can make a successful match, we stop and return true.
You can check my implementation of regexMatch on my Gist along with some tests in RegexMatchJTests.
Given a NxN board and N queens, count how many placements exist where no queen blocks another.
This is an extension of a problem known as eight queens, which feels like dynamic programming, but is slightly different from the usual approach of finding a recursion, then caching.
The reason is that the solutions are NOT incremental. Finding a solution for a smaller N is NOT expanded to a bigger N, therefore we can't reuse already computed work. And usually when we do DP, we cache something, but in this case there is no possibility.
Given a binary tree, return all nodes at a given depth.
We could do a level traversal with a queue BFS style, adding markers in the queue to determine when a new level is reached. Once we arrive at the desired level, we add all nodes between the current marker and the next to the solution.
Complexity is O(N) time and space in worst case. Although for BFS space worst case happens when tree is balanced (all nodes at a certain level are added to the queue).
We can also do DFS which has O(N) time and space complexity again, but worst case for space in DFS is when tree is a branch (call stack is the whole tree).
If we do BFS we can iteratively collect the result, if we do recursive DFS, we need to pass in input a structure where we will collect the result.
The order of elements in the result can be controlled by deciding whether to move left or right first.
You can check my implementation of getAllValuesAtDepth on my Gist along with some tests in GetAllValuesAtDepthJTests.
Given an array of positive integers, with possible duplicates, find if a subset exists whose sum is a given target.
Example:
1,2,3 target 3 result = {1,2} or {3}
1,2,3 target 5 result = {}
This is clearly a dynamic programming problem, however I think the approach of using a matrix as cache makes it a bit harder to backtrack to a valid solution.
Given a string representing a text and a dictionary of words, return a possible reconstruction of a sentence built by breaking off the given text using whitespaces to separate valid words.
Example:
text = "bedbath", words = {bed, bath} return "bed bath"
text = "bedbath", words = {bed} return ""
My initial idea used a Aho-Corasik trie which I though would give a linear time solution by greedily matching longest prefixes, then falling back to shorter ones while walking on the string.
This is partially true unfortunately as it works when prefixes are contained within each other, however it fails when the last character of a word is the start character of another word, and we have a fail link between them.
In that case, we would incorrectly assume we have matched two words (technically true) but in reality we matched two substrings. The shared character cannot be used for both words.
Example: text = "catsand", words = {cats, sand} return ""
If we match until "catS", then we can't continue, however we can follow the fail link to root and continue on the "S" edge for "Sand". We mistakenly assume that "S" appeared twice.
So it's fallback to DP, where we apply a similar approach to the trie matching BUT we break off any valid word we encounter and continue matching from the NEXT character onward.
Therefore for each character in the string, we have two choices: break off a word here (if the current suffix forms a dictionary word) or expand the current suffix and break later.
This translates to a O(2^N) time solution. We can however use O(N) cache space to bring the cost down to O(N^2) if we cache the indexes from where we have found in the past that no valid break can be made. This means we explore all pairs of prefix-postfix once.
If we want to reconstruct the sentence and not just return a boolean saying whether the break can be done, we can use StringBuilder objects to track the matched words up to a certain point, discarding their content if we reach a failure node or appending if we can progress with the matching.
In the end, we will have the text that is broken down to the shortest words possible to make it.
Example:
string = aaab
words = a, aa, aaa
recursion tree looks like:
aaab
a,0 aa,1 aaa,2
a,1 aa,2 a,2 b,3
a,2 b,3 b,3
b,3
Where we start from the whole string and for each matched suffix (a dictionary word) we break off at the current index and explore from there.
As you can see we have many repeated calculations, which we can cache.
You can check my implementation of reconstructSentence on my Gist along with some tests in ReconstructSentenceJTests.
Given an array of unique integers, count all out of order pairs. A pair of elements is out of order if its position in the array is less than the position of the other element, but its value is bigger.
In short, count the pairs that have the first element bigger than the second, in the order that the elements appear.
A first attempt to solve this problem in complexity better than O(N^2) gave a O(N^2) solution due to a data structure limitation.
Given the root of a binary tree, find any of the deepest nodes.
This problem is similar to finding the depth of a tree, only this time we collect a pair (node, depth) and when we recurse on each node, we pick from it the node that was deepest among the two left and right children.
We can do this in O(N) time and space worst case (tree is a branch).
You can check my implementation of getDeepestNode on my Gist along with some tests in GetDeepestNodeJTests.
Similar to ThreeSum, but this time we need to find all unique quadruples that sum up to a given target.
I think if we were required to only count all possible quadruples, we could do this in O(N^2) time and space, but finding all unique quadruples means discarding already used elements and since our array can contain duplicates I think O(N^3) is what we can do.
We use a class Quadruple that stores four integers, we also define a hashCode and equals so that if all elements in different quadruples are same, no matter in which order they appear, then we consider the quadruples same.
I thought about XORing all values in both objects, then ANDing them and check if result is 0, but negative elements are allowed, therefore we get a wrong result (at least in Java with the 2's complement representation of negatives). I ended up adding elements of both objects to two sets, then comparing the sets for equality.
The approach to solve the problem is scanning the array in O(N^2) time to generate all sums of two elements, and track them in a map where the key is the sum and the value is the list of all pairs with that sum in the form (element1, element2, index1, index2).
This also gives O(N^2) space usage.
Then we scan again the array and for each pair we check if the map contains the complement we need: target - sum of pair.
If it does, we scan the list of pairs to remove duplicates (other pairs that have at least one index in common with the current pair), then add the result to the output only if we have not seen that quadruple already (store it in a set).
Total time is O(N^3) and space is O(N^2).
Of critical importance is the implementation of hashCode and equals for the Quadruple class since the set will deduplicate ONLY if it can verify equality.
Maybe an approach similar to the second option of threeSums where we sort the array first, then do the two nested loops with a third loop on the remaining portion of the array could give O(N^2) time if we still use O(N) or O(N^2) extra space, but I couldn't figure it out.
You can check my implementation of fourSum on my Gist along with some lazy tests in FourSumJTests.
Given two strings, check whether exactly ONE swap of two different characters can be made in any string to form the other.
Example:
abc,abc: false
asd,jkl: false
aa,aa: true
ab,ab: false
ab,ba: true
The main issue is that we FORCE a swap, even if strings are equal already.
After checking for string length which must be at least 2 and both must have same length, we can walk both strings at the same time, counting number or unmatched characters.
If we ever have more than 2 mismatched characters, we stop and return false as we can only swap two characters at most (eg: asd,jkl), otherwise we track the indices of the mismatched ones.
Also we check if a string has any duplicate characters, this is necessary as we MUST perform a swap, even if the strings are equal. Therefore we need to have the possibility to do a harmless swap between two duplicates (eg: aa,aa is ok but ab,ab is not).
At the end we have the following cases:
This will work in O(N) time and space.
You can check my implementation of checkBuddyStrings on my Gist along with some tests in CheckBuddyStringsJTests.
Given a palindrome string, change any character in order to form the lexicographically earliest non palindrome.
Example:
"a" return ""
"aa" return "ab"
"aba" return "abb"
We have two options: change an initial 'a' character in the first half (excluding middle point) or change a last 'a' or 'b' character in the second half (excluding middle point).
For odd length palindromes, changing the middle point will still yield a palindrome, so we must skip the midpoint. For odd length palindromes, the middle point is in between two chars, so we're good.
If first half of the string is all 'a', then changing any might give a non palindrome, however it won't be the lexicographically earliest, example: 'aa' could give 'ba' but the earliest is 'ab'
This means, if we can't change any 'a' from the left side, we must change the last char from the right to either 'a' or 'b' and will be left with the solution.
The only case where we can't give a solution at all is if the string only has one character, which is always a palindrome.
We can do this in O(N) time and space. The time is actually O(N/2) worst case, but we need to generate the new string, which requires us to copy the input somewhere where we can edit it, which costs O(N).
You can check my implementation of breakPalindrome on my Gist along with some tests in BreakPalindromeJTests.
Given an array of integers with duplicates, negatives and zeros, find a subarray that reaches a target sum.
The sum must be formed by at least two elements.
Example:
2, -1, -2, 5
target 5, no result
target -3, one result: -1,-2
The linear time approach builds upon this observation: having the rolling sum (prefix sum) for each position, if at any point the current sum - target results in an already seen sum, it means there are two subarray sums whose difference is exactly K, which implies there is a subarray whose sum is exactly K.
We can see the current sum as every element from the first to the current element and wonder whether we can use any previous sum (which is contained in the current one) to calculate the middle portion between that sum and the current index.
This however could be a single element, therefore we can't use a simple Set to track this information. If we use a Map instead to store pairs: sumAtIndex, Index we can then easily check whether the subarray we would consider as result has at least two elements: index - indexOfSum must be greater than 1.
Specifically:
if currentSum (curr) - K = any of the previous prefix sums (other), there is a subarray between other and curr whose sum is K.
To avoid the case where the first element is equal to K, we must initialize the map to (0, -1).
It took a while to visualize this, in our example with K = -3:
current subarray sum is made of elements: 2
map = (0,-1), (2,0)
current subarray sum is made of elements: 2 , -1
map = (0,-1), (2,0) , (1,1)
current subarray sum is made of elements: 2 , -1, -2. We have the sums of subarrays (2), (2, -1) stored.
Could we remove any of those sums to retrieve the sum of elements between those subarrays and ourselves? Yes in O(N) time, but we don't need to check all of them as we are only interested in knowing whether any subarray in between sums up to K so we can approach it from the opposite direction. If we remove K from the current sum, we are deleting (if any) a subarray in the middle whose sum is K.
If that subarray existed, we sould reach a prefix sum we've already seen. In this case from current subarray sum (2, -1, -2) we remove K (-3) which corresponds to subarray (-1, -2) and are left with sum of 2 which was subarray (2). Therefore between (2) and current index we had (-1, -2) which is our answer.
We just need to check if that subarray is formed by more than one element:
index of sum 2 is 0, current index is 2. 2 - 0 is greater than 1 so that subarray contains at least two element, we can stop.
You can check my implementation of subarrayOfSumK on my Gist along with some tests in SubarrayOfSumKJTests.
Given an array of unique items, which was sorted and then rotated an unknown number of positions left or right, find whether an element exists in the array in O(logN) time.
We can do a normal binary search, but each time we need to understand where to continue searching.
Given a middle element, either the left or right side will be sorted and the other side not as there will be at least one element whose successor is not in order, unless array is all ascending or mid is the break point.
After checking the middle element, we look at both sides to determine where the item would be and move in the correct direction:
Given a number, find the next number which is bigger than the given one and has the same digits.
Example:
9876 - no next exists
6789 - 6798
8276 - 8627
We first need to convert the number to an array for digit manipulation, we can convert it first to a string and then to the array.
Then, we need to identify (if any) a digit that can be swapped in another place. If it exists, it will be the first digit from the right which is smaller than the next digit.
Example: 9876
has no valid digit since that is already the biggest number that can be made with those digits, notice all digits are in decreasing order
Example: 6789
the first digit smaller than the next from the right is 8, we can use it to make 6798 which is the next bigger number than 6789 using same digits
But simply swapping two digits is not enough, example: 8276, a swap would give 8672 which is bigger but not the next, that would be 8627.
We notice that after the swap, the rest of the digits on the right of the swapped one are sorted in increasing order.
If we do that, we have our answer, this reordering can be done in linear time since in the first portion we stop as soon as we find an element that breaks the increasing sequence right to left.
If there was no such element, we are in the first example where no next number can be built.
Complexity is O(N) for both time and space.
You can check my implementation of smallestBiggerNumWithSameDigits on my Gist along with some tests in SmallestBiggerNumWithSameDigitsJTests.
Given a binary tree, check whether it is mirrored along a line that runs across the root.
By drawing an example we can deduce what is the recursion to apply:
1
2 2
4 3 3 4
We notice that a single node is always mirrored. Given two nodes, children of nodes at a previous level, they are mirrored only if they have the same value and their subtrees are identical, but swapped left and right.
We can do this recursively in O(N) time and space.
You can check my implementation of isMirrored on my Gist along with some tests in IsMirrorJTests.
A power set is the set of all possible subsets of a set. For example for {1,2} it is {{}, {1}, {2}, {1,2}}
It contains 2^N elements.
We can use DFS recursion to generate it, removing one element from each subset we generate at each step, skipping repeated sets.
This can be done in O(N) space (we won't add more than N calls on the stack) and O(N 2^N) time since there are 2^N sets to generate AND everytime we create a new set we need to copy over all its elements in a NEW set.
You can check my implementation of generatePowerSet on my Gist along with some tests in GeneratePowerSetJTests.
Given a string representing a unix path, simplify it to remove dots and repeated slashes, condensing only to the folders appearing in the final path.
Example:
/../ return / as we can't move up from root
/asd/../lol return /lol as we went into asd, then moved out from it
We can do this in O(N) time and space by using a queue.
We first split the string over the "/" character to separate all folders and special characters.
If there are repeated slashes together (eg "//") the split would return an empty string for them.
We then loop over all strings in the split and check the following cases:
Then, we can recreate the path by appending all elements in the queue together
This won't be O(N^2) since removing from the queue at most will make us walk the whole string twice (we can't remove more than we add).
You can check my implementation of simplifyPath on my Gist along with some tests in SimplifyPathJTests.
A matrix is called toeplitz matrix if all element along the left to right diagonals are same.
Given a matrix, test whether it is a toeplitz matrix.
We can verify the given condition with two consecutive loops. The first will check all diagonals for the first row starting with the previous to last element until the first of the row.
The last element of the row is on a diagonal with itself, therefore there is nothing to check.
We repeat the process for all diagonals for the first column starting with the second element until the previous to last. The first element was already checked as first element of the row at the previous step, and the last element again is on a diagonal with itself.
We can do this in O(NM) time and constant space.
You can check my implementation of isToeplitz on my Gist along with some tests in ToeplitzMatrixJTests.
Given an array of integers with possible duplicates, negatives and zeros, find the largest product that can be made using three elements in the array.
We notice that if the array was sorted, we would have the smallest (possibly negative) elements at the beginning and the largest (also possibly negative) at the end.
Given an ordered sequence of elements, we can find the largest product in two ways:
By choosing the biggest of those two, we have our answer. This could be done in O(N log N) time and space for sorting.
But we then notice that all we need are 5 elements: 3 largest ones and 2 smallest ones, we can simply create 5 variables and scan the array in one pass in O(N) time and constant space to track those elements to achieve the same result.
Careful: the if conditions to decide which elements to track must be chained together otherwise you might propagate the largest/smallest element everywhere.
You can check my implementation of maxThreeProduct on my Gist along with some tests in MaxThreeProductJTests.
Given an array of unique integers and a target K, find all pairs of elements that satisfy the formula X - Y = K
The output should preserve the order of elements for Y. Example:
0,-1,1 target 1 result: (1,0), (0, -1)
We can add all elements to a set, then walk the array again and consider each element as the Y in the equation.
We then check if the complement X = K + Y is in the set, and if so, we add it to the output.
We can do this in O(N) time and space.
You can check my implementation of pairsWithDifferenceK on my Gist along with some tests in PairsWithDifferenceKJTests.
Given a binary tree, return a list containing all elements we would side at each level if we were looking at the tree from the right side.
Example
1
/\
2 3
return 1,3 since 2 is hidden by 3 on its level.
We can solve this with a BFS or even recursively.
Given an array of words and a page size, return a list of lines that have been padded to fit the given page size.
If a line can fit only one word or is the last line, pad on the right, otherwise pad between words and add excess padding starting from the left.
This can be done in linear time in the size of the output text by walking on the input array and tracking how many words we are adding to the current line, plus how much space is left.
Whenever we add a word, we also check if we could fit the next, as in that case we would add at least a space on the current line.
When we can't add more words to a line or the line is full, we process all words in the start,end range we found so far and correctly pad between them.
The complexity is in calculating how wide each space should be and how much padding we need to add to those spaces:
spaceSize = (page size - length of words on the line) / (number of words on the line - 1)
Then we need to calculate if there is excess padding which needs to be distributed among those breaking points:
remainingPadding = (page size - length of words on the line) % (number of words on the line - 1)
When we add a word, we add spaceSize spaces after it, then one space from remainingPadding (if any are left)
In the special case of single word or last line, spaceSize will be 1 and remainingPadding will be 0
We then check if the line has still some space left (only can happen in the special case above) and if so, we add enough padding spaces to the right side.
We only process each string in input twice (first we read and add, then we push to result) and in terms of spaces we only add the ones required. At most in one line there can be M characters, that's the size of the page so in worst case each line can contain only one word and some spaces, the total amount of characters we process among words and spaces is O(NM) where N is the number of input words and M is the page size. This is linear in the size of the output.
Regarding space, we use a StringBuilder, therefore at most we add M words to it each time, bringing space to O(M).
You can check my implementation of fullJustify on my Gist along with some tests in FullJustifyJTests.
Given an array of integers, move all zero elements to the end while preserving the order of the other elements.
We are supposed to alter the given array, therefore let's make use of it.
We want to scan the array to find all non zero elements and put them to the front of the array, then fill the rest of the positions with zeros.
We notice though that the first non zero element would be placed at the beginning of the array, then the next non zero would be placed after that and so on.
If an element is non zero and there were no zeros before it, it stays in its place.
Therefore we can use a pointer to track where would we insert a non zero element, then scan all other elements of the array.
When we encounter a non zero element, we copy it to the location pointed by our pointer UNLESS it's exactly our position. If we did move, we replace the current position with a zero. In both cases, we increase the pointer.
We can process the array in O(N) time using constant space.
You can check my implementation of moveZeros on my Gist along with some tests in MoveZerosJTests.
A wiggle sequence is a series of numbers where elements are strictly increasing or decreasing.
Given an array of numbers, find the longest wiggle subsequence. Example:
1,1 - longest is 1
1,2,3 - longest is 2
1,2,1 - longest is 3
The sequence can start going up or down, then all other elements must alternate between going down or up.
Given a text representing a compressed string, return the uncompressed version.
Compression works as such: if a substring is repeated K times, we represent as K[substring] which can be nested. Example:
K[ssL[a]] means we repeat 'a' L times (call it T) and then repeat 'ssT' K times.
K is always > 0 and the string will always be well formed.
Fractals certainly build beautiful shapes, in this exercise we are tasked with creating an H tree, that is a tree where given a starting point which is the center of the horizontal line in the H, all corners of the H repeat the pattern until a given depth.
Example:
depth = 0, no tree
depth = 1, H
depth = 2;
H H
H
H H
We can solve this recursively by calculating for a given center point, the boundaries of the horizontal line and drawing that, then for those boundaries, calculating the top and bottom point of the vertical lines at those centers and drawing those, finally going deeper and repeat the pattern.
The total number of H we draw is linked to the depth: 4^depth, which is also the running time of our algorithm as we must go through all those points to draw the H.
Using a stack, we only add at most depth points to it from a given start, therefore keeping the space to a minimum.
You can check my implementation of drawHTree on my Gist. No tests for this since I didn't actually implement the line drawing portion.
Here is a problem where the challenge lies solely in correct index handling: given a NxM matrix (could be square) return an array which is the result of a clockwise spiral visit from top left corner.
Example:
12
34
result = 1,2,4,3
The problem description itself is the solution, we simply need to correctly set boundaries for our visit and process all elements in the matrix.
This is another exercise where drawing out a sample greatly helps with handling those boundary cases, I think the smallest sample that shows the correct logic is a 3x3 matrix.
We can view the matrix as a series of arrays wrapped around each other, and we process one of them each time.
We can do this in O(NM) time and O(1) space using 4 indices, representing the current boundaries:
By making our indices inclusive we have an easier time handling the logic. This means a boundary index indicates the first or last element we want to add (no out of bounds handling necessary)
Initially our boundaries are:
Then, until we have added all elements in the matrix to our result, we execute 4 loops in succession, each processing one of the four boundaries.
When each of these loops end, we update the boundaries for the next.
We walk the matrix in a spiral and always add the bounds working our way inside:
We can see that we need to move only ONE boundary after each loop by drawing a 3x3 matrix and executing this logic on it.
We can also see that while we do have 4 loops within one outer loop, we are only processing each element once.
You can check my implementation of spiralVisit on my Gist along with some tests in SpiralVisitJTests.
Here is another quite difficult problem: given an integer N, find how many valid binary search trees can be built using N nodes.
Being a problem on trees, we can try approaching it with recursion, which means we need to find some formula and base case to generalize the structure.
Drawing this problem out definitely helps reaching a solution, but the number of results grows quite rapidly even for small values of N so honestly spotting a pattern early was not super easy, N = 4 is the first where I think it's possible to see the recurrence.
Base case(s) are quite easy, a tree with 0 and 1 nodes can only be represented in one way: no nodes, or the single root.
Then we need to generalize, for a given root and at least another node, the root is one node and all remaining N-1 nodes can either be:
- all on the left side (keys are smaller than root)
- all on the right side (keys are bigger than root)
- some on the left and some on the right
The last case actually covers the previous two as well, we can simply see it as zero nodes being on the other side.
If some nodes are left and some are right and we are the root, it means some nodes in range 1..root-1 are on the left and nodes in range root+1..N are on the right, if we view all nodes as the numbers in the range 1..N and the root is value X, we will have the full sequence 1..X..N for a single value X.
Therefore for a given root, the number of ways its children can be combined is:
number of ways left subtree can be built * number of ways for right subtree can be built
If we repeat this process for all N possible roots, we get our final answer. Definitely using a cache here helps as the number of combinations rises terribly fast.
I am not sure if having the problem described as counting binary search trees rather than simply binary trees would help of complicate finding a solution, in any case, the answer is same for both.
It also turns out there is a sequence called Catalan numbers which represents exactly this pattern and is a special case of combinations. However, the n choose k formula involves factorials and for even small inputs, those can easily overflow the space of an integer. We can still use those numbers to test our solution though ;)
Both the top down and bottom up cached approaches will use O(N) space and O(N^2) time. As usual this is easier to see in the bottom up approach where we must explicitly run the inner loop to generate all 1..X..N combinations for the value of N being considered at that moment.
You can check my implementation of numOfBSTs and numOfBSTsBottomUp on my Gist along with some tests in NumOfBSTsJTests.
The GCD of two numbers is the biggest number that divides both. I was going through some books and found Euclid's formula, which I am fairly certain is one of those formulas I learned in the past and just forgotten.
Anyway, the book was mentioning it has complexity O(logN) where N is the sum of the two numbers:
gcd(a, b){
if(b == 0 ) return a;
return gcd(b, a % b);
}
However, this assumes the modulo operation is done in constant time regardless of the input numbers, a more realistic complexity is somewhere O(N logN) as the modulo might need to be computed in linear time.
A better approach uses bit operations instead and gives a O((logN)^2) time since the operations it uses can be computed in O(logN) time:
gcd(a, b){
return gcd(a, b, 1);
}
gcd(a, b, res){
if(a == b) return res * a;
if(a % 2 == 0 && b % 2 == 0) return gcd(a >> 1, b >> 1, res << 1);
if(a % 2 == 0) return gcd(a >> 1, b , res);
if(b % 2 == 0) return gcd(a, b >> 1, res);
if(a > b) return gcd(a - b, b, res);
return gcd(a, b - a, res);
}
As an added bonus, we can use this to compute the LCM which is the smallest number divisible by both:
lcm(a,b){
return a * b / gcd(a, b);
}
You can find gcd and lcm on my Gist.
Here is an easy one to balance the last, given an array representing the height of people standing behind each other from left to right, find how many people have an unobstructed view in front of them.
We can do this in O(N) time and constant space by walking the array from right to left tracking each time the tallest person we have found. If the current person is NOT taller than the current tallest, he won't be able to see.
You can check my implementation of witnessOfTheTallPeople on my Gist along with some tests in WitnessOfTheTallPeopleJtests.
Wow this exercise was harder than expected, also yay for String methods.
Given a string representing a filesystem, find the length of the longest path to a file.
The string has the following format (without spaces):
root \n \t dir \n \t \t file_in_dir.ext
which represents the path: root/dir/file_in_dir.ext that has a total length of 24 characters.
We are told filenames will always include a dot followed by an extension and directories will never contain a dot.
Given an array representing dominoes, determine the final position of each piece. Array contains the following chars:
. = domino is standing still
R = domino is falling right
L = domino is falling left
The original problem used a string as input, however that is simply an array of characters, therefore the logic is the same.
Example:
R. = RR
R.L = R.L as center piece is being pushed from both sides
R..L = RRLL as center pieces can fall once but the get stuck in the middle
We can scan the input twice, from left to right and then right to left trcking partial outcomes in two arrays.
We then scan both arrays and determine the final position of a piece with the following cominations:
We can get rid of the additional arrays altogether and just use the output array for all our operations. Still scan the array twice, first time left to right to determine which pieces would be falling right and we toggle a boolean to track whether pieces are falling right or not.
A piece falls right if it is AFTER another piece that also is falling right AND the NEXT piece is NOT falling left.
Second time we scan both input and partial result array right to left at the same time and repeat the process however we now have information about right falling pieces therefore we can determine the final domino position.
We use the same toggle to indicate whether pieces are falling left or not this time. We have the following cases:
We need to be careful in handling boundary cases for example when a piece that was standing still at the borders of the array is being pushed to fall, in that case no other force can balance it and we need to correctly update it to fall.
This provides a solution in O(N) time and constant space.
You can check my implementation of fallingDominoes on my Gist along with some tests in FallingDominoesJTests.