Function to check if a singly linked list is palindrome

January 31, 2015 by vinaybysani

(Use a Stack)
A simple solution is to use a stack of list nodes. This mainly involves three steps.
1) Traverse the given list from head to tail and push every visited node to stack.
2) Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node.
3) If all nodes matched, then return true, else false.

Time complexity of above method is O(n), but it requires O(n) extra space. Following methods solve this with constant extra space.

Binary tree notes from video

January 25, 2015 by vinaybysani

k largest(or smallest) elements in an array using Min Heap method

January 24, 2015 by vinaybysani

An array sorted from lowest to highest is a min-heap.

Q : Write an efficient program for printing k largest elements in an array. Elements in array can be in any order.

For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30 and 23

Algo :

1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)

2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
……a) If the element is greater than the root then make it root and call heapify for MH
……b) Else ignore it.
// The step 2 is O((n-k)*logk)

3) Finally, MH has k largest elements and root of the MH is the kth largest element.

External Merge sort interview question

January 24, 2015 by vinaybysani

Q1 : How to sort a 1000 GB file with ram size is 4 GB only. Which algorithm or data structure we need to use to sort these files?
Follow Up: External sort is Ok… but how can you make this solution more efficient…
Follow Up 2: Ideal chunk size for external sort (I said 512 MB based on my experience with MS Word 2013, it can not load file size >512 MB)

Q2 : How would you sort a text file full of phone numbers. You do not have enough memory to load all the file contents at once and sort them. You should write back the sorted list to the file in the end.

Q3 : Given 2 files find common words.
Both files are too large to be loaded in memory.

One example of external sorting is the external mergesort algorithm. For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:

   1. Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.
   2. Write the sorted data to disk.
   3. Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks, which now need to be merged into one single output file. The idea of external sorting is divide and conquer.
   4. Read the first 10 MB of each sorted chunk into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)
   5. Perform a 9-way merge and store the result in the output buffer. If the output buffer is full, write it to the final sorted file. If any of the 9 input buffers gets empty, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available.

Answers :

http://en.wikipedia.org/wiki/External_sorting#External_merge_sort

http://www.careercup.com/question?id=14947055

http://www.careercup.com/question?id=4072082

Why space Complexity of Binary search is O(log n) ?

January 24, 2015 by vinaybysani

For example, looking up people in a phone book(dictionary order) is O(log n). You don’t need to checkevery person in the phone book to find the right one; instead, you can simply divide-and-conquer, and you only need to explore a tiny fraction of the entire space before you eventually find someone’s phone number.

Of course, a bigger phone book will still take you a longer time, but it won’t grow as quickly as the proportional increase in the additional size.

Big O Cheat Sheet (Time and Space complexity of various algo’s)

January 24, 2015 by vinaybysani

http://bigocheatsheet.com/

Add two numbers without using arithmetic operators

January 24, 2015 by vinaybysani

public static int addIterative(int a, int b)
{
    while (b != 0)
  {
    int carry = (a & b) ; //CARRY is AND of two bits
    a = a ^ b; //SUM of two bits is A XOR B
    b = carry << 1; //shifts carry to 1 bit to calculate sum
  }
    return a;
}

How to check if two words are anagrams (faster way)

January 24, 2015 by vinaybysani

Fastest algorithm would be to map each of the 26 English characters to a unique prime number. Then calculate the product of the string. By the fundamental theorem of arithmetic, 2 strings are anagrams if and only if their products are the same.

Binary Tree (BT) vs Binary Search Tree (BST)

January 24, 2015 by vinaybysani

Binary tree: Tree where each node has up to two leaves

  1
 / \
2   3

Binary search tree: Used for searching. A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent.