Algorithm to find top 10 search terms in search engine

Problem :  "You have been asked to design some software to continuously display the top 10 search terms on Google (or any other search engine). You are given access to a feed that provides an endless real-time stream of search terms currently being searched on Google. Describe what algorithm and data structures you would use to implement this. You are to design two variations: (i) Display the top 10 search terms of all time (i.e. since you started reading the feed). (ii) Display only the top 10 search terms for the past month, updated...

Read More

Find the k most frequent words from a file

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/top-k-frequent-words-problem/. Case 1 - Consider the file is not big The question can be described as: Input: A positive integer K and a text file which can stay in-memory. The text can actually be viewed as word sequence. So we don't have to worry about how to break down it into word sequence. Output: The most frequent K words in the text. My thinking is like this. 1) use a Hash table to record...

Read More

Given a binary tree with extra field "next pointer" in node, populate the next pointer to the nodes inorder successor

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/populate-next-pointer-to-inorder-successor-in-binary-tree/. Problem : Given a Binary tree where each node has an extra field (node * next), write a function that puts the inorder successor of that node in the next pointer. This is how our binary tree node looks like : struct node { int data; struct node* left; struct node* right; struct node* next; } Initially, all next pointers have...

Read More

Data Structure to Emulate LRU Cache

Problem Implement the LRU cache  Solution Least Recently Used (LRU) Cache is to discard the least recently used items first How do you design and implement such a cache class? The design requirements are as follows: 1) find the item as fast as we can 2) Once a cache misses and a cache is full, we need to replace the least recently used item as fast as possible. We use two data structures to implement an LRU Cache : 1. A Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number...

Read More

Print nodes at k distance from root

Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root. For example, in the below tree, 4, 5 & 8 are at distance 2 from root. 1 / \ 2 3 / \ / 4 5 8 Code: void printKDistant(node *root , int k) { if(root == NULL) return; if( k == 0 ) { printf( "%d ", root->data ); return ; } else { printKDistant( root->left, k-1 ) ; printKDistant( root->right, k-1 ) ; } } Time Complexity:...

Read More

Find the time period with the maximum number of overlapping intervals

Problem There is one very famous problem. I am asking the same here. There is number of elephants time span given, here time span means, year of birth to year of death. You have to calculate the period where maximum number of elephants are alive. Example : 1990 - 2013 1995 - 2000 2010 - 2020 1992 - 1999 Answer is 1995 - 1999 Solution Pseudocode Split each date range into start date and end date. Sort the dates. If a start date and an end date are the same, put the end date first (otherwise you could get an empty date range as the...

Read More

Given an array of 100,000 pixel color values and each of which is an integer in the range (0,255). Give sorting algorithm.

We should use counting sort. There are only 256 key value, so aux array will have only 256 values, and in O(n) time and 2 passes we will be able to sort in efficient wa...

Read More

Sort a linked list using bubble sort

Merge sort looks like a best choice for sorting the linked list.At a first appearance, merge sort may be a good  selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists. We have discussed the sorting options for linked list here. Here we will discuss about bubble sort Pseudocode for bubble sort: public void sortList() { if (isEmpty()) { System.out.println("An empty list is already sorted"); } else...

Read More

Selection sort on linked list

Another O(n2) sorting algorithm that can be adapted for linked lists is selection sort. This can be implemented very easily (assuming you have a doubly-linked list) by using this algorithm: Initialize an empty list holding the result. While the input list is not empty: Scan across the linked list looking for the smallest remaining element. Remove that element from the linked list. Append that element to the result list. This also runs in O(n2) time and uses only O(1) space, but in practice it's slower than insertion sort; in particular,...

Read More

Insertion sort on linked list

If you want a simpler algorithm that needs only O(1) space, you can also consider using insertion sort to sort the linked lists. While insertion sort is easier to implement, it runs in O(n2) time in the worst case (though it also has O(n) best-case behavior), so it's probably not a good choice unless you specifically want to avoid merge sort. The idea behind the insertion sort algorithm is as follows: Initialize an empty linked list holding the result. For each of the three linked lists: While that linked list isn't empty: Scan across...

Read More

Sort a linked list using quick sort

Merge sort looks like a best choice for sorting the linked list.At a first appearance, merge sort may be a good  selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists. We have discussed the sorting options for linked list here. Here we will discuss about quick sort. Another O(n log n) sort that you can implement on linked lists is a modification of quicksort. Although the linked list version of quicksort is fast (still...

Read More

Bubble sort on double linked list

 Following can be the pseudocode: public void bubbleSort() { boolean done = false; while (!done) { Node cur = head; done = true; while(cur != tail) { if (cur.getNext().getCount()>cur.getCount()) { swap(cur.getNext(),cur); done=false; } cur = cur.getNext(); } } } Thanks. Source : stackoverflow...

Read More

Sort a linked list using merge sort

 Merge sort looks like a best choice for sorting the linked list.At a first appearance, merge sort may be a good  selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists. We have discussed the sorting options for linked list here. Merge sort is very special (in fact many standard sort libraries like in java internally uses a combination of merge sort and insertion sort) because it has the wonderful property of being...

Read More

What's the fastest algorithm for sorting a linked list?

Merge sort is the best choice. At a first appearance, merge sort may be a good  selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists. It is reasonable to expect that you cannot do any better than O(N log N) in running time, whenever we use comparison based sorts. However, the interesting part is to investigate if you can sort it in-place, stably, and so on. Auxiliary storage requirement is small and constant (i.e. a few...

Read More

Find increasing 3-tuple (sub-sequence)

Problem: You given an array: 3, 2, 1, 6, 5, 4, 9, 8, 7 you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array. Answer can have multiple tuples, you have to find any one. In this array, answer will be 3, 6, 9 Solution: Simple. Time complexity = O(n ^ 2) Create an array of indexes, and sort the original array keeping track of the indexes in the second array. Now go through the sorted array and for each element try to find a pair of grater elements whose indexes are increasing. Complexity:...

Read More

Merge two arrays efficiently - one sorted, another unsorted

Problem Given a sorted array of n elements followed by an unsorted array of length n. Sort the 2 list into one efficiently. Solution Method 1 - Insert the elements in sorted array using binary search Since inserting a single element into array and keeping it sorted is O(n), you cannot get better then that. Thus, for both cases - sorting the smaller array and then using merge(part1,part2) will be O(n), and thus optimal in terms of asymptotic complexity. sorting the smaller array: O(logn*loglog(n)), or O(sqrt(n)*log(sqrt(n)) respectively...

Read More

Sorting implementation in c

Binary Sort implementation in C Quick sort in c Merge sort in c Radix sort in c Shell sort in c Sorting binary array...

Read More

Red Black Tree vs AVL Tree vs B-Tree

B-tree when you're managing more than thousands of items and you're paging them from a disk or some slow storage medium. RB tree when you're doing fairly frequent inserts, deletes and retrievals on the tree. AVL tree when your inserts and deletes are infrequent relative to your retrievals. think B+ trees are a good general-purpose ordered container data structure, even in main memory. Even when virtual memory isn't an issue, cache-friendliness often is, and B+ trees are particularly good for sequential access - the same asymptotic performance...

Read More

Union Find

The Union-Find data structure is used to keep track of a partition of a set and supports two operations. The Union(x, y) operation merges the subsets containing x and y, and the Find(x) operation returns the name of the leader element of the subset to which x belongs. The implementation is based on a response to this post on StackOverflow, but extended with a makeSet operation, a getNumGroups operation, and tests. Union-Find can be used to create very efficient implementations of Kruskal’s minimum spanning tree algorithm and the single-link...

Read More

Bottom-up Merge Sort

Recursive algorithm In the earlier article I’ve described a recursive version of the Merge Sort Algorithm OR Top Down Merge sort. Of course every recursive algorithm can be written in an iterative manner . Non recursive algorithm So today I am going to present the bottom-up version of the same algorithm, written in a non-recursive fashion . The main idea of the bottom-up merge sort is to sort the array in a sequence of passes . During each pass the array is divided into smaller sub-arrays of a pseudo-fixed size (step or sz) . Initially step...

Read More

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space]. e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8] http://stackoverflow.com/questions/6153915/merging-of-two-sorted-halfs-without-extra-memory...

Read More

Amazon Questions - Set 1

Write code to find Nth last node in a linked list. Solution Given a binary tree build a vertical sum array.    Solution Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1? Solution Given two lists of strings return a list of strings that is an intersection of both of the lists. Analyze running time and space complexity. Give Test Case scenarios. There is n node graph, each node having only one root. All nodes are labeled in a random order from int 0 to n-1. The graph is represented...

Read More

k-way merge - Merging k sorted arrays of n elements

 Given k sorted arrays of size n each, merge them and print the sorted output. Example: Input: k = 3, n = 4 arr[][] = { {1, 3, 5, 7}, {2, 4, 6, 8}, {0, 9, 10, 11}} ; Output: 0 1 2 3 4 5 6 7 8 9 10 11 Method 1 - Merging from 1 array to other It does so by using the "merge" routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged. Time complexity - O(n . k^2) It doesn't traverse each of the k arrays once. The first...

Read More

Find the maximum repeating number in array where all the elements are in range 0 to k-1, k ∈ [0,N]

: This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-element-which-appears-maximum-number-of-times-in-the-ranged-array/. Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2. Expected time...

Read More

Finding the max repeated element in an array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-most-frequent-element-in-the-array/. Problem : Find the element which occurs maximum number of times. METHOD 1 : Sorting the array and scanning the array The simple solution is to 1) Sort the array 2) Scan the array such that keep the track of the elements which occurred max number of times METHOD 2 : Using Binary Search Tree We can have a binary search tree with an extra field count,...

Read More

Print letters followed by their frequency (Run Length Encoding)

Given a string ,Write a program to print letter followed by it’s frequency.This is also knows as Run Length Encoding. Example: Input aaabcc Output a3b1c2 Algorithm: 1.Pick the first character from the string and print it. 2.Count the number of subsequent occurrences of the picked character and then print the count. 3.Pick the next character and repeat step 2 till we reach end of the String. #include <iostream> #include<string> using namespace std; int main() { string str = "aaabcc"; int count=0; int i=0,j; int...

Read More

Remove duplicate characters in a string

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/remove-duplicate-characters-in-a-string/. Problem Given a string, Write a program to remove duplcate characters from the string. Input String : kodeknight Output String : kodenight Solution Method 1 : Brute force void removeDuplicates(char *str) { if (!str) return; int len = strlen(str); if (len < 2) return; int tail = 1; for (int...

Read More