anonymous
BAN USER- 0of 0 votes
AnswersLRU Cache
- anonymous in United States| Report Duplicate | Flag | PURGE
Uber Senior Software Development Engineer Algorithm
@CookieMonster hey man, are you crazy? I believe you should stop to watch films about "conspiracy theory".
I didn't understand your last reply at all.
> "What is my main instrument? Your point about "only one hammer see nail yada yada" is actually a point against people who think in one or few languages."
I wrote about me, that my main instrument influenced me to the first comment, because "Hashtable" is a specific data structure in Java, after that I realized where I was wrong. That's all. I thought is was clear and what are you talking about in the last comment I have no idea.
> "Why are you arguing main instrument and blah blah over 1 min. coding exercises?"
This portal is created for the communication about any questions, what I'm actually doing. If you don't have anything to reply - your right is to be silent (or downvote).
I hope this debate is over, because it's already off top of actual coding question.
@CookieMonster thank you for the suggestion, of course I'm trying some other languages, but anyway you are working with your main instrument whole the day :)
Comments upvoting - it's not possible to up/downvote your own comments, it's the rule of this portal, so it's not me. How do people voting here is a separate topic, sometimes very strange.
To make sure that white cell will not be used second time we can pass the same boolean array 'visited' used on step (2) to step (3).
Another possible way is to flip the cell to black state once it's visited, in this case we don't even need array 'visited', but it's require modification of the initial array.
The worst case for 'findPath' that come to mind is when 'start' and 'target' cell will be located on different corners of the array, for example 'start = Cell(0,0)' and 'target = Cell(N-1, N-1)'. In this case it's require 2N memory to store cells in the queue + we use cells with the memorization.
public List<Cell> findPath(int[][] arr, boolean[][] visited,
Cell start, Cell target) {
final Queue<Cell> queue = new LinkedList<Cell>();
queue.add(start);
while (!queue.isEmpty()) {
final Cell current = queue.poll();
final int x = current.getX();
final int y = current.getY();
visited[x][y] = true;
final List<Cell> path = current.getPath();
path.add(current);
if (x == target.getX() && y == target.getY()) {
return path;
}
optionalQueueAdd(arr, visited, new Cell(x + 1, y, path), queue);
optionalQueueAdd(arr, visited, new Cell(x, y + 1, path), queue);
optionalQueueAdd(arr, visited, new Cell(x - 1, y, path), queue);
optionalQueueAdd(arr, visited, new Cell(x, y - 1, path), queue);
}
return null;
}
public void optionalQueueAdd(int[][] arr, boolean[][] visited,
Cell newCell, Queue<Cell> queue) {
if (newCell.getX() < arr.length &&
newCell.getY() < arr.length &&
newCell.getX() >= 0 &&
newCell.getY() >= 0 &&
!visited[newCell.getX()][newCell.getY()] &&
arr[newCell.getX()][newCell.getY()] != 1) {
queue.add(newCell);
}
}
Modification of BFS.
1. Find the gray cell in the array
2. Find and save path between (0,0) and gray cell index using 'findPath'
3. Find and save path between gray cell index and (N-1, N-1) using 'findPath'
4. Concatenate paths
The procedure 'findPath' could be optimized (with next steps checking only right and bottom cells).
Same, but a bit less code
public static Set<Set<String>> getSetPermutations(List<List<String>> lists) {
final HashSet<Set<String>> acc = new HashSet<Set<String>>();
getSetPermutations(new ArrayList<List<String>>(lists),
new HashSet<String>(), acc);
return acc;
}
private static void getSetPermutations(List<List<String>> lists,
Set<String> current,
Set<Set<String>> acc) {
if (lists.isEmpty()) {
acc.add(current);
return;
}
List<List<String>> listsLocal = new ArrayList<List<String>>(lists);
for (String s : listsLocal.remove(0)) {
final HashSet<String> set = new HashSet<String>(current);
set.add(s);
getSetPermutations(listsLocal, set, acc);
}
}
public static boolean match(String s1, String s2) {
if (s1.equals(s2))
return true;
if (isHeadWithAsterisk(s1) && match(s1.substring(2), s2))
return true;
if (isHeadWithAsterisk(s2) && match(s1, s2.substring(2)))
return true;
if (!s1.isEmpty() && !s2.isEmpty()) {
if (s1.charAt(0) == '*') return match(s1.substring(1), s2);
if (s2.charAt(0) == '*') return match(s1, s2.substring(1));
return matchChars(s1.charAt(0), s2.charAt(0)) &&
match(s1.substring(1), s2.substring(1));
} else {
return false;
}
}
private static boolean isHeadWithAsterisk(String s1) {
return s1.length() > 1 && s1.charAt(1) == '*';
}
private static boolean matchChars(char c1, char c2) {
return c1 == c2 || c1 == '.' || c2 == '.';
}
oh
while (s1p < s1.length() && s2p < s2.length()) {
if (s1.charAt(s1p) == s2.charAt(s2p)) {
builder.append(s1.charAt(s1p));
s1p++;
s2p++;
} else {
s2p = s2p - s1p + 1;
s1p = 0;
builder.setLength(0);
}
}
Working for the all above examples.
Do you have a full set of test cases?
Nice catch.
It's simple to fix that changing the while loop:
while (s1p < s1.length() && s2p < s2.length()) {
if (s1.charAt(s1p) == s2.charAt(s2p)) {
builder.append(s1.charAt(s1p));
s1p++;
s2p++;
} else {
s1p = 0;
s2p -= s1p + 1;
builder.setLength(0);
}
}
Unfortunately the complexity is growing from nice O(n) to O(n^2) in worst case.
- anonymous October 16, 2013public static String longestPrefixSuffix(String s1, String s2) {
final StringBuilder builder = new StringBuilder();
int s1p = 0;
int s2p = 0;
while (s1p < s1.length() && s2p < s2.length()) {
if (s1.charAt(s1p) == s2.charAt(s2p)) {
builder.append(s1.charAt(s1p));
s1p++;
} else {
s1p = 0;
builder.setLength(0);
}
s2p++;
}
return builder.toString();
}
We can create two pointers, for the first and the second string. Increment second each iteration, first increment if there is the matching, if matching is not present - reset pointer and temporary result.
- anonymous October 16, 2013
In the tree each node should be a "child" of 0 (root) or 1 "parent". In this case if some "child" presented in the list of pairs (parent, child) twice or more - than the tree have cycles.
- anonymous November 28, 2013Searching the duplicates in the list is known algorithm that could be solved by O(n).