Longest substring
in Programming on Search, Interview, Python
Write a function to find the longest common prefix string amongst an array of strings.
Longest common prefix for a pair of strings S1 and S2 is the longest string S which is the prefix of both S1 and S2.
As an example, longest common prefix of “abcdefgh” and “abcefgh” is “abc”.
Given the array of strings, you need to find the longest S which is the prefix of ALL the strings in the array.
Example:
Given the array as:
[
"abcdefgh",
"aefghijk",
"abcefgh"
]
The answer would be “a”.
Idea: Use binary search idea
- Pick up the shortest string among all strings.
- Divide the string equally,
- If the left part is common among strings, we update our common prefix and search for the remaining in the right part
- If not, search for the common prefix in the left part.
class Solution:
# @param A : list of strings
# @return a strings
def isSubStringofAll(self, A, s, lo, hi):
for i in range(1, len(A)):
string = A[i]
if string[lo:hi+1] != s[lo:hi+1]:
return 0
return 1
def longestCommonPrefix(self, A):
if len(A) == 1:
return A[0]
# find min length
min_len = 10**6
for a in (A):
if len(a) < min_len:
min_len = len(a)
# binary search
lo = 0
hi = min_len
common_prefix = ''
while (lo <= hi):
mid = int(lo + (hi - lo)//2)
s = A[0]
if self.isSubStringofAll(A, s, lo, mid):
common_prefix += s[lo:mid+1]
lo = mid + 1
else:
hi = mid -1
return common_prefix
Implement Power Function
Implement pow(x, n) % d.
In other words, given x, n and d,
find (xn % d)
Note that remainders on division cannot be negative. In other words, make sure the answer you return is non negative.
Input : x = 2, n = 3, d = 3
Output : 2
2^3 % 3 = 8 % 3 = 2.
class Solution:
# @param x : integer
# @param n : integer
# @param d : integer
# @return an integer
def pow(self, x, n, d):
if x == 0:
return 0
if n == 0:
return 1
temp = self.pow(x, n//2, d)
if n % 2 == 0:
return (temp * temp) % d
else:
return (x * temp * temp) % d
Search for a Range
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example:
Given [5, 7, 7, 8, 8, 10]
and target value 8,
return [3, 4].
class Solution:
# @param A : tuple of integers
# @param B : integer
# @return a list of integers
def searchRange(self, A, B):
n = len(A)
lo = 0
hi = n-1
is_found = False
while(lo<=hi):
mid = int(lo + (hi-lo)//2)
if A[mid] < B:
lo = mid + 1
elif A[mid] > B:
hi = mid - 1
else:
is_found = True
while(A[lo]!=B):lo += 1
while(A[hi]!=B):hi -= 1
break
if is_found:
return [lo, hi]
else:
return [-1, -1]
Also make sure that the solution set is lexicographically sorted.
Solution[i] < Solution[j] iff Solution[i][0] < Solution[j][0] OR (Solution[i][0] == Solution[j][0] AND … Solution[i][k] < Solution[j][k])
Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
HINT do merge sort, when right element is smaller than left element, update count
class Solution:
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
def sort_count(enum):
mid = int(len(enum) / 2)
if mid:
left, right = sort_count(enum[:mid]), sort_count(enum[mid:])
for i in range(len(enum))[::-1]:
# we compare largest elements first
if not right or left and left[-1][1] > right[-1][1]:
# because right[-1][1] is the largest element in right
smaller[left[-1][0]] += len(right)
enum[i] = left.pop() # pop the largest element
else:
enum[i] = right.pop()
return enum
smaller = [0] * len(nums)
sort_count(list(enumerate(nums)))
return smaller
Container with most water
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). ‘n’ vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Your program should return an integer which corresponds to the maximum area of water that can be contained ( Yes, we know maximum area instead of maximum volume sounds weird. But this is 2D plane we are working with for simplicity ).
Note: You may not slant the container. Example :
Input : [1, 5, 4, 3]
Output : 6
Explanation : 5 and 3 are distance 2 apart. So size of the base = 2. Height of container = min(5, 3) = 3.
So total area = 3 * 2 = 6
class Solution:
# @param A : list of integers
# @return an integer
def maxArea(self, A):
lo = 0
hi = len(A)-1
max_area = 0
while lo < hi:
max_area = max(max_area, min(A[lo], A[hi])*(hi-lo))
if A[lo] < A[hi]: lo += 1
else: hi -= 1
return max_area
Intersection of Sorted arrays
Find the intersection of two sorted arrays. OR in other words, Given 2 sorted arrays, find all the elements which occur in both the arrays.
Example :
Input :
A : [1 2 3 3 4 5 6]
B : [3 3 5]
Output : [3 3 5]
Input :
A : [1 2 3 3 4 5 6]
B : [3 5]
Output : [3 5]
class Solution:
# @param A : tuple of integers
# @param B : tuple of integers
# @return a list of integers
def intersect(self, A, B):
if len(A) == 0 or len(B) == 0: return []
p1 = 0
p2 = 0
res = []
while p1 < len(A) and p2 < len(B):
if A[p1] == B[p2]:
res.append(A[p1])
p1 += 1
p2 += 1
elif A[p1] > B[p2]:
p2 += 1
else:
p1 += 1
return res
