Uber Interview Question for SDE-2s


Country: United States
Interview Type: Phone Interview




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

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

- Anonymous November 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Student November 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

class InputValue {
    String name;
    double login;
    double logout;
}

class Type implements Comparable {
    boolean loggedin;
    double time;

    int compareTo(Type that) {
        return this.time - that.time
    }
}

class ReturnValue {
    double time;
    int numLoggedIn;
}

public List<ReturnValue> findLoggedIn(List<InputValue> list) {
    List<Type> loggedIn = new ArrayList<Type>();
    List<ReturnValue> retValue = new ArrayList<ReturnValue>();
    int loggedInNow = 0
    
    for (InputValue iv: list) {
        loggedIn.add(iv.login, true);
        loggedIn.add(iv.logout, false);
    }
    
    Collections.sort(loggedIn);
    
    for(Type t: loggedIn) {
        if (t.loggedin == true)
            loggedInNow++;
        else loggedInNow--;
        
        retValue.add(t.time, loggedInNow);
    }
    
    return retValue;
}

- dora November 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- NoOne December 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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

- Anshil Bhansali February 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anshil Bhansali February 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- anshilbhansali February 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jason February 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jason February 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- teji.catia February 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

After sorting the list by the starting time, using a queue based events should do.

- Hasit Bhatt November 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous November 26, 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