Uber Interview Question
Senior Software Development EngineersCountry: India
Interview Type: Phone Interview
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.
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)
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;
}
}
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;
}
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
}
#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;
}
#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;
}
#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;
}
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
}
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
}
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);
}
}
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);
}
}
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
}
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;
}
}
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)
- Chris August 22, 2017