Arista Networks Interview Question


Country: United States




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

Hmmm...it appears that not that many people who have answered so far have studied computer architecture.

Performance will probably be better for the first function because the data being accessed is arranged sequentially (or mostly sequentially) in memory. This is faster because doing a read on one memory location will cause adjacent memory locations to be brought into the cache, so when they are read, they will be read much faster than if they weren't in the cache.

The reason everyone should really know about things like this is because the performance difference can be absolutely dramatic. About 5 years ago, I was working on optimizing the performance of a project that had code like in the second function. I was able to increase the speed of some loops just like that by a factor of 10 when programming in C by accessing memory sequentially.

- eugene.yarovoi January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good answer ....it is depends on computer architecture.but i have small doubt ...i guess it may depend on how array elements are stored ....there are concepts ROW-MAJOR ,COLUMN-MAJOR ..do these concepts have any effect on the question.

- gladiator January 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the memory is accessed sequentially, the code will probably be faster. Simple as that.

Row-major vs. column-major determines whether each row is stored as a contiguous chunk or whether each column is a contiguous chunk. Since contiguous memory locations should be read sequentially, the algorithm should read either row-by-row or column-by-column depending on whether the matrix is row-major or column-major. If the desired printouts are in row-major order, it'll be better to store the matrix in row-major order.

- eugene.yarovoi January 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correct. Cahce: Spatial Locality

- saga January 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Is this for(i=0;j<rows;i++) by mistake in function2 ?

- Nana January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Let's assume it's a mistake.

- eugene.yarovoi January 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If cache stores data in row major order, then fun 1 is efficient. If cache is in column major order then fun 2 is efficient.by default we assume cache RMO so fun 1 is more efficient.

- Anonymous November 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

func1() is more efficient because you are calling "for" function for less times than in func2().

- Wayne January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

in both functions we are calling 20000 * 30000 times only? so how func1 is better?

- shivacherukuri January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It has better cache performance.

- eugene.yarovoi January 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

At the end of each 'for' block there is a comparison operation to check weather to continue or not. For the inner 'for' loop this check is always row*column times but we can save this for the outer 'for' loop. Hence func1() is better.

- Aseem Vyas January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

even if rows are 100,000 and cols are 10,000 -> first one is better.. due to cache performance (read above answer: eugene.yarovoi) and also disk performance (disk head) will be better - it will access in increasing order of memory -- rather than going back and forth.. all cols are always placed together : EG: say each data is 4 bytes, subsequent cols addresses will be baseaddr+4,+8+12,+16..-> easier to read... Consider if rows are accessed (in the inner loop) then baseaddr+40,000 bytes +80,000 bytes .. all the way and then again back at baseaddr+40004, +80004,+12004,...

- Optimus September 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The question is about the time of calculating the index of the item, both (should be) two "identical" loops, printing all elements of the matrix - row-wise and column-wise.

- Selmeczy, Péter January 19, 2012 | 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