Improving Basics

Hey folks
I was interviewed yesterday for a programming/web-development profile.
I cleared 3 rounds but was rejected in the last round(the programming round).
The question I was asked was a basic one:implement get_max function in a stack. Though I did it,the time complexity was not good,O(n). I understood how to do it later but I wanted to know how I can improve upon my basics.
I have solved a lot of problems on Codechef but never encountered such a problem where my basics were questioned(Correct me if Iā€™m wrong).
Codechef was more of implementing the STL libraries/puzzle solving/number theory. I hardly remember when I last implemented a stack/queue/priority queue/tree from scratch without using libraries.
How do I get my basics in place??
I would appreciate frank opinions and also resources/ opinions where people faced the same problem and how they tacked it.

Thanks a lot Codechef community

Hello @mancoolgunda
Donot worry too much you can revise your all skills from geeksforgeeks.

I am giving this link to you and also keep moving forward in codechef.

[http://www.geeksforgeeks.org/][1]

Happy Coding!!!
[1]: http://www.geeksforgeeks.org/

4 Likes

you implemented in O(n) or the best implementation is O(n)??
(for the getmax fxn in stack)

I implemented in O(n) but the best soln is O(1)

@rahul_nexus the best algorithm for finding minimum is implementing Min_Heap this will cost only O(1) for finding minimum and Max_Heap will cost O(1) for finding maximum element.

1 Like

This comes from practice only, and there are problems on Codechef also where you need to modify the primitive tasks you do in the basic data structures, it assumes that you are clear with the basic concepts, however, if you are not, you must practice more.

and where should I practice more if Im not clear with my basics? any suggestions on that?

@mancoolgunda: I have been through lot of rejections in some very good companies and it feels very low when you tend to realize where you went wrong. I have being doing lot of coding websites for 2 years or so but always went down on occasions because after all you canā€™t get the precision of doing what the interviewer wants at once with a good coding profile alone. There are some other things such as knowing answers of some very frequently asked interview questions to the point and the best algos for them . I figured out that perhaps careercup or glassdoor are essentials for getting a good developer job. Apart from this I was always weak at linked lists and trees because I never made trees or linked lists in coding competitions because of speed concerns. You need to brush up those yourselves because these problems require a lot of practice and involve lots of recursions and multiple ways to implement the same problem .The thing is they ask you to implement the same problem with single pointer,with double pointer , with recursion ,using stack/queue, dummy node , why double pointer, why not recursion , why not single pointer etc etc. You wonā€™t be perfect at these until you try yourselves these questions at first. Apart from this one thing that I learnt that test cases are very important especially in coding rounds of MS etc. You visualize all the test cases whether relevant or not you can think of and incorporate those in your solution.

2 Likes

hey thanks a lot for sharing your experienceā€¦ :slight_smile:

you can practice on your own, or SPOJ or codechef. I said that there are problems already. Tell me a particular topic, only then specific practice problem can be told.

just by telling ā€œbasicsā€ you are actually covering a whole lot of things. Some chapters from CLRS Intro to Algorithms are must. And, the answer to your question get_max lies there too. :slight_smile: Good luck for the future.

hmmā€¦ So I actively take part in every Codechef challenge/cook-off and am regularly solving the practice probsā€¦though I am still not done with the easy set.
I wanted to know where I can find typical problems on stack/queue/tree/linked list where I would have to implement a ds on my own from scratch and not directly use STLs. What I thought of doing is browse the questions tagged with stack/queue in discuss.codechef.com and then start solving them.

What I think is, sitting back with the long contest questions and trying to do it in different ways will definitely build our concepts, and that is what I am trying to do these days.
And, short contests/college contests are there to test the tricky part.

all i can suggest to you is to learn basics again and againā€¦ there is nothing to be ashamed of, to re-read the same thing again and againā€¦

there is a, well, sort of a book, called crack-the-interview which has the list of frequently asked programming questions during interview.

regarding the questions you have mentioned, you will have to develop Analysis skills which sadly no ā€˜bookā€™ can helpā€¦ you may refer to CLRS as a reference, but analysis is something builds in you instead of learning!!

I found few problems at UVa, related to specific topics. You can check that.

thanks i will look into itā€¦