CareerCup

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

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

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

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