Determine if a string has all unique characters
Posted on February 4, 2014
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Problem:
Implement an algorithm to determine if a string has all unique characters.
Solution
Solution1 - My first algorithm is a straightforward, brute force approach. Basically, we take each character in the string and compare it to every other character in the string. We do this using for loops. This would mean a time complexity of O(n^2) because of the nested loop.
bool uniqueChars(string myString) { for (int x = 0; x < myString.
[Read More]Algorithm to find top 10 search terms in search engine
Posted on January 28, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
**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.
[Read More]Find the k most frequent words from a file
Posted on January 28, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
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.
use a Hash table to record all words’ frequency while traverse the whole word sequence.
[Read More]Given a binary tree with extra field "next pointer" in node, populate the next pointer to the nodes inorder successor
Posted on January 24, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
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 NULL values. Your function should fill these next pointers so that they point to inorder successor.
[Read More]Data Structure to Emulate LRU Cache
Posted on January 23, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
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:
find the item as fast as we can 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 :
[Read More]Print nodes at k distance from root
Posted on January 22, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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: O(n) where n is number of nodes in the given binary tree.
[Read More]Find the time period with the maximum number of overlapping intervals
Posted on January 22, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
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.
[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.
Posted on January 22, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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 way.
Insertion sort on linked list
Posted on January 19, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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:
[Read More]Selection sort on linked list
Posted on January 19, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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.
[Read More]