|
1 | 1 | packageAlgorithms.algorithm.interviews.uber; |
2 | 2 |
|
| 3 | +importjava.util.*; |
3 | 4 | publicclassExample { |
4 | | - |
| 5 | +/* sqrt(100) => 10,1 , sqrt(300) => 10,3 300 = 10^2 * 3 */ |
| 6 | +// Running time: O(sqrt(n)) |
| 7 | +publicint[]sqrt(intnum){ |
| 8 | +int[]rst = {-1,-1}; |
| 9 | + |
| 10 | +if (num <0){// edge case |
| 11 | +returnrst; |
| 12 | +} |
| 13 | + |
| 14 | +intn = (int)Math.sqrt(num); |
| 15 | +while (n >=1){ |
| 16 | +if (num % (n*n) ==0){ |
| 17 | +rst[0] =n; |
| 18 | +rst[1] =num/(n*n); |
| 19 | +returnrst; |
| 20 | +} |
| 21 | +n--; |
| 22 | +} |
| 23 | +returnrst; |
| 24 | +} |
| 25 | + |
| 26 | +/* given a number, find the next prime which is bigger than it */ |
| 27 | +// Running time: O(nlogm) => m is an average recursion depth for each number, how to optimize it? |
| 28 | +publicintgetNextPrime(intvalue){ |
| 29 | +if (value <=1){ |
| 30 | +return2; |
| 31 | +} |
| 32 | +inttarget =value+1; |
| 33 | +while (!isPrime(target)){ |
| 34 | +target++; |
| 35 | +} |
| 36 | + |
| 37 | +returntarget; |
| 38 | +} |
| 39 | +publicbooleanisPrime(inttarget){ |
| 40 | +intn =2; |
| 41 | +while (n*n <=target){// may overflow here! |
| 42 | +if (target %n ==0){ |
| 43 | +returnfalse; |
| 44 | +} |
| 45 | +n++; |
| 46 | +} |
| 47 | +returntrue; |
| 48 | +} |
| 49 | +/* given many logs <username,log_time,logout_time>, output <time,number_of_users> */ |
| 50 | +// use two priorityqueue: O(2nlogn) ; just sort: O(2nlog2n) |
| 51 | +publicList<result>countRecord(List<record>records){ |
| 52 | +if (records ==null ||records.size() ==0){ |
| 53 | +returnnewArrayList<result>(); |
| 54 | +} |
| 55 | +List<result>rst =newArrayList<result>(); |
| 56 | +Collections.sort(records,newComparator<record>(){ |
| 57 | +@Override |
| 58 | +publicintcompare(recordo1,recordo2) { |
| 59 | +// TODO Auto-generated method stub |
| 60 | +returno1.log_time -o2.log_time; |
| 61 | +} |
| 62 | +}); |
| 63 | +PriorityQueue<Integer>endheap =newPriorityQueue<Integer>(records.size(),newComparator<Integer>(){ |
| 64 | +@Override |
| 65 | +publicintcompare(Integero1,Integero2) { |
| 66 | +// TODO Auto-generated method stub |
| 67 | +returno1-o2; |
| 68 | +} |
| 69 | +}); |
| 70 | +PriorityQueue<Integer>startheap =newPriorityQueue<Integer>(records.size(),newComparator<Integer>(){ |
| 71 | +@Override |
| 72 | +publicintcompare(Integero1,Integero2) { |
| 73 | +// TODO Auto-generated method stub |
| 74 | +returno1-o2; |
| 75 | +} |
| 76 | +}); |
| 77 | +intcurr,i; |
| 78 | +for (i=0;i<records.size();i++){ |
| 79 | +recordtmp =records.get(i); |
| 80 | +startheap.offer(tmp.log_time); |
| 81 | +endheap.offer(tmp.logout_time); |
| 82 | +} |
| 83 | +// output |
| 84 | +curr =0; |
| 85 | +while (startheap.size() >0 ||endheap.size() >0){ |
| 86 | +intcurr1 =startheap.size() >0 ?startheap.peek() : -1; |
| 87 | +intcurr2 =endheap.size() >0 ?endheap.peek() : -1; |
| 88 | +if (curr1 <0 ||curr1 >curr2){// only end time left |
| 89 | +while (endheap.size() >0 &&endheap.peek() ==curr2){ |
| 90 | +curr--; |
| 91 | +endheap.poll(); |
| 92 | +} |
| 93 | +rst.add(newresult(curr2,curr)); |
| 94 | +} |
| 95 | +elseif (curr2 <0 ||curr1 <curr2){// go with start time |
| 96 | +while (startheap.size() >0 &&startheap.peek() ==curr1){ |
| 97 | +curr++; |
| 98 | +startheap.poll(); |
| 99 | +} |
| 100 | +rst.add(newresult(curr1,curr)); |
| 101 | +} |
| 102 | +else{// curr1 == curr2 |
| 103 | +while (endheap.size() >0 &&endheap.peek() ==curr2){ |
| 104 | +curr--; |
| 105 | +endheap.poll(); |
| 106 | +} |
| 107 | +while (startheap.size() >0 &&startheap.peek() ==curr1){ |
| 108 | +curr++; |
| 109 | +startheap.poll(); |
| 110 | +} |
| 111 | +rst.add(newresult(curr1,curr)); |
| 112 | +} |
| 113 | +} |
| 114 | + |
| 115 | +returnrst; |
| 116 | +} |
| 117 | +// decode ways: 1-26 => 'A'-'Z' |
| 118 | +publicintnumDecodings(Strings){ |
| 119 | +if (s ==null ||s.length() ==0){ |
| 120 | +return0; |
| 121 | + } |
| 122 | +intlast =0; |
| 123 | +intcurr =s.charAt(0) =='0' ?0 :1; |
| 124 | +intnext =last +curr; |
| 125 | +inti,copy =0; |
| 126 | + |
| 127 | +for (i =0;i <s.length();i++){ |
| 128 | +next =0; |
| 129 | +if (s.charAt(i) >='1' &&s.charAt(i) <='9'){ |
| 130 | +next =curr; |
| 131 | + } |
| 132 | +intvalue =copy*10 +s.charAt(i)-'0'; |
| 133 | + |
| 134 | +if (value >=10 &&value <=26){ |
| 135 | +next +=last; |
| 136 | + } |
| 137 | +copy =value %10; |
| 138 | + |
| 139 | +last =curr; |
| 140 | +curr =next; |
| 141 | + } |
| 142 | + |
| 143 | +returnnext; |
| 144 | + } |
| 145 | +// wordbreak => [lock,locker, erning] ; lockerning : true, lockern : false |
| 146 | +publicbooleanwordBreak(Strings,Set<String>dict){ |
| 147 | +if (dict ==null ||s ==null ||s.length() ==0 ||dict.size() ==0){ |
| 148 | +returnfalse; |
| 149 | + } |
| 150 | +intm =s.length(); |
| 151 | +intrange =0; |
| 152 | +inti,j; |
| 153 | +boolean[]dp =newboolean[m+1]; |
| 154 | +dp[0] =true; |
| 155 | +Stringcurr; |
| 156 | + |
| 157 | +for (i=1;i<=s.length();i++){ |
| 158 | +for (j=0;j<i;j++){ |
| 159 | +curr =s.substring(j,i);// current substring |
| 160 | +if (dict.contains(curr) && (dp[j] ||j <range)){ |
| 161 | +range =Math.max(range,i-1); |
| 162 | +dp[i] =true; |
| 163 | +break; |
| 164 | + } |
| 165 | + } |
| 166 | + } |
| 167 | + |
| 168 | +returndp[m]; |
| 169 | + } |
5 | 170 | } |
