kr.neerav
BAN USER1)Break the number into an array of digits
2)Start using insertion sort from right to left
3)When you insert a digit(using insertion sort) if there is a digit on its right, put it in the original position of the digit that was being inserted. Stop
4)Recombine the digits to the number
Let me try to explain the sliding window.
We calculate the histogram of string a (length 3). Then we calculate the historgram of the first 3 characters of string b. If it doesn't matches we calculate the histogram of the next set of 3 chars which are at position 1,2,3 and then next 3 which are 2,3,4 etc So it behaves as if we are sliding a windows across the length of string a. Hope it helps.
1) Scan the tree to look for the node and push all parent nodes encountered in the path to a stack S
2) Write a function to find nodes at K distance which are child of this node (simple DFS). Lets call that function kChild(node)
3) Now pop the parent of the node and find out the k -1 distance child nodes of it.
4) Repeat the process till the stack is empty.
Can be solved through recursion in O(n^2)
Simply put where current index + arr[current index] > n then it can escape the array. So lets add the index of each number to arr[current index].
Scan from left to right and stop at the first occurance of value >= n. From this cell we can escape the array in 1 jump. Now we have to find the min number of jumps to reach this cell, a very obvious case of recursion.
Assumption M<=N
For no of squares in MxN
Size of square: 1 2 3 4..... k... M-1 M
No of squares in row: N N-1 N-2 N-3 N-k+1 N-M+2 N-M+1
No of squares in col: M M-1 M-1 M-1 M-k+1 2 1
Total no of squares = no of squares in row * no of squares in col
sigma [(N-k+1)*(M-k+1)] for k from 1 to M
For rectangles
Length of rectange 1 2 ... k ... N-1 N
No of rectange N N-1 N-k+1 2 1
Total rectangles = N*(N+1)/2
Height of rectange 1 2 ... k ... M-1 M
No of rectange M M-1 M-k+1 2 1
Total rectangles = M*(M+1)/2
Total no of rectanges = M*N*(M+1)*(N+1)/4
Let me explain.
If there is a triangle then its a closed loop. So from any vertex if i go 3 steps and reach it back then there is a closed loop of 3 edges => triangle. Now Since you will do this for all vertices of the graph final output will be number of triangles you found / 3
The scanning of the graph is done by DFS for this problem.
Good idea about log but am not sure how it helps. Also if the number of factors increase by just 1 then the number up combinations will go up exponentially. Here is a different approach to the problem.
The idea is to find the next combination of [m,n,p] using dynamic programming.
Create an array out[N][N][N] to store the various values of product for different combination of [m,n,p] where N is the N'th number we have to find.
//track which factors have been used (Y = Yes, N = No). we will see its use towards the end
used_flag = [N,N,N]
//base values of m,n,p. This will be clear in the end
base_val = [0,0,0]
//pervious combination of [m,n,p]
prev_comb = [0,0.0]
for p = 0 to N
//the next number will have one of the values of [m,n,p] increased. So lets assume the value of all increased by 1
new_comb = prev_comb + [1,1,1]
//try all possible combinations till base_val to find the next smallest number
//finding out value of number with the new combination of m,n,p
min = value(new_comb)
last_val = value(prev_comb)
for i from new_comb[0] to base_comb[0]:
for j from new_comb[1] to base_comb[1]:
for k from new_comb[2] to base_comb[2]:
if out[i][j][k] == 0:
out[i][j][k] = (2^i)*(3^j)*(5^k)
//do not process any value which is smaller than the previous value
if out[i][j][k] <= prev_value:
continue
if min>out[i][j][k]:
temp_comb = [i,j,k]
min = out[i][j][k]
prev_comb = temp_comb
find out which of the value of m,n,p increased at the end of the iteration and marked used flag as Y for that. Once all flags are marked as Y change the value of base combination to that of temp_comb and used_flag = [N,N,N]
With the help of used_flag and base_comb we are able to reduce the number of times the inner loop of i,j,k runs. e.g. in the given example once the value 30 (which contains all factors used atleast once) we only want to check all combinations of m,n,p which will be greater than its combinaion.
Hope the explanation was sufficient.
The idea is wherever we parse the right subtree while searching thats the in order predecessor. And whenever we parse the left subtree we have to remember for which parent we parsed the right subtree.
node = root
pre = NULL
found = False
while True:
if el < node.value:
node = node.left
continue
else if el > node.value:
pre = node
node = node.right
continue
else if node == NULL:
break
else:
found = True
break
if found == True:
if pre != NULL:
print pre
else:
print 'no predecessor exists'
else:
print 'element not found'
Time complexity: O(logn)
Space complexity: O(1)
For both the problem its gonna be DFS with the slight change of printing the path before calling recursion. I will write the algo for the graph one.
for node in all_nodes:
DFS(path, node) {
print path
if node in path:
return
for child in node.children:
DFS(path+node, child)}
The visited flag logic is insufficient here as we might have to visit a node more than once if its a part of more than 1 path.
- kr.neerav March 24, 2014You are right this logic won't work..
Lets try another approach. This problem can be broken down into the subproblem of finding max rectangle area in a histogram.
Preprocessing
Scan the array top to bottom and A[i+1,j] = A[i,j] + A[i+1,j] whenever A[i+1,j] is 1
This will give us the count of continuous 1's associated with a given cell above it. So the array becomes.
00000
01110
02200
03000
00000
Now each row represents a historgram. We have 2 algorithms to solve this problem O(n) and O(nlogn).
So total time complexity is O(mn) or O(mnlogn).
Space complexity O(n)
Am not sure how to prove it but the logic is to develop the size of the rectangle of 1's from top to bottom and left to right. At each step i am using information about the rectangles already created (top and left) and expanding it.
I tried it for a few examples and it worked. Now that you have mentioned it I am very eager to find out how to prove it. if you happen to get a proof please share.
I guess the problem is to find out the max rectangle. It can be done with Dynamic Programming.
1) Create an array with size of the given array i.e. Sol[m][n] which is an array of tuple(left, right) and let input array by A[m][n]
2) Outer loop (i) from left to right and inner loop (j) from top to bottom
3) if A[j,i] = 0 then Sol[j,i] = (0,0)
else
Sol[j,i] = (Sol[j,i-1].right+1, Sol[j-1,i].left + 1)
The max rectangle will be where the product of the tuple is max. Here is how the solution array looks like
(0,0) (0,0) (0,0) (0,0) (0,0)
(0,0) (1,1) (1,2) (1,3) (0,0)
(0,0) (2,1) (2,2) (0,0) (0,0)
(0,0) (3,1) (0,0) (0,0) (0,0)
(0,0) (0,0) (0,0) (0,0) (0,0)
Time Complexity O(mn)
Space Complexity O(mn)
I guess the question is given the initial position of 2 knights which one of them will win.
A logic similar to BFS can be used to find out min number of steps needed to go from 1 cell to another. Once you reach the bottom of the cell stop.
Do the same for the other knight. The one with lesser number of steps is the winner.
1) For each node in the tree count the no of nodes in the left subtree (k).
2) Store all elements in an array (A) and sort them
3) The root node of the BST will have the same number nodes in the left subtree as the one in the original tree. So use the count of root to find the element that will form the root of BST e.g. if left count is k then root of BST is A[k]
4) Recursively do this for the left and right subtree
Space complexity O(n)
Time complexity O(nlogn)
There are 2 parts to this question in order traversal and printing alternatively. Both cannot be done simultaneously because of the difference in structure and size of the 2 trees.
So lets preprocess the tree first and then print it alternatively. There is a concept of right in threaded tree where each node points to the next in order successor (you can find more online). Once this is done in order traversal in both the trees will be just like traversing through a linked list and hence printing alternatively will be easy.
Now the question is how to convert this tree into a threaded tree. Its a lot easier to construct such a tree from scratch, but in this case we need to convert the current one. Here is a pseudo code for it
current = root //current node
next = NULL //in order successor
inorder(current, next)
if current == NULL
return
if current->right == NULL //not linked to the inorder successor
current->right = next //create the link
threadedFlag[current] = True //hashmap to keep track of all nodes whose right pointer has been changed as they create loops in the tree.
if current->right == next //to avoid traversing the loops created in the tree
return
inorder(current->left, current) //traverse the left subtree
inorder(current->right, next) //traverse the right subtree
I have not implemented this code. But I think it should work. The hashmap is causing space complexity of O(m+n). However its not needed if the intended purpose of tree is only whats mentioned in the problem.
- kr.neerav February 23, 20141) Build hashmap of the array (or sort the arrray) for part 1
Complexity O(N) in case of hashmap and O(nlogn) in case of sort
2) Use 2 loops and hashmap to find out all unique values of sum possible
3) Find the different between sum of min 2 elements (sum1) and max 2 elements(sum2) and let it be D. If D<<N, then iterate from sum1 to sum2 to find various values of sum possible.
1) Use recursion to get all combinations of coins (2^n) and hashmap to store unique sum values.
combination(sum,i)
if i == no of elements in array
//a particular combination of coins reached
H[sum] = sum
return
//include element i in the sum
combination(sum+A[i],i+1)
//do not include element i in the sum
combination(sum, i+1)
I guess any algorithm that stores the strings is going to face space issues. One way to store strings efficiently is a trie. At each leaf node we can store the number of times it appears. Then you can simply use the top K min/max elements in the array algorithm.
Time complexity O(N)
Space complexity not sure. It will be great if anybody can shed more light on it.
In case there are only 2 eggs.
Lets say we have N floors and I choose a constant step size of x
No of steps to find the floor where it breaks = N/x + x
First part to identify the block size where it breaks
Second part to check for each floor in the block to identify the exact floor where it breaks
Now its just a problem of minimizing it which can be solved by differentiation, which gives x = sqrt(N)
In case of infinite eggs binary search is the right option.
I can only come up with a brute force method for this.
1) create a historgram of characters of needle string
2) Starting at the beginning of haystack pick sets of k chars (where k is the length of needle string). If the historgram of this set matches the one for needle then return true
Running time O(kn)
We will use recursion to solve this.
dequeue(set of people)
filter all people who have 0 no of people in front of them
//as 0 means either they are in the front of the queue or all people ahead of them are smaller than them
find the person with smallest height
//this will be the guy standing at the front of the queue
As this person will be removed so all people having height less than him and behind him (no of tall > 0) will no longer be able to see him. So we need to reduce the count of no of tall people by 1 for each
print the person and call the function with the remaining set of people.
Please ignore the logic i shared earlier. Its not dynamic programming but only brute force. Here is the dynamic programming one
Observation: given a palindrome
abcdcba
we see that all substrings of this is also palindrome e.g.
bcdcb
cdc
This is the logic that we are gonna use here. We will also use array A of the same length as the string which will store the length of palindrome that ends at a given char e.g.
abcdcba
A = {0,0,0,0,3,5,7} //we will just see how this array is generated
Q) how to check if there is a palindrome ending in the previous char
Ans) if A[i-1] > 0 then true else false
Also if A[i-1]== 0 then check if the previous char = current char. This will be a 2 length palindrome.
or if the last 2 character and current character form a pallindrome
(Its confusing, but hope i have explained enough)
Lets suppose isPalindrome() is a function that implements the above logic and returns the length of the palindrome ending at a given char
Now start scanning the string.
for each char value = isPalindrome()
if value == 0 A[i] = 0
if value >0 and if current char = char at position i - value
then A[i] = value + 2
In the end scan the array A[i] and find the max length of the palindrome present.
There is one algorithm which will work in linear time but it is probabilistic.
1) Create a bloom filter (BF1) and add each element to it ( O(1) space and O(N) complexity)
2) If any element is already present then add it to a separate bloom filter (BF2) (O(1) space and O(N) complexity)
3) Once scanning the array is done. Start with the first element and use bloom filter BF2 to check if its present in it or not. The first element that you find that is not present in BF2 is the answer.
RepProcess Technicians are responsible for monitoring and improving manufacturing and engineering processes. They are employed by a wide variety of ...
Repchristinetcollazoc, Software Analyst
I am a pediatric nurse.I administer directly procedures and medicines to children according to prescribed I also continually assess ...
A number could be decimal also. So also need to check that there is atmost 1 dot character and it is not present in the beginning or end.
- kr.neerav April 04, 2014