vitas / test-tasks Goto Github PK

Write a console application what merges overlapped intervals. Input list of intervals, output array of merged overlapped intervals and intervals what could not be merged

Example: Input: [25,30] [2,19] [14, 23] [4,8] Output: [2,23] [25,30]

Try to achieve best algorithmic efficiency (complexity, memory usage, estimated time) Write tests and documentation, answer questions

• interval has only two int numbers (n, j)
• min two intervals could attempted to merge
• intervals array length should be between 1..n
• start of interval has to be <= end of interval
• end of interval <= n
• n ..how big is the value? 10000, more?

golang

build project make

if make is not installed, just build the app

go build -o merge_interval *.go

run example

./merge_interval

make test

without make go test

• What is execution time?
  • I think in worst case time complexity is O( n log n )
• How can robustness be ensured, especially with regard to very large inputs?
  • Knowing a memory usage of of intervals we can estimate max count of intervals we can process
  • Do not forget about CPU usage, use a profiler to get a sense of CPU amd memory consumtion, use GOGC param to increase memory before CG
  • Do performace testing and make a final estimation
  • Consider about parallel computing, like map reduce systems
• What is memory consumption?
  • For a 2 dimensional array of "int" a total size is about 24 + (24 + 4 * i) * j, where array with intervals int[i][j]. Basically in 64bit system, "int" is 4 bytes, int[] is 24 + 4 * i, where 24 is size of empty "int" array in go