renegade403
BAN USERThe obvious solution is the brute force one having (4^16)*48 steps (48 steps to check it). It can be reduced by using permutations of 1234 on each row. The total number of steps will be (4!*4!*4!*4!)*32 (32 steps to check it, since we don't need to check each row now).
This can be easily implemented in a dfs manner.
public void dfs(int r, int c, int[][] map, boolean[] values) {
if (r == 4 && c == 0) {
check(map);
return;
}
for (int i = 0; i < 4; i++) {
if (!values[i]) {
map[r][c] = i + 1;
values[i] = true;
if (c == 3) {
dfs(r + 1, 0, map, new boolean[4]);
} else {
dfs(r, c + 1, map, values);
}
values[i] = false;
}
}
}
The interesting thing would be the check method. It can be written in a very clean way for each of the small 2X2 squares.
Here's the complete code. Works perfectly :)
import java.util.ArrayList;
public class Impromptu {
ArrayList<int[][]> list = new ArrayList<int[][]>();
int[] dx = { 0, 1, 1, 0 };
int[] dy = { 0, 0, 1, 1 };
public void dfs(int r, int c, int[][] map, boolean[] values) {
if (r == 4 && c == 0) {
check(map);
return;
}
for (int i = 0; i < 4; i++) {
if (!values[i]) {
map[r][c] = i + 1;
values[i] = true;
if (c == 3) {
dfs(r + 1, 0, map, new boolean[4]);
} else {
dfs(r, c + 1, map, values);
}
values[i] = false;
}
}
}
public int[][] clone(int[][] map) {
int[][] ret = new int[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
ret[i][j] = map[i][j];
}
}
return ret;
}
public void print(int[][] map) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
System.out.print(map[i][j]);
}
System.out.println("");
}
System.out.println("------------------");
}
public boolean check(int[][] map) {
int r = 0, c = 0;
for (int i = 0; i < 4; i++) {
int nr = r + 2 * dy[i];
int nc = c + 2 * dx[i];
boolean[] vals = new boolean[5];
for (int j = 0; j < 4; j++) {
int ncc = nc + dx[j];
int nrr = nr + dy[j];
if (vals[map[nrr][ncc]]) {
return false;
} else
vals[map[nrr][ncc]] = true;
}
}
for (int j = 0; j < 4; j++) {
boolean vals[] = new boolean[5];
for (int i = 0; i < 4; i++) {
if (vals[map[i][j]]) {
return false;
} else
vals[map[i][j]] = true;
}
}
list.add(clone(map));
print(map);
return true;
}
public static void main(String args[]) {
new Impromptu().dfs(0, 0, new int[4][4], new boolean[4]);
}
}
I thought of the exact same solution!! The only reason deletion in the Java/C++ api linked list is O(n) is because we don't have the reference to the link we want to delete, so we search in O(n). But in this case, the operations are internal and thus the references can be saved. We could keep storing the newly added url nodes' reference in a HashMap. If the new url already exists in the map, get its reference, delete it, update reference. All in O(1).
- renegade403 January 12, 2015What is the point of using 2 loops? each task can be assigned to one of the eight servers so total complexity is 8^8. So in each step of the dfs, you get 8 choices of server for each task. A simple 15 line code would do :)
public boolean dfs(int pos, int[] tasks, int[] servers) {
boolean result = false;
if (pos >= tasks.length)
return true;
for (int i = 0; i < servers.length; i++) {
if (servers[i] - tasks[pos] >= 0) {
servers[i] -= tasks[pos];
result |= dfs(pos + 1, tasks, servers);
servers[i] += tasks[pos];
}
}
return result;
}
Assumption: the dictionary is a text file containing all words separated by spaces.
Complexity:
Can be loaded in memory : O(1)
Cannot be loaded in memory: O(n)
So, we'd just sort up the input word and make up sorted strings of all possible lengths i.e. from 2 to 4 eg: ogeg = oegg = oe,og,gg,oeg,ogg,egg. This can be done in constant time.
While making the dictionary out of the text file, we can take each word, sort it and add it to a HashMap<String,ArrayList<String>> that could store all the words with a given set of letters. Since this is pre-processing, it can also be achieved in constant time. All you gotta do now homie is check those words created in the hashtable. So overall constant.
If we cannot load the dictionary in the memory, the problem clearly becomes a string matching problem, which can be solved in O(n) using Z-Algorithm. Just makeup all the possible permutations (4! + 4C3*3!+ 4C2*2!) and search'em up!
Hey this question can be solved in O(n) easily.
I'm assuming overlapping of the pairs is allowed.
Just maintain an array of number of occurrences of every letter before a certain index in an array like dp[i][c] i=index, c=character. And for every possible pair, once you find the second char add the number of occurences of the first char before the index.
Here's a working Java code
public int getTotal(String s) {
char[] in = s.toCharArray();
int n = in.length;
int[][] dp = new int[n][26];
for (int j = 0; j < 26; j++) {
if (in[0] - 'a' == j)
dp[0][j]++;
for (int i = 1; i < n; i++) {
dp[i][j] = dp[i - 1][j];
if (in[i] - 'a' == j)
dp[i][j]++;
}
}
int res = 0;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
int occ = 0;
for (int k = n - 1; k > 0; k--) {
if (in[k] - 'a' == i) {
occ += dp[k - 1][j];
}
}
if (occ > 1){
System.out.println(((char)(j+'a'))+" "+((char)(i+'a')));
res += 1;}
}
}
return res;
}
Even a non overlapping version can be made by recursion. It would still be O(n).
- renegade403 January 03, 2015
You should not inherit the player class. Player must be an interface so that different classes can call .initialize() and .play() functionality depending on what they are playing. Hardcoded inheritance of a class whose implementation varies for different types of files is a bad OOP design.
- renegade403 January 17, 2015