taisinT
BAN USERBase will be hashmap structure name - phone. As many maps as there are first letters. And a reference table letter - how to find the data map.
This way you just find the needed Map by the first letter, load it in memory and then retrieve the phone. It works well only if the letter distribution is more or less uniform.
Put the tree into array form. 0 where there's no node, 1 where is one. Throw a random between 0 and array size, if found 1 return, if found 0 repeat.
Caveat: we are wasting space and time if the tree is hugely unbalanced.
If no previously visited nodes must be returned, we have to keep track of every cell visited and check if there is still one unvisited (number of all visited, filled or no has to be less then array) unless the algo never returns.
If strings are not too big (no risk of overflow).
public boolean isAnagrams(String str1, String str2){
if(str1 == null || str2 == null || str1.length() != str2.length()){
return false;
}
return getHash(str1) == getHash(str2);
}
public int getHash(String str){
int res = 0;
for(int i = 0; i < str.length(); i++){
res += str.charAt(i);
}
return res;
}
If entry is ASCII. I assume that there are no spaces and punctuation marks. Time complexity O(n), where n is string length. Space complexity O(1)
public boolean is Anagrams(String str1, String str2){
if(str1 == null || str2 == null || str1.length() != str2.length()){
return false;
}
int[] countsStr1 = new int[256];
int[] countsStr2 = new int[256];
for(int i =0; i < str1.length(); i++){
countsStr1[str1.charAt(i)] += 1;
countsStr2[str2.charAt(i)] += 1;
}
for(int i =0; i < countsStr1.length; i++){
if(countsStr1[i] != countsStr2[i]){
return false;
}
}
return true;
}
If entry is Unicode.
public boolean is Anagrams(String str1, String str2){
if(str1 == null || str2 == null || str1.length() != str2.length()){
return false;
}
Map<Character, Integer> countsStr1 = new HashMap<Character, Integer>();
Map<Character, Integer> countsStr2 = new HashMap<Character, Integer>();
for(int i =0; i < str1.length(); i++){
add(str1.charAt(i), countsStr1);
add(str2.charAt(i), countsStr2);
}
if(countsStr1.size() != countsStr2.size()){
return false;
}
if(!countsStr1.keySet().containsAll(countsStr2.keySet())){
return false;
}
if(!countsStr2.keySet().containsAll(countsStr1.keySet())){
return false;
}
for(Map.Entry<Character, Integer> entry1 : countsStr1.entrySet()){
Integer value2 = countsStr2.get(entry1.getKey());
if(entry1.getValue().intValue() != value2.intValue() ){
return false;
}
}
return true;
}
private void add(char value, Map<Character, Integer> counts){
Character ch = Character.valueOf(value);
Integer cnt = counts.get(ch);
if(cnt != null){
counts.put(ch, cnt + 1);
} else {
counts.put(ch, 1);
}
}
I don't see the necessity for the last loop. If there is an outlander, you will exit during the first one.
If they were asking to find all of them, then the "return" in the first loop has to be replaced with adding the outlander to the result structure, and I still don't see the need for the last loop.
void int count(int[] a, int val) {
if(a == null || a.length == 0 || a[0] > val || a[a.length - 1] < val){
return 0;
}
if(a[0] == val && a[a.length - 1] == val){
return a.length;
}
int foundLowerBound = -1;
int foundUpperBound = -1;
int foundValue = -1;
if(a[0] == val){
foundLowerBound = 0;
foundValue = 0;
}
if(a[a.length - 1] == val){
foundUpperBound = a.length - 1;
foundValue = a.length - 1;
}
if(foundValue == -1){
int beg = 0;
int end = a.length-1;
while(beg < end) {
int mid = (beg + end)/2;
if(a[mid] == val){
foundValue = mid;
break;
}
if(a[mid] < val)) {
beg = mid+1;
} else {
end = mid;
}
}
if(foundValue == -1){
return 0;
}
}
if(foundLowerBound == -1){
int beg = 0;
int end = foundValue - 1;
if(a[end] != val){
foundLowerBound = foundValue;
}
else{
while(beg < end) {
int mid = (beg + end)/2;
if(a[mid + 1] == val && a[mid] != val){
foundLowerBound = mid + 1;
break;
}
if(a[mid] == val){
end = mid - 1;
if(a[end] != val){
foundLowerBound = mid;
break
}
} else {
beg = mid;
}
}
}
}
if(foundUpperBound == -1){
int beg = foundValue + 1;
int end = a.length - 1;
if(a[beg] != val){
foundUpperBound = foundValue;
}
else{
while(beg < end) {
int mid = (beg + end)/2;
if(a[mid - 1] == val && a[mid] != val){
foundUpperBound = mid - 1;
break;
}
if(a[mid] == val){
beg = mid + 1;
if(a[beg] != val){
foundUpperBound = mid;
break;
}
}
else {
end = mid;
}
}
}
}
return foundUpperBound - foundLowerBound + 1;
}
public class BinaryDFSInterator<E> implements Iterator<E>{
private E[] binaryTree;
private boolean[] visited;
private int currentIndex = -1;
public BinaryDFSInterator(E[] binaryTree){
this.binaryTree = binaryTree;
this.visited = new boolean[binaryTree.length];
}
public boolean hasNext(){
return currentIndex != binaryTree.length - 1;
}
public E next(){
if(currentIndex < 0){
currentIndex = 0;
visited[currentIndex] = true;
return binaryTree[currentIndex];
}
if(isLeaf()){
currentIndex = getParent();
}
int nextNotVisitedNode = getNotVisitedChild();
while(nextNotVisitedNode == -1){
currentIndex = getParent();
nextNotVisitedNode = getNotVisitedChild();
}
currentIndex = nextNotVisitedNode ;
visited[currentIndex] = true;
return binaryTree[currentIndex];
}
public void remove(){
throw new UnsupportedOperationException();
}
private boolean isLeaf(){
return 2*currentIndex + 1 >= binaryTree.length;
}
private int getParent(){
int parentIndex = (currentIndex - 1)/2;
return parentIndex >= 0? parentIndex : 0;
}
private int getNotVisitedChild(){
for(int i = 1; i <= 2; ++){
int childIndex = 2*currentIndex + i;
if(!visited[childIndex ]){
return childIndex;
}
}
return -1;
}
}
For the input 2 1 5 5 1 3 3 your code gives 2, expected is 4.
- taisinT June 21, 2016