Scavi
BAN USERI don't see your problem @dummy. The questions are good to practice. He/She might get the questions from searching the net, or from banned interview lists or ...
The questions are to learn, to prepare and to improve your ability. If you hope to see the same questions during the interviews at companies like Amazon and Google you need to have quite a lot of luck because they remove interview questions frequently from their lists if they are public ;-)
Assuming that everything fits into memory and we don't need an iterator I would use a sliding window approach. O(m) space and O(n) time while m represents the words of the lookup paragraph words and n the number of characters in the entire paragraph.
public int shortestDistance(@Nonnull final String paragraph, @Nonnull final String lookupParagraph) {
if (lookupParagraph.length() == 0) {
throw new IllegalArgumentException();
}
String[] lookupWords = lookupParagraph.split(" ");
Map<String, Integer> foundWordCount = new HashMap<>();
Set<String> searchWords = new HashSet<>();
initialize(lookupWords, foundWordCount, searchWords);
int startSlidingWindow = 0;
int currentWordCount = 0;
int minWordCount = Integer.MAX_VALUE;
StringBuilder currentWord = new StringBuilder();
for (int i = 0; i < paragraph.length(); ++i) {
char c = paragraph.charAt(i);
if (isInWord(c)) {
currentWord.append(c);
} else {
String word = currentWord.toString();
currentWord = new StringBuilder();
// test the current word
if (word.length() > 0) {
currentWordCount++;
// found the word, remove it from the search words and increment the existence count for the
// sliding window
if (foundWordCount.containsKey(word)) {
foundWordCount.put(word, foundWordCount.get(word) + 1);
if (searchWords.contains(word)) {
searchWords.remove(word);
}
}
if (searchWords.size() == 0) {
for (int j = startSlidingWindow; j < i; ++j) {
char c2 = paragraph.charAt(j);
if (isInWord(c2)) {
currentWord.append(c2);
} else {
if (currentWord.length() > 0) {
String tmpWord = currentWord.toString();
if (foundWordCount.containsKey(tmpWord)) {
if (foundWordCount.getOrDefault(tmpWord, 0) > 1) {
foundWordCount.put(tmpWord, foundWordCount.get(tmpWord) - 1);
}
// stop sliding
else {
break;
}
}
startSlidingWindow = j;
currentWordCount--;
}
currentWord = new StringBuilder();
}
}
minWordCount = Math.min(currentWordCount, minWordCount);
}
}
currentWord = new StringBuilder();
}
}
return minWordCount;
}
private void initialize(final String[] lookupWords, final Map<String, Integer> foundWordCount, final Set<String>
searchWords) {
for (String lookupWord : lookupWords) {
searchWords.add(lookupWord);
foundWordCount.put(lookupWord, 0);
}
}
private boolean isInWord(final char c) {
return (c >= 65 && c <= 90) || (c >= 97 && c <= 122);
}
public int findPlace(@Nonnull final boolean[] input) {
int pos = 0;
int maxDistance = 0;
int left = 0;
int right = 0;
for (int i = 0; i < input.length; ++i) {
if (input[i]) {
if (left == 0 && !input[0]) {
pos = 0;
} else {
pos = right - left > maxDistance ? left + ((right - left) / 2) : pos;
}
left = right;
} else if (i == input.length - 1) {
pos = right - left > maxDistance ? i : pos;
} else {
maxDistance = Math.max(maxDistance, right - left);
}
right++;
}
return pos;
}
/**
* The algorithm takes O(k) space (for PriorityQueue and HashMap).
* The runtime is (O (k) + O((n - k) log k) to build up the heap and O(n) to iterate through the length of the matrix.
*/
public int findShortestPath(@Nonnull int[][] matrix, int k) {
if (matrix.length == 0 || matrix[0].length == 0 || matrix[0].length != matrix.length) {
return -1;
}
PriorityQueue<Integer> minHeapForMaxDistance = new PriorityQueue<>(k);
int currentDistance = 0;
// determine the longest distances that will be skipped later. The longest distance will be added
// into the min heap. If the current distance is > then the min, it will be replaced.
// This takes (O (k) + O((n - k) log k)
for (int i = 1; i < matrix.length; ++i) {
currentDistance = matrix[i - 1][i];
while (minHeapForMaxDistance.size() >= k &&
minHeapForMaxDistance.peek() < currentDistance) {
minHeapForMaxDistance.poll();
}
if (minHeapForMaxDistance.size() < k) {
minHeapForMaxDistance.offer(currentDistance);
}
}
int shortestPath = 0;
// after we found all max distances, we put them into a HashMap. The key is the max distance and the value the
// amount of max distances in the matrix. s represents source, t represents target position.
Map<Integer, Integer> maxDistances = from(minHeapForMaxDistance);
for (int s = 0, t = 1; t < matrix.length; ++t) {
currentDistance = matrix[s][t];
// found a max distance. Skip it. e.g. the path from a-800->b-300->c and a-400->c. B will be skipped
// and a->c will be used.
if (maxDistances.containsKey(currentDistance) &&
maxDistances.get(currentDistance) > 0) {
maxDistances.put(currentDistance, maxDistances.get(currentDistance) - 1);
} else {
shortestPath += currentDistance;
s = t;
}
}
return shortestPath;
}
/**
* Converts the priority queue to the HashMap. The key is the distance, the value the amount of the distance.
*/
private Map<Integer, Integer> from(PriorityQueue<Integer> minHeapForMaxDistances) {
Map<Integer, Integer> maxDistances = new HashMap<>();
int current;
while (!minHeapForMaxDistances.isEmpty()) {
current = minHeapForMaxDistances.poll();
if (maxDistances.containsKey(current)) {
maxDistances.put(current, maxDistances.get(current) + 1);
} else {
maxDistances.put(current, 1);
}
}
return maxDistances;
}
EDIT: On second thought this approach might not work in case we have the same max distance more then k times. Then there is a difference how we follow the path
- Scavi November 30, 2017public int minCost(final int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return -1;
}
for (int x = 1; x < matrix[0].length; ++x) {
matrix[0][x] = Math.max(matrix[0][x], matrix[0][x - 1]);
}
for (int y = 1; y < matrix[0].length; ++y) {
matrix[y][0] = Math.max(matrix[y][0], matrix[y - 1][0]);
}
for (int y = 1; y < matrix.length; ++y) {
for (int x = 1; x < matrix[0].length; ++x) {
matrix[y][x] = Math.max(matrix[y][x], Math.min(matrix[y][x - 1], matrix[y - 1][x]));
}
}
return matrix[matrix.length - 1][matrix[0].length - 1] - matrix[0][0];
}
public List<int[]> shortestPath(final int[][] matrix) {
int minPath = minCost(matrix);
if (minPath == -1) {
return null;
}
List<int[]> path = new ArrayList<>(matrix.length + matrix[0].length - 1);
int x = matrix[0].length - 1;
int y = matrix.length - 1;
addPath(path, x, y);
while (x != 0 || y != 0) {
if (x > 0 && y > 0) {
if (matrix[y - 1][x] > matrix[y][x - 1]) {
addPath(path, x - 1, y);
--x;
} else {
addPath(path, x, y - 1);
--y;
}
} else if (x > 0) {
addPath(path, x - 1, y);
--x;
} else {
addPath(path, x, y - 1);
--y;
}
}
return path;
}
private void addPath(final List<int[]> path, final int x, final int y) {
path.add(new int[]{x, y});
}
Create a directed weighted graph out of the given list ( a-100->b , b -200->c, e-200->f, ...). Then you can either use BFS or dijkstra and stop after two followup. Keep track of the parent node and the distance.
I would prefer dijkstra (with a good datastructure) over BFS because dijkstra follows the shortest path while BFS that just all possible steps.
The second followup is pretty neat! If somebody finds something better then (#shortestStringOfAllBin) it would be great (or if somebody points out that my solution is wrong ;-))
k = 1 => 2
k = 2 => 5
k = 3 => 10
k = 4 => 18
k = 5 => 37 (already takes ~4 seconds)
// first question: O(2^k * k) space and runs in O(n) time (while n is the length of the input string)
public boolean checkBinariesExisting(final String input, final int k) {
if (input == null || k > input.length()) {
return false;
}
Set<String> binary = new HashSet<>();
for (int i = 0; i < 1 << k; ++i) {
binary.add(createBinString(k, i));
}
String temp;
for (int i = 0; i <= input.length() - k && !binary.isEmpty(); ++i) {
temp = input.substring(i, i + k);
if (binary.contains(temp)) {
binary.remove(temp);
}
}
return binary.size() == 0;
}
// first followup (lazy solution)
public String stringOfAllBin(final int k) {
if (k < 0) {
return null;
}
int length = 1 << k;
StringBuilder temp = new StringBuilder(length * k);
for (int i = 0; i < length; ++i) {
temp.append(createBinString(k, i));
}
return temp.toString();
}
// second followup:runs in O(2^ (k² - 2) ) * k and uses constant space
public String shortestStringOfAllBin(final int k) {
if (k < 0) {
return null;
}
int length = 1 << k;
String current = createBinString(k, length - 1) + createBinString(k, 0);
return shortestStringOfAllBin(current, k, length - 2);
}
private String shortestStringOfAllBin(final String current, final int k, final int i) {
if (i <= 0) {
return current;
} else {
String newBinary = createBinString(k, i);
String result = null;
// search pruning - the new binary exists already in the current string
if (Pattern.compile(newBinary).matcher(current).find()) {
result = shortestStringOfAllBin(current, k, i - 1);
}
// the current newBinary doesn't exist yet in the current
else {
String tempResult = null;
for (int j = newBinary.length(); j > 0; --j) {
String binaryPart = newBinary.substring(0, j);
String overlapping = newBinary.substring(j, newBinary.length());
// try to add the current string part from the left side
if (j == newBinary.length() || current.startsWith(overlapping)) {
tempResult = shortestStringOfAllBin(binaryPart + current, k, i - 1);
}
result = result == null || result.length() > tempResult.length() ? tempResult : result;
// try to add the current string part from the right side
if (j == newBinary.length() || current.endsWith(overlapping)) {
tempResult = shortestStringOfAllBin(current + binaryPart, k, i - 1);
}
result = result == null || result.length() > tempResult.length() ? tempResult : result;
}
}
return result;
}
}
private String createBinString(final int k, final int i) {
return String.format("%0" + k + "d", Integer.valueOf(Integer.toBinaryString(i)));
}
public String decode(final String input) {
if (input == null || input.length() == 0) {
return null;
}
int balance = 0;
for (char c : input.toCharArray()) {
if (c == '(') {
balance++;
} else if (c == ')') {
balance--;
}
}
StringBuilder result = new StringBuilder(input.length());
int currentBracketBalance = 0;
for (char c : input.toCharArray()) {
if (c == '(') {
currentBracketBalance++;
if (balance > 0) {
result.append(-1);
balance--;
} else {
result.append(0);
}
} else if (c == ')') {
if (currentBracketBalance > 0) {
result.append(1);
} else {
result.append(-1);
}
--currentBracketBalance;
} else {
result.append(c);
}
}
return result.toString();
}
public int longestChain(@Nonnull Map<String, String> relationships) {
int count = 0;
Map<String, Integer> cache = new HashMap<>();
for (Map.Entry<String, String> relationship : relationships.entrySet()) {
count = Math.max(count, longestChain(relationships, cache, relationship.getKey()));
}
return count;
}
private int longestChain(@Nonnull Map<String, String> relationships, Map<String, Integer> cache, String lookup) {
int count = 0;
if (cache.containsKey(lookup)) {
count = cache.get(lookup);
}
else if (relationships.containsKey(lookup)) {
String newLookup = relationships.get(lookup);
count = 1 + longestChain(relationships, cache, newLookup);
cache.put(lookup, count);
}
return count;
}
@Test
public void test1() {
Map<String, String> relationships = new HashMap<>();
relationships.put("beidu", "ofo");
relationships.put("mobike", "alibaba");
relationships.put("alibaba", "somethingElse");
relationships.put("cookies", "mobike");
int result = new CompanyMerger().longestChain(relationships);
assertThat(result).isEqualTo(3);
}
@Test
public void test2() {
Map<String, String> relationships = new HashMap<>();
relationships.put("foo", "bar");
relationships.put("bar", "abc");
relationships.put("abc", "ooo");
relationships.put("ooo", "xyz");
relationships.put("xyz", "cookies");
int result = new CompanyMerger().longestChain(relationships);
assertThat(result).isEqualTo(5);
}
The worst case runtime behaviour is O(n * m) while n is the number of key-entries in the relationship and m the number of relationships between the companies.
I used an additional cache to store already calculated distance of relationships. It reduces the recursive calls if we have a company multiple times (e.g. in test1 mobike->alibaba->somethingElse (2) and cookies->mobike reuses the calculated value of 2).
Due to the cache the best case is O(n) if you have something like in test2.
public int determineMinimumMoves(Point positionPlayer1, Point positionPlayer2,
final Point... gems) {
if (positionPlayer1 == null) {
throw new IllegalArgumentException("Player 1 is null");
} else if (positionPlayer2 == null) {
throw new IllegalArgumentException("Player 2 is null");
}
int moves = 0;
if (gems != null) {
for (Point gemPosition : gems) {
final int distancePlayer1ToGem = positionPlayer1.distanceTo(gemPosition);
final int distancePlayer2ToGem = positionPlayer2.distanceTo(gemPosition);
// player 2 is closer - move player 2
if (distancePlayer1ToGem > distancePlayer2ToGem) {
positionPlayer2 = gemPosition;
}
// player 1 is closer or distance is equal - move player 1
else {
positionPlayer1 = gemPosition;
}
moves += Math.min(distancePlayer1ToGem, distancePlayer2ToGem);
}
}
return moves;
}
public class Point {
private final int _x;
private final int _y;
/**
* Constructor
*
* @param x the x position of the current point
* @param y the y position of the current point
*/
public Point(final int x, final int y) {
this._x = x;
this._y = y;
}
/**
* Determines the distance between the current and the given point. All 8 movement directions
* are allowed.
* <p/>
* This algorithm determines the max distance of x1 -> x2 and y1 -> y2. Because all 8 movement
* directions are allowed, this is the distance between both points
*
* @param otherPoint the other point
* @return the distance between the current point and the other point
*/
public int distanceTo(final Point otherPoint) {
int disX = Math.abs(_x - otherPoint.getX());
int disY = Math.abs(_y - otherPoint.getY());
return Math.max(disX, disY);
}
/**
* @return the x position of the current point
*/
public int getX() {
return _x;
}
/**
* @return the y position of the current point
*/
public int getY() {
return _y;
}
}
public static final int countBits(final byte input, final int lookupBit) {
int counter = 0;
int tmpInput = input;
if (tmpInput != 0) {
while (tmpInput != 0) {
if ((tmpInput & lookupBit) == lookupBit) {
counter++;
}
tmpInput = tmpInput >>> 1;
}
} else {
if (lookupBit == 0) {
counter++;
}
}
return counter;
}
public static final boolean checkIfByteHas3OneBits(final byte input) {
final int oneBits = countBits(input, 1);
return oneBits == 3;
}
- Scavi January 09, 2018