kr.neerav
BAN USER1) Scan the array in concentric squares outside in.
2) Mark all 'O' elements as 'o' if any of the 8 elements surrounding it is an 'o' or its on the edge. In case neither of the above is true change it to 'X'
3) In the end scan through the array and convert all 'o' to 'O'
Solve by dynamic programming in O(n^2)
Lets try with an example
abbaabbac
Starting at position 3 each next character either forms palindromes or it forms none. e.g.
initial string : 'abb' (first 3 chars)
next character added : 'a' (char at pos 4)
Now check string of different length that end at 'a' (next char)
'ba'
'bba'
'abba'
Whenever you encounter a palindrome print it.
The logic to check a palindrome is easy and not included here.
Case 1: the digits in the number are capable of forming a palindrome number
1) capture frequencies of each digits in an array
2) all frequencies will be even or there will be only 1 digit with odd frequency
3) In case of former append a string of half the frequency of a digit to the output string e.g. '22'+outputString+'22'
4) In case of latter make the odd frequency digit as the central digit in the output string. Now repeat the above step for the rest of the digits.
Case2: In case the digits in the number are not capable of forming a palindrome number and we have to creating the palindrome by adding/removing min number of digits
1) Same as above case
2) To identify case 2 the logic is that if there are more than 1 digit with odd frequency then it cannot be converted into a palindrome.
3) add/remove digits to make all frequencies even except 1
4) repeat steps of case 1
We will do this by doing a pre order traversal by the tree and maintaining of stack of conditions at each node. i.e. if we are traversing the left tree then we add a condition (< value of node) and if right then condition (>= value of node). These are the conditions that a BST satisfies. For each node check which conditions is doesn't satisfy in the stack and print the pair for which it doesn't satisfy the condition. Running time n nodes and logn comparisons for each node no n*log(n)
- kr.neerav February 12, 2014Very interesting problem. Lets scan the array and find out if we sold the share next day what would be our profit(+) or loss(-). So the new array is
-65,-11,18,83,-60,-42.-3,85,-93,95,5,-96
Now scan the array from left to right and keep summing continuous +ives and store it in a variable max. If the next continuous +ive sum is > max then store that value in max. At the end of the scan we will have the max output. Complexity O(n)
We will do this by doing a pre order traversal by the tree and maintaining of stack of conditions at each node. i.e. if we are traversing the left tree then we add a condition (< value of node) and if right then condition (>= value of node). These are the conditions that a BST satisfies. For each node check which conditions is doesn't satisfy in the stack and print the pair for which it doesn't satisfy the condition. Running time n nodes and logn comparisons for each node no n*log(n)
- kr.neerav February 12, 2014This solution is only applicable when N is so big that it cannot be fit into memory. For a smaller N BFS is the way to go. But can't compare the complexity of both the solution as they work in different scenarios.
Also I don't understand how do we combine space and time complexity into one single complexity. I haven't read any such thing till now. Share any links if you find.
Join the line from center of circle to the outside point. Now the point at minimum distance from M has the least angle with this line i.e. min(theta, 360 - theta) should be the least among all the points.
If we assume points are in order clockwise/anti clockwise this breaks down to the problem of rotated array which is solvable in log(N)
Agreed. First we need to find out in how many steps it can be done. If the number of steps in the input is less than that then it cannot be solved.
If greater then find the number of extra steps. If its even then we can solve the problem in the given number of steps (one step to change something and other to undo that). If odd then it cannot be solved.
The question looks very tough but becomes easy with the following observation.
First we rotate the source string (left or right) to get the maximum match with target. Then change the mismatch characters. If there are n characters in the string then the complexity will be:
1) n times we rotate the array and do n comparison for each rotation = O(n^2)
2) one scan of both source and target to change the mismatch = O(n)
But i guess the n^2 complexity is still very poor. Looking forward to a smarter algorithm for it.
Once we have the minimum number of steps it can be done then we can verify if it can be done in the given number of steps in input.
Writing the algorithm instead of the program
Let 'hello' = 1, 'you' = 2, all other words = 0
1) convert the string into an array of numbers as given e.g. "hello how are you" = 1-0-0-2
2) initialize min_distance = 999999 (very large value)
2) scan this array from left and store distance in count variable (initialized to -1)
whenever array element = 1, reset count value to 1
whenever array element = 0, copy value of count in min_distance if count<min_distance and reset count = -1
increment count if count >0
Can be solved depending on the number of digits.
First lets identify the pattern of frequency of usage of each digit
0-9 : 1
10-99 : 10+10
100-999 : 100+100+100
let N be the input number and A be an array to store frequency of digits
Scan the number from left to right and extract each digit out of it. Let the digit be k and position be j e.g. N = 4375 for k = 4, j = 3
For each digit in N
for i = 0 to k-1
for x = 0 to 9
A[x]+= 10^(j-1)
A[k] += N%10^j
1) Scan all elements and store all elements <= k in an array A O(n)
2) Sort this array. Let the total elements be e O(e*loge) in descending order
3) For i from 1 to e/2
d = k-A[i]
Do a binary search in this array to find the position of d. Output pairs A[i] and all A[j<=d]
Total complexity O(n) + O(e*loge)
Can be solved by dynamic programming. Let
W(k) : no of words in the string from 0 to k. If there are incomplete words then the number is infinity
word(i,k) : returns 1 if a word formed from characters in the string from i to k exists in dict else return infinity
Recursion equation
W(k+1) = min [W(i) + word(i,k+1)] for i from 1 to k
A more optimized approach using recursion can be used:
C(k) : number of numbers of k digits that do not contain 4
N[k] : kth digit in the number N
f(k) : for a given digit k return the number of digits possible for that place (unit, tens, hunderds) e.g if k = 3 then we have 4 options 0,1,2,3 and if k = 5 then we have 5 options 0,1,2,3,5
The recursion equation will be
C(k+1) = (f(N[k]) -1)*(9^k) + C(k)
Base case
C(1) = f(N[1])
Note: This solution includes 0 as a number in its answer
if we use the same array as stack we only need one extra element to track the index of top element of stack. This will be an O(n) time and O(1) space complexity.
If this is not allowed then we can use brute force i.e. to scan the array n times and remove values if they occur simultaneously. This will work in O(n^2) time and will require O(1) space to store the last value viewed in the scan.
This problem is something similar to finding palindrome but that also takes O(n^2).
I can think of an algorithm to do it in 2 passes but not less than that.
1) Take 1 pass through the entire set of balls and use the array to capture frequency of each color (histogram). Thus we can decide what range positions to allot to each color i.e. positions are from 1 to 10000.
2) In the array capture the first available position for each color.
3) Pick the ball at position 1 and place it at the correct position according to the color. Simultaneously update the array to capture the next position available for that color.
4) Repeat the above step for the ball that was displaced because of it.
Not sure about the question. But i will answer some of the specific points in the question.
How to differentiate between different nodes with same data and encountering the same node? A: use the address of the node to differentiate
also how do you make sure you don't run into loops for the exact node? A: as its done in DFS.
I can think of 2 solutions for it
1) Run DFS on the tree to find parent of each node. Now this tree becomes a graph. Run BFS/DFS to find all nodes at distance K
2) Use the concept of rotating trees as in red black trees.
First take the tree with root at the starting node (arbitrary node) and find all nodes at level K. These are all the nodes at distance K in the sub tree.
Then remove all child nodes from the starting node and do multiple rotations so that this node becomes the root. Now find all nodes at level K
The union of both of these is the solution.
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 ...
My understanding is that we need to find palindromes in the existing string. If I store the frequency of characters then I have lost the original order of chars. Your code will work for the problem where we have to print all palindromes that can be formed using the characters in the string. This is a slightly different problem.
- kr.neerav February 15, 2014