DarkKnight
BAN USERdivm01986, string builders shouldn't be used for adding single characters. it is causing too much overhead.
- DarkKnight August 31, 2015dinesh kumar's solution doesn't handle multiple spaces well.
- DarkKnight August 31, 2015i/ should contain "D" too correct ?
- DarkKnight August 30, 2015dana,
can the original lists be modified ?
sg
1) does each node have link to its parent ?
2) what do you mean by "if all nodes of a tree are not given, return null". In you example all the nodes (A-F) are not in the list (FEA). Did you mean if the list contains a node that is not in the tree ?
sg,
did you ask the interviewer about the following assumptions
1) Are the points in the input provided in a particular order (e.g. clockwise, anti-clockwise, no particular order )
2) Is the Square or Rectangle, parallel to the axis
Can you provide a sample of the file
- DarkKnight July 28, 2015The Question is not clear. Can you provide an example.
What is the expected solution for
10 20 30
5 15 20 30 35
Assumption : there EXISTS a majority element
Logic : keep a record of majority element candidate and its count so far, if the next number matches, increase the count, else decrease the count, if count = 0, set candidate = current number
Time Complexity : O(n)
int candidate = 0;
int count = 0;
for i = 0 to n - 1
if(count==0)
candidate=a[i];
else if(a[i]==candidate)
count++;
else
count--;
end for
print candidate
can some one tell me what is "lexicographically largest suffix"
- DarkKnight October 21, 2012More descriptive questions please.
What do you mean by mix two binary strings?
What do you mean by special constaints.
how are pennies related to maze ?
- DarkKnight October 19, 2012What is a bit string algorithm ?
What is a squashed order ?
In your question you have said all rows are sorted.
But I think in this solution you are assuming all rows and columns are sorted.
One should ask, will we necessarily have only 5 words. In that case I would use simple string matching
On the other hand, if the number of words are large, I will use a Trie.
This is a dynamic programming problem.
Let original array = a[0 to n-1]
Let solution array = s[0 to n-1] where
s[I] = max sum of non-adjacent numbers from a[0 to I];
So,
s[0] = a[0];
s[1] = Max(a[0],a[1]);
Now recursively,
s[I] = Max(s[I-1],a[I]+s[I-2]); you either take the ith element or you dont
s[n-1] will be final solution.
Also make sure when you are sorting, if boundary value are same then a start should come before end.
my boundary class looks like this
enum BoundaryType
{
Start = 0,
End = 1
}
class Boundary : IComparable<Boundary>
{
public int Value { get; set; }
public BoundaryType BoundaryType { get; set; }
public int CompareTo(Boundary other)
{
if (Value == other.Value)
{
return BoundaryType.CompareTo(other.BoundaryType);
}
else
return Value.CompareTo(other.Value);
}
}
store each boundary value as a separate element in an array with the information whether it's the start boundary or end boundary.
Sort this array by boundary value.
initialize an integer overLapCount = 0;
Traverse this array from start to finish
whenever you cross a "Start" boundary, increment overlapCount
whenever you cross an "End" boundary, decrement overlapCount
store the maxOverLapCountSoFar
at the end of the traversal you will have the information about what is the maximum possible overlap for a range.
You can easily modify this to store the range information as well.
Not all questions have to be algorithm intensive.
For good or bad, Some interviewers are looking for
1) Whether you are handling all corner cases
2) Whether you are reducing duplication of code ( we can parse integral and decimal part by some common code )
3) Whether you are using descriptive variables names ( "decimalPart" instead of "d" )
Assumption : All Numbers, Keys are +ve
Sliding Window Method
int low = 0;
int high = 0;
int minimum = int.MaxValue;
int sum = 0;
while (low < size)
{
while (sum < key && high < size)
{
sum += a[high];
high++;
}
if (sum >= key && sum < minimum)
minimum = sum;
sum -= a[low];
low++;
}
Does anyone have a solution for positive and negative numbers ?
- DarkKnight October 14, 20121 = 1
4 = 1 + (1 + 2 * 1)
9 = 4 + (1 + 2 * 2)
16 = 9 + (1 + 2 * 3)
Continue this series
if you reach exactly n then n is perfect square
but if you reach > n, then n is not perfect square
O(root n)
Use a stable sort like Merge Sort with the following Comparision function :
two +ve are same
two -ve are same
two zeros are same
and
-ve < zero < +ve
Considering an unsigned 32 bit integer
There are 2^32 possible values ( about 4 Billion )
Allocate a single bit for each value ( This would required 512 MB of memory )
Read the file, for each integer I, set ith bit to 1
Once reading file is complete
find the first bit which is not 1
print the number corresponding to this bit.
class Stack
{
private int c = 0;
private PriorityQueue pq;
public void Push(int x)
{
c++;
pq.Insert(x,c);
}
public int Pop()
{
c--;
return pq.Remove();
}
}
Crazy Idea very likely to be shot down instantly
O(nlogn)
Have a BST where each node is of this form
{
class Node
{
public int Data;
public Node Parent;
public Node Left;
public Node Right;
public int SumOfLeftSubTree;
public int SumofAllValuesLessThanCurrent;
}
}
Modify insert such that
1) In tree with root n, if you are trying to insert new element x into n's Left subtree then do this
n.SumOfLeftSubTree += x
2) To calculate SumofAllValuesLessThanCurrent, traverse tree upwards till root node. Every time temp node t Right child of parent p, do n.SumofAllValuesLessThanCurrent+=p.Data+p.SumOfLeftSubTree
Hope the solution makes sense.
I think its correct.
But its quite complicated and may not be optimal.
Hi Susheel,
how can we make the assumption that "because y-coordinate of bottom points is always 0". The question says the rectangles are axis aligned, which means that the sides are parallel to the axis. Not necessarily on the axis.
I think you make a fair point that if we only have to check for 1 rectangle we can do it in log(n) time.
But note that sorting will take at o(nlogn) time.
So how is this method better than checking the new rectangle against each existing rectangle which will take O(n) time
Hi Susheel, my observations here - I think you would need to maintain two sorted arrays ( one by x and one by y )
Try to insert the new rectangle into these sorted arrays.
Intersection will happen when
New Rectangle N overlaps with same rectangle R from existing list on both x and y axis.
Note that trying to insert this rectangle into the sorted array is O(N) operation.
So I am not sure if this method is any better than just checking against each rectangle by simple method.
Thoughts ?
For two rectanles A and B
A : (AX1,AY1,AX2,AY2)
B : (BX1,BY1,BX2,BY2)
{
if(AX2<BX1||AY2<BYW||AX1>BX2||AY2>BY2)
No Intersect
ELSE
Intersect
}
- DarkKnight October 06, 2012Use a combination of iterative inorder traversal, reverse in-order traversal and the algorithm to find two numbers in a sorted array whose sum is k
- DarkKnight July 31, 2012Everyone is using modulus. As people pointed out, this will lead to slightly non-uniform probability.
We should use divide
x = r1 + ( random() / Int32.MaxValue ) * ( r2 - r1 )
I may be wrong here. But I don't think a O(logn) solution exsists.
- DarkKnight July 24, 2012I do not how to identify whether a pair of characters constitute a valid multibyte character or not.
We can ask this to the interviewer.
Let us assume we have this function at our disposal to use
bool IsMultibyte(char a,char b)
I would proceed like this
let i = 0
repeat while i < n
if IsMultiByte(a[i],a[i+1])
Swap(a,i,i+1)
i+=2
else
i+=1
Reverse Entire String
Sorry for the indentation. I don't know how it works
The question is not clear to me. Can someone clarify.
e.g.
Let us say the stack Is like this
v00
v10 v11
v20 v21 v22
I am guessing, v00 fills in first.
In which scenario will water flow from v00 to v01 or some place else
Am I missing something here. Isn't this as easy as performing an inorder traversal
And when we "visit" each node. Just add it to the end of the linked list.
Let input = I
Let Find string = F
Let Replace string = R
Let n = I.Length
Let fn = F.Length
Let rn = R.Length
Use KMP to find each occurrence of F in I store in an array A
Loop through this array to ensure that distance between consecutive elements is greater than fn.
If for any element the distance is less, delete that element
Let no. of elements remainining in array = c
if(rn>fn)
{
allocate (rn-fn)*c extra bytes to input I
shift the original string so that it occupies the end of the array ( e.g. 0000ABCD )
}
take two variables i = 0, j = start of the shifted array ( 0 in case of no shift )
Repeat till j < n
{
if j is not present in A
{
a[i]=a[j]
increment i
increment j
}
else
{
insert R
increment i by rn
increment j by fn
}
}
I request everyone to write algorithm rather than code. It's much easier and faster to read.
Here is my proposed solution. It's O(n*n) time. O(n*n) space.
Let in any substring, the minimum value be n, maximum value be m, sum of all values be s.
For the condition to be true in this substring the following condition should be satisfied
s = m * ( m + 1 ) / 2 - ( n - 1) * n / 2
Let us find the m, n and s for each possible substring
We can formulate a dynamic programming to calculate this
I would leave it as an exercise to calculare these.
This can be done O(n*n)
s[i,j] = sum of all values in from char i to char j ( i <= j )
m[i,j] = max of all values in from char i to char j ( i <= j )
n[i,j] = min of all values in from char i to char j ( i <= j )
Define two variables iMaxRange, jMaxRange
Loop through each value in our 2-D arrays to check if condition is satisfied. ( s = m * ( m + 1 ) / 2 - ( n - 1) * n / 2 )
If condition is satisfied
{
if( j - i > jMaxRange - iMaxRange)
{
iMaxRange = i
jMaxRange = j
}
}
At the end iMaxRange and jMaxRange should give you the answer.
Please let me know if this is not satisfiying any scenario.
Request to all. Please referain from writing code here. A algorithm is much more helpful.
I guess the question is challenging when we mention that the matrix is actually a "Young Tableau"
My proposed method destroys the array.
Pop the Minimum Value from the "Young Tableau" while maintaining the "Young Tabluea" property.
Each Pop can be done O(m+n) time
Hence to get k'th smallest, time would be O(k(m+n))
homeofcox-cs.blogspot.in/2010/04/young-tableau.html
Can someone tell a method which would not destroy the array
I hate that evil dwarf
- DarkKnight July 23, 2012I request everyone to post algorithm rather than code. Most people here do not have time to go through many lines of code.
I could only think of a O(n) time and extra O(n) space complexitiy for this problem.
While performing traversal store the parent of each node in an array.
e.g
parent = new int[n];
parent[i] = j; // Means j is parent of I
Now when you reach a leaf node. Back Track this array to find the path.
I request everyone to post algorithm rather than code. Most people here do not have time to go through many lines of code.
- DarkKnight July 23, 2012This is probably lame
1) Sort using merge sort O(nlogn)
2) Do 3SUM
This is a simple question. Why are we making it complicated. "Student" has already given the solution.
- DarkKnight July 23, 2012The Question is in correct.
Considering a binary Tree.
Parent can have 0 - 2 child nodes
child can have 0 - 1 parent ( 0 in case of root )
How do you reverse this ?
The question is not clear. Can the original poster or someone else who
knows what the question is describe the problem clearly.
Question is incorrect
As some one pointed out - any array can be converted to this format
So sorting will take n*n with O(1) space
or n*log n with O(1) space.
I am probably wrong but does the following approach work
1) Find the "Lowest Common Ancestor" of A and C
2) Modify this algorithm to keep track whether B is encountered on the path selected.
in step 1, count the number of odd number. Let it be n.
Perform Array Reverse from 0 to (n-1)
"sen" has already posted the correct solution.
- DarkKnight July 19, 2012IMHO - Most people will not have time to go through code. A neatly explained algorithm works the best.
As for this question. This is my suggestion
1) Divide the pattern into 2 parts so that first part doesn't have a '*'. e.g. Divide "ab*bc*cd" into "ab" and "bc*cd"
2) Using KMP find first occurrence of "ab". For the rest of string, recursively search for the pattern "bc*cd". If match is found return true.
3) Repeat for remaining occurrence of "ab".
4) Return false if not more instance of "ab" lest.
why stop when i>=j ? we need to reverse the entire string.
- DarkKnight August 31, 2015