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);
}
}

taisinT
July 15, 2015 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.length1;
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;
}

taisinT
July 08, 2015 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;
}
}

taisinT
July 07, 2015 Open Chat in New Window
For the input 2 1 5 5 1 3 3 your code gives 2, expected is 4.
 taisinT June 21, 2016