Add 2 large numbers in the form of list, without reversing the linked lists
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
You are given two numbers in the form of linked list.Add them without reversing the linked lists. linked lists can be of any length.
Take two stacks and push a linked list to a stack. After done pushing, simply start popping the stacks, add the numbers, get the carry over, generate another node with the result and add to front to a new linked list.
We have already done this question here, which involves reversal of 2 numbers and then adding it.
[Read More]Sorting a very large file which cannot fit in memory
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
The solution to it is External sorting.
One solution is to use external merge sort, where you sort small chunks of data first, write it back to disk and than iterate over those to sort all. However this has a limitation because you have to read write the data again and again from the disk.
Hadoop
An external sort is always slower compared to an in-memory sort, but you are no longer limited by your ram.
[Read More]Stack DS to implement constant time Minimum element lookup
Posted on December 28, 2011
(Last modified on August 11, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: You need to implement a stack data structure that can also report the minimum element in constant-time.
Solution
Method 1 - Using extra stack
This is not all that difficult if you think about it. Regular stacks support push() and pop() functions. We need to add a new read-only property, Minimum. You can’t just add a new variable to track the minimum because when the stack is popped you wouldn’t be know how to update the minimum variable without scanning through all items in the stack which would require you to pop and re-push each item, which is downright ugly.
[Read More]Print a Binary Tree in Zig Zag Level Order or spiral order
Posted on December 27, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Question: Print a binary tree in zig-zag level order. Zig-zag means print 1st level from left to right, then 2nd level right to left and alternate thereafter.
Example: zig-zag level order traversal of below tree will be
0 2 1 3 4 5 6 14 13 12 11 10 9 8 7
Solution1 - Iterative solution
Answer: We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal on every alternate level?
[Read More]Finding the Start of a Loop in a Linked List
Posted on December 27, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Fantastic explanation. Thanks a lot.
crazybuddy - Feb 6, 2015
Fantastic explanation. Thanks a lot.
Thank you :)
Finding the Start of a Loop in a Linked List
Posted on December 27, 2011
(Last modified on August 7, 2020)
| 9 minutes
| Kinshuk Chandra
Problem Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
DEFINITION
Circular linked list:
A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C
Example
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 ^ | | | +------------------------+ Answer here is 3.
[Read More]GitHub: Setup SSH - Permission denied public key error
Posted on December 27, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
I already setup SSH for GitHub which tutorial provided from GitHub, but there still somtething error with my Public Key Permission Denied, so that means I have missed the config.
Solution that worked in my case was that I renamed the pub and private key to id_rsa. That solved the cause. Also those who already have files by this name, should try
chmod 600 ~/.ssh/id_rsa* from Git bash, assuming you installed Git for Windows.
[Read More]Karp-Rabin algorithm
Posted on December 25, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Some points to note about this String matching algorithm:
uses an hashing function; preprocessing phase in O(m) time complexity and constant space; searching phase in O(m__n) time complexity; O(n_+_m) expected running time. Instead of checking at each position of the text if the pattern occurs or not, it is better to check first if the contents of the current string “window” looks like the pattern or not. In order to check the resemblance between these two patterns, a hashing function is used.
[Read More]Given a 10 digit number,find the greatest continuous 4 digit number.
Posted on December 24, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
given a 10 digit number,find the greatest continuous 4 digit number.
Ex:9164352435
Ans : 9164
int indexoflargest4digitnumber(int\[\] number) {
if(number == 0)
return -1;
int result = 0;
int length = number.length;
int count = 0;
while ( count <= length-4 ) { //9164916500
if( number\[result\] < number\[count\] )
result = count;
else if ( number\[result\] == number\[count\]){
if( (number\[result+1\] <= number\[count+1\]) ||
(number\[result+2\] <= number\[count+2\]) ||
(number\[result+3\] < number\[count+3\]))
result = count;
}
count++;
}
return result;
}
WAP to Find Number of Divisor & sum of All Proper Devisor of Number Efficiently
Posted on December 23, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Given a natural number n (1 <= n <= 500000), please output the summation of all its proper divisors.
Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.
e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.
**Input
**An integer stating the number of test cases (equal to about 200000), and that many lines follow, each containing one integer between 1 and 500000 inclusive.
[Read More]