lalat.nayak
BAN USERuse a suffix tree. Find the deepest node having more than one child.
- lalat.nayak July 06, 2017I initially thought that this was really hard, but after some analysis, the solution appeared simple. You initialize your result as either 12 or 21 depending on what the first item in the pattern is. Track and update the index of the maximum number in result as you add more items.
When you encounter an I add result[max_index] + 1 to the right and set max index to the last element in the result
When you encounter a D get the insert result[max_index] + 1 at max index, shifting everything after it to the right. I have tried using a deque so that this operation can be done in constant time.
from collections import deque
def get_min(pattern):
if len(pattern) > 9:
raise ValueError('Invalid Pattern')
if pattern[0] == 'D':
q = deque([2, 1])
max_index, min_index = 0, 1
elif pattern[0] == 'I':
q = deque([1, 2])
max_index, min_index = 1, 0
else:
raise ValueError('Invalid Pattern')
for i in range(1, len(pattern)):
if pattern[i] == 'I':
q.append(q[max_index]+1)
max_index = len(q) - 1
elif pattern[i] == 'D':
n = q[max_index]
q.insert(max_index, n+1)
else:
raise ValueError('Invalid Pattern')
return q
print(get_min('D'))
print(get_min('I'))
print(get_min('DD'))
print(get_min('II'))
print(get_min('DIDI'))
print(get_min('IIDDD'))
print(get_min('DDIDDIID'))
def get_balancing_index(string):
left_counts, right_counts = [0, 0], [0, 0]
for c in string:
if c == '(':
left_counts[0] += 1
elif c == ')':
left_counts[1] += 1
for i in range(len(string)-1, -1, -1):
if left_counts[0] == right_counts[1]:
return i + 1
if string[i] == '(':
left_counts[0] -= 1
right_counts[0] += 1
elif string[i] == ')':
left_counts[1] -= 1
right_counts[1] += 1
return None
print(get_balancing_index('(())'))
print(get_balancing_index('(())))('))
print(get_balancing_index('))'))
def partition_array(arr, k):
if not arr:
return None
avg = sum(arr)//k
results = []
left = 0
right = len(arr) - 1
while left < right:
result = []
if arr[right] <= avg:
s = arr[right]
while s < avg and left < right:
result.append(arr[left])
s += arr[left]
left += 1
result.append(arr[right])
results.append(result[:])
right -= 1
return results
import math
def get_all(n):
result = []
if n <= 3:
result = [i for i in range(n)]
else:
k = math.floor(math.log(n, 2)) + 1
nxt = pow(2, k-2) + 1
seqs = get_all(nxt)
result.extend(seqs)
m = max(seqs)
i = 0
temp = 0
while i < len(seqs) and temp <= n:
temp = try_append_one_to_left(seqs[i], k-1)
if temp and n >= temp > m:
result.append(temp)
i += 1
return result
def try_append_one_to_left(n, k):
if not n & (1 << (k-1)):
return (1 << k) | n
else:
return None
print(get_all(17))
This is just a matter of getting the next smallest permutation till no smaller values are possible. I solved this iteratively. Essentially it boils down to
1. Identify what two elements need to be swapped to get the next lowest permutation
2. Swapping the the identified elements
Here are the steps
1. Starting from the rightmost element keep going left till you find an element that is larger than the previous element. Let's call this John. I have used to pointers for this
2. Once the pivot has been identified find the closest element(by value) right of John that is larger than pivot (by value). Lets call this Doe
3. Swap the values of John and Doe
4. Reverse sort the array starting from the index next to the original position of John all the way till the end.
Repeat 1-4 till no John is found in step 1
This particular question has an annoying peculiarity that the numbers in the array are not digits. So you'll need to write a custom comparator to compare the numbers. Below is a python implementation
from functools import cmp_to_key
def generate_permutations_desc(array):
custom_sort(array, 0, len(array))
yield array
while True:
current = len(array) - 2
prev = len(array) - 1
index = -1
swap_index = -1
while current >= 0:
if custom_compare(array[prev], array[current]) < 0:
index = current
break
current -= 1
prev -= 1
if index == -1:
return
max_val = 0
for i in range(index+1, len(array)):
if custom_compare(array[i], array[index]) < 0 and custom_compare(max_val, array[i]) < 0:
swap_index = i
max_val = array[i]
array[index], array[swap_index] = array[swap_index], array[index]
custom_sort(array, index+1, len(array))
yield array[:]
def custom_sort(array, start, end):
array[start:end] = sorted(array[start:end], key=cmp_to_key(custom_compare_rev))
def custom_compare(x, y):
n = str(x) + str(y)
np = str(y) + str(x)
return int(n) - int(np)
def custom_compare_rev(x, y):
n = str(x) + str(y)
np = str(y) + str(x)
return int(np) - int(n)
arr = [12, 4, 66, 8, 9]
for p in generate_permutations_desc(arr):
print(p)
def reorder(array, permutation):
i = 0
while i < len(array):
while i != permutation[i]-1:
x = permutation[i] - 1
if 0 < x < len(array):
array[i], array[x] = array[x], array[i]
permutation[i], permutation[x] = permutation[x], permutation[i]
else:
raise ValueError('Invalid permutation')
i += 1
a1 = [17, 5, 1, 9]
a2 = [3, 2, 4, 1]
reorder(a1, a2)
print(a1)
BFS going right to left starting at root and print reverse of path time and space O(n)
- lalat.nayak June 14, 2017You could visualize subarrays of each array as a level in the tree. subarray[0] will be root. subarray[1, 2] will be first level subarray[3, 4, 5, 6] will be second level etc.
All you need to verify is that for a given subarray of the first array the corresponding subarray of the second is a valid rotation. Below is a python code.
def form_same_bst(arr1, arr2):
if len(arr1) != len(arr2):
return False
n = len(arr1)
i = 1
while i < n:
start = i-1
end = 2*i - 1
if not are_rotations(arr1[start:end], arr2[start:end]):
return False
i *= 2
return True
def are_rotations(arr1, arr2):
arr = arr1 * 2
n = len(arr1)
i = 0
result = False
while i < n and not result:
result = True
for j in range(n):
if arr[i + j] != arr2[j]:
result = False
break
i += 1
return result
print(form_same_bst([2, 4, 3, 1, 5, 6, 7], [2, 3, 4, 5, 6, 7, 1]))
def print_frequency(array):
n = len(array)
for i in range(1, n+1):
k = array[i-1] % (n+1)
array[k-1] += (n+1)
for i in range(1, n+1):
print(i, array[i-1] // (n+1))
a = [3, 1, 3, 2, 6, 7, 3, 8, 10, 10]
print_frequency(a)
The best solution has already been provided by Venkatesh. The above is a python implementation of the same. Key thing to note is that we know the range of the numbers i.e 1-n and the size of the array i.e. n. So we can use the array as some kinda makeshift hash table.
We iterate through the array and we add (n+1) to the array[item mod n+1]. Basically every time we encounter the number k we add (n+1) to the kth item of the array.
We take the mod to get the original value of k as k would have been modified as result of the above additions.
In the second iteration all we have to do is to divide each item of the array by (n+1) to get the frequency of the index
The algorithm required here is weaving 2 lists. Consider if you have to weave [1, 2] and [3, 4] together. You can get all the permutations by recursively weaving [2] and [3, 4] prefixed with one and then recursively weaving [1, 2] and [4] prefixed with 3
- lalat.nayak March 17, 2017def weave_arrays(array1, array2):
right = deque()
left = deque()
for item in array1:
right.append(item)
for item in array2:
left.append(item)
prefix, results = deque(), []
weave(right, left, prefix, results)
for q in results:
print(q)
def weave(left, right, prefix, results):
if not len(left) or not len(right):
result = deepcopy(prefix)
result.extend(left)
result.extend(right)
results.append(result)
return
left_head = left.popleft()
prefix.append(left_head)
weave(left, right, prefix, results)
left.appendleft(left_head)
prefix.pop()
right_head = right.popleft()
prefix.append(right_head)
weave(left, right, prefix, results)
right.appendleft(right_head)
prefix.pop()
The solution is not truly O(1) space. The depth of the recursion depends on the elements in the stack.
- lalat.nayak July 07, 2017