Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

public class C1_33RealTimeCounter {

    static class Timer {

        /*
          timer in nanoseconds accurracy
         */
        public static long time() {
            return new Date().getTime() * 1000;
        }

        /**
         *
         * @param start the start time in nanoseconds
         * @param end  the end time in nanoseconds
         * @return
         */
        public static int diff(long start, long end) {
            return (int) (end - start) / 1000000;
        }
    }

    class CyclicBuffer {

        int[] data = new int[86400];
        int beginOffset = 0;
        int endOffset = 0;

        /**
         *
         * @param value current counter value
         * @param seconds how many seconds passed since last append
         */
        public void append(int value, int seconds) {
            for(int i = 1; i <= seconds; i ++) {
                endOffset = (endOffset + i) % data.length; 
                data[endOffset] = value;
            }
            beginOffset = (beginOffset + seconds) % data.length;
        }
        
        public int get(int distanceFromEnd) {
            int offset = (endOffset + data.length - distanceFromEnd) % data.length;
            return (int)data[offset];
        }
    }

    private int counter = 0;
    private long lastIncrementTime = -1;
    private CyclicBuffer buffer = new CyclicBuffer();

    public void increment() {
        long currentTime = Timer.time();

        if(lastIncrementTime < 0) 
            lastIncrementTime = currentTime;

        int secondsSinceLastIncrement = Timer.diff(lastIncrementTime, currentTime);
        counter ++;
        buffer.append(counter, secondsSinceLastIncrement);
    }

    public int getCountInLastSecond() {
        return buffer.get(0) - buffer.get(1);
        
    }

    public int getCountInLastMinute() {
        return buffer.get(0) - buffer.get(60);
    }

    public int getCountInLastHour() {
        return buffer.get(0) - buffer.get(3600);
    }

    public int getCountInLastDay() {
        return buffer.get(0) - buffer.get(86399);
    }

- zouzhile February 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

extract day/hour/minute/second part in timestamp, and use them as key, each time to increment(), if key doesn't change, increase counter for that key, otherwise update key and reset counter to 1. In getCountInLastX(), get day/hour/minute/second part from current Date(), and compare them with existing keys, if not match, return 0, otherwise return counter for that key.

- Anonymous February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for example, key_day could be calculated as (timestamp / one_day * one_day), where one_day is 24 * 60 * 60 * 1000000 ns, similarly to key_hour is (timestamp / one_hour * one_hour), so key_X is used to only track timer in last X, and counter associated with key_X is to record how many timer in key_X.

- KewpieWang February 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

class RealTimeCounterImpl implements RealTimeCounter{
    
    //factor for seconds = 1;
    //factor for minutes = 60;
    //factor for hour = 1200;
    //factor for day = 1200*24;
    long getOneRange(long end, long factor){
        long elapsedTime = end - (1000000000 * factor);        
        return elsapsedTime;
    }
    
    /*
    *    Keep saved the following data:
    *    - first time we incremented the counter
    *    - count in last day
    *    - count in last hour
    *    - count in last minute
    *    - count in last second
    *
    */
    
    int countInLastDay = 0;
    int countInLastHour = 0;
    int countInLastMinute = 0;
    int countInLastSecond = 0;
    
    long timeFirstInsertLastDay = 0;
    long timeFirstInsertLastHour = 0;
    long timeFirstInsertLastMinute = 0;
    long timeFirstInsertLastSecond = 0;

    void increment(){
        long currentTime = time();
        
        long start = getOneRange(currentTime, 1);
        
        if (timeFirstInsertLastSecond == 0 || timeFirstInsertLastSecond < start) {
            timeFirstInsertLastSecond  = currentTime;
            countInLastSecond = 1;
        }else{
            countInLastSecond++;
        }

	//the same should be done for the other three increments
    }
        
    int getCountInLastSecond(){
        return countInLastSecond;
    }
    
    int getCountInLastMinute(){
        return countInLastMinute;
    }
    
    int getCountInLastHour(){
        return countInLastHour;
    }
    
    int getCountInLastDay(){
        return countInLastDay;
    }
    
}

- Luca February 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;


public class Counter {

	private enum StatsType {
		SEC(1000), MIN(60000), HOUR(3600000), DAY(24*60*60*1000), MONTH(30*24*60*60*1000);
		private final long divisor;
		StatsType(int d) {
			this.divisor = d;
		} 
	}
	
	static class Stats {
		long key = 0;
		long count = 0;
		StatsType t;
		Stats(StatsType t) {
			this.t = t;
		}		
	}
	
	static class StatsPair {		
		Stats cur;
		Stats saved;
		public StatsPair(Stats cur, Stats saved) {
			this.cur = cur;
			this.saved = saved;
		}
	}
	
	Map<StatsType, StatsPair> tab;
	
	Counter() {
		tab = new HashMap<Counter.StatsType, Counter.StatsPair>();		
		for(StatsType t : StatsType.values())
			tab.put(t, new StatsPair(new Stats(t), new Stats(t)));
	}
	
	
	public void incr() {
		long curMs = System.currentTimeMillis();
		for(Entry<StatsType, StatsPair> e: tab.entrySet()) {
			StatsPair sp = e.getValue();
			StatsType ty = e.getKey();
			long curKey  =  curMs/ty.divisor;
			
			if( sp.cur.key != curKey ) {
				sp.saved.key = sp.cur.key;
				sp.saved.count = sp.cur.count;
				sp.cur.key = curKey;
				sp.cur.count = 0;
				//System.out.println("moved to saved [" + ty + "] " + sp.saved.key + " " + sp.saved.count);
			}
			++sp.cur.count;
		}
				
		//System.out.println(tab);
	}

	private long getCountInLast(StatsType ty) {
		long last = System.currentTimeMillis()/ty.divisor - 1;
		StatsPair sp = tab.get(ty);
		if ( sp.cur.key  == last )
			return sp.cur.count;
		else if ( sp.saved.key == last ) 
			return sp.saved.count;
		return 0;
	}
	
	public long getCountInLastSec() {
		return getCountInLast(StatsType.SEC);
	}
	
	public long getCountInLastMin() {
		return getCountInLast(StatsType.MIN);
	}
	
	public long getCountInLastHour() {
		return getCountInLast(StatsType.HOUR);
	}
	
	/**
	 * @param args
	 * @throws InterruptedException 
	 */
	public static void main(String[] args) throws InterruptedException {

		Counter c = new Counter();
		for(int i=0; i<100; i++)
			c.incr();
		Thread.sleep(2000);
		for(int i=0; i<50; i++)
			c.incr();
		System.out.println(c.getCountInLastSec());
		Thread.sleep(1000);
		System.out.println(c.getCountInLastSec());
		Thread.sleep(60000);
		
		System.out.println(c.getCountInLastMin());
		System.out.println(c.getCountInLastHour());
		

	}
}

- hack0x March 13, 2014 | 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