m3th0d.itbhu
BAN USER
Comments (16)
Followers (1)
Reputation 140
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
@sam Using O(n) space you can definitely find duplicates in an array in O(n) time complexity.

m3th0d.itbhu
August 28, 2013 Comment hidden because of low score. Click to expand.
1
of 5 vote
1) create a temp array of same size as input array.
2) Now assume each zero as 1, so for every index i in temp array, store the count of ones and zeroes till that index in original array. (count of ones + (1*count of zeroes))
3) find two farthest index which has same value. That would be the answer.
Why so, say at index i and j we have same values. > S[i] == S[j] > S[i] + count of ones  count of zeroes =S[i](since S[i] == S[j])
> count of ones = count of zeroes.
Time complexity = O(n), Space complexity = O(n)

m3th0d.itbhu
August 11, 2013 Comment hidden because of low score. Click to expand.
1
of 1 vote
1)create interface Area with method getArea(double ... parameters)
2)have concrete implemetations like rectArea, circArea etc which have getArea method implemented accordingly.
3) Have a base class Shape implements Comparable and which has Area as a member field.
4) Have a constructor like Shape(Area requiredArea){ this.Area = requiredArea) and a method getArea(){ return Area.getArea())
5) Have comparable to act on Area.getArea() of Shape class.
6) Since all are type of Shape class, hence they can be stored in collection of type Shape.

m3th0d.itbhu
August 10, 2013 Comment hidden because of low score. Click to expand.
0
of 0 vote
def parseword(a_word):
return max([a_word.count(c) for c in a_word.lower()])

m3th0d.itbhu
July 31, 2013 Comment hidden because of low score. Click to expand.
0
of 0 vote
what you have done is definitely log(n) solution but it will make integer overflow very easily as x^n will easily cross integer max limit.
It could be safely done in below steps, not crossing integer overflow limit.
using the formula (ab) mod n = ((a mod n)*(b mod n)) mod n
public int getMod(int x, int y, int z){
if(y == 1)
return x%z;
int halfMod = ((getMod(x, y/2, z)%z) * getMod(x, y/2,z))%z;
if (y%2 == 0){
return halfMod;
}else {
return ((halfMod%z)*(x%z))%z;
}
}
It is O(logY) complexity and will never cross integer max limit.

m3th0d.itbhu
July 27, 2013 Comment hidden because of low score. Click to expand.
0
of 0 vote
@Yang, I believe the maximum stack depth would be log n in average case, hence total memory used would be 2 * log n , and in case of array it has to be n. Hence on an average case 2 stacks has to be a preferred option.

m3th0d.itbhu
April 23, 2013 Comment hidden because of low score. Click to expand.
1
of 1 vote
Its simply maximum single sell profit algorithm,
Steps:
1) maxDiff = 0, currentMinimum = a[0]
2) for i in [0,n1] do:
curMinimum = min(curMinimum, a[i])
maxDiff = max(maxDiff, a[i]  curMinimum)
3) maxDiff is the answer
Complexity = O(n)
working code:
public int[] getIndexIandJ(int[] integers){
if(integers == null  integers.length == 1){
return integers;
}
int maxDiff = 0;
int curMin = integers[0];
int startIndex = 0;
int endIndex = 0;
int tempStart = 0;
for(int i = 1; i<integers.length; i++){
if(curMin > integers[i]){
curMin = integers[i];
tempStart = i;
}
if (maxDiff < (integers[i]  curMin)){
maxDiff = (integers[i]  curMin);
startIndex = tempStart;
endIndex = i;
}
}
int[] indices = new int[2];
indices[0] = startIndex;
indices[1] = endIndex;
return indices;
}

m3th0d.itbhu
April 14, 2013 Comment hidden because of low score. Click to expand.
1
of 1 vote
Time Complexity = O(d lgd), d = number of digits
eg: 4765
Step 1: Scan from right and insert all numbers into priorityqueue(min heap) which are in
increasing order i.e. 5, 6, and 7
Step2: As our pointer is at '7' start de queue and insert elements starting with location of '7' till we get number just greater than 4. As it is min heap, we will get numbers starting from lower most and hence filling them we ensure we are maitaining the shortest possible number.
step 3: as soon as we get a number just greater than 4, place it at location of '4' and place '4' at location where we were while filling the entries starting from '7',
step:4 fill all the entries remaining in the queue from the location where we placed '4'.
Complexity = O(d) for numbers scanning and lg(d) for heapify operation, hence worst is O(d lgd).
code:
public int getNextLargestNumber(int[] numbers){
int lastIndex = numbers.length 1;
PriorityQueue priorityQueue = new PriorityQueue();
while (lastIndex>0 && (numbers[lastIndex1] >= numbers[lastIndex])){
priorityQueue.add(numbers[lastIndex]);
lastIndex;
}
priorityQueue.add(numbers[lastIndex]);
if(priorityQueue.size() == numbers.length){
return getInt(numbers);
}
int justGreater = (Integer)priorityQueue.peek();
priorityQueue.remove(priorityQueue.peek());
int start = lastIndex;
while (justGreater < numbers[lastIndex1]){
numbers[start++] = justGreater;
justGreater = (Integer)priorityQueue.peek();
priorityQueue.remove(priorityQueue.peek());
}
numbers[start++] = numbers[lastIndex1];
numbers[lastIndex1] = justGreater;
while (!priorityQueue.isEmpty()){
numbers[start++] = (Integer)priorityQueue.peek();
priorityQueue.remove(priorityQueue.peek());
}
return getInt(numbers);
}
private int getInt(int[] nums){
int number = 0;
for (int i=0; i<nums.length; i++){
number = number*10 + nums[i];
}
return number;
}

m3th0d.itbhu
April 12, 2013 Comment hidden because of low score. Click to expand.
1
of 1 vote
Complexity: O(N^2)
Steps:
1) Pick the first number and try to find two maximum numbers to its right in increasing order,
2) if Found , store the product of all three numbers
3) do this for all numbers
well it can be improved furthure , once we got a triplet a1<a2<a3, we can skip these test for any b right of a1 and left of a2 where b<a1.
public int getMaxProd(int[] nums){
if(nums == null  nums.length < 3 ){
return 1;
}
int maxProdSoFar = 0;
for(int i=0; i<nums.length; i++){
int pivot = nums[i];
int localMax = pivot*getProdOfTwoLargest(nums,i+1,nums.length1, pivot);
if(localMax > maxProdSoFar){
maxProdSoFar = localMax;
}
}
return maxProdSoFar;
}
public int getProdOfTwoLargest(int[] nums, int startIndex, int endIndex, int pivot){
int firstLargest = 1;
int secondLargest = 1;
// largest has to be in contiguous manner
for (int i=startIndex; i<=endIndex; i++){
if ( (nums[i] > pivot) && (nums[i] > firstLargest)){
secondLargest = firstLargest;
firstLargest = nums[i];
}
}
if(firstLargest == 1  secondLargest == 1){
return 0;
}
return firstLargest*secondLargest;
}

m3th0d.itbhu
April 12, 2013 Comment hidden because of low score. Click to expand.
0
of 0 vote
@vinod
what should be the output for
Input = [1,11,8,9 ,10,14]??

m3th0d.itbhu
April 10, 2013 Comment hidden because of low score. Click to expand.
0
of 0 vote
@vinod,
yeah I got you, condition in step14 will be true only for A[i] = 7.
Thanks :)
Comment hidden because of low score. Click to expand.
0
of 0 vote
Consider Input: [1, 11, 12, 7, 8, 9]
Your Output = 1*11*12
Expected Output: 7*8*9

m3th0d.itbhu
April 10, 2013 Comment hidden because of low score. Click to expand.
2
of 2 vote
public String removeMultipleSpaces(String word){
if(word == null){
return word;
}
int pivot1 = 0;
int pivot2 = 0;
char[] words = word.toCharArray();
int length = words.length1;
while (pivot1 <= length){
while (pivot1 <= length && (words[pivot1]) != ' '){
words[pivot2] = words[pivot1];
pivot2++;
pivot1++;
}
if(words[pivot1] == ' '){
words[pivot2] = words[pivot1];
pivot1++;
pivot2++;
}
while (pivot1 <= length && (words[pivot1] == ' ')){
pivot1++;
}
}
String result = String.copyValueOf(words);
return result.substring(0,pivot2);
}

m3th0d.itbhu
April 09, 2013 Comment hidden because of low score. Click to expand.
4
of 4 vote
void removeSpaces(char* source){
if(source == NULL)
return;
char* i = source;
char* j = source;
while(*j){
*i = *j++;
if(*i != ' '){
i++;
}
}
*i = '\0';
}

m3th0d.itbhu
April 05, 2013 Comment hidden because of low score. Click to expand.
1
of 1 vote
public int indexOfRepeatedBlock(char[] word){
if(word == null  word.length == 0){
return 1;
}
int length = word.length 1;
int finalIndex = 0;
int maxCount = 0;
int startIndex = 0;
int iterator = 1;
while (iterator <= length){
int count = 1;
startIndex = iterator1;
while (iterator <= length && (word[iterator1] == word[iterator])){
iterator++;
count++;
}
if(count > maxCount){
maxCount = count;
finalIndex = startIndex;
}
iterator++;
}
return finalIndex;
}

m3th0d.itbhu
April 05, 2013 Page:
1
Repbarrietrosado, abc at ABC TECH SUPPORT
Hi, I am Barrie, from Ualapue USA. I believe that every challenge has a solution  and I take great satisfaction ...
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
 m3th0d.itbhu September 01, 2013