Trees and Graphs Basics

So let's have an intro into some of the type of trees

Just a brief idea:

Binary Tree: It's just a tree with at most 2 child nodes.

Binary Search Tree: Nodes to the left are less than the current node and nodes to the right are larger than the current node.

Balanced Tree : It's a tree that keeps its height in check or to a minimum.

Unbalanced Tree : It's a tree in which its height isn't kept in check. Eg. A node having a right node which has a right node etc.

Full tree: All nodes have either 2 child nodes or is a leaf node.

Complete tree: All nodes except the last level are complete, and the nodes of the last level have all its nodes to the left.

Traversal

Preorder: Root,Left,Right

Inorder:Left,Root,Right

Postorder: Left,Right,Root

Stacks and Queue questions

https://github.com/prasanthlouis/C-equivalent-to-Cracking-the-Coding-Interview

Question 1: Implement 3 stacks using a single array. I was actually looking for a flexible way to do this. But when the author stated that it's beyond the scope, I was kinda disappointed.

The conventional way to do it is to allocate a fixed size to each stack. Boring.

Question 2: Find the min element with low complexity. I liked the algorithm they presented. Made me use a class as well. I haven't gone deep into class, but I've implemented the solution with it.

Moral: I liked using class when a real world object has several properties.

Eg. A toy duck has properties of color,size,price, etc. So to implement this, use a class.

Here our values in the stack have 2 properties, their original values as well as minimum value.

Question 3: Multiple stack overflow structure. Nothing difficult here. I used the provided stack structure in C++, made things a whole lot easier. Made an array containing stack structures.

Question 4: Towers of Hanoi. I loved this question. As a CSE student, we were taught about Hanois towers, but were never actually given an algorithm to solve it. It was more of a puzzle the teachers gave us to do, and we'd solve it manually as fast as possible. So I was interested on how to develop an algorithm

There are 3 steps:

1) Move n-1 disks to the buffer
2) Move the nth disk to the destination
3) Move n-1 disks from buffer to destination, using the source as a buffer.

Once you got down these 3 steps, you can implement it yourself. I used recursion.

Question 5: Implement a queue using 2 stacks. At first I thought of copying data from one stack to another to implement push() and pop(). But as we know, copying data is a big NO!. So use one stack for newer elements, and another one for older elements.

Question 6: Sort a stack. When they said "don't use any other storage other than another stack", it was pretty misleading. Looking at the solution, I saw that they used another variable to store an element at a time. Meh. Nothing too fancy here.

Question 7: Cats and Dogs. Nothing hard here. I used a class to maintain OOD. Nothing else worth mentioning.

Stacks and Queues

https://github.com/prasanthlouis/C-equivalent-to-Cracking-the-Coding-Interview

So stacks are a kind of FIFO structure.

Similar to a stack of plates. The last plate that was placed on a pile of plates will be the first one to be taken out/used.

So when I was in school, we were taught to implement stacks as an array.

Again, after researching online. C++ has a built in stack class that allows you to manipulate stacks easily with built in functions.


Declaration

stack<date type> name;

It's similar to a vector, but there's no need to specify the size.

.push(element), allows you to push the element into the stack.

.pop(element) removes the top element.

.top() gives access to the top most element.

.empty() whether the stack is empty.

If only they taught all this in school. Sigh.


Queues are a FIFO structure. Like waiting in a line for a movie ticket. The people who've arrived earlier than others will get their tickets before them.

The syntax is pretty much the same, but instead of .top() you have the function .front()


Don't forget about the headers
#include<queue>
#include<stack>

Link List questions

https://github.com/prasanthlouis/C-equivalent-to-Cracking-the-Coding-Interview

Here's my thought process on the link list questions:


Question 1: Find duplicates. One thing I've learned from the array and strings chapter is that manipulation of the original structure is always better than copying the data from one structure to another.

So there are two parts to this. But reading the slow/fast runner concept racked my brain and I got the follow up solution before the original question.

It's sort of like 2 for loops used when searching for duplicates in an array, but instead here you'll have to use 2 pointers. The slowpointer used for indexing the element to be compared with and the fast pointer to iterate through the list.

Moral: Always manipulate linklist questions with 2 pointers and at various speeds to see what kind of algorithm you can come up with to implement the question.

Here's where the concept of next->next came into my mind.

If you want to delete the node, you'll have to check the data of the next node the fastrunner is on.

If its a match, then it's that node you'll want to delete by setting fastrunner->next=fastrunner->next->next.

Moral: Always think of ways to use next->next instead of implementing more pointers than necessary.

This makes it so much easier than using more pointers than actually necessary.


Question 2: Find kth to last element. I thought of also solving this with the fast and slowrunner concept. One pointer reaches the end and returns a count value of the number of hops.

Start another pointer at the head of the list and traverse for (count-kth element) steps. Your pointer will then reach the kth from end element.

Then I read up on the recursive solution. I liked that much more than what I did. So its basically calling the function over and over. When you reach the end of the list, you'll return a 0. From there, each return value will be incremented by 1. So once the return value reached the kth value, you can print out the data value pointed by the pointer.

Moral: Recursive solutions are less optimal but much more cleaner.

Question 3: Delete the middle of the node given only access to that node.  This is just a question to rack your brains. Just copy the next node data into the current node and delete the next node. Easy.

Moral: Copying data can be useful when you've got restrictions in access.

Question 4: Partitioning. I thought of implementing with 4 pointers and keeping 2 lists just like the solution said to do. But it didn't occur to me that if I attached the new nodes to the beginning of the lists rather than the end, I could implement this question with 2 pointers instead of 4.

Moral : Attach your nodes to the beginning of the lists if you want to merge them at the end.

Question 5: Addition. I thought this question was kinda standard-ish. But nothing too complex. The follow up solution was pretty tricky, but I didn't really feel like reading the solution provided. I thought it'd be much easier just to reverse the link list and implement the same way as the original question.

This question may take a bit more time than the others, since you'll have to check for cases if one number is shorter for the other.

Oooo! And don't forget about the zero padding in the follow up!


Question 6: I ABSOLUTELY LOVED THIS QUESTION. It was totally new for me and if you don't want to do these questions I strongly recommend to at least do this one.

I had no clue how to do this.

But they explain the algorithm so well in the book, so I recommend you to read up on it.

Once you get the algorithm, its very easy to implement in code.

Moral: Awesome algorithm here.

If you want to see my explanation of it, you can check my post here : http://cselabintro.blogspot.in/

I made it for those, who are too lazy to read the whole algorithm in the book. My post describes it in 4 steps.

Question 7: Palindrome. I thought maybe copying everything down would be easy. But then I thought to use the runner concept. It became much easier and again nothing complex.

There was a recursive solution, but at the end the author states that "it's ugly". Yeesh. No thanks.

Moral:Same as question 1

Link Lists Basics

So I finished the section on link lists.

This post will be on the basics of link lists and how to manipulate them.

So my code on github was very inefficient. But I updated the efficient code within comments so no worries.

What they taught us in school was using malloc and how to create link lists based on that.

Due to all the memory manipulation, I honestly liked the concept of link lists, but I hated on its implementation. So I took some time reading online for its manipulation.


It was actually pretty easy.

struct node
{
node *next;
int x;
};

So you have a pointer node and a value x for each node you create and don't forget the semi colon after the struct.

Here's where it made a big difference for me.

Apparently you can create a new node without its explicit memory allocation using malloc by simply using

node *cond;
cond=new node;


That's it. (This goes to show you, that the things you learn in school may not be the most straight forward);

Manipulation with link lists are using 2 pointers namely a slowrunner and a fastrunner.

Slowrunners tend to traverse the list slower than fastrunners which make them useful in several algorithms. (I'll explain them as I go into the problems).

Personally, I always keep a pointer at the start of the link list and never modify it. It makes it simple to access the beginning of the link list.

If you want to delete a node

node1->next=node2->next;

By assigning the next of node1 to the next of node2(meaning node 3), you've actually removed the node2 from the linklist.

That's basically it. Nothing to fancy. Now to the questions.

Arrays and Strings

https://github.com/prasanthlouis/C-equivalent-to-Cracking-the-Coding-Interview

There's nothing too complex on the arrays and strings problems. Most of them are common problems you've probably seen before.

Like I said before, I'll make a post for each section unless there's a question that needs to be explained in detail. These were kinda easy, so I didn't really feel the need to dedicate a whole post for each question.

Remember you can always check my code out on Github.


Things that intrigued me were (Or what I did differently are):

Question 1: The unique characters question. - Pretty straight forward, but after doing it the only difference I saw in my code was that I used 0s and 1s instead of boolean values in the solution provided. Meh. Not much of a difference.

Question 2: Reverse a string- Again, nothing complex. An easy second semester of college question.

Question 3: Permutation: Originally I thought of a simple search for each letter and whether the other word contains that letter. The algorithm presented in the book was pretty nice.

First of all, they checked if the two strings length was equal. If not they aren't a palindrome. (I didn't really think about this case)

Second they sorted the words by the characters present in them, and from there on out, it was just matching the letters in both the arrays. This was way more simpler than what I initially thought.

Question 4: Replacement with %20. My initial attempt made me copy the letters into another array and adding a %20 where ever needed. After reading the algorithm, I realized that you didn't need to copy the array, instead move to the end of the array, and work backwards while shifting. Again nothing hard here.

Question 5: The repeated aabbccc question. I'll admit, I attacked this head on and got the output. But when I went back to read the algorithm, I realized for big strings, my code wasn't efficient.

If its one thing I learned by now its this:

IF YOU CAN AVOID COPYING STRINGS, DO IT. INSTEAD, MANIPULATE THE ORIGINAL STRING OR CREATE A NEW STRING AND UPDATE IT BY INDEX INSTEAD OF CONCATENATION.

I then realized why in question 4 they wanted to modify the original array rather than copying it into a new array. It wasn't explicitly said at the time, but looking back on it I realized I could've done it better.

I liked how we first had to find the length of the array and then we attack it. Seemed interesting to me. But again, no problems in implementation.

Question 6: Matrix rotation. This again, I attacked it and got it right. On reading the algorithm, I realized again, the faster way is to update by INDEX and not COPYING STRINGS.

(Facepalm! Oh well. This is how you learn and I won't forget it anymore.)

So I implemented my own copying algorithm and did it.

This was probably the hardest question of this session, or at least the most time consuming.

Question 7: I liked the algorithm they used here. Instead of finding the elements that were 0, just store the indexes of the row and column of the element that was zero and put the element to zero if the index was marked. Again I used 0s and 1s instead of boolean values.

Question 8:Substring. I was stumped on this question. But when I saw the solution they provided, it was really easy to implement.

Waterbottle
terbottlewa

If you write the original string twice, it'll be easy to determing whether the second string is a rotated substring of the first.


Waterbottlewaterbottle
      terbottlewa


And that's it! Session one is done!

Nothing to difficult. I used bold text whenever I thought was necessary.

Vectors

https://github.com/prasanthlouis/C-equivalent-to-Cracking-the-Coding-Interview

Vectors are pretty cool. They're more of a replacement for the original arrays in C++.


Let's check them out!


So normally you'll have a static array such as

int number[20];

As you can see, your array has a constant size.

What about dynamic arrays in C++?

Well, the size parameter doesn't have to be constant.

int number[size], where size is defined as a non constant variable.

However dynamic arrays come at the disadvantage that they have to be cleared from the memory when you're done using them.

Eg. delete[] array

Now vectors combine the advantage of both the above arrays.
They can use a non-constant size attribute for the array (like dynamic) but you don't need to clear the memory when you're done using them (like static).

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int i;
   vector<int> intarr(10);
   for(i=0;i<10;i++)
   intarr[i]=i;
 
   for(i=0;i<10;i++)
   cout<<intarr[i];
 
   return 0;
}


The rest of the syntax, is pretty much the same. But it should be said, that vectors tend to use a bit more memory due to the dynamic allocation. In fact, if you declared your variable size=20, the actual memory allocation is a bit bigger, just in case you need to change your memory size dynamically later on.

Maps

https://github.com/prasanthlouis/C-equivalent-to-Cracking-the-Coding-Interview

So I've worked with maps and vectors in other languages. But never in C++.

It troubled me at first, because it wouldn't compile at first. I later realized that I had to use C++ 11 (facepalm!).

My code:


unordered_map<string,int> mymap={{"prasanth",21},{"nelson",19}};
mymap.insert({"louis",54});
for(auto& x: mymap)
cout<<x.first<<"-"<<x.second<<endl;
cout<<mymap.at("louis");


Nothing to complex here. You have your keyword followed by your data types within angle brackets (i.e your key data type and your data data type). This is followed by your keys and data values within curly braces.

If you want to enter values into your map use the .insert() method, with your key and data value inside.

Here was something I didn't really understand the first time.

'auto& x:mymap'

Lets break this down.

The colon means "a range", x will iterate inside every element inside the map 'mymap'.

Now auto&

Auto means that the variable that it is being assigned to will take the type according to its initializer.

Eg. auto a=3+4

and if you decided to print the type a, it'll be an integer (Since int+int=int).

Now &. & is used for a reference. So use auto& if you want to work with the original variables and modify them.

Now to print the key out use the keyword .first and the print out the values use .second.

You can access a value by it's key by  using .at.

Introduction

https://github.com/prasanthlouis/C-equivalent-to-Cracking-the-Coding-Interview

So here's my attempt to solve the questions provided in Cracking the Coding Interview in C++/C.

The idea came up because I wanted to become better at C++/C instead of learning Java all over again, so I was fairly disappointed that all the solutions were provided in Java.

Then I thought, there might be other readers who'd love a C implementation of the solutions provided in the book.

So this blog is dedicated to anyone who wants the solutions provided in C.

After I complete each section, I'll come back and write a post on it rather than giving a post on each question because come on, lets be honest. Nobody wants to read pages of a solution to a single question if it can be explained easily.

Note : This isn't perfect.

I just wrote code to how I perceived the question.

I first read the question and thought on how to solve it.

Next I read the algorithm and tips provided to see if there was a better solution.

Then I closed the book and tried to implement the algorithm in C++.

(No, I didn't look at the code they provided unless I was absolutely stuck).

You can get the code on github: https://github.com/prasanthlouis/C-equivalent-to-Cracking-the-Coding-Interview