## Uber Interview Question for Senior Software Development Engineers

• 2

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

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

Comment hidden because of low score. Click to expand.
1
of 1 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.
Radix sort answer above will also take O(n) space and run slightly slower.

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++;
}
e = elem;
// look if the sequence can grow to the right
while (set.contains(++e)) {
len++;
}
maxLen = len > maxLen ? len : maxLen;
}
return maxLen;
}
}``````

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.

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

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

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() {
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;
}

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

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

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

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

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

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

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

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++;
}
e = elem;
// look if the sequence can grow to the right
while (set.contains(++e)) {
len++;
}
maxLen = len > maxLen ? len : maxLen;
}
return maxLen;
}
}``````

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.