Uber Interview Question for SDE1s


Country: India




Comment hidden because of low score. Click to expand.
2
of 2 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

- Iuri Sitinschi November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- emb November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- zr.roman January 07, 2016 | Flag
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?

- sameer November 17, 2015 | Flag Reply
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

- Archit Jain January 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

KMP algorithm

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

- kyduke November 17, 2015 | Flag Reply
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.

- Iuri Sitinschi November 17, 2015 | Flag
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 :) ...

- Anonymous November 17, 2015 | Flag Reply
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?

- Sameer November 17, 2015 | Flag Reply
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?

- Sameer November 17, 2015 | Flag Reply
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)

- wminghao November 17, 2015 | Flag Reply
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?

- Dinesh November 27, 2015 | Flag Reply
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

- zr.roman January 07, 2016 | Flag Reply
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");
            Console.ReadLine();
        }
    }
}

- zr.roman January 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

P N algorithm shall work here.

- sunny March 23, 2016 | Flag Reply
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

- Anonymous May 20, 2016 | Flag Reply
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

- Saaber May 20, 2016 | Flag Reply
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++) {
        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;
}

- dora December 01, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More