Uber Interview Question
SDE1sCountry: India
>O(n) time
So you've just solved longest increasing subsequence in linear time.
Suppose we need to find longest increasing subsequence of permutation 1..n = P
We can instead find longest common subsequence of string
[1 2 3 ... n] and permutation P, so we can apply your algorithm to it and it will give us the longest common subsequence, which is also the longest increasing subsequence of permutation P in O(n) time.
c# implementation.
Longest Common Subsequence's length.
Classic algo, O(m*n).
using System;
namespace LongestCommonSubsequence {
class Program {
private static int LCSsLength( string s1, string s2 ) {
int[,] arr = new int[ s1.Length + 1, s2.Length + 1];
int[] maxValCoords = new int[2];
int maxVal = 0;
for ( int row = 0; row < s1.Length; row++ ) {
for ( int col = 0; col < s2.Length; col++ ) {
var leftCell = arr[ row + 1, col ];
var upCell = arr[ row, col + 1 ];
var leftDiagonalCell = arr[ row, col ];
if ( s1[ row ] != s2[ col ] ) {
arr[ row + 1, col + 1 ] = Math.Max( leftCell, upCell );
} else {
arr[ row + 1, col + 1 ] = leftDiagonalCell + 1;
}
var currVal = arr[ row + 1, col + 1 ];
if ( currVal < maxVal ) { continue; }
maxValCoords[ 0 ] = row + 1;
maxValCoords[ 1 ] = col + 1;
}
}
return GetVal( arr, maxValCoords, s1, s2 ).Length;
}
private static string GetVal( int[,] arr, int[] coords, string s1, string s2 ) {
string commonChar = string.Empty;
var row = coords[ 0 ];
var col = coords[ 1 ];
if ( arr[ row, col ] == 0 ) return string.Empty;
var leftCell = arr[ row, col - 1 ];
var upCell = arr[ row - 1, col ];
var chFromS1 = s1[ row - 1 ];
var chFromS2 = s2[ col - 1 ];
if ( chFromS1 == chFromS2 ) {
commonChar = chFromS2.ToString();
row--;
col--;
}
else if ( upCell >= leftCell ) { row--; }
else { col--; }
return GetVal( arr, new[] { row, col }, s1, s2 ) + commonChar;
}
static void Main( string[] args ) {
var res = LCSsLength("MICHAELANGELO","HIEROGLYPH");
Console.ReadLine();
}
}
}
Can be done in O(n) using hachMap:
def maxCommonSubString(S1,S2):
##Assuming S2 has all unique chars
S2Dic = {S2[i]:i for i in xrange(len(S2))}
maxR = 0
subS = ''
i = 0
while i < len(S1):
if S1[i] in S2Dic:
j = S2Dic[S1[i]]
k = i
while j < len(S2) and k < len(S1) and S1[k] == S2[j]:
k += 1
j += 1
if k - i > maxR:
maxR = k-i
subS = S1[i:k]
i = k
else:
i += 1
return subS
It can be done in O(n) using hashmap
def maxCommonSubString(S1,S2):
##Assuming S2 has all unique chars
S2Dic = {S2[i]:i for i in xrange(len(S2))}
maxR = 0
subS = ''
i = 0
while i < len(S1):
if S1[i] in S2Dic:
j = S2Dic[S1[i]]
k = i
while j < len(S2) and k < len(S1) and S1[k] == S2[j]:
k += 1
j += 1
if k - i > maxR:
maxR = k-i
subS = S1[i:k]
i = k
else:
i += 1
return subS
Isn't the following an O(n) solution? It requires O(n) space though.
public int lcString(String a, String b) {
Map<Character, Integer> map = new HashMap<>();
// Store a in the map
for (int i = 0; i < a.length; i++) {
map.add(a.charAt(i), i);
}
// for each character in b, see if it is occurring linearly in the map
int lcs = 0, currLcs = 0;
Integer oldLocation = -1, newLocation = -1;
for (int i = 0; i < b.length; i++) {
newLocation = map.get(b.charAt(i));
if ((newLocation != null) && (newLocation == oldLocation+1)) // increasing
currLcs++;
else {
if (lcs < currLcs)
lcs = currLcs;
currLcs = 0;
}
oldLocation = newLocation;
}
// currLcs will be greater than lcs if the common string
// ends at the termination of both strings
return (currLcs > lcs) ? currLcs : lcs;
}
O(N) time, O(N) space
- Iuri Sitinschi November 17, 2015