EPavlova
BAN USERclass Range implements Comparable<Range>{
private int l;
private int r;
private double cost;
public Range(int i, int j, int k) {
l = i;
r = j;
cost = k;
}
@Override
public int compareTo(Range obj) {
if (r == obj.r) {
return obj.l - l;
}
return r - obj.r;
}
}
double minCost(Range[] ranges, int L, int R) {
double[] dp = new double[R + 1];
for (int j = L + 1; j <= R; j++) {
double min = Double.MAX_VALUE;
int i = ranges.length - 1;
while (i >= 0) {
if (ranges[i].r >= j&& ranges[i].l < j) {
if (dp[ranges[i].l] != -1 && dp[ranges[i].l] + ranges[i].cost < min) {
min = dp[ranges[i].l] + ranges[i].cost;
}
}
i--;
}
if (min == Double.MAX_VALUE) {
dp[j] = -1;
}
else
dp[j] = min;
}
return dp[R];
}
dynamic programming O(n^2)
class Range implements Comparable<Range>{
private int l;
private int r;
private double cost;
public Range(int i, int j, int k) {
l = i;
r = j;
cost = k;
}
@Override
public int compareTo(Range obj) {
if (r == obj.r) {
return obj.l - l;
}
return r - obj.r;
}
}
double minCost(Range[] ranges, int L, int R) {
Arrays.sort(ranges);
double[] dp = new double[R + 1];
for (int j = L + 1; j <= R; j++) {
double min = Double.MAX_VALUE;
int i = ranges.length - 1;
while ( i >= 0 && ranges[i].r >= j) {
if (ranges[i].l < j) {
if (dp[ranges[i].l] != -1 && dp[ranges[i].l] + ranges[i].cost < min) {
min = dp[ranges[i].l] + ranges[i].cost;
}
}
i--;
}
if (min == Double.MAX_VALUE) {
dp[j] = -1;
}
else
dp[j] = min;
}
return dp[R];
}
void partition(int[] nums, int pos, List<Integer> res) {
if (nums.length == pos) {
int set = -1;
int i = 0;
String str = "";
for (Integer j : res) {
if (j != set) {
if (set != -1)
System.out.print(")");
set = j;
System.out.print("(");
}
System.out.print(nums[i] +"");
System.out.print(str +"");
i++;
}
System.out.print(")");
System.out.println();
}
else {
int s = pos == 0? 1:res.get(pos - 1);
int t = pos == 0?1:s+1;
for (int i = s; i <= t; i++) {
res.add(i);
partition(nums, pos + 1, res);
res.remove(res.size() - 1);
}
}
}
ArrayList<Integer> res = new ArrayList<Integer>();
gp.partition(new int[]{1,2,3,4}, 0, res);
Here is my code ,which use Acho Corasic algorithm with time complexity O(n+m+k), where n is stream length, m - total length of dictionary world, k - number of appearance of dict keys in text.
Trie could be implemented with only HashMap, but I decided for the sake of clarity to implement class Trie with internal class TrieNode
class Trie {
TrieNode root = new TrieNode();
class TrieNode {
private List<Integer> output;
private TrieNode link;
private Map<Character,TrieNode> children;
private boolean end;
public TrieNode() {
output = new ArrayList<>();
children = new HashMap<Character,TrieNode>();
link = root;
}
public Map<Character,TrieNode> getChildren() {
return children;
}
public TrieNode getLink() {
return link;
}
public void setLink(TrieNode lnk) {
link = lnk;
}
public boolean hasChild(char ch) {
return children.get(ch)!=null;
}
public TrieNode getChild(char ch) {
return children.get(ch);
}
public List<Integer> getOutput() {
return output;
}
public void addOutput(List<Integer> ls) {
output.addAll(ls);
}
public void addOutput(int index) {
output.add(index);
}
TrieNode add(char ch) {
TrieNode node = children.get(ch);
if (node == null) {
node = new TrieNode();
children.put(ch, node);
}
return node;
}
void setEnd(boolean isEnd) {
end = isEnd;
}
}
public void add(String key, int index) {
TrieNode current = root;
for (char ch : key.toCharArray()) {
current = current.add(ch);
}
current.setEnd(true);
current.addOutput(index);
}
public TrieNode getRoot() {
return root;
}
}
//------------------------------------------------------------------------------------------------------------
Map<String,Integer> getWordCount(String input, String[] dict) {
Trie trie = new Trie();
Map<String,Integer> res = new HashMap<>();
for (int index =0; index < dict.length; index++) {
String key = dict[index];
trie.add(key, index);
}
Queue<TrieNode> q = new java.util.LinkedList<>();
trie.getRoot().setLink(trie.getRoot());
q.add(trie.getRoot());
TrieNode root = trie.getRoot();
while (!q.isEmpty()) {
TrieNode parent = q.remove();
for(Entry<Character,TrieNode> childEntry : parent.getChildren().entrySet()) {
TrieNode child = childEntry.getValue();
char ch = childEntry.getKey();
if (parent != root) {
TrieNode link = parent.getLink();
while (!link.hasChild(ch)) {
link = link.getLink();
if (link == root)
break;
}
if (link.hasChild(ch)) {
TrieNode childLink = link.getChild(ch);
child.setLink(childLink);
child.addOutput(childLink.getOutput());
}
}
q.add(child);
}
}
TrieNode current = root;
for (char ch : input.toCharArray()) {
while (!current.hasChild(ch)) {
current = current.getLink();
if (current == root)
break;
}
if (current.hasChild(ch)) {
current = current.getChild(ch);
countWords(current.getOutput(), res, dict);
}
}
return res;
}
Here is a possible solution with the stipulation that I assume that it is given a set of digraphs in advance and each digraph has a its own place in the alphabet, for example we have a, b, c, ch,cz,d,e,f ...z n. Ofcourse I don't pretend that algorithm is correct when I don't know concrete details of the problem, just try to solve the problem with my own assumptions.
Time complexity O(n)
Set<String> digraphs = new HashSet<>();
boolean isDigraph(String word) {
if (word.length() < 2)
return false;
return digraphs.contains(word.substring(0,2));
}
int compare(String a, String b) {
if(a.length() == 0 && b.length() == 0)
return 0;
else if(a.length() == 0){
return -1;
} if(b.length() == 0){
return 1;
}
else {
if (a.charAt(0) != b.charAt(0))
return a.charAt(0) < b.charAt(0)? -1 : 1;
else {
if (isDigraph(a) && isDigraph(b)) {
if(a.charAt(1) != b.charAt(1))
return a.charAt(1) < b.charAt(1)? -1 : 1;
else
return compare(a.substring(2), b.substring(2));
}
else if(isDigraph(a)) {
return 1;
}
else if(isDigraph(b)) {
return -1;
}
else
return compare(a.substring(1), b.substring(1));
}
}
}
The problem could be solved with dynamic programming O(n^3)
the recursive relation is cost[i][j] = max(cost[i][K - 1] + cost[K+1][j] + nums[i-1]*nums[K]*nums[j+1]
where cost[i][j] means cost taken when all ballons in [i..j] range are burst before ballons at i - 1 and j+1. With other words, cost to burst all ballons in range [i..j] before ballons at i - 1 and j + 1 have been burst is max by K element in range [i..j]:
cost of burst in range[i..K - 1] before burst ballon K and ballon i - 1 +
cost of burst in range[k + 1, j] before burst ballon k and ballon j+ 1 +
cost of burst of K-th ballon (that is nums[K]*nums[i-1]*nums[j+1] because all ballons between K and i and K and j have been already burst and ballons i -1, K and j +1 become adjacent.
Yes, definitely your implementation could be improved as we keep for each word - list of its position in the text. They are stored in ascending order. We will iterate through the position lists of two words and calculate the min distance between positions O(min(m,n)) where m , n - lengths of two words
class ShortestDistance {
private Map<String,List<Integer>> distance;
public ShortestDistance(String[] words) {
distance = new HashMap<>();
for (int i = 0; i < words.length; i++) {
if (distance.get(words[i]) == null) {
distance.put(words[i],new ArrayList<Integer>());
}
distance.get(words[i]).add(i);
}
}
public int shortestDistance(String word1, String word2) {
int min = Integer.MAX_VALUE;
List<Integer> ls1 = distance.get(word1);
List<Integer> ls2 = distance.get(word2);
int i = 0;
int j = 0;
while (i < ls1.size() && j < ls2.size()) {
if (ls1.get(i) < ls2.get(j)) {
min = Math.min(min,Math.abs(ls1.get(i) - ls2.get(j)));
i++;
}
else {
min = Math.min(min,Math.abs(ls1.get(i) - ls2.get(j)));
j++;
}
}
return min;
}
}
Shouldn't max len for {1, 2, 51, 50, 60, 55, 70, 68, 80, 76, 75, 12, 45} be 10?
2- 51 - 50 -60 - 55 -70-68-75-12-45
Problem could be solved using dynamic programming technicue for O(n^2) time complexity.
We define two recursive function rise[i] = Max (fall[j] ) + 1 for j < i
and fall[i] = Max (rise[j] ) + 1 for j < i. rise[i] means length of longest subsequence that end in index i with rise, fall[i] is the opposite. We can store current subsequence in additional memory while we calculate up and fall function.
Let's use Failure function of KMP algorithm. First calculate it. Then iterate the array and each time get Failure[i] which is the end of the longest prefix that is suffix to the substring[0...i]
We check if next character a[i +1] is great than arr[Failure[i]+1].That's is the place where we have first unmatch.
In case it is greater, we have found the longest substring that is lexicographic great than our string S. Otherwise we continues to iterate the array with incremented i. Time complexity - O(n), space complexity O(n).
String longestSubstring(String str) {
int[] failure = new int[str.length()];
failure[0] = -1;
int i = 1;
//compute failure function
while (i < str.length()) {
int cur = failure[i - 1];
while (str.charAt(i) != str.charAt(cur + 1)) {
if (cur != -1)
cur = failure[cur];
else
break;
}
if (str.charAt(i) == str.charAt(cur + 1)) {
failure[i] = cur + 1;
}
else
failure[i] = -1;
i++;
}
String res = null;
for (i = 1; i < str.length() - 1; i++) {
if (failure[i] == -1) {
if (str.charAt(0) < str.charAt(i)) {
res = str.substring(i);
break;
}
}
else {
if (str.charAt(failure[i] + 1) < str.charAt(i + 1)) {
res = str.substring(i - failure[i]);
break;
}
}
}
if (str.charAt(0) < str.charAt(i))
return str.substring(i);
return res;
}
Let's use Failure function of KMP algorithm. First calculate it. Then iterate the array and each time get Failure[i] which is the end of the longest prefix that is suffix to the substring[0...i]
We check if next character a[i +1] is great than arr[Failure[i]+1].That's is the place where we have first unmatch.
In case it is greater, we have found the longest substring that is lexicographic great than our string S. Otherwise we continues to iterate the array with incremented i. Time complexity - O(n), space complexity O(n).
About this problem could you share with us if recruiter gave you hint. Did hi mentioned how many are approximately the images. I see two approaches actully - dynamic programming and brute force soluiton with backtrack. The problem in my dynamic approach is the my state is too big - all possible configurations of pictures (visited, not visited(. Is there a way to decrease state?
- EPavlova March 14, 2016Just a comment. I was thinking a little bit on the approach you suggest. I could speculate on what happens.
You are going to create suffix trie, but a trie with keywords which are first 10 letters from each suffix in DNA sequence. You are going to generate iterative, in sense first check if 10 -letter prefix of given suffix is in trie, if so return it as dublicate , if it is not dublicate you will add it to suffix trie ( trie from all 10 prefix of all suffixes of DNA). Complexity is again O(n) and it is dubious if it is better solution than hashing.
With hashing , complexity is O(n) where n - length of DNA sequence.
I don't think that using tries you will achieve complexity better than O(n).
What hash function did you suggest to the interviewer?
You could create suffix tree for O(n) time and check all 10-letter DNA if there is dublicate in suffix tree , but it is also O(n) approach and I don't think that interviewer expect to use suffix tree approach for 45 minutes
As it was mentioned above there is recursive dependancy:
number of ways sum X could be calculated from n dice with m face is equal to
number of ways sum X - 1 could be calculated from n - 1 dice with m face +
number of ways sum X - 2 could be calculated from n - 1dice with m face +...
number of ways sum X - m could be calculated from n - 1 dice with m face
We use dymamic programming because of overlapping subproblems and optimal substructure.
int numberOfWays(int n, int m, int sum) {
int[][] ways = new int[n + 1][sum + 1];
int min = Math.min(sum,m);
for(int i = 1; i<= min; i++) {
ways[1][i] = 1;
}
for (int i = 2; i <= n ;i++) {
for (int j = 1; j <= sum ; j++)
for (int k = 1; k <= m && k < j; k++)
ways[i][j] += ways[i-1][j - k];
}
return ways[n][sum];
}
Time complexity is O(sum*m*n)
- EPavlova March 10, 2016My solution is a little bit more optimal in time - could be O(n) or O(nlog) depending on the sort algorithm used to sort HashMap. In this solution I use TreeMap, so complexity is O(nlogn) time and O(n) space.
The idea is to traverse root, right, left the tree and each time you go left to hash current element with parent hash - 1, and when you go right to hash with parent hash + 1.
Here is some impl. As I mentioned above in case I use ordinary HashMap with no order characterisitcs and sort hash keys with counting sort by hash value, time complexity could optimize to O(n)
TreeMap<Integer,ArrayList<TreeNode>> tree = new TreeMap<>();
void verticalTraverse(TreeNode root, int pos) {
if(root == null)
return;
if (!tree.containsKey(pos))
tree.put(pos,new ArrayList<TreeNode>());
tree.get(pos).add(root);
verticalTraverse(root.right, pos + 1);
verticalTraverse(root.left, pos - 1);
}
For a0 = 1, till max_value a[0] could be (there is a constraints on the sums) try to generate all numbers taking into the account the current minimum sum. Each time we add new number we generate all sums of given number and previously added numbers and check if these sums actually exists, if not we try with another a[0] (first) number. If all sums exists we generate next number as difference between current minimum sum and a[0].
- EPavlova February 23, 2016Could you explain what is given - sum of pairs or sum of pairs and numbers in the beginning. Initally I tought that we have only sum of pair of numbers and should find numbers in these sums, without having then in advance, but after I had a look on the proposed solutions , I noticed that you assume that you have numbers and their sum in unordered way and has to guess which numbers belongs to which sum. Please explain better
- EPavlova February 23, 2016I still think that we have some string X and should find all words from dictionaries that formed the same X where they make sentence S and and S is transformed to X ( transformation means - remove whitespace and shuffle random letters in each word) . So if there are word's anagrams they also could form some new S.
For example - one case for X = "Ajavdoeceehr" is java, code , here is hava, code here are part of dictionary or could be some word dictionary for example Javdao ( shuffle to Ajavdo) and heeceer ( shuffle to eccehr)
Repgeraldgloria02, Android test engineer at Achieve Internet
I am a personal trainer. I design programs and provide nutritional advice and coaching. I wanted to share my knowledge ...
Repjacksonbetty625, Accountant at 247quickbookshelp
My work is specialized help, regardless of whether on the telephone, face to face, or distantly, identified with PC frameworks ...
RepHenryMelvin, Korean Air Change Flight at AMD
Hello, everybody! My name is Henry,I am a picture-drawer.Art drawing & painting classes for adults, kids, teens.We have ...
rishab99999, did the interviewer want you to implement the data structure?
- EPavlova July 19, 2016