PKT
BAN USER- 0of 2 votes
AnswersClass A
- PKT in India
{ void print(){}
}
Class B extends A
{ void print(){}
public static void main(String args[])
{
B b = new A();
}
}
Whats wrong with the above piece of code?
will below mentioned line work?
B b = (B)new A();| Report Duplicate | Flag | PURGE
Citigroup Java - 0of 0 votes
AnswersYou have given a number, rearrange the digits of given number and find the next large number.
- PKT in India
For example given number is 2576
the next large number is 2657
code is not required approach or algo is enough.| Report Duplicate | Flag | PURGE
Amazon Applications Developer - 0of 0 votes
AnswersGiven:You have given Amazon's stock prices for next 10 days
- PKT in United States
Find out: max benefit in best time complexity to buy and sell 1 share
Condition: Share must be sold any day after buying date.
For ex:
Share in thousands
5 1 4 6 7 8 4 3 7 9
Max benefit 9 - 1 = 8 thousand| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm - 0of 0 votes
AnswersGiven a non sorted array consisting 0's and 1's. find the index of first '1'. write a complete program which takes less time complexity. and test all boundary conditions also.
- PKT in United States
Eg: If given array is 0,0,0,1,0,0,0,1,1,1,1 the out put should be 3.| Report Duplicate | Flag | PURGE
Problem Solving
Simple Solution:
-Have a linked list where we can store nodes and a ArrayList
-Insert Root in linked list
-Insert 'Root->left' and 'Root->right' in ArrayList
-In case 'Root->left' exists insert 'Root->left' at Root's just left
-In case 'Root->right' exists insert 'Root->right' at Root's just right
-Repeat above steps for each level of tree
For Ex:
Let's say we have a tree
Inorder= D B E A F C G
Root = A
Procedure:
-Insert Root 'A' in Linked List
-Insert Roots Left 'B' and Right 'C' in ArrayList.
-Insert 'A' -> left (B) just before A
-Insert 'A' -> right (C) just after A
-Linked List is now = B A C
-Now Perform root action in all node present in Array List
-Linked List is now = D B E A F C G
I think qus must mention that your written code should have complexity of O(1) complexity is excluding pre-built APIs and functions.
Because HashMap itself has its own algorithm and complexity to add, delete and searching... and I think HashMap's internal algo is surly not be O(1)
Lets say there are two node given 'F' and 'P'
-Find the traversing path for 'F'
[Path_1] Root => 'A' => 'B' => 'D' => 'F'
-Find the traversing path for 'P'
[Path_2] Root => 'A' => 'B' => 'G' => 'L' =>'P'
-Compare both of the path and find the last same node in both path
---- A and B are common in both of the path, hence B is the common parent for both node 'F' and 'P'
FYI: Qus filler has commented missed clause in qus:
[I forgot to clarify that * can only delete the character before it, but * can be skipped. So
"a*" is "a" or is an empty string ""]
Approach:
-Traverse both of the strings from right side
-In case found char [a-z] in str_1 just match this particular char in str_2
-In case found [.] in str_1 skip one char in str_2
-In case found [*] in str_1, check the char before [*] and check also no. of time it is repeating consecutively say N.
[For ex: abbb*c : Here before [*] char 'b' is repeating 3 times]
-Now check in str_2 it should have either (N) or (N-1) no. of time char 'b'
[As in case of abbb*c valid str are: {abbc} & {abbbc}]
-Repeat above steps until anything unmatch not occurs or string ends.
Sometime we think something is senseless but actually not and sometime we think something is senseless and in actual it is senseless
in both case ask client to send a mail CCing your manager. That's all.
We can show the correct way to customer... if he/she is not agree.... no one can help on this.
customer is the BOSS
In case sorted array we can get
''''''the number of pairs (x, y) of distinct elements with condition x + y <= Threshold''''''
in complexity O(n)
Lets say we have a sorted array as follows:
1--3--3--4--6--7--8--9--12--13--15--17--70
Threshold is 12
Start traversing in array from end side with rightIteratorIndex (1 <= 3 <= 3 <= 4----------17 <= 70)
-Compare array element with Threshold
-If ArrayElement > Threshold then move to previous element
-If ArrayElement < Threshold then
--Start traversing ArrayElement from left side with another leftIteratorIndex
until Array[leftIteratorIndex] + Array [rightIteratorIndex] < Threshold
also have a counter initialized to zero and increase counter.
in case repeated element as previous move leftIteratorIndex to one more left without updating counter
--When ever Array[leftIteratorIndex] + Array [rightIteratorIndex] > Threshold found
move rightIteratorIndex to left ArrayElement ,
update counter = counter + leftIteratorIndex
and start traversing from 'Array[leftIteratorIndex]' for Array[leftIteratorIndex] + Array [rightIteratorIndex] < Threshold
for Array[leftIteratorIndex] + Array [rightIteratorIndex] > Threshold again move 'rightIteratorIndex' to left
repeat above procedure until rightIteratorIndex != 0
--At last print counter which has been asked in qus.
Traverse through String array:
--Fetch first version and save it in a string MaxVersion
--Fetch next string's numeric value before (.) dot and compare with MaxVersion's first numeric value before (.).....
--In case [MaxVersion's first numeric value before (.)] > [next string's numeric value before (.)] move to next string and repeat above step
-- In case [MaxVersion's first numeric value before (.)] < [next string's numeric value before (.)] ...... copy next string in MaxVersion.... fetch next string and repeat steps again...
--In case [MaxVersion's first numeric value before (.)] = [next string's numeric value before (.)] ... check for next numeric value between first and second (.) dot
We can optimize string to numeric conversion in case we have constrain on no/ of levels in version.... for ex 5 level of version.... 11.1.0.2.5
Data structure for this question is not given...
Lets say equation is given in string format...
-Tokanize the formulas like (H2O) by checking below point
---in case first occurrence is numeric (5H2O) then save this multipliable number 5 in a variable coefficient array . (coefficient [token_index]=5)
-Initialize a HashMap and start inserting elements as key and next numeric as its value... in case no next numeric value assume it 1... also multiply the value with 'coefficient [token_index]'.... take care of Capital/Small letter as HS are two element but Hs is a single
-Now start fetching resultant formula and compare with hashmap
----in case element from right side not present in HashMap return -1
----in case coefficient is there in right side multiply it with elements coefficient value the compare in HashMap.
Merge Sort requires a lot of rearrangement in a elements which increases unnecessary complexity in case we use Array....
Linked List is always best option where-ever a lot of element re-ordering is required.
for ex:
4 3 2 1
sort 4,3 and 2,1
Reorder: 3,4,1,2 [4 element changed their order]
sort 3,4,1,2
Reorder: 1,2,3,4 [again 4 element changed their order]
In case Array: We requires many swapping and re ordering for n numbers in worst case. O(n)
Linked List: Breaking and re arranging links does need only O(1) element operation
Logic to generate rand7() with the help of rand5():
rand5() - function to generate random number b/w 0 to 5
rand7() = [sum of rand5() generated 7 times] % 7
rand7() = [rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5()] % 7
In this way [sum of rand5() generated 7 times] will vary from 0 to 35
and rand7() will generate random number between 0 to 7 with equal probability.
A different approach:
**Benefit: We do not need to rearrange resultant array again and again as we do in conventional way merging first 2 then 3rd then fourth.... and so on....
-Have k integer index to traverse K sorted arrays
[index1,index2,index3,index4.......indexk]
-Initiate all with first element of respective sorted arrays.
[index1=array1's first index ,index2=array2's first index.......indexk=arrayk's first index ]
-Now compare elements from all traversing indexes [index1,index2,index3,index4.......indexk] in respective array.
-Which ever element is smallest.... copy that element to new mergeSortedArray[] and increase the traversing index by 1.
-keep repeating above steps unless all the arrays are not traversed.
@yarovoi: yeah.. u r right.....but...that's all I could think of it...... drop egg exponentially first and where ever got broken... start dropping sequentially from previous non breakable floor.
complexity is defiantly better then O(n)
Any sol for infinite no. of floors better then this is most welcome if possible.
Logic for infinite case:
as we dont know the no of floors and it is about infinite....
drop egg from 1st floor then
drop egg from 2nd floor then
drop egg from 4th floor then
drop egg from 8th floor then
double the no of floor each time.... where ever it got break... start dropping egg in sequence from previous non breakable floor.
Logic for given no pf floors: (optimal sol)
drop egg from xth floor then
drop egg from (x)+(x-1) floor then
drop egg from (x)+(x-1)+(x-2) floor then
drop egg from (x)+(x-1)+(x-2)+(x-3) floor then
drop egg from prev floor+(x-3) floor then
..
..
drop egg from prev floor+1) floor.
in case egg broke in any floor mentioned above.. start dropping eff in sequence from prev non breakable floor.
lets calculate value of optimal x:
x + (x-1) + (x-2) + (x-3) + ...... 2 + 1 = no of floors
x(x+1)/2 = no. of floors
for no. of floors = 10
x = 4 in worst case we need only 4 drops.
Logic for infinite case:
as we dont know the no of floors and it is about infinite....
drop egg from 1st floor then
drop egg from 2nd floor then
drop egg from 4th floor then
drop egg from 8th floor then
double the no of floor each time.... where ever it got break... start dropping egg in sequence from previous non breakable floor.
shortest distance between the first and the last element in a two dimension:
Case 1: first element = a[0][0] & last element a[M][N]
Sol: you can never move from a[0][0] to a[M][N] with only possible action left and down. Right move is required unless left move from a[0][0] is not a[0][N]
Case 2: first element = a[0][0] & last element a[M][index] (bottom row)
Sol: no matter what matrix is given made up with o and 1. ans will always M down moves.
Case 3: first element = a[0][0] & last element a[M][N] (right most column) and we have move down or right for each 1
Sol: when ever you got 1 go right and down for 0...once reached rightmost column go down for all elements (0 or 1)
Logic to search jthIndex and ithIndex for a[jthIndex]>a[ithIndex]
Note: ithIndex can be greater then jthIndex for some case and (j-i) could be best possible lesser -ve value
Ex: 9 8 7 6 5 4 3 1
Logic: Search for all possible couple for indexDiff where indexDiff is looping from (arraylength-1) to 1. Whenever I got a[jthIndex] > [index] for very first time... those ithIndex and jthIndex will be our ans.
Code:
void getMaxIndexDiffForCondition(int a[])
{
int ithIndex;
int jthIndex;
int flag;
int indexdiff;
flag = 0;
indexDiff = 0;
for(indexDiff = (a.length-1); indexDiff > 0; indexDiff++)
{
ithIndex = 0;
jthIndex = indexDiff;
while (jthIndex < a.length)
{
if(a[jthIndex] > a[ithIndex])
{
flag = 1;
break;
}
else
{
ithIndex++;
jthIndex++;
}
}
if(flag==1)
{
break;
}
}
cout<<"best possible i and j for max (j-i) in such a way that a[j]>a[i] are:";
cout<<"index j="<<j;
cout<<"index i="<<i;
cout<<"element diff is"<<a[j]-a[i];
cout<<"index diff is"<<(j-1);
}
we can calculate depth of both nodes d1 and d2 which may help us to optimize our code in order to find common parent.
For ex:
case:1 --- if(d1 == d2)
then find the parent node of both nodes and compare in case not same again find parent of parent for both nodes and compare...
case:2 --- if(d1 > d2 && (d1-d2)>1)
then get (d1-d2-1) grand parent of d1 and check whether d2 is parent of d1... if not ....get the parent of (d1-d2) grand parent of d1 and proceed for case :1 [if(d1 == d2)]
case :3 ---- same as case 2
In case we are using java APIs HashMap or HashSet...... they do have their own algo to keep functioning.... so we can't just say O(1) is the complexity.... using these APIs for purpose is OK if we are not too concerned about complexity or we are sure the best algo is being used in these APIs.
In case we are not using any pre built APIs yes BST or a SORTED ARRAY data structure is looking good as total nlog(n) complexity is required to insert, delete duplicates and maintain unique data having n elements.
Regarding complexity even in worst case we are not touching all elements n......
As we are using binary search two times it looks like complexity is:
O(log [n / constant1] ) + O(log [n / constant2] )
in case pure increasing or decreasing order array
O(log n)
in all other cases:
O(log [n / constant1] ) + O(log [n / constant2] )
where
constant1 = 2+ {2,3,4....}
constant2 = 2+ {2,3,4....}
same as two more cases:
if((a[mid]<a[low]) && key > a[mid])// in this case
//our pivot and key will always occur before a[mid]
//searching in right subArray is waste
return search(a,low.mid,key);
if((a[mid]<a[low]) && key < a[mid])// in this case
//our pivot will always occur before a[mid]
//key will occur after a[mid]
//a[mid] to a[high] is uniform decreasing order
Optimization:
int search(int a[],int low,int high,int key)
{
if(high<=low)
return 0;
int mid=(low+high)/2;
if(a[mid]==key)
return mid;
if((a[mid]<a[high]) && key > a[mid])// in this case
//our pivot and key will always occur after a[mid]
//searching in left subArray is waste
return search(a,mid+1,high,key);
if((a[mid]<a[high]) && key < a[mid])// in this case
//our pivot will always occur after a[mid]
//key will occur before a[mid]
//a[low] to a[mid] is just increasing subArray
return search(a,low,mid-1,key);
return search(a,low,mid-1,key) || search(a,mid+1,high,key);
}
@D.Tox: yeah.. nice approch
@Ano: The only hard part of this qus is finding the formula
Sum of 1 3 5 7 9 . . . . .. .n = (1/2) * [(n+1)^2]
once we got the formula... writing program for this qus is quite simpler
Steps:
-Read input value 'n'
-calculate the value sum = (1/2) * [(n+1)^2] by replacing value n with input value
-print sum
Derivation:
To Find: Sum of 1 3 5 7 9 . . . . .. .n
Sum of 1 3 5 7 9 . . . . .. .n = [Sum of 1 2 3 4 . . . .n] - [Sum of 2 4 6 8.... (n-1)]
Sum of 1 3 5 7 9 . . . . .. .n = [Sum of 1 2 3 4 . . . .n] - [Sum of 2 4 6 8.....(n-1)]
Sum of 1 3 5 7 9 . . . . .. .n = [Sum of 1 2 3 4 . . . .n] - (2) * [Sum of 1 2 3 4.....{(n-1)/2}]
Sum of 1 3 5 7 9 . . . . .. .n = [Sum of 1 2 3 4 . . . .n] - (2) * [Sum of 1 2 3 4.....{(n-1)/2}]
Sum of 1 3 5 7 9 . . . . .. .n = [n*(n+1)/2] - (2) * [{(n-1)/2} * [{(n-1)/2}-1] / 2]
Sum of 1 3 5 7 9 . . . . .. .n = [n*(n+1)/2] - (2) * [(1/2) * {(n-1)/2} * {(n+1)/2}]
Sum of 1 3 5 7 9 . . . . .. .n = [(1/2) * n * (n+1)] - [(1/4) * (n^2-1)]
Sum of 1 3 5 7 9 . . . . .. .n = [(1/2) * n * (n+1)] - [(1/4) * (n-1) * (n+1)]
Sum of 1 3 5 7 9 . . . . .. .n = [(n+1) / 2] * [n+1]
Sum of 1 3 5 7 9 . . . . .. .n = (1/2) * [(n+1)^2]
Ans: (1/2) * [(n+1)^2]
-Calculate the length of string. [length]
-As Palindrome consists of two kind of char... at most only one char can be single else it should be couple chars
For ex: abbcbba, abbbba,ababbcbbaba
-now get the no. of couple char [noOfCoupleChar]
-and get the no of non-coupled char [noOfNonCoupleChar]
for Ex: abbababbac
no of char 'a'=4
no of char 'b'=5
no of char 'c'=1
hence
noOfCoupleChar = 8 and
noOfNonCoupleChar =2
-get the no of all palindrome anagrams having length = noOfCoupleChar + 1
[facorialOf(noOfCoupleChar / 2)] / [factorialOf(noOfOccuranceOfChar(a)/2)*factorialOf(noOfOccuranceOfChar(b)/2)..... ]*[noOfNonCoupleChar ]
-same as get the no of all palindrome anagrams having length = noOfCoupleChar
[facorialOf(noOfCoupleChar / 2)] / [factorialOf(noOfOccuranceOfChar(a)/2)*factorialOf(noOfOccuranceOfChar(b)/2)..... ]
-like as we can calculate all possible palindromes of various length
<End Of Logic>
For Ex:
String: abbabcabba
no of couple # 4(a) + 4(b) = 8
no of non couple # 1(b) + 1(c) = 2
no of palindromes for length = 8+1 =>
[fact(4)]/[fact(2)*fact(2)]*[2] = 12
like wise calculate for all possible length of palindrome.
Given:
Matrix [M x N]
Logic:
-Have 4 variable columnMin, columnMax, rowMin, rowMax
-Initialize variables as
columnMin = 0
rowMin = 0
columnMax = N
rowMax = M
Loop
if(columnMin != columnMax)
{
Print Row from Matrix [rowMin][columnMin] to Matrix [rowMin] [columnMax]
rowMin ++ ;
}
else
{
break;
}
if(rowMin != rowMin)
{
Print Column from Matrix [rowMin][columnMax] to Matrix [rowMax][columnMax]
columnMax - - ;
}
else
{
break;
}
if(columnMin != columnMax)
{
Print Row from Matrix [rowMax][columnMax] to Matrix [rowMax][columnMin]
rowMax - - ;
}
else
{
break;
}
if(rowMin != rowMin)
{
Print Column from Matrix [rowMax][columnMin] to Matrix [rowMin][columnMin]
columnMin ++ ;
}
else
{
break;
}
END LOOP
Logic:
-get the no. of '?' char in string given [ noOfWildChar ]
-now calculate no of possible strings = [ noOfStrings = 2 ^ noOfWildChar ]
-write a loop initiating from 0 to noOfStrings having index as loopIndex
-Inside Loop:
--calculate binary form of loopIndex for ex: 11 = 1011, 12 = 1100, 17 = 10001 [binaryForm]
--now start replacing '?' char with binaryForm sequence and print it.
For Ex:
String = 1 1 0 ? 1 ? 0 0 ? ? 1 ?
noOfWildChar = 5
noOfStrings = (2^5) = 32
Loop
-loopIndex = 0 then binaryForm = 00000 hence put '0' at all occurance of '?' char
-loopIndex = 1 .........
-loopIndex = 2 .........
-...
-..
-loopIndex = 11 then binaryForm = 01011 hence put '0' at first and third occurance of '?' and rest fill '1'
-..
-..
-loopIndex = 31 then binaryForm = 11111 hence put '1' at all occurance of '?' char
END LOOP
Logic:
- PKT January 12, 2014There can be three possibilities:
1. There is only one element in the tree
2. The key element is the left node of it's parent node
3. The key element is the right node of it's parent node
Approach:
For case one there can be no result possible
For case two parent of key node is the next larger element
For case three parent of parent is the next larger element
Sol:
Perform binary search on the tree to search key element just make sure you are keeping parent and parent's parent in temp var for current node while traversing tree
Time Complexity: nlog(n)
Space Complexity: (2 * logn)