Solving For The Max Value In An Array

The Issue of Data Structure and Algorithms

You get to to the interview on time. Disciplined character. You had a good run first thing and now your energy is just beyond and over. You are ready to give the best interview session of their lives at Wicked.inc, the company you are interviewing for.

You are feeling good about this front end development position you have gone through your cheat sheets and your industry best practices. Your friends truly profess that you are a JavaScript ninja. Your colleagues shout out your praise and lay purple carpets when you walk by.

You plunge into the session questions after questions, you are smashing. At a point you seem bored, this is too easy. Big mistake. Its like the interviewer picked on this and decided. Okay time to bring out the big guns. But you weren't ready for big guns, in fact you weren't ready for no guns.

First question rolling out of his mouth is something about Binary Trees, you don’t get it. How did we get here?

Another questions pops out your way. Sorry. did you say Doubly Linked Lists? now you are sure you are feeling dizzy was there something in that coffee your colleague gave you this morning.

Your feet is cold now too. At this juncture you are seriously considering spewing incessantly about how you are a fraud, an impostor, that you didnt really know anything and that thanks to Google all you are is was by doing this => google.com/search . Every time.

I think I stretched that a little bit. On the other hand you can totally avoid this. You can start by picking the most popular and pragmatic learning materials based on peer review. That way you don’t waste precious time in this toil.

What I will do here with this article is to guide your hand a little and give you a couple of links and what I think about them based on my interaction with them at some point in time. But lets go through an example of what kind of questions you can meet.

There’s is this question where you are to write a function that returns the largest value in an array without using any native functions. They can leave it really vague, because most of the time they aren’t specifically looking for anything super-optimized (Big O-Notations) or shiny; they just want to see if you can write clean code.

From experience self-taught developers struggle with this particular question and still end up not having a working solution to show even after several minutes of toiling. On the other hand an average CS background, it’s undoubtedly a super simple task.

But even from the CS Graduates it can still expose some lazy or thoughtless programming.

A bad way to solve this is :

Using several if…else cases and comparing arr[i] to arr[i+1] inside the loop.

The efficiency of that method will be damning and you would know this by understanding what Big O Notations are.

a. A “for” loop can be used for this (Not that efficient but its okay and it works)

b. An array.forEach method too, using forEach which is a style of coding familar to programmers. (Interesting and efficient)

Here is my solution (Pseudo code):

a. Set a variable to accept your max value(s) say : var CurrentMax . As your program runs and accepts and deletes multiple choices as the max value changes.

b. Pick first element in array as potential max with something like theArray[0] remember that arrays start at position 0 not 1. And then variable CurrentMax which is set at zero compare it to theArray[0] that holds the value for the first number in that array.

Because this is a normal scenario. We are dealing with positive integers. Using a forLoop, compare the current max with every array element without starting over from the begining with something like for

( i=0, i < theArray.length, i++)

The i++ Helps us not go back and commit serious Big-0 Notation blunders.

theArray[0]

is way we check the next big thing from the array using the index. This is good practice since you don’t know the actual details of an array.

d. Set the new max number from **theArray[something]**if it’s bigger than CurrentMax, iterate through the whole array?

NOT Until array is exhausted will the Loop stop: this invariably means we have found our Max number and it is in CurrentMax.

Code

We did not use native functions. Native functions are the functions already baked into the language that make it easy to write clean code.

Right now we have set the initial max value to 0

1. What if all of the array elements are negative?
2. What if it’s an array of strings?
3. What if the array is in another array

That’s where it gets interesting and then your knowledge of patterns and data structure comes to help.

Voila we are done!

Resources For Studying Data Structure & Algorithms - Quora

1. CLRS — The classic comprehensive text book on algorithms. A must read atleast once in programmer’s career.

2. Introduction to Algorithms: A Creative Approach by Udi Manber — An excellent book on various algorithm categories. Many interesting questions on web portals as interview questions can be found in this book. Chapter end exercises are an asset. One must attempt the “Creative Problems” section at the end of every chapter. If a programmer wants to know the power of induction as problem solving approach, he must read this book. Strongly recommended.

3. The Algorithm Design Manual by Skiena — Lots of algorithmic problems, and discussions, war stories, related problems, interesting exercises. It helps in modeling a problem in different ways. A must work book for every passionate programmer. Don’t read this unless you have good insight into algorithms.

4. Algorithms by Das Gupta — Precise book on few algorithmic categories, pick any chapter based on interest and attempt end of chapter exercises.

5. Algorithms 4e by Sedgewick — Relatively beginner level book, covers graphs, strings, hashing, searching, sorting, etc. very well. It follows OOP approach in Java. Strongly recommended for beginners, though nothing stops a professional. Web portal containing plenty of interesting exercises. There are other books by Sedgewick on Algorithms. Recommended for data structure learning.

6. Introduction to Design and Analysis of Algorithms by Levitin — An introductory book in algorithm design. Recommended for beginners. One can enjoy the explanation and solving end of section exercises.

_On Programming Style:_1. Programming Pearls by Bentley — A must read book on design and implementation of computer programs.

2. The Practice of Programming by Kernighan — Written during Unix days, still one of the best resource on program design and implementation principles.

3. Advanced Programming in the Unix Environment by W. Richard Stevens — It covers many Unix internals and kernel level API. It follows an excellent programming style. Stevens books are one of the best in their category. I would say, they stand at the level of CLRS in algorithms category. Highly recommended.