Uber Interview Question for Senior Software Development Engineers


Country: India
Interview Type: Phone Interview




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

how about looking at it as a graph:
- the nodes are connected if consecutive(e.g. if for node with value 3, if there is a
value 2 and/or 4 those would be connected to 3 with an edge)
- then it would be finding the largest connected component in the graph.

1. run through the graph and put all nodes into a HT.
2. loop over all the numbers in the array. If the number has been visited before,
repeat 2 with next number. Otherwise push that number onto a stack and find
component size using DFS, while marking all visited numbers.
3. max on component size
4. on the maxed component, walk to the min value, and add to result from there

I assume no value occurs multiple times, it would be easy to solve with
duplicates using a ht instead of a set where the value would be key and the
frequency value.

requires O(n) extra space, time complexity of O(n)

/*
#include <vector>
#include <stack>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <limits>

using namespace std;

void print_longest_consecutive_sequence(const vector<int>& arr) 
{	
	if (arr.size() == 0) return;
	unordered_set<int> elements(arr.begin(), arr.end()); // O(n)
	unordered_set<int> visited;
	int max_component_size = 0;
	int max_component_minElement = 0;
	for (int e : elements) { // O(n)
		if (visited.find(e) != visited.end()) continue; // compensate from 1)
		stack<int> st({e});
		int component_size = 0;
		int min_element = numeric_limits<int>::max();
		while (!st.empty()) { // O(n) for each loop, penaltize 1)
			int u = st.top(); st.pop();
			min_element = min(min_element, u);
			visited.insert(u);
			component_size++;
			for (int adj : { u - 1, u + 1 }) {
				if (elements.find(adj) != elements.end() 
					&& visited.find(adj) == visited.end()) {
					st.push(adj); 
				}
			}
		}
		if (max_component_size < component_size) {
			max_component_size = component_size;
			max_component_minElement = min_element;
		}
	}

	// at most O(n)
	int e = max_component_minElement;
	while (true) {
		cout << e;
		auto it = elements.find(e + 1);
		if (it == elements.end()) break;
		cout << ", ";
		e = *it;
	}
}

int main()
{
	print_longest_consecutive_sequence({100, 4, 200, 1, 3, 2});
}

- Chris August 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Using O(n) space,
store integers in a hash which has number as the key, and contains no. of consecutive elements smaller than, and no. of consecutive numbers greater than that.
For each number in array, search smaller and larger numbers, then store it updating its own smaller than & greater than values.
keep track of max consecutive sequence, consecutive smaller + larger + number.
That's your answer in O(n) and O(n) space.
Radix sort answer above will also take O(n) space and run slightly slower.

- gumanji August 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

There are at least two ways to solve it with O(n).
1. Sort using radix sort, and then linear search. Solved using Theta(k n ) where k = Log(max(arr),10) or rather any base.
2. The one I am posting down - much complex:

def  max_contiguous_sub_seq( my_list ){
  left = dict()
  right = dict()
  for ( x : my_list ){
    prev = x - 1
    next = x + 1
    merged = false 
    if ( prev @ right ){
      merged = true
      val = right[prev]
      val += x 
      right -= prev 
      right[x] = val
    } 
    if ( next @ left ){
      merged = true
      val = left[next]
      left -= next
      val.add(0,x)
      left[x] = val 
    }
    if ( !merged ){
      // here, create one element guy 
      my_list = list( x )
      left[x] =  my_list
      right[x] = my_list
    }
  }
  // find the max length guy from left/right 
  #(min,max) = minmax( left ) where { size($.l.value ) < size($.r.value ) } 
  max.value // here we go 
}
l = [ 1, 11, 102, 12, 32, 13, 80, 10 ]
sol = max_contiguous_sub_seq(l)
println(sol)

- NoOne August 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public class LongestConsecutiveSequenceInUnsortedIntArray {

    public static void main(String[] args) {
        System.out.println(longestConsecutiveElementsSequencefinder(new int[]{101,102,11,10,1,2,3,4,5,6,7,8,9,0,22,23,24,25,34,55,56,49}));
    }

    /*
   Algorithm:
   Add all ints to a set
   iterate over the set of ints AND as long as set is NOT empty
        let element from iterator be a
        if a was marked for deletion  - then delete a using the iterator and continue
        remove a from set
        find if (a+1, a+2 , a+3 ..) exist in the set, in sequence
        find if (a-1, a-2,.. ) exist in the set, in sequence
        mark all elements found in the above two steps for deletion
        keep a running value of max Sequence found as above in a variable
     */
    public static int longestConsecutiveElementsSequencefinder(int[] a) {

        Set<Integer> set = new HashSet<>();
        for (int e : a) set.add(Integer.valueOf(e));
        Set<Integer> delete = new HashSet<>();

        Iterator sir = set.iterator();

        int maxLen = 0;
        while (sir.hasNext()) {
            int len = 1;
            Integer elem, e;
            elem = e = (Integer) sir.next();
            if (delete.contains(elem)) {
                sir.remove();
                continue;
            }
            // look if sequence can grow on the left
            while (set.contains(--e)) {
                len++;
                delete.add(e);
            }
            e = elem;
            // look if the sequence can grow to the right
            while (set.contains(++e)) {
                len++;
                delete.add(e);
            }
            maxLen = len > maxLen ? len : maxLen;
        }
        return maxLen;
    }
}

- Anonymous August 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about asking if there is a max value to the numbers in the array A. if not allocate an array B with that length. Go over array A and add 1 in the corresponding cell. B[A[n]]++. and then in another iteration go once over array B and count the longest sequence of not zero cells.

- Ram August 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const longestConsecutive = nums => {
    const s = new Set(nums);
    let max = 0;
    
    for (let i = 0; i < nums.length; i++) {
        let l = 1;
        let n;
        
        n = nums[i] - 1;
        while(s.has(n)) {
            l++;
            s.delete(n);
            n--;
        }
        
        n = nums[i] + 1;
        while(s.has(n)) {
            l++;
            s.delete(n);
            n++;
        }
        
        max = Math.max(l, max);
    }
    
    return max;
}

- Anonymous August 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Radix sort is O(kn). The problem asks for an O(n) solution. Here, I've used linked lists and hash maps, in combination with two passes over the integer array for a true O(n) solution.

func lcs(ints []int) (bl *list.List) {
        m, s := map[int]*int{}, map[int]*list.List{}
        for _, v := range ints {
                m[v-1] = &v
                m[v+1] = &v
        }
        for _, v := range ints {
                if m[v] == nil {
                        continue
                }
                l := s[v]
                if l == nil {
                        s[v] = list.New()
                        l = s[v]
                }
                s[v-1] = l
                s[v] = l
                s[v+1] = l
                f := l.Front()
                if f == nil {
                        l.PushFront(v)
                } else {
                        if f.Value.(int) < v {
                                l.PushBack(v)
                        } else {
                                l.PushFront(v)
                        }
                }
                if bl == nil {
                        bl = l
                } else {
                        if l.Len() > bl.Len() {
                                bl = l
                        }
                }
        }
        return bl
}

- Zachary Kaplan September 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <string.h>
#include <vector>
using namespace std;

int main() {
// your code goes here
int i,j,k,l,n,count,max_count=0;
scanf("%d", &n);
vector<int> arr;
map<int, int> m;
for(i=0;i<n;i++) {

scanf("%d", &l);
arr.push_back(l);
m[l] = 0;
}

map<int,int>::iterator it;
for(i=0;i<n;i++) {

count=0;
m[arr[i]] = 1;
it = m.find(arr[i]+1);
if(it!=m.end()) {
count+= it->second;
}
it = m.find(arr[i]-1);
if(it!=m.end()) {
count+= it->second;
}
count += m.find(arr[i])->second;
m[arr[i]] = count;
printf("%d %d\n", arr[i], count);
if(max_count < count) {
max_count = count;
}
}

printf("%d\n",max_count);

return 0;
}

- Somesh Maurya September 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <string.h>
#include <vector>
using namespace std;

int main() {
	// your code goes here
	int i,j,k,l,n,count,max_count=0;
	scanf("%d", &n);
	vector<int> arr;
	map<int, int> m;
	for(i=0;i<n;i++) {
		
		scanf("%d", &l);
		arr.push_back(l);
		m[l] = 0;
	}
	
	map<int,int>::iterator it;
	for(i=0;i<n;i++) {

		count=0;
		m[arr[i]] = 1;
		it = m.find(arr[i]+1);
		if(it!=m.end()) {
			count+= it->second;
		}
		it = m.find(arr[i]-1);
		if(it!=m.end()) {
			count+= it->second;
		}
		count += m.find(arr[i])->second;
		m[arr[i]] = count;
		printf("%d %d\n", arr[i], count);
		if(max_count < count) {
			max_count = count;
		}
	}
	
	printf("%d\n",max_count);
	
	return 0;
}

- Anonymous September 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <string.h>
#include <vector>
using namespace std;

int main() {
	// your code goes here
	int i,j,k,l,n,count,max_count=0;
	scanf("%d", &n);
	vector<int> arr;
	map<int, int> m;
	for(i=0;i<n;i++) {
		
		scanf("%d", &l);
		arr.push_back(l);
		m[l] = 0;
	}
	
	map<int,int>::iterator it;
	for(i=0;i<n;i++) {

		count=0;
		m[arr[i]] = 1;
		it = m.find(arr[i]+1);
		if(it!=m.end()) {
			count+= it->second;
		}
		it = m.find(arr[i]-1);
		if(it!=m.end()) {
			count+= it->second;
		}
		count += m.find(arr[i])->second;
		m[arr[i]] = count;
		printf("%d %d\n", arr[i], count);
		if(max_count < count) {
			max_count = count;
		}
	}
	
	printf("%d\n",max_count);
	
	return 0;
}

- Somesh Maurya September 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

func longestSequence (array : [Int]) -> Int {
        var maxCount = 1
        var lowerBoundMap = [Int : [Int]]()
        var upperBoundMap = [Int : [Int]]()
        
        for value in array {
            if lowerBoundMap[value] != nil {
                if upperBoundMap[value] != nil {
                    var newArray = upperBoundMap[value]
                    newArray?.append(value)
                    if let lowerArray = lowerBoundMap[value] {
                        newArray?.append(contentsOf: lowerArray)
                    }
                    
                    if let last = newArray?.last {
                        upperBoundMap[last+1] = newArray
                    }
                    
                    if let first = newArray?.first {
                        lowerBoundMap[first-1] = newArray
                    }
                    maxCount = max(newArray?.count ?? 0, maxCount)
                }else{
                    var newArray = lowerBoundMap[value]
                    newArray?.insert(value, at:0)
                    lowerBoundMap[value-1] = newArray
                    lowerBoundMap[value] = nil
                    maxCount = max(newArray?.count ?? 0, maxCount)
                }
            } else if upperBoundMap[value] != nil {
                var newArray = upperBoundMap[value]
                newArray?.append(value)
                upperBoundMap[value+1] = newArray
                upperBoundMap[value] = nil
                maxCount = max(newArray?.count ?? 0, maxCount)
            } else {
                let array = [value]
                upperBoundMap[value+1] = array
                lowerBoundMap[value-1] = array
                
            }
        }
        return maxCount
    }

- Anonymous September 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

func longestSequence (array : [Int]) -> Int {
        var maxCount = 1
        var lowerBoundMap = [Int : [Int]]()
        var upperBoundMap = [Int : [Int]]()
        
        for value in array {
            if lowerBoundMap[value] != nil {
                if upperBoundMap[value] != nil {
                    var newArray = upperBoundMap[value]
                    newArray?.append(value)
                    if let lowerArray = lowerBoundMap[value] {
                        newArray?.append(contentsOf: lowerArray)
                    }
                    
                    if let last = newArray?.last {
                        upperBoundMap[last+1] = newArray
                    }
                    
                    if let first = newArray?.first {
                        lowerBoundMap[first-1] = newArray
                    }
                    maxCount = max(newArray?.count ?? 0, maxCount)
                }else{
                    var newArray = lowerBoundMap[value]
                    newArray?.insert(value, at:0)
                    lowerBoundMap[value-1] = newArray
                    lowerBoundMap[value] = nil
                    maxCount = max(newArray?.count ?? 0, maxCount)
                }
            } else if upperBoundMap[value] != nil {
                var newArray = upperBoundMap[value]
                newArray?.append(value)
                upperBoundMap[value+1] = newArray
                upperBoundMap[value] = nil
                maxCount = max(newArray?.count ?? 0, maxCount)
            } else {
                let array = [value]
                upperBoundMap[value+1] = array
                lowerBoundMap[value-1] = array
                
            }
        }
        return maxCount
    }

- Mookkan September 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Scanner;

/**
* Created by sameer on 30/11/17.
*/
public class Merge {
public static void main(String args[])
{
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();

int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = scanner.nextInt();
}

HashMap<Integer, Integer> startsWith = new HashMap<>();
HashMap<Integer, Integer> endsWith = new HashMap<>();

for (int i = 0; i < n; ++i) {
if (endsWith.containsKey(a[i] - 1) && startsWith.containsKey(a[i] + 1)) {
// Merge
int startsWithItem = endsWith.get(a[i] - 1);
int endsWithItem = startsWith.get(a[i] + 1);

startsWith.remove(a[i] + 1);
endsWith.remove(a[i] - 1);

startsWith.put(startsWithItem, endsWithItem);
endsWith.put(endsWithItem, startsWithItem);

} else if (startsWith.containsKey(a[i] + 1)) {
int endsWithItem = startsWith.get(a[i] + 1);

startsWith.remove(a[i] + 1);
startsWith.put(a[i], endsWithItem);
} else if (endsWith.containsKey(a[i] - 1)) {
int startsWithItem = endsWith.get(a[i] - 1);

endsWith.remove(a[i] - 1);
endsWith.put(a[i], startsWithItem);
} else {
startsWith.put(a[i], a[i]);
endsWith.put(a[i], a[i]);
}
}

int max = Integer.MIN_VALUE;
for (HashMap.Entry<Integer, Integer> entry: startsWith.entrySet()) {
int startsWithItem = entry.getKey();
int endsWithItem = entry.getValue();

if (max < endsWithItem - startsWithItem + 1) {
max = endsWithItem - startsWithItem + 1;
}
}

System.out.println(max);
}
}

- sameer November 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Scanner;

/**
 * Created by sameer on 30/11/17.
 */
public class Merge {
    public static void main(String args[])
    {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = scanner.nextInt();
        }

        HashMap<Integer, Integer> startsWith = new HashMap<>();
        HashMap<Integer, Integer> endsWith = new HashMap<>();

        for (int i = 0; i < n; ++i) {
            if (endsWith.containsKey(a[i] - 1) && startsWith.containsKey(a[i] + 1)) {
                // Merge
                int startsWithItem = endsWith.get(a[i] - 1);
                int endsWithItem = startsWith.get(a[i] + 1);

                startsWith.remove(a[i] + 1);
                endsWith.remove(a[i] - 1);

                startsWith.put(startsWithItem, endsWithItem);
                endsWith.put(endsWithItem, startsWithItem);

            } else if (startsWith.containsKey(a[i] + 1)) {
                int endsWithItem = startsWith.get(a[i] + 1);

                startsWith.remove(a[i] + 1);
                startsWith.put(a[i], endsWithItem);
            } else if (endsWith.containsKey(a[i] - 1)) {
                int startsWithItem = endsWith.get(a[i] - 1);

                endsWith.remove(a[i] - 1);
                endsWith.put(a[i], startsWithItem);
            } else {
                startsWith.put(a[i], a[i]);
                endsWith.put(a[i], a[i]);
            }
        }

        int max = Integer.MIN_VALUE;
        for (HashMap.Entry<Integer, Integer> entry: startsWith.entrySet()) {
            int startsWithItem = entry.getKey();
            int endsWithItem = entry.getValue();

            if (max < endsWithItem - startsWithItem + 1) {
                max = endsWithItem - startsWithItem + 1;
            }
        }

        System.out.println(max);
    }
}

- sameer November 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think it is as complicated as some have perceived.
1) Create a hashmap of Int -> Int
2) Iterate through the items in the array and for each item, check hashmap.get(i-1) & hashmap.get(i+1). Take the max of their values. That gives you the largest contiguous series for that i that has been seen until now.
3) When we have gone through all items in the array, the max value of all hashmap.values() is the answer.

def findLargestContiguous(list: List[Int]): Int = {
    val hashMap: scala.collection.mutable.HashMap[Int, Int] = mutable.HashMap[Int, Int]()

    for (i: Int <- list) {
      val contiguousCt = Math.max(hashMap.getOrElse(i-1, 1), hashMap.getOrElse(i+1, 1))
      hashMap.put(i, contiguousCt + 1)
    }

    hashMap.values.max
  }

- Aditya December 05, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class LongestConsecutiveSequenceInUnsortedIntArray {

    public static void main(String[] args) {
        System.out.println(longestConsecutiveElementsSequencefinder(new int[]{101,102,11,10,1,2,3,4,5,6,7,8,9,0,22,23,24,25,34,55,56,49}));
    }

    /*
   Algorithm:
   Add all ints to a set
   iterate over the set of ints AND as long as set is NOT empty
        let element from iterator be a
        if a was marked for deletion  - then delete a using the iterator and continue
        remove a from set
        find if (a+1, a+2 , a+3 ..) exist in the set, in sequence
        find if (a-1, a-2,.. ) exist in the set, in sequence
        mark all elements found in the above two steps for deletion
        keep a running value of max Sequence found as above in a variable
     */
    public static int longestConsecutiveElementsSequencefinder(int[] a) {

        Set<Integer> set = new HashSet<>();
        for (int e : a) set.add(Integer.valueOf(e));
        Set<Integer> delete = new HashSet<>();

        Iterator sir = set.iterator();

        int maxLen = 0;
        while (sir.hasNext()) {
            int len = 1;
            Integer elem, e;
            elem = e = (Integer) sir.next();
            if (delete.contains(elem)) {
                sir.remove();
                continue;
            }
            // look if sequence can grow on the left
            while (set.contains(--e)) {
                len++;
                delete.add(e);
            }
            e = elem;
            // look if the sequence can grow to the right
            while (set.contains(++e)) {
                len++;
                delete.add(e);
            }
            maxLen = len > maxLen ? len : maxLen;
        }
        return maxLen;
    }
}

- Makarand August 22, 2017 | 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