blackfever
BAN USER
- 1of 1 vote
AnswersGiven a stream of characters (stream is increasing char by char), check if newly
- blackfever in India
formed 10character word is present in already parsed/scanned stream. Print such
repeating streams lexicographically at the end.| Report Duplicate | Flag | PURGE
Directi SDE1 Algorithm - 1of 1 vote
AnswersGiven a graph where every two nodes are either friends or enemies with each other. Find a way to go from one node to the other.
- blackfever in India
Restrictions:
1) You can also travel from one node to next if they are friends with each other
2) You have some “magic potions”. You can convert an enemy path to a friend path with a magic potion.
I know this can be solved easily using dfs or bfs but i want to know the time complexity of each approach| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm - 4of 4 votes
AnswersTwo finite, strictly increasing, integer sequences are given. Any common integer between the two sequences constitute an intersection point. Take for example the following two sequences where intersection points are
- blackfever in India
printed in bold:
First= 3 5 7 9 20 25 30 40 55 56 57 60 62
Second= 1 4 7 11 14 25 44 47 55 57 100
You can ‘walk” over these two sequences in the following way:
1. You may start at the beginning of any of the two sequences. Now start moving forward.
2. At each intersection point, you have the choice of either continuing with the same sequence you’re currently on, or switching to the other sequence.
The objective is finding a path that produces the maximum sum of data you walked over. In the above example, the largest possible sum is 450 which is the result of adding 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, and 62
this is the same problem which I saw in SPOJ Problem Set| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 3of 3 votes
AnswersGiven a set of intervals like 5-10, 5-10, 8-12, 9-15
- blackfever in India
Find the ith smallest number in these intervals.
for eg:-
Suppose we have intervals like 5-10, 8-12.
Then total numbers in these two intervals would be: {5,6,7,8,8,9,9,10,10,11,12}
So, 1st smallest number: 5
4th smallest number: 8
5th smallest number: 8 (here is the
change since now we have duplicate elements also) and so on.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersGiven a n (large number) lists of customers who visited n webpages on n (large number) days, design a data structure to get customers who have visited the website on exactly “k” days and should have visited at least “m” distinct pages altogether.
- blackfever in India
Was then asked to improvise the solution as much as possible| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
Answers1. N-Petrol bunk problem: There are n petrol bunks located in a circle. We have a truck which runs 1 km per 1 liter (mileage 1kmpl). Two arrays are given. The distances between petrol bunks are given in one array. Other array contains the no of liters available at each petrol bunk. We have to find the starting point such that if we start at that point , you we would able to visit entire circle without running out of fuel. Initially truck has no fuel
- blackfever in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm
this can be done in nlogn.
1.Store the position of each element for that we can use an object with
{
val: value
position: array_index
}
for each element in the array
2.Then sort the object array created above with value.
3.Subtract the old position from the new position for each element. i.e (old position - new position) remember don't take absolute value .
and the maximum of this is the maximum surpasser of the array
this is pretty easy if you think in terms of Dp approach.
Lets say we have String as "1" so our output will be 1 because we only form 'A'
but if we add 2 to the existing string "12" then output is "AB" and "L" so if you see
the logic is when you add a character to an existing string the number of combinations increase by combining last 2 digits
in dp it can be formulized As
d[i]=dp[i-1]+dp[i-2](if the last 2 digits combined is smaller than 27)
else dp[i]=dp[i-1];
code is as below
void getMappingDp(String str)
{
int arr[]=new int[str.length()];
long Dp[]=new long[str.length()];
for(int i=0;i<arr.length;i++)
{
arr[i]=Integer.parseInt(""+str.charAt(i));
}
Dp[0]=1;
if(arr[0]*10+arr[1]<27)
Dp[1]=2;
else
Dp[1]=1;
for(int i=2;i<arr.length;i++)
{
long combinedLast2didgits=0;
if(arr[i-1]*10+arr[i]<27)
combinedLast2didgits=Dp[i-2];
Dp[i]=Dp[i-1]+combinedLast2didgits;
}
System.out.println("Total mapping are:"+Dp[Dp.length-1]);
}
see anonymous for your case the answer will be AB
- blackfever April 16, 2014guys in order to solve this u just need to remove all i mean all the even length palindromes from the string.
for eg:- in above case ABCCBCBA remove BCCB as it is even length paliondrome.
for eg:-ABBBBADD need to remove ABBBA and then DD and return -1
Algo:-
let the array be arr
1.Create An array sum as below
sum[i]=arr[0]+arr[1]+...arr[i];
2.Now see for duplicate values in sum array.
for eg:-
the array is 1,2,3,-2,-1,4,-5,1
sum array 1,3,6, 4, 3,7,2,3
so after finding duplicate values you will see the all the elements between their indices will sum upto zero and you can print it.
It will also work for over lapping intervals
geeksforgeeksdotorg slash median-of-stream-of-integers-running-integers
a good explanation
public class CombinationofCoins {
int numberoways(int den,int array[],int pos)
{
if(den<0||pos==array.length)
return 0;
if(den==0)
return 1;
int numways=0;
for(int i=pos;i<array.length;i++)
{
numways+=numberoways(den-array[i],array,i);
}
return numways;
}
public static void main(String args[])
{
int arr[]={2,3,4,5};
CombinationofCoins obj=new CombinationofCoins();
System.out.println(obj.numberoways(9, arr, 0));
}
}
u see your code only does a trivial check it will fail for many test cases
for eg:- let's say A="AAA" and B="AAB" and interlevead string be C="AABAAA"
so your statement
if (*ptrA++ != *ptrC++) {
break;
}
will give true for first 2 A's but after that your logic will fail as C will now point to "B" A is pointing to 'A' and B is also pointing to "A"..And you will come out of the loop.
because of these test cases you need to come with a dynamic programming.
Which is there in my post below you.
Construct a (n1+1)*(n2+1) table, A[0 .. n1][0 .. n2], where n1 and n2 is the length of s1 and s2, respectively.
A[i][j] = true, i.e. s3[0 .. i+j-1] is an interleaving of s1[0 .. i-1] and s2[0 .. j-1].
Thus, A[n1][n2] represents whether s3 is a interleaving of s1 and s2.
To build up such a table,
1.Set A[0][0] = true. Period.
2.Initialize the first row. The first row means whether s1[0 .. (n1-1)] matches s3[0 .. (n1-1)], correspondingly.
3.Similarly, initialize the first column which means whether s2[0 .. (n2-1)] matches s3[0 .. (n2-1)], correspondingly.
Now we fill up the table. For A[i][j], s3[0 .. (i+j-1)] match? s1[0 .. i-1] weaving s2[0 .. j-1]
4.Note that A[i-1][j] comes from s1[0 .. i-2] weaving s2[0 .. j-1]. Thus, if it is true, we need to compare s1[i-1] with s3[i+j-1].
Similarly, A[i][j-1] comes from s1[0 .. i-1] weaving s2[0 .. j-2]. Thus, if it is true, compare s2[j-1] with s3[i+j-1].
5.Return A[n1][n2]
Hi this a tested code i used using backtacking.
public class combinations {
int arr[];
int sumuptoAi(int m,int n)
{
int sum=0;
for(int i=m;i<=n;i++)
sum=sum*10+arr[i];
return sum;
}
public boolean Combinations(int start,int sum)
{
if(sum==0&&start==arr.length)
return true;
for(int i=start;i<arr.length;i++)
{
if(Combinations(i+1, sum-sumuptoAi(start, i)))
return true;
}
return false;
}
public static void main(String args[])
{
int arr[]= {2,3,7,2};
combinations obj=new combinations();
obj.arr=arr;
System.out.println(obj.Combinations(0, 239));
}
}
instead of using hash you can directly use array.It will save you lot of space.
for eg. as the number ranges from 0 to n-1
you can write this as
for(int j=0;j<arrayLngth;j++)
{
i=j;
len=0;
init(array) // this will make all entries again positive
while(array[i]>0)
{
i=array[i];
array[i]=array[i]*-1;
len++
}
System.out.println(len)
}
Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.
1.insert(value): append the value to array and let i be it's index in A. Set H[value]=i.
2.remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.
3.getRandomElement(): let r=random(current size of A). return A[r].
1.Sort the elements to be searched to be stored in arr[]
2.Now Start from the root of bst.
2.1 search root element in the array arr
if it's index is index>0 or (index < arr.length -1) return false
else if index is 0 then move to Tree's right and arr is from 1 to arr.length-1
or if index is arr.length-1 move to tree's left and arr is now from 0 to arr.length-2;
at the end arr should be empty.
return true
does not work for case
8 14 11 9 13 20 16 22
8 14 20 22 16 11 13 9
@guest in the heap we keeping 2 things the value of element and the array to which it belongs so when removed we will know which element to fetch
- blackfever August 02, 2013@apostle you are right the complexity will be mlogk
- blackfever August 02, 2013time complexity will be m*[log k] assuming log k << m so it can be taken as m ofcourse we need to do nk inserts in heap
- blackfever August 01, 2013Algorithm as follows
1.Create a min heap of first elements of all the arrays.
(a node of heap would be an object containg number's value and number of array it belongs to.)O(Klogk)
2.Now remove the element from the min heap
3. Add corresponding element of that array to heap to which min element belonged.
repeat steps 2 and 3
total time complexity will be ->m is total no of element i.e m=k*n
Here goes the algo
1. Find the max element in the series and that element becomes root.
2.elements which are in the series to the left of root is in left subtree and on the right belongs to right subtree
do it recursively for left and right subtree
for eg:-
Inorder traversal- 5 10 8 20 6 7 4
so 20 is the root
and left subtree {5,10,8}
right subtree {6,7,4}}
no do it recursively for (5,10,8)
here 10 becomes the root and 5 it's left child and 8 it's right child
we can use heap to perform k-way merge sort
Algo
1.create a min heap of first element of all the k array(time klogk)
2.remove the min element and enter the element of the same array to which min element belonged.
now repeat step 2
time-nklogk
did u see here overlap need to be considered.
- blackfever July 21, 2013int dictionaryContains(string word)
{
string dictionary[] = {"mobile","samsung","sam","sung","man","mango",
"icecream","and","go","i","like","ice","cream"};
int size = sizeof(dictionary)/sizeof(dictionary[0]);
for (int i = 0; i < size; i++)
if (dictionary[i].compare(word) == 0)
return true;
return false;
}
// Returns true if string can be segmented into space separated
// words, otherwise returns false
bool wordBreak(string str)
{
int size = str.size();
if (size == 0) return true;
// Create the DP table to store results of subroblems. The value wb[i]
// will be true if str[0..i-1] can be segmented into dictionary words,
// otherwise false.
bool wb[size+1];
memset(wb, 0, sizeof(wb)); // Initialize all values as false.
for (int i=1; i<=size; i++)
{
// if wb[i] is false, then check if current prefix can make it true.
// Current prefix is "str.substr(0, i)"
if (wb[i] == false && dictionaryContains( str.substr(0, i) ))
wb[i] = true;
// wb[i] is true, then check for all substrings starting from
// (i+1)th character and store their results.
if (wb[i] == true)
{
// If we reached the last prefix
if (i == size)
return true;
for (int j = i+1; j <= size; j++)
{
// Update wb[j] if it is false and can be updated
// Note the parameter passed to dictionaryContains() is
// substring starting from index 'i' and length 'j-i'
if (wb[j] == false && dictionaryContains( str.substr(i, j-i) ))
wb[j] = true;
// If we reached the last character
if (j == size && wb[j] == true)
return true;
}
}
}
/* Uncomment these lines to print DP table "wb[]"
for (int i = 1; i <= size; i++)
cout << " " << wb[i]; */
// If we have tried all prefixes and none of them worked
return false;
}
// Driver program to test above functions
int main()
{
wordBreak("ilikesamsung")? cout <<"Yes\n": cout << "No\n";
wordBreak("iiiiiiii")? cout <<"Yes\n": cout << "No\n";
wordBreak("")? cout <<"Yes\n": cout << "No\n";
wordBreak("ilikelikeimangoiii")? cout <<"Yes\n": cout << "No\n";
wordBreak("samsungandmango")? cout <<"Yes\n": cout << "No\n";
wordBreak("samsungandmangok")? cout <<"Yes\n": cout << "No\n";
return 0;
}
can be done by giving threads their sequence and when the running value equals that value then the thread is allowed to run
as below
class resource
{
private int sequence;
public resource(int i) {
this.sequence=i;
}
public int getSequence() {
return sequence;
}
public synchronized void incementSequence()
{
sequence++;
}
}
class sequence implements Runnable
{
int sequence;
resource obj;
public sequence(int i,resource obj) {
this.sequence=i;
this.obj=obj;
}
public void run() {
synchronized(obj)
{
while(obj.getSequence()!=sequence)
{
try {
obj.wait();
} catch (InterruptedException ex) {
Logger.getLogger(sequence.class.getName()).log(Level.SEVERE, null, ex);
}
}
System.out.println("my processing is done with sequence->"+sequence);
obj.incementSequence();
obj.notifyAll();
}
}
}
public class sequenceRunning {
public static void main(String args[])
{
sequence obj[]=new sequence[3];
resource objresource=new resource(1);
for(int i=0;i<3;i++)
{
obj[i]=new sequence(i+1,objresource);
Thread runThread=new Thread(obj[i]);
runThread.start();
}
}
}
It can be done in o(n) with space o(2n)
Algo as follows:-
1.create 2 arrays maxTillNow and minTillNow
where Maxtillnow[i]=max{maxTillNow[i+1],A[i]}
and MaxTillnow[n]=A[n]
MinTillNow[i]=min{MinTillNow[i-1],A[i]}
and MinTillNow[0]=A[i]
2.Now again traverse the array
if a[i]!=minTillnow[i] && a[i]!=maxtillnow[i]
print mintillnow[i] a[i] maxtillnow[i]
plus the above condition can also be written as
if a[i]>minTillnow[i] && a[i]<maxtillnow[i]
@aka u forced me to write the complete code :)
int sumUptoi=a[0];
int x[]=new int[a.length];
x[0]=sumUptoi
i=1;
while(i<a.length)
{
x[i]=a[i]+=sumUptoi;
i++;
} //(o(n) asu can see)
int y[]=new int[a.length];
int sumfromi=a[a.length-1];
y[a.length-1]=a[a.length-1];
j=a.length-2;
while(j>=0)
{
y[j]=sumfromi+a[j]
j--;
}//(o(n) asu can see)
for(int i=0;i<a.length;i++)
{
if(i==0)
s[i]=y[i+1];
else if (i==a.length-1)
s[i]=x[i-1]
s[i]=x[i-1]+y[i+1]
}//this is also o(N)
Algo
1.take 2 arrays X and Y
where X[i]={A[1]+A[2]+ _ _ _ _ +A[i]}
AND Y[i}={A[i]+A[i+1]+A[i+2]+_ _ _ _ +A[n]}
THE ABOVE can be calculated in O(n) time
Now s[i]=x[i-1]+y[i+1]
Boundry conditions needs to be handled for i=0 and i=n
It just another version of finding middle of linked listwith following modifaction
1.Storing head in a temp variable.
2.The termination condition will now be while(p2>next!=Head&&p2->next->next !=head)
this is a kind of producer consumer problem where consumer can consume only until producer has produced
- blackfever May 05, 2013
what I can think of is there should be separate table of department having id->department.
- blackfever April 14, 2016So we can use id instead of the name(which occupies more space)