CareerCup

use a stack to store the function not returned, if read a log entry that a function starts, push the entry. if read a log entry that a function ends, pop up an entry from the stack

when read an entry and the current running function is "foo" by checking whether the top element of the stack, add the time difference between the current entry and the previous one to the total

Time: O(n)

Pseudo Codes

enum Type 
{
     START, 
     END
};

class LogEntry
{
     public DateTime timeStamp;
     public String function;
     public Type type;
}

public int getElapse(List<LogEntry> log, String function)
{
     int elapse = 0;
     Stack<LogEntry> s = new Stack<LogEntry>();
     for(int i = 0; i < log.size(); i++) {
          LogEntry entry = log.get(i);
          if(!s.empty() && s.peek().function.equals(function)) {
               elapse += entry.timeStamp - log.get(i - 1).timeStamp;
          }
          if(entry.type == Type.END && s.peek().type == Type.Start && entry.function.equals(s.peek().function)) {
               s.pop();
          } else {
               s.push(entry);
          }
          return elapse;
}

Do you have an approach?

my solution will use a stack, as long as start is found push into stack.when an end is encountered, pop the first start line of the similar function

what if under multi-thread ormulti process situation? like:
(foo()_start, 10:01);
(foo2()_start, 10:03);
(foo()_start, 10:05);
(foo2()_end, 10:08);
(foo()_end, 10:12);
(foo()_end, 10:20);

BTW, ifenjoy9 already gave a wonderful solution here:
careercup.com/question?id=14990939

Given how the problem is stated, you have a log file with the format above. If you set it up to have a LogEntry object like described above, then you will have to iterate through the list twice, which is not bad but there is a more efficient way to do it.
- Scan through the file, look for where the function first occur.
- Set startFunct = 1, endFunct = 0; Setting it this way, startFunct will always lead endFunct unless the corresponding ending function matches with the originally calling function.
- Create a variable to keep track of the time for even iteration count evenTime, and another one for odd iteration count oddTime. Time elapse is the difference between the even and the odd.
- Iterate until startFunct == endFunct, increment them along the way. Add time into the evenTime and oddTime.
Here is the code:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class ElapseTime 
{
	
	public int getElapsedTime( String fileName, String startFunct, String endFunct ) throws IOException
	{
		int elapseTime = -1;
		if( fileName == null || startFunct == null || endFunct == null )
			return elapseTime;
		
		BufferedReader br = null;
		String currentLine = "";
		try
		{
			br = new BufferedReader( new FileReader( fileName ) );
			currentLine = br.readLine();
			while( currentLine != null && !getFunctName(currentLine).equals(startFunct) )
			{
				currentLine = br.readLine();
			}
		}
		catch( IOException e )
		{
			if( br != null )
			{
				br.close();
			}
			return -1;
		}
		
		int startCount = 1;
		int endCount = 0;
		int oddTime = getTime(currentLine);
		int evenTime = 0;
		int count = 1;
		
		while( (currentLine = br.readLine()) != null && startCount != endCount )
		{
			if( getFunctName(currentLine).equals(startFunct) )
				startCount++;
			if( getFunctName(currentLine).equals(endFunct) )
				endCount++;
			
			count++;
			
			if( count % 2 == 0 )
				evenTime += getTime( currentLine );
			else
				oddTime += getTime( currentLine );
		}
		
		br.close();
		
		if( startCount == endCount )
		{
			return evenTime - oddTime;
		}
		
		return -1;
			
	}
	
	public String getFunctName( String readLine )
	{
		if( readLine == null )
			return null;
		int index = readLine.indexOf(",");
		if( index != -1 )
		{
			return readLine.substring(1, index);
		}
		
		return null;
	}
	
	public int getTime( String readLine )
	{
		if( readLine == null )
		{
			return -1;
		}
		
		int start = readLine.indexOf(",") + 1;
		int end = readLine.indexOf(":", start);
		
		if( start > 1 && end > start )
		{
			return Integer.parseInt(readLine.substring(start, end))*60 + 
					Integer.parseInt(readLine.substring(end + 1, readLine.length()-2)); 
		}
		
		return -1;
	}
	
}

import java.util.LinkedList;
import java.util.Stack;

public class Logs {
	LinkedList<LogEntry> entries;

	public class LogEntry {
		String funName;
		int timestamp;
		String type;

		public LogEntry(String funName, int timestamp, String type) {
			super();
			this.funName = funName;
			this.timestamp = timestamp;
			this.type = type;
		}

		@Override
		public String toString() {
			return funName + " " + timestamp + " " + type;
		}

	}

	public Logs() {
		super();
		entries = new LinkedList<LogEntry>();
		LogEntry e1 = new LogEntry("foo", 1, "start");
		LogEntry e2 = new LogEntry("foo2", 3, "start");
		LogEntry e3 = new LogEntry("foo", 5, "start");
		LogEntry e4 = new LogEntry("foo", 8, "end");
		LogEntry e5 = new LogEntry("foo2", 12, "end");
		LogEntry e6 = new LogEntry("foo", 20, "end");
		entries.add(e1);
		entries.add(e2);
		entries.add(e3);
		entries.add(e4);
		entries.add(e5);
		entries.add(e6);
	}

	public int calElapse(String functionName) {
		int elapse = 0;
		Stack<LogEntry> stack = new Stack<LogEntry>();
		for (int i = 0; i < entries.size(); i++) {
			LogEntry entry = entries.get(i);
			if (!stack.isEmpty() && stack.peek().funName.equals(functionName)) {
				elapse += (entry.timestamp - entries.get(i - 1).timestamp);
			}
			if (entry.type.equals("end") && stack.peek().type.equals("start")
					&& entry.funName.equals(stack.peek().funName)) {
				stack.pop();
			} else {
				stack.push(entry);
			}
		}
		return elapse;
	}

	public static void main(String[] args) {
		Logs logs = new Logs();
		System.out.println(logs.calElapse("foo"));
	}
}