naomi.lijing@googlemail.com
BAN USER- 1of 1 vote
AnswersWrite a maxDepth function to find maximum depth of a binary tree. What is the time and space complexity of your function.
Given:
- naomi.lijing@googlemail.com in UKclass Tree { public Tree left; public Tree right; } int maxDepth(Tree head) {}
| Report Duplicate | Flag | PURGE
Bloomberg LP Software Developer - 0of 0 votes
AnswersGiven a string containing letter, digit, and other characters, write a function to check palindrome for only letter and digit. The implementation need to be in-place, no extra memory is allowed to create another string or array.
- naomi.lijing@googlemail.com in UK
For example:
"ABA" is palindrome
"A!#A" is palindrome
"A man, a plan, a canal, Panama!" is palindrome| Report Duplicate | Flag | PURGE
Facebook Software Developer
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(findLongest("acddsssefffffale"));
}
public static char findLongest(String s)
{
int max = 0, len = s.length(),counter=1;
char longest = s.charAt(0),current = s.charAt(0);
for(int i = 1; i<len;i++)
{
char ch = s.charAt(i);
if(ch==current)
counter++;
else
{
if(counter>max)
{
max = counter;
longest = current;
}
counter = 0;
current = ch;
}
if(i==len-1 && counter>max)
{
max = counter;
longest = ch;
}
}
return longest;
}
}
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
ArrayList<int[]> list = new ArrayList<int[]>();
list.add( new int[]{4,5} );
list.add( new int[]{9,9} );
list.add( new int[]{1,2} );
findPairWithMidpoint(list);
}
public static boolean isEven(int x){return x%2==0?true:false;}
public static void findPairWithMidpoint(ArrayList<int[]> list)
{
int[] pair = list.get(0);
int j = 0, len = list.size();
for(int i=1; i<len; i++)
{
int[] pair2 = list.get(i);
int x1,x2,y1,y2;
x1 = isEven(pair[0])?0:1;
y1 = isEven(pair[1])?0:1;
x2 = isEven(pair2[0])?0:1;
y2 = isEven(pair2[1])?0:1;
if((((x1^x2)!=1)&&((y1^y2)!=1)))
{
System.out.println("("+pair[0]+","+pair[1]+")");
System.out.println("("+pair2[0]+","+pair2[1]+")");
return;
}
else if(i == len-1)
{
if(++j<len-1)
{
pair = list.get(j);
i = j;
}
else
{
System.out.println("NONE");
return;
}
}
}
System.out.println("NONE");
return;
}
}
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int[] arr = {23,45,43,43,23,45,32};
System.out.print(findUnique(arr,7));
}
public static int findUnique(int[] arr,int size)
{
int unique = arr[0], index = 0;
HashSet<Integer> myset = new HashSet<Integer>();
for(int i = 0; i < size; i++)
{
System.out.println(i);
if(i!=index && arr[i]==unique)
{
if(index < size-1)
{
myset.add(index);
myset.add(i);
index++;
while(myset.contains(index))
{
index++;
}
if(index <= size -1)
{
unique = arr[index];
i=1;
while(myset.contains(i))
{
i++;
}
if(i>=size)
return -1;
i--;
}
else
return -1;
}
else
return -1;
}
}
return unique;
}
}
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
fib(10);
}
public static void fib(int n)
{
int p=1,q=1;
while (p<n)
{
System.out.println(p);
int temp;
temp = q;
q = p + q;
p = temp;
}
}
}
class Ideone
{
public static void main( String[] args ){
System.out.println(reverse(12345));
}
public static int reverse(int in)
{
String s = Integer.toString(in);
String num="";
for(int i = s.length()-1; i>=0; i--)
{
num = num + s.charAt(i);
}
return Integer.parseInt(num);
}
}
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
HashMap<Integer,Integer> map = getHist(3,3);
System.out.println(map.get(3));
System.out.println(map.get(4));
System.out.println(map.get(5));
System.out.println(map.get(6));
System.out.println(map.get(7));
System.out.println(map.get(8));
System.out.println(map.get(9));
}
public static HashMap<Integer,Integer> getHist(int n, int m)
{
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
map.put(n,1);
map.put(n+1,n);
int mid = (n+n*m)/2;
for(int i= n+2; i<= n*m ; i++)
{
if(i<=mid)
{
int dif = i - n;
int sum=0;
for(int j=0;j<dif;j++)
{
sum += map.get(n+j);
}
map.put(i,sum);
}
else
{
int dif = i - mid;
map.put(i,map.get(mid-dif));
}
}
return map;
}
}
int my_strcmp(char* s1, char* s2)
{
while(*s1!='\0' && *s2!='\0')
{
if(*s1>*s2)
return 1;
else if(*s1<*s2)
return -1;
s1++;
s2++;
}
return *s1=='\0'&&*s2=='\0'?true:*s1=='\0'?-1:1;
}
int main() {
cout<<my_strcmp("abc","ab");
return 0;
}
Thanks for the comment on improving my code! :) Feel like getting more professional now~
- naomi.lijing@googlemail.com February 25, 2015class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
Vector v = new Vector();
v.add("JFK");
v.add("LXA");
v.add("SNA");
v.add("RKJ");
v.add("LXA");
v.add("SNA");
findpath(v);
}
public static void findpath(Vector<String> v)
{
HashMap<String,String> map = new HashMap<String,String>();
ArrayList<String> list = new ArrayList<String>();
String depart="";
for(int i = 0; i < v.size(); i++)
{
//build map
map.put(v.get(i),v.get(++i));
}
//find departure airport
for(int i = 0; i<v.size(); i=i+2)
{
if(!map.containsValue(v.get(i)))
{
depart = v.get(i);
break;
}
}
String airport = depart;
for(int i = 0; i < v.size()/2 +1; i++)
{
if(i<v.size()/2)
System.out.print(airport+"=>");
else
System.out.print(airport);
airport = map.get(airport);
}
}
}
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(isPalindrome("ABA"));
System.out.println(isPalindrome("A#!A"));
System.out.println(isPalindrome("A man, a plan, a canal, Panama!"));
}
public static boolean isLetterDigit(char ch)
{
if(Character.isLetter(ch)||Character.isDigit(ch))
return true;
else
return false;
}
public static boolean isPalindrome(String s)
{
boolean valid = true;
for(int i = 0, j = s.length()-1; i<j; i++,j--)
{
while(!isLetterDigit(s.charAt(i)) && i<j)
i++;
while(!isLetterDigit(s.charAt(j)) && i<j)
j--;
if(Character.toLowerCase(s.charAt(i))!=Character.toLowerCase(s.charAt(j)))
{
valid = false;
break;
}
}
if(valid)
return true;
else
return false;
}
}
- naomi.lijing@googlemail.com February 27, 2015