Uber Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class OfficeEntry {
static class Interval implements Comparable<Interval> {
double start;
double end;
Interval(double s, double e) {
start = s;
end = e;
}
@Override
public String toString() {
return "Start " + start + " End " + end;
}
@Override
public int compareTo(Interval o1) {
return (int) (this.start - o1.start);
}
}
public static void main(String[] a) {
Map<Double, Integer> map = new HashMap();
List<Interval> intervalList = new ArrayList();
Interval intr = new Interval(1.2,4.5);
intervalList.add(intr);
intr = new Interval(3.1,6.7);
intervalList.add(intr);
intr = new Interval(8.9,10.3);
intervalList.add(intr);
Collections.sort(intervalList);
for(Interval i : intervalList) {
map.put(i.start, 0);
map.put(i.end, 0);
}
Interval prev = intervalList.get(0);
map.put(prev.start, 1);
for (int i = 1; i < intervalList.size(); i++) {
Interval curr = intervalList.get(i);
map.put(curr.start, 1);
if(curr.start > prev.start && curr.start < prev.end) {
map.put(curr.start, map.get(prev.start) + 1);
if(curr.end > prev.start && curr.end < prev.end) {
map.put(curr.end, map.get(prev.end) + 1);
} else {
map.put(curr.end, map.get(prev.end));
map.put(prev.end, map.get(prev.end) + 1);
}
}
prev = curr;
}
System.out.println(map);
}
}
namespace T3
{
class LogEvents
{
public int UserId { get; set; }
public double EventTime { get; set; }
}
class Program
{
static string[] listofusers = { "Mark", "John", "Sharon" };
static void PrintLoginHistory(List<LogEvents> mylelist)
{
int n = listofusers.Length;
bool[] islogged = new bool[n];
double[] loggedtime = new double[n];
for (int i=0; i<n; ++i) { islogged[i] = false; }
foreach (LogEvents le in mylelist )
{
if (false == islogged[le.UserId])
{
islogged[le.UserId] = true;
loggedtime[le.UserId] = le.EventTime;
}
else
{
if (le.EventTime < loggedtime[le.UserId])
{
Console.WriteLine("Data format error");
}
else {
Console.WriteLine(listofusers[le.UserId] + " " + loggedtime[le.UserId] + " " + le.EventTime);
}
islogged[le.UserId] = false;
}
}
}
static void Main(string[] args)
{
List<LogEvents> lelist = new List<LogEvents>();
lelist.Add(new LogEvents { UserId = 1, EventTime = 1.2});
lelist.Add(new LogEvents { UserId = 2, EventTime = 3.1});
lelist.Add(new LogEvents { UserId = 1, EventTime = 4.5});
lelist.Add(new LogEvents { UserId = 0, EventTime = 6.7});
lelist.Add(new LogEvents { UserId = 2, EventTime = 8.9});
lelist.Add(new LogEvents { UserId = 0, EventTime = 10.3});
PrintLoginHistory(lelist);
}
}
}
In ZoomBA lang, you can be as declarartive as you want, and you can mix style.
events = [ ["Jane", 1.2, 4.5], ["Jin", 3.1, 6.7], ["June", 8.9, 10.3] ]
// sort them with field index 1 : e.g. start time
sorta( events ) :: { $.left.1 < $.right.1 }
// create a list of time slots
left = { 's' : events[0].1 , 'e' : events[0].2 , 'c' : 1 } // first one
col = fold ( [1 : #|events| ], list( left ) ) -> {
right = events[$.o]
/* There can be two cases.
1. right is included in left
2. right and left are independent, with no overlap
*/
left = $.p[-1] // last one is the left
if ( left.e >= right.1 ) { // overlap
// completely included
continue ( left.e >= right.2 ){ left.c += 1 }
// split the interleaving
left_half = { 's' : left.s , 'e' : right.1 , 'c' : left.c }
middle_half = { 's' : right.1 , 'e' : left.e , 'c' : left.c + 1 }
right_half = { 's' : left.e , 'e' : right.2 , 'c' : 1 }
$.p.pop() // pop the last item added to the list
// add them up
$.p += [ left_half , middle_half , right_half ]
}else{ // non overlap
$.p += { 's' : left.e , 'e' : right.1 , 'c' : 0 }
$.p += { 's' : right.1 , 'e' : right.2 , 'c' : 1 }
}
// return partial
$.p
}
col += { 's' : col[-1].e , 'e' : num('inf') , 'c' : 0 }
// now print
println( str( col , ' , ' ) -> { str('(%s,%s)', $.o.s, $.o.c ) } )
public class IntervalOverlap {
public static boolean rangeOverlap(double loA, double hiA, double loB, double hiB) {
if (hiA <= loB || hiB <= loA) {
return false;
} else {
return true;
}
}
public static boolean pointOverlap(double point, double lo, double hi) {
if (point >= lo && point <= hi) {
return true;
} else {
return false;
}
}
public static int overlapCount(double point, List<Range> ranges) {
int count = 0;
for (Range range : ranges) {
if (pointOverlap(point, range.lo, range.hi)) {
count++;
}
}
return count;
}
public static void main(String[] args) {
System.out.println(rangeOverlap(1.2, 4.5, 3.1, 6.7));
List<Range> ranges = new ArrayList<>();
ranges.add(new Range(1.2, 4.5));
ranges.add(new Range(3.1, 6.7));
ranges.add(new Range(8.9, 10.3));
ranges.add(new Range(2.5, 5.3));
ranges.add(new Range(2.5, 3));
Map<Double, Integer> map = new TreeMap<>();
for (Range range : ranges){
map.put(range.lo, overlapCount(range.lo, ranges));
map.put(range.hi, overlapCount(range.hi, ranges));
}
System.out.println(map);
}
static class Range {
double lo;
double hi;
Range(double lo, double hi) {
this.lo = lo;
this.hi = hi;
}
}
}
// Example program
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
struct timestamp{
string name;
float login_time;
float logout_time;
};
int main()
{
vector<timestamp> input;
timestamp t;
t.name = "A";
t.login_time = 1.2;
t.logout_time = 4.5;
input.push_back(t);
t.name = "B";
t.login_time = 3.1;
t.logout_time = 6.7;
input.push_back(t);
t.name = "C";
t.login_time = 8.9;
t.logout_time = 10.3;
input.push_back(t);
map<float, int> hmap;
for(int i=0;i<input.size();i++)
{
hmap[input[i].login_time]++;
hmap[input[i].logout_time]--;
}
int users = 0;
for(auto p : hmap)
{
users += p.second;
cout<<p.first<<", "<<users<<endl;
}
return 0;
}
// Example program
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
struct timestamp{
string name;
float login_time;
float logout_time;
};
int main()
{
vector<timestamp> input;
timestamp t;
t.name = "A";
t.login_time = 1.2;
t.logout_time = 4.5;
input.push_back(t);
t.name = "B";
t.login_time = 3.1;
t.logout_time = 6.7;
input.push_back(t);
t.name = "C";
t.login_time = 8.9;
t.logout_time = 10.3;
input.push_back(t);
map<float, int> hmap;
for(int i=0;i<input.size();i++)
{
hmap[input[i].login_time]++;
hmap[input[i].logout_time]--;
}
int users = 0;
for(auto p : hmap)
{
users += p.second;
cout<<p.first<<", "<<users<<endl;
}
return 0;
}
function timeLog(entries) {
let timePunches = [];
let numPeopleClockedIn = 0;
//first remap the entries to "clock in" or "clock out" events and add them to the timePunches array
entries.map(entry => {
timePunches.push({name: entry[0], time: entry[1], action: 'in'});
timePunches.push({name: entry[0], time: entry[2], action: 'out'});
});
//sort the timePunches array in order or time
//then increment or decrement the number of people logged in depending on the action
timePunches
.sort((a, b) => a.time - b.time)
.forEach(clock => {
numPeopleClockedIn = clock.action === 'in' ? numPeopleClockedIn+1 : numPeopleClockedIn-1;
console.log({time: clock.time, numPeopleClockedIn});
});
}
timeLog([
['jane', 1.2, 4.5],
['jin', 3.1, 6.7],
['june', 8.9, 10.3]
]);
function timeLog(entries) {
let timePunches = [];
let numPeopleClockedIn = 0;
//first remap the entries to "clock in" or "clock out" events and add them to the timePunches array
entries.map(entry => {
timePunches.push({name: entry[0], time: entry[1], action: 'in'});
timePunches.push({name: entry[0], time: entry[2], action: 'out'});
});
//sort the timePunches array in order or time
//then increment or decrement the number of people logged in depending on the action
timePunches
.sort((a, b) => a.time - b.time)
.forEach(clock => {
numPeopleClockedIn = clock.action === 'in' ? numPeopleClockedIn+1 : numPeopleClockedIn-1;
console.log({time: clock.time, numPeopleClockedIn});
});
}
timeLog([
['jane', 1.2, 4.5],
['jin', 3.1, 6.7],
['june', 8.9, 10.3]
]);
Its a problem of login and logout. Increment counter at any login and decrement counter at any logout.
Here is pseudo code:
Lets quantify login as -1 and logout as -2
Create a TreeMap as result<Integer,Integer>. Because it sorts entries with natural order or you can create comparator.
Iterate through log entries. and add it in result TreeMap as like <1.2,-1>,<4.5,-2>,<3.1,-1><6.7,-2>...etc.....But because its a Treemap the entries will be added in sorted order as <1.2,-1>,<3.1,-1>,<4.5,-2><6.7,-2>....etc
Iterate again this set. Increment counter at every -1 value and decrement at every -2 and add value back. So the list will become: <1.2,1>,<3.1,2>,<4.5,1><6.7,0>...etc.... which is what was desired.
This will only need one list to be created and hence save space too.
def unique_pegs(data):
pegs = {}
for name, start, end in data:
if start not in pegs:
pegs[start] = 0
if end not in pegs:
pegs[end] = 0
return pegs
def cnt_users(data, pegs):
for name, start, end in data:
for time, cnt in pegs.iteritems():
if time >= start and time < end:
pegs[time] = pegs[time] + 1
return pegs
p = unique_pegs(a)
p = cnt_users(a, p)
print p
def unique_pegs(data):
pegs = {}
for name, start, end in data:
if start not in pegs:
pegs[start] = 0
if end not in pegs:
pegs[end] = 0
return pegs
def cnt_users(data, pegs):
for name, start, end in data:
for time, cnt in pegs.iteritems():
if time >= start and time < end:
pegs[time] = pegs[time] + 1
return pegs
p = unique_pegs(a)
p = cnt_users(a, p)
print p
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class OfficeEntry {
static class Interval implements Comparable<Interval> {
double start;
double end;
Interval(double s, double e) {
start = s;
end = e;
}
@Override
public String toString() {
return "Start " + start + " End " + end;
}
@Override
public int compareTo(Interval o1) {
return (int) (this.start - o1.start);
}
}
public static void main(String[] a) {
Map<Double, Integer> map = new HashMap();
List<Interval> intervalList = new ArrayList();
Interval intr = new Interval(1.2,4.5);
intervalList.add(intr);
intr = new Interval(3.1,6.7);
intervalList.add(intr);
intr = new Interval(8.9,10.3);
intervalList.add(intr);
Collections.sort(intervalList);
for(Interval i : intervalList) {
map.put(i.start, 0);
map.put(i.end, 0);
}
Interval prev = intervalList.get(0);
map.put(prev.start, 1);
for (int i = 1; i < intervalList.size(); i++) {
Interval curr = intervalList.get(i);
map.put(curr.start, 1);
if(curr.start > prev.start && curr.start < prev.end) {
map.put(curr.start, map.get(prev.start) + 1);
if(curr.end > prev.start && curr.end < prev.end) {
map.put(curr.end, map.get(prev.end) + 1);
} else {
map.put(curr.end, map.get(prev.end));
map.put(prev.end, map.get(prev.end) + 1);
}
}
prev = curr;
}
System.out.println(map);
}
}
// Example program
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
struct timestamp{
string name;
float login_time;
float logout_time;
};
int main()
{
vector<timestamp> input;
timestamp t;
t.name = "A";
t.login_time = 1.2;
t.logout_time = 4.5;
input.push_back(t);
t.name = "B";
t.login_time = 3.1;
t.logout_time = 6.7;
input.push_back(t);
t.name = "C";
t.login_time = 8.9;
t.logout_time = 10.3;
input.push_back(t);
map<float, int> hmap;
for(int i=0;i<input.size();i++)
{
hmap[input[i].login_time]++;
hmap[input[i].logout_time]--;
}
int users = 0;
for(auto p : hmap)
{
users += p.second;
cout<<p.first<<", "<<users<<endl;
}
return 0;
}
Sort the input values based on time. Walk down this array one by one, noting the number of logins and logouts.
Storage is O(n) and runtime is O(nlogn), n = number of login/out values
- dora November 26, 2016