All permutations of a string
Posted on September 7, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
small trick ,but a very nice solution for duplicat…
nikhil - Feb 4, 2014
small trick ,but a very nice solution for duplicates!!!!
Thanks Nikhil. :)
can u please write the main function for duplicate program. I ran the duplicate program and it is not giving me the desired output
All permutations of a string
Posted on September 7, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem
Write a method to compute all permutations of a string.
Example
For a string of length n, there are n! permutations.
INPUT: “abc”
OUTPUT: “abc” “acb” “bac” “bca” “cab” “cba” So, we have 3! = 6 items for string abc.
Solution
There are several ways to do this. Common methods use recursion, memoization, or dynamic programming.
The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually.
[Read More]Deleting a middle node from a single linked list when pointer to the previous node is not available
Posted on October 22, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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
If we are allowed to make some assumption, it can be solved in O(1) time. To do it, the strictures the list points to must be copyable.
[Read More]Find the nth Fibonacci number
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
Problem: Write the code for nth Fibonacci number.
Solution: There are basically two approaches to solving the Fibonacci problem. Lets looks at the definition of Fibonacci series first.
The Fibonacci series is defined as follows
F(n) = 0 for n = 0 1 for n = 1 F(n-1) + F(n-2) for n > 1 So, F(n) = F(n-1)+F(n-2) for n≥2and 1 otherwise.
There are couple of approach to solve this.
[Read More]Return the nth node from the end of a linked list
Posted on April 8, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem Get the nth element from the end of the linked list
Example Lets say the Single Linked List (SLL) is 0-1-2-3-4-5-6-7-8-9, and we want to find last 3rd element (say ‘pos=3′) in this SLL. So, we have to return 7 here.
Solutions Method 1 - 2 pointer approach
Here is a solution which is often called as the solution that uses frames.
Suppose one needs to get to the 6th node from the end in this LL.
[Read More]First / Lowest common ancestor (LCA) of 2 node in binary tree
Posted on January 25, 2010
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
Problem
Case 1 - Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
Case 2- What will you do if it is Binary search tree
Example
So for example look into below figure:
So for node 4 and 14, LCA is 8.
[Read More]Find the median in a continous stream of numbers
Posted on January 18, 2010
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem
Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.
OR
You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time)
**OR **
[Read More]To add two long positive numbers (each represented by linked lists in C)
Posted on December 5, 2009
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8
[Read More]To determine whether machine is Little-Endian and Big-Endian?
Posted on November 28, 2009
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Write a program to find whether a machine is big endian or little endian.
Solution What Little-Endian and Big-Endian? How can I determine whether a machine’s byte order is big-endian or little endian? How can we convert from one to another?
First of all, Do you know what Little-Endian and Big-Endian mean?
Little Endian means that the lower order byte of the number is stored in memory at the lowest address, and the higher order byte is stored at the highest address.
[Read More]Swap two number in place without temporary variables.
Posted on November 27, 2009
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem Write a function to swap two number in place without temporary variables.
Solution Method1 - The XOR or Exclusive trick
In C this should work:
a ^= b ^= a ^= b; to simplify :
a=a^b; b=a^b; a=a^b; OR
a^=b; b^=a; a^=b; Following are operations in XOR
0^0=0 0^1=1 1^0=1 1^1=0 Hence, we have:
a=a^b: ‘a’ will save all the bits that a differs from b: if the bit that ‘a’ and ‘b’ differ, it gets 1, otherwise 0.
[Read More]