G10
BAN USER- 5of 7 votes
AnswersImplement below function.
int getRandom(int N, int K[])
Constraints:
->K is sorted and contains elements in range [0,N)
->Output should be a random number between [0,N) excuding elements from K
->probability of generated number should be 1/(N-K.length) and not 1/N
-->int uniform(int N) is given which returns random number [0,N) with 1/N probability for each number.
->No more than O(1) memory
->No more than O(N) time
Below is my solution but it uses O(N) space.
- G10 in United Statespublic int randomNumber(int N, int[] K) { // K is sorted //assumed size of K is less than N int remains[] = new int[N-K.length]; //i is index [0,N-1], j is an index of K, k is an index of remainings //Fill remaining array for (int i=0,j=0,k=0;i<N;i++){ if (i!=K[j]){ remainings[k++]=i; }else{ j++; } } int index = uniform(remainings.length); return remainings[index]; } Time complexity: O(N) Space Complexity: O(N)
| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm
Here is O(N) time algorithm. It's kinda hard to explain in words so I wrote a program. It may not seem O(N) because of so many loops but I guarantee that it's O(N). I have tested for given two inputs and some other special cases. You may try more others. If you have counter example then please let me know.
def sort(lst):
s1=0
s2=1
#Find start index of second list
while s2 < len(lst) and lst[s2-1]<lst[s2]:
s2+=1
#sorting loop
while s1<len(lst) and s2<len(lst) and s1<s2:
if lst[s1] >= lst[s2]:
index=s2
count=0
#finding the count of elements which need to be swapped
while index< len(lst) and lst[s1] >= lst[index]:
count+=1
index+=1
index=s2
#swapping elements
swap(lst,s1,index,count)
s1+=count
else:
s1+=1
print(lst)
def swap(lst,s1,s2,count):
while count!=0:
lst[s1],lst[s2] = lst[s2] , lst[s1]
s1+=1
s2+=1
count-=1
lst=[1, 5, 10, 15, 20, 2, 3, 4]
lst=[1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11]
sort(lst)
This is corrected code. I've also optimized the search. In your case even though T2 is part of T1.right, it will go and search for T2.root in entire T1.left because in your else condition you search for T2 in T1.left before in T1.right.
Corrected code:
def isSubTreeOrNot(T1,T2,search):
if T2==None:
return True
elif T1==None:
return False
if T1.data == T2.data:
return isSubTreeOrNot(T1.left,T2.left,search) and isSubTreeOrNot(T1.right, T2.right,search)
if search:
if T1.data>T2.data:
return isSubTreeOrNot(T1.left,T2,search)
elif T1.data<T2.data:
return isSubTreeOrNot(T1.right,T2,search)
else:
return isSubTreeOrNot(T1,T2,False)
else:
return False
isSubTreeOrNot(T1,T2,True)
This code won't work as you have combined two functionality into single function.
[1] searching T2's root into T1 tree.
[2] After finding T2's root in T1, checking if entire T2 exists into T1.
This is because of following example.
T1:
4
/ \
2 6
/ \ / \
1 3 5 8
\
9
T2:
6
/ \
5 9
In this case when you call isSubTreeOrNot(T1,T2), it will first try to search 6 in T1. Once it finds it, it will return true for (6,6) and (5,5) calls which is correct so far. But when you call isSubTreeOrNot(8,9) it will go in if condition try to search 9 in the sub trees of node 8 of T1. Eventually it will return true and whole function call will return true where as it was supposed to return false.
I know It's kinda confusing. I tried my best to explain my point. We need to pass a flag which indicates that we are not supposed to try to search T2's node in T1.
I've tried to decompose all the conditions in three separate functions because not all the conditions are applicable to all the nodes. This fact becomes more significant when # of nodes in given trees is in terms of thousands.
def subTree(T1, T2):
if T1==None or T2==None:
return True
return isSubTree(T1,T2) or isSubTree(T2,T1);
def isSubTree(T1,T2): #Finds T2.root in T1
if T1 == None: # Reached Leaf of T1 but could not find T2.root yet
return False
if T1.data < T2.data: # Find T2 on left subtree of T1
return isSubTree(T1.left,T2)
elif T1.data > T2.data: # Find T2 on right subtree of T1
return isSubTree(T1.right,T2)
else: # compare both trees now as we found T2.root in tree T1
return isSubTreeHelper(T1,T2)
def isSubTreeHelper(T1,T2):# Checks if T2 is subtree of T1
if T2==None: # T2's branch ends then return true
return True
elif T1==None:# T1 ends before T2 then return False
return False
else:
return T1.data==T2.data and isSubTreeHelper(T1,T2) and isSubTreeHelper(T1,T2)
def findFarthestLeaf(root,level,maxLevel,leaf):
if root==None:
return 0,None
if root.left==None and root.right==None:
if level>=maxLevel:
return level,root
else:
return maxLevel,leaf
if root.left!=None:
level,leaf = findFarthestLeaf(root.left,level+1,maxLevel,leaf)
if root.right!=None:
level,leaf = findFarthestLeaf(root.right,level+1,maxLevel,leaf)
return level,leaf
findFarthestLeaf(root,0,0,None)
def inOrderSuccessorMain(root, node):
if root == None or node==None or (root.left==None and root.right):
return False
return inOrderSuccessorHelper(root, node)
def inOrderSuccessorHelper(root, node):
found = False
if root == None:#node not found then return False
return found
elif node.data < root.data:#node less than root then search left subtree
found = inOrderSuccessor(root.left, node).
if found == None:#if found=None then root is the successor
return root
elif node.data > root.data:#node less than root then search right subtree
found = inOrderSuccessor(root.right, node)#found can be False, None, or some node
else:
if root.right != None:# Find left most node of right subtree
found = rightSubTree(root.right)
else
return None # return None if no right node exists
return found
def rightSubTree(root):
if root.left == None:
return root
else:
return rightSubTree(root.left)
Easiest solution. No need to use stack or create a new list at all. It's all inplace reversing.
- G10 May 30, 2013