Most Living People

June 5, 2015

Our strategy is to read the inputs and count the years in a hash table; when the input is exhausted, we scan the hash table and find the maximum years. The only tricky part is that some lines have both birth years and death years but some lines have only a birth year:

$ python
Python 2.7.8 (default, Jul 28 2014, 01:34:03)
[GCC 4.8.3] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> def judge(filename, currYear):
...     f = open(filename, 'r')
...     n = int(f.readline())
...     for i in range(n):
...         Y = {}
...         m = int(f.readline())
...         for j in range(m):
...             years = str.split(f.readline())
...             start = int(years[0])
...             stop = int(years[1] if len(years) > 1 else currYear)
...             for k in range(start, stop+1):
...                 if k not in Y: Y[k] = 0
...                 Y[k] += 1
...         x = max(Y.values())
...         print sorted([y[0] for y in Y.items() if y[1] == x])
...
>>> judge("judge.txt", 2015)
[1948]
[1945, 1946, 1947, 1948]

You can run the program at http://ideone.com/Y2LPLC.

Pages: 1 2

8 Responses to “Most Living People”

  1. In perl – this is what perl was written for!

    my $Y = 2015;
    my $cases = ;
    foreach my $case ( 1..$cases ) {
    my $rows = ;
    my %years;
    foreach my $row ( 1..$rows ) {
    $_ = ;
    my($s,$e) = split;
    $years{$_}++ foreach $s..($e||$Y);
    }
    my $max = 0;
    foreach (values %years) {
    $max = $_ if $max < $_;
    }
    printf "@{[ sort grep {$years{$_}==$max} keys %years ]}\n",
    }

  2. Priyank said

    I was wondering if there is a better data structure/algorithm to solve this ?

    Intersection of intervals and maintaining a count of intersection ?

  3. haari said
    public class LifeSpan {
    
    	public static void main(String[] args) throws NumberFormatException,
    			IOException {
    		LifeSpan ls = new LifeSpan();
    		List<List<Integer>> listOfAllYears = new ArrayList<List<Integer>>();
    
    		Scanner scanner = new Scanner(System.in);
    		System.out.println("Enter the Number of cases to be examined");
    		int n = scanner.nextInt();
    
    		for (int i = 1; i <= n; i++) {
    
    			System.out.println("Enter Number of People");
    			Scanner s = new Scanner(System.in);
    			int numberOfLinesToRead = new Integer(s.nextLine());
    
    			String[] result = new String[numberOfLinesToRead];
    			List<List<Integer>> list = new ArrayList<List<Integer>>();
    
    			for (int j = 0; j < numberOfLinesToRead; j++) {
    				result[j] = s.nextLine();
    			}
    
    			for (int a = 0; a < result.length; a++) {
    				ls.calCommonYearString(result[a], list);
    			}
    			ls.setToReturn(list, numberOfLinesToRead, listOfAllYears);
    		}
    
    		for (List<Integer> l : listOfAllYears) {
    			l.toArray();
    			for (Integer h : l) {
    				System.out.print(h + " ");
    			}
    			System.out.println();
    		}
    	}
    
    	private void calCommonYearString(String string, List<List<Integer>> list2) {
    		List<String> list = new ArrayList<String>();
    		StringTokenizer str = new StringTokenizer(string, " ");
    		if (str.countTokens() < 2) {
    			Calendar now = Calendar.getInstance();
    			String currentYear = String.valueOf(now.get(Calendar.YEAR));
    			list.add(string);
    			list.add(currentYear);
    		} else {
    			while (str.hasMoreTokens()) {
    				list.add((String) str.nextToken());
    			}
    		}
    		calCommonYear(list, list2);
    	}
    
    	private void calCommonYear(List<String> list, List<List<Integer>> list2) {
    		int a = Integer.parseInt((String) list.get(0));
    		int b = Integer.parseInt((String) list.get(1));
    		List<Integer> every = new ArrayList<Integer>();
    		for (int i = a; i <= b; i++) {
    			every.add(i);
    		}
    		list2.add(every);
    	}
    	
    	private void setToReturn(List<List<Integer>> list, int numberOfLinesToRead,
    			List<List<Integer>> listOfAllYears) {
    		List<Integer> temp = null;
    		for (int i = 0; i <= numberOfLinesToRead - 1; i++) {
    			if (i == 0) {
    				temp = list.get(i);
    			}
    			temp.retainAll(list.get(i++));
    			i--;
    		}
    		listOfAllYears.add(temp);
    	}
    }
    
  4. haari said

    The above code is written in java and assuming all the validations are true

  5. Prabu said

    Haari, I tried a solution with set too. The problem is when there is a range which doesn’t overlap at all (someone noncontemporary).
    Try this dataset – there wont be any output.
    1(# of cases)
    3(# of entries)
    2010
    1910 1948
    1927 1995

    Though expected output is 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948.

  6. haari said

    Prabhu, go through the task once more. The task to print a common year lived by all the people. In your dataset, if you give 2010, it won’t be a common year for all the 3 people since other people died in 1948 and 1995 so there wont be any output.

  7. H. F. said

    Consider an inverse problem: you are given a list of birth years and a list of death years for a group of people. The same birth (or death) year may be listed for multiple times if there are more than one birth (or death) in that year. However, the two lists are separate and no names are attached to each year. Please estimate the numbers of years that these people have lived.

  8. Mike said
    from collections import Counter
    from datetime import date
    
    def mostliving(line):
        thisyear = date.today().year
        for case in range(int(next(line))):
            pop = Counter()
            for person in range(int(next(line))):
                birth, *tail = [int(s) for s in next(line).split()]
                death = tail[0] if tail else thisyear
                pop.update(range(birth, death+1))
    
            maxpop = max(pop.values())
            print(*[y for y,p in sorted(pop.items()) if p == maxpop])
        
    # test
    data = """\
    2
    3
    1910 1948
    1948 2011
    1927 1995
    3
    1910 1948
    1927 1995
    1945
    """
    
    mostliving(io.StringIO(data))
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: