Random Stuff

Problem Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->e Result: nothing is returned, but the new linked list looks like a->b->d->e Solution The question is a bit confusing. I first though its asking to remove the middle element of the list and I thought we have the full list. But later I think I got it. As per my understanding is we clear the node which we have access only and it will be somewhere in the middle. What we can do, we can migrate the data from next one to this one and set next to next of next. Code https://github.com/tapos/ctci/tree/master/src/p23

Problem Write code to remove duplicates from an unsorted linked list. Solution Two types of solution came to my mind 1) Use hashmap to check the duplicates and remove that as necessary. Time complexity for this solution is O(n) and Space Complexity O(n) 2) We also can check if by checking all previous entries for duplciate. In this case time complexity will be O(n^2) and Space Complexity O(1) Code https://github.com/tapos/ctci/tree/master/src/p21

I was trying to get back to solve some problems to prepare an interview. I have started an easy problem on HackerRank - Circular Array Here is the details of problem and solution -  https://github.com/tapos/hackerrank/tree/master/src/circulararray

Problem Description: For given 15 > n > 0, print all balanced parenthesis eg: For n = 1 () n = 2 ()() (()) n=3 ((())) (()()) (())() ()(()) ()()() Solutions : Solution is simple. Start with empty string  Add only valid parenthesis at the end  And continue until you reach to the length Code : public class BalancedParenthesis { public void printParenthesis(int n) { print("", n, 0, 0); } private void print(String strSoFar, int n, int opc, int cpc) { if(opc == n && cpc == n) { System.out.println(strSoFar); } if(opc < n) { print(strSoFar + "(", n, opc + 1, cpc); } if(cpc < opc) { print(strSoFar + ")", n, opc, cpc + 1); } } public static void main(String[] agrs) { BalancedParenthe...

I think everyone knows the use cases of Arrays and Linked List but revising things wont hurt :) Array: One memory block  0-based indexing Easier to use and access Constant access time Fixed size Delete and Insert in front or middle is expensive Linked List: Elements are not stored in contiguous memory locations Extra memory needed to save pointer for next element Searching any element is expensive. Insert and Delete is very cheap. Constant time. No memory limitation as long as system has enough memory. Easier to store different data size. There are some good comparison listed on Wiki . Also you will get the tradeoff between above two data structures.