## Uber Interview Question for SDE1s

• 0

Country: India

Comment hidden because of low score. Click to expand.
3
of 3 vote

``````public String findLCS(String a, String b) {
if (a == null || b == null ||
a.length() == 0 || b.length() == 0) {
return "";
}

Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < b.length(); ++i) {
map.put(b.charAt(i), i);
}

String lcs = null;
int count = 0;
for (int i = 0; i < a.length(); ++i) {
if (map.containsKey(a.charAt(i))) {
if (count != 0 && map.get(a.charAt(i - 1)) + 1 == map.get(a.charAt(i))) {
++count;
} else {
count = 1;
}

if (lcs == null || lcs.length() < count) {
lcs = a.substring(i - count + 1, i + 1);
}
} else {
count = 0;
}
}

return lcs;
}``````

O(N) time, O(N) space

Comment hidden because of low score. Click to expand.
0

>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.

Comment hidden because of low score. Click to expand.
3

this is not longest common subsequence solution,
this is a longest common substring solution.
These are totally different.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``Why (Talented?)People from Indian R&D centers asks diffcult(actually nonsense) questions  as compared to US and Europe R&D centers of same company?``

Comment hidden because of low score. Click to expand.
1
of 1 vote

Since the all the letters in the second string are distinct the problem can be reduced to longest increasing sub sequence(nlogn)

Make and array where arr[i] is the index of the letter a[i] in b
and find its LIS in nlogn

Comment hidden because of low score. Click to expand.
0
of 0 vote

KMP algorithm

en.m.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

Comment hidden because of low score. Click to expand.
1
of 1 vote

KMP algorithm is for searching for occurrences of word "b" in "a", but not longest common subsequence.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why People from Indian R&D center always ask difficult(read as Nonsense) question as compared US, Europe R&D centers of same company :) ...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why (Talented?)People from Indian R&D centers asks diffcult(actually nonsense) questions as compared to US and Europe R&D centers of same company?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``Why (Talented?)People from Indian R&D centers asks diffcult(actually nonsense) questions  as compared to US and Europe R&D centers of same company?``

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use binary tree to organize b, for each char in a, do a search in b in log(n) time and do a comparison. O(nlogn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,
What do u mean by all distinct characters.Does that mean the string b has all of the characters appearing exactly once?

Comment hidden because of low score. Click to expand.
0
of 0 vote

@ siva.sai, what do you mean by "Expected complexity O(nlogn)"?
MIT teaches that best known algo for LCS today is O(n^2).
youtu.be/ocZMDMZwhCY?t=27m54s

Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

P N algorithm shall work here.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++) {
}

// 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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.