K reverse a linked list with increasing K
Posted on May 25, 2015
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Reverse k elements in the linked list such that k goes on increasing
Example
Eg. 1 - 2 - 3 - 4 - 5 - 6 - 7
output - 1 - 3 - 2 - 6 - 5- 4 - 7
Solution You can take this problem here. Here we are just increasing k.
public static ListNode<Integer> reverseSubLinkLists(ListNode<Integer> headerNode) { ListNode<Integer> nextNode = headerNode.next; ListNode<Integer> startNode = null; ListNode<Integer> endNode = null; int k = 2; while (nextNode !
[Read More]Reverse the doubly linked list
Posted on April 18, 2015
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem Reverse the doubly linked list
Input
10 - 8 - 4 - 2
Output
2 - 4 - 8 - 12
Solution Method 1 - Reversing the prev and next references
Reversing a doubly linked list is much simpler as compared to reversing a singly linked list. We just need to swap the prev & next references in all the nodes of the list and need to make head point to the last node of original list (which will be the first node in the reversed list).
[Read More]Rotate n * n matrix by 90 degrees
Posted on February 5, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
#include void main() { int mat1[3][3],ma… Anonymous - Jan 2, 2015#include
void main()
{
int mat1[3][3],mat2[3][3],i ,j;
static int k=0;
printf(“Enter the values for the matrix \n”);
for(i=0;i<3;i++)
{
printf("\n”);
for(j=0;j<3;j++)
{
scanf("%d”,&mat1[i][j]);
}
}
printf(“Printing the given matrix”);
for(i=0;i<3;i++)
{
printf("\n”);
for(j=0;j<3;j++)
{
printf("%d “,mat1[i][j]);
}
}
printf(“Rotating the given matrix by 90 degrees”);
for(i=2;i>=0;–i)
{
// printf("\n”);
for(j=0;j<3;j++)
{
mat2[j][k]=mat1[i][j];
}
k=k+1;
}
printf(“Printing the rotated matrix “);
[Read More]Rotate n * n matrix by 90 degrees
Posted on February 5, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem Rotate the n*n matrix by 90 degrees.
**Another way to ask the same problem **
Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
Example
Example 1 Example 2 INPUT >> OUTPUT | INPUT >> OUTPUT | 4 | 4 | 1 2 3 4 1 1 1 1 | 11 12 13 14 41 31 21 11 | 1 2 3 4 2 2 2 2 | 21 22 23 24 42 32 22 12 | 1 2 3 4 3 3 3 3 | 31 32 33 34 43 33 23 13 | 1 2 3 4 4 4 4 4 | 41 42 43 44 44 34 24 14 Solution Consider the array
[Read More]Reverse a c-style string
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
For example if a user enters a string “kodeknight” then on reversing the string will be “thginkedok“.
The basic approach here is to swap the first half of the string, with the next half.
Method 1 - Iterative using string length
#include<stdio.h> int string\_length(char\*); void reverse(char\*); int main() { char string
100; printf("Enter a string\\n"); gets(string); reverse(string); printf("Reverse of entered string is \\"%s\\".\\n", string); return 0; } void reverse(char \*string) { int length, i; char \*begin, \*end, temp; length = string\_length(string); begin = string; end = string; for ( i = 0 ; i < ( length - 1 ) ; i++ ) end++; // swap the chars till half of the length of the string //begin with the end char and so on for ( i = 0 ; i < length/2 ; i++ ) { temp = \*end; \*end = \*begin; \*begin = temp; begin++; end--; } } int string\_length(char \*ptr) { int len = 0; while( \*(ptr+len) !
[Read More]Check If an Integer's Bit Representation Is a Palindrome
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Question: how can you determine if a positive integer is a palindrome. For example, 5 is a palindrome because 5 = 101. Also, 9 is a palindrome because 9 = 1001.
Solution: an integer is palindrome when its bit representation is the same reading from left to right or from right to left. Thus, in order to know if it is a palindrome or not, we just have to check if the number’s value is still the same when we read the number’s bits backward (right to left).
[Read More]K – Reverse a linked list
Posted on January 2, 2012
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
This is one of the questions asked in Microsoft Interview.
Given a linked list, we need to write a function that reverses the nodes of a linked list ‘k’ at a time and returns modified linked list.
The following are the constraints given:
If the no. of nodes in a link list is not a multiple of k then left-out nodes in the end should remain as it is You have to retain the memory address of the nodes without modifying it i.
[Read More]Reverse a String using bits
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Question: Reverse a string in C using as little additional memory as possible.
Answer: The first solution needs the size of a char and size of two integers, all of which will be allocated from the stack. This solution is the most commonly accepted “good” solution. Here is the code.
Method 1 - Normal Reversal of String
void reverseString(char\* str) { int i, j; char temp; i\=j\=temp\=0; j\=strlen(str)\-1; for (i\=0; i<j; i++, j\-\-) { temp\=str
i; str
i\=str
j; str
j\=temp; } } Method 2 - Using xor to swap 2 characters
[Read More]How to reverse a stack in place ?
Posted on December 20, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Reverse a stack, using just push(), pop(), top() operations, in its place itself.
You can not assign any known memory address.
Solution:
Simple methodology for this problem is, take last element from the stack i.e. you need to empty the stack [do it recursively, keeping other elements in memory].
Push the last element in the stack again.
Now while pushing each of earlier elements, first empty whole stack and then push them.
[Read More]Reverse the words in a sentence in place
Posted on September 19, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Given a sentence you have to reverse it word by word.
Example
That is, given a sentence like this :
I am a good boy
The in place reverse would be:
boy good a am I
Solutions Method1 - Reverse the sentence first and then words again
First reverse the whole string and then individually reverse the words
I am a good boy
<————->
yob doog a ma I
[Read More]