carlosgsouza
BAN USER- 2of 2 votes
AnswersGiven a binary tree, implement an iterator that will iterate through its elements.
- carlosgsouza in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm
Average case is log_2(N) assuming equal distribution between +1s and -1s.
- carlosgsouza June 19, 2015Your algorithm works, but it is still O(N). In the worst case, you could be looking for 2 in an array like [1,0,1,0,1, 0, 1, 0, 1,...,0,1,2], which will cost you around N/2 searches.
- carlosgsouza June 19, 2015O(N) time solution and O(M) space given N is the size of B and M is the size of A. Implemented in Groovy with automated tests.
@Unroll
def "isAnagramSubstring(#str1, #str2) == #result"() {
expect:
isAnagramSubstring(str1, str2) == result
where:
str1 | str2 | result
"abc" | "abc" | true
"abc" | "cab" | true
"abc" | "def" | false
"abcdefabc" | "fed" | true
"abcdefabc" | "ghi" | false
"abcdeefabc" | "fed" | false
"abcdeefabc" | "fee" | true
"abc" | "" | true
"" | "" | true
"" | "def" | false
}
/*
abcdadefdabc | ddef
5--8
count | expected
d: 2 | 2
e: 1 | 1
f: 1 | 1
charactersCountMatching=2
*/
public boolean isAnagramSubstring(String str1, String str2) {
if(str1.length() < str2.length()) {
return false;
}
Map<Character, Integer> expectedCount = countCharacters(str2);
Map<Character, Integer> windowCount = new HashMap<Character, Integer>();
for(Character c : expectedCount.keySet()) {
windowCount.put(c, 0);
}
int start = 0;
int end = str2.length() - 1;
for(int i=0; i <= end; i++) {
char c = str1.charAt(i);
if(windowCount.get(c) != null) {
windowCount.put(c, windowCount.get(c)+1);
}
}
int charactersCountMatching = 0;
for(Character c : windowCount.keySet()) {
if(windowCount.get(c) == expectedCount.get(c)) {
charactersCountMatching++;
}
}
if(charactersCountMatching == expectedCount.size()) {
return true;
}
while(end+1 < str1.length()) {
start++;
end++;
char removedChar = str1.charAt(start-1);
if(windowCount.get(removedChar) != null) {
if(windowCount.get(removedChar) == expectedCount.get(removedChar)) {
charactersCountMatching--;
}
windowCount.put(removedChar, windowCount.get(removedChar)-1);
if(windowCount.get(removedChar) == expectedCount.get(removedChar)) {
charactersCountMatching++;
}
}
char addedChar = str1.charAt(end); //d
if(windowCount.get(addedChar) != null) {
if(windowCount.get(addedChar) == expectedCount.get(addedChar)) {
charactersCountMatching--;
}
windowCount.put(addedChar, windowCount.get(addedChar)+1);
if(windowCount.get(addedChar) == expectedCount.get(addedChar)) {
charactersCountMatching++;
}
}
if(charactersCountMatching == windowCount.size()) {
return true;
}
}
return false;
}
private Map<Character, Integer> countCharacters(String str) {
Map<Character, Integer> result = new HashMap<Character, Integer>();
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if(result.get(c) == null) {
result.put(c, 0);
}
result.put(c, result.get(c)+1);
}
return result;
}
Solution in Groovy with unit test
def "should calculate all the intervealed string of 'AB' and 'CD'"() {
expect:
intervealedStrings("AB", "CD") == ["ABCD", "ACBD", "ACDB", "CABD", "CADB", "CDAB"]
}
public List<String> intervealedStrings(String str1, String str2) {
List<String> result = new ArrayList<String>();
char[] s = new char[str1.length() + str2.length()];
intervealedPermutations(result, str1, str2, 0, 0, s, 0);
return result;
}
public void intervealedPermutations(List<String> result, String str1, String str2, int next1, int next2, char[] s, int i) {
if(next1 == str1.length() && next2 == str2.length()) {
result.add(new String(s));
}
if(next1 < str1.length()) {
s[i] = str1.charAt(next1);
intervealedPermutations(result, str1, str2, next1+1, next2, s, i+1);
}
if(next2 < str2.length()) {
s[i] = str2.charAt(next2);
intervealedPermutations(result, str1, str2, next1, next2+1, s, i+1);
}
}
I don't think you need DP in this problem and your sliding window solution looks fine. If you assume that there is only a limited number of characters that can show up on your string (ASCII or the English alphabet, for example), you can claim your solution to be O(1) space.
- carlosgsouza June 15, 2015@Unroll
def "the #k th occurence of #number in #numbers is #result"() {
expect:
findKthOcurrence(numbers, number, k) == result
where:
numbers | number | k | result
[1, 2, 3] | 1 | 1 | 0
[1, 2, 3] | 2 | 1 | 1
[1, 2, 3] | 4 | 1 | -1
[1, 2, 3] | 1 | 2 | -1
[1, 1, 2, 2, 3] | 1 | 1 | 0
[1, 1, 2, 2, 3] | 1 | 2 | 1
[1, 1, 2, 2, 3] | 2 | 1 | 2
[1, 1, 2, 2, 3] | 2 | 2 | 3
[1, 1, 2, 2, 3] | 3 | 1 | 4
}
int findKthOcurrence(List<Integer> numbers, int number, int k) {
int firstOcurrence = findFirstOcurrence(numbers, number, 0, numbers.size() - 1);
if(firstOcurrence == -1) {
return -1;
}
int indexOfK = firstOcurrence + k - 1;
if(numbers.get(indexOfK) == number) {
return indexOfK;
} else {
return -1;
}
}
int findFirstOcurrence(List<Integer> numbers, int number, int left, int right) {
if(left > right) {
return -1;
}
int mid = left + (right - left)/2;
if(numbers.get(mid) == number) {
if(mid == 0 || numbers.get(mid-1) != number) {
return mid;
} else {
return findFirstOcurrence(numbers, number, left, mid-1);
}
} else if(number < numbers.get(mid)){
return findFirstOcurrence(numbers, number, left, mid-1);
} else {
return findFirstOcurrence(numbers, number, mid+1, right);
}
}
This depends on the type of work the threads will do over the file. If processing an entry in the file is significantly more expensive than reading the file, have one thread reading the file and producing entries while all other threads consume these entries and process them.
Now suppose that processing an entry in the file is comparable in terms of processing time to reading such entry. The above schema would not work well since the producer wouldn't keep up with the consumers. Let's try something different.
Let's suppose each line in the file with F lines is an entry to be processed. Scan every character in the file and index all line breaks. Now create N threads and use a FileInputStream to skip to the nth line of the file and from there on use a BufferedReader.readLine(). Each thread should stop after it completed its own portion of the job (N/F lines).
You can remove the line indexing if, instead of splitting the file in lines, you split it in bytes. In this case you have to be very careful if you use BufferedReader because knowing when to stop is not trivial. You might have to count the number of characters in each entry so you know how many characters a thread has processed.
/*
->( ) -> ( ) -> (null) -> ( ) -> ( )
1 4 5
2 6
3
*/
class LinkedListOfLinkedListIterator implements Iterator<T> {
LinkedList<LinkedList<T>> parentList;
Iterator<LinkedList<LinkedList<T>>> parentIt;
LinkedList<T> childIt;
public LinkedListOfLinkedListIterator(LinkedList<LinkedList<T>> list) {
this.parentList = list;
if(list != null) {
this.parentIt = parentList.iterator();
}
}
public boolean hasNext() {
if(parentList == null) {
return false;
}
if(childIt != null && childIt.hasNext()) {
return true
} else {
// This child list has no next elements, move the parent list iterator
while(parentIt.hasNext()) {
LinkedList<T> childList = parent.next();
// The next element of the parent list is not null
if(childList != null) {
// Get the iterator of the child list. If we have next element, return true
childIt = childList.iterator();
if(childIt.hasNext()) {
return true;
}
} else {
childIt = null;
}
}
}
// The childIt had no next elements. Then, we looked for another child list in the parent list and we haven't found any lists with elements
return false;
}
public T next() {
// If hasNext returns true, childIt is positioned and ready to return the next element
if(hasNext()) {
return childIt.next();
} else {
throw new NoSuchElementException("It is over :(");
}
}
public void remove() {
throw new UnsupportedOperationException("This is too difficult");
}
}
A simple Groovy algorithm which runs in O(n**2). Look for palindromes starting from the center. Note that the center might be on character (in case the palindrome length is odd - aba) or between two characters (when the palindrome length is even aabbaa).
The most efficient solution would be the Manacher’s algorithm, which runs in O(n), but is too complex for me.
def run() {
expect:
getLongestPalindromeSubsequence(string) == result
where:
string | result
"a010c" | "010"
"abc" | "a"
"a001100" | "001100"
"" | ""
"0aa1bb2" | "aa"
}
def getLongestPalindromeSubsequence(String string) {
if(string.length() == 0) {
return ""
}
char[] s = string.toCharArray()
int first = 0
int last = 0
// Look for palindromes with odd length starting from the center
for(int i = 1; i < string.length() - 1; i++) {
int i_l = i-1, i_r = i+1
while(i_l >= 0 && i_r < string.length() && s[i_l] == s[i_r]) {
i_l--
i_r++
}
i_r--
i_l++
if(i_r-i_l > last-first) {
last = i_r
first = i_l
}
}
// Look for palindromes with even length starting from the center (between two chars)
// i = the first character to the left of the center
for(int i = 1; i < string.length() - 1; i++) {
int i_l = i, i_r = i+1
while(i_l >= 0 && i_r < string.length() && s[i_l] == s[i_r]) {
i_l--
i_r++
}
i_r--
i_l++
if(i_r-i_l > last-first) {
last = i_r
first = i_l
}
}
return string.substring(first, last+1)
}
Recursive and iterative versions written in Groovy. Both are O(n), but iterative is more efficient because there is less overhead.
def "should solve the problem"() {
given:
def tree = n(10, n(5, n(9, n(14), null), n(20)), n(11, null, n(15, null, n(25, null, n(30)))))
when:
def resultRecursive = extremeNodesInAlternateOrderRecursive(tree)
def resultIterative = extremeNodesInAlternateOrderIterative(tree)
then:
resultRecursive == [10, 11, 15, 25, 30]
resultIterative == [10, 11, 15, 25, 30]
}
static class Node {
def value
Node left
Node right
public String toString() {
"$value:{$left, $right}"
}
}
static Node n(value, left, right) {
return new Node(value:value, left:left, right:right)
}
static Node n(value) {
return new Node(value:value)
}
def extremeNodesInAlternateOrderRecursive(tree) {
def level_values = []
extremeNodesInAlternateOrderRecursive(tree, 0, level_values)
return level_values
}
def extremeNodesInAlternateOrderRecursive(node, level, level_values) {
if(!node) {
return
}
// even levels should return the leftmost element
// odd levels should return rightmost element
def even = level%2 == 0
// only add the element in case it is the first of that level
if(even && level_values.size() <= level) {
level_values << node.value
} else {
if(level_values.size() <= level) {
level_values << node.value
} else {
level_values[level] = node.value
}
}
extremeNodesInAlternateOrderRecursive(node.left, level+1, level_values)
extremeNodesInAlternateOrderRecursive(node.right, level+1, level_values)
}
def extremeNodesInAlternateOrderIterative(tree) {
def level_values = []
def nodeQueue = [tree] // nodes found in breadth-first
def levelQueue = [0] // level of the nodes in the nodeQueue
def i = 0
while(i < nodeQueue.size()) {
def node = nodeQueue[i]
def level = levelQueue[i]
// even levels should return the leftmost element
// odd levels should return rightmost element
def even = level%2 == 0
// only add the element in case it is the first of that level
if(even && level_values.size() <= level) {
level_values << node.value
} else {
if(level_values.size() <= level) {
level_values << node.value
} else {
level_values[level] = node.value
}
}
if(node.left) {
nodeQueue << node.left
levelQueue << level+1
}
if(node.right) {
nodeQueue << node.right
levelQueue << level+1
}
i++
}
return level_values
}
This problem can be solved very efficiently with recursion. The algorithm below runs in O(log(n)).
def getNumberOfOcurrencesOfDigits(int N) {
def result = [0:0, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0]
def addToAll = getNumberOfOcurrencesOfDigits(N, result)
(0..9).each {
result[it] += addToAll
}
return result
}
def getNumberOfOcurrencesOfDigits(int N, result) {
int Nby10 = N / 10
int Nmod10 = N % 10
(1..Nmod10).each {
result[it]++
}
if(Nby10 > 0) {
return Nby10 + getNumberOfOcurrencesOfDigits(Nby10, result)
} else {
return 0
}
}
Thanks for sharing!
- carlosgsouza February 07, 2014
Mohan, you are implementing tree traversal. The question asked for an iterator. In Java, for example, that would be a class implementing the Iterator interface (next(), hasNext() and remove() methods).
- carlosgsouza July 07, 2015