kala kutta
BAN USERDude I hope you check your code for segmentation fault before you paste it in here.
- kala kutta July 11, 2013You make it sound very simple. Do you have a working code for this?
- kala kutta July 11, 20131. Find the node with the searched value for using the regular BST node lookup. Also look for the first time the branching happens for the left and start counting the nodes thereafter.
(If there is no branching, there can't be any next sibling)
2. If branching occurs again, keep a note of the node and reset count
3. The count is the distance b/w the LCA (at the location where branching occurred) of the sibling and the searched value.
4. Knowing the LCA node, start DFS until the depth traversed == count (from last step).
class Node(object):
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def findcommonNode(node, val):
isLeft = True
nodeP = None
count = 0
while node != None:
if node.data == val and isLeft:
return nodeP, count
if val < node.data :
if node.right:
nodeP = node
count = 0
isLeft = True
node = node.left
else:
node = node.right
count += 1
return None, count
def nextSibling(node, i, count):
if not node:
return None
if i == count:
return node
if node.left:
node = nextSibling(node.left, i+1, count)
elif node.right:
node = nextSibling(node.right, i+1, count)
return node
def findNextSibling(root, val):
pNode, count = findcommonNode(root, 7)
if pNode:
sNode = nextSibling(pNode.right, 1, count)
return sNode.data if sNode else None
Updated and fixed.
- kala kutta June 21, 2013Algorithm:
-------------------
- Decrement 1 from the least significant digit and increment for 1 it's predecessor only if least significant digit != 0 and predecessor < 9. Reason is you cannot decrement from 0 and increment above 9 to make it fall under 0-9.
- Evaluate the sum of all the digits seen so far.
- If the above condition doesn't satisfy, repeat the same with the same number without the least significant digit.
- The moment we hit the condition, take the sum and find the smallest number for all the rest of the digits seen before.
Code:
-------------------
I treat the number as a number array to account for 0999. 0999 otherwise means octal representation (leading 0).
Let's say I have num = {A0, A1, A2, A3 }
Things to check for
1. Always start with last but 1 (A2 and the second least significant digit) element and check if it is < 9. If it is 9, there's no way you can increment it by 1. Also check if A3 != 0. If so, you cannot decrement it. Hence continue
2. Repeat the above step until you do hit the if case and can break out of the loop. (Since we are looking for the next larger number to satisfy the mentioned condition)
#include <stdio.h>
void smallestNum(int *numarr, int i, int j, int sum)
{
for (j;j>i; j--)
{
int sub = sum>9?9:sum;
numarr[j] = sub;
sum -= sub;
}
}
void nextBig(int *numarr, int length)
{
int sum = numarr[length-1];
for (int i =length-2; i>=0; i--){
sum += numarr[i+1];
if (numarr[i] != 9 and numarr[i+1] != 0)
{
numarr[i] += 1;
numarr[i+1] -= 1;
sum -= 1;
smallestNum(numarr, i, length-1, sum);
break;
}
}
}
int main(void){
int number[] = {1,9,9,9,0};
int length = (int)(sizeof(number)/sizeof(number[0]));
nextBig(number, length);
for (int i=0; i<length; i++)
printf("%d",number[i]);
printf("\n");
}
190 -> 208
1990 ->
listString = list()
def getChar(num):
if num >= 1 and num <= 26:
return chr(num + 96)
return ''
def getNum(char):
return ord(char) - 96
def generateStrings(numString, length):
newNum = int(numString[length-1])
if length == 1:
listString.append(getChar(newNum))
return
generateStrings(numString, length - 1)
# Check if the new number can be summed with the existing number
for i in range(len(listString)):
string = listString[i]
newChar = getChar(newNum + getNum(string[-1])*10)
if newChar:
if newNum != 0:
listString.append(string[:-1] + newChar)
else:
listString[i] = string[:-1] + newChar
if newNum != 0:
listString[i] = string + getChar(newNum)
x = "1123"
x = "101523"
x = "1020"
generateStrings(x, len(x))
o/p =
1> ['aabc', 'kbc', 'alc', 'aaw', 'kw']
2> ['jaebc', 'jobc', 'jaew', 'jow']
3> ['jt']
Everyone wants to be a smart-ass. I am human after all!
I think Shashanks solution is the best possible solution one can ever have. Google itself (and Amazon ) uses trie for string comparison purposes :). You need to do more than just Masters in CS (to get a job) to know that.
Jikes solution is hopelessly wrong. The second string has to be matched for all the prefixes. Each prefix comparison takes O(1) with m such comparisons which makes it O(M). N such comparisons makes it O(N*M)
However tje question itself isn't clear. Do you want to find the longest common prefix among all the strings or just the longest common prefix?
Nice and easy solution!
The only comment I could make is that
childIndex can be calculated in the following way
childIndex = i + height[i] + 1 for the first child,
childIndex += 1 for the next.
I think O(n^2) cannot be avoided....
A rectangle can also be formed without taking the max-height of any bar into consideration. What if sub-rectangles are allowed?
For e.g take a bar graph as follows - [1,1,2,3,1,1,1,2,3,1,2]
In this case, the rectangle with the largest area is max_height(bar(0))=1 to max_height(bar(10))=1.
Was atoi and itoa not allowed? Otherwise....
char *charIncr (char *myStr) {
int myInt = atoi(myStr)+1;
myStr[0] = '\0'; //Can be ignored
int strLen = strlen(myStr);
char *newStr = (char*)malloc(sizeof(char)*(strLen+1));
itoa(myInt,newStr,10);
return newStr;
}
Agree with alex
- kala kutta December 19, 2017