Dart replacing the node in the abstract syntax tree

Here is the solution for that.

import 'package:analyzer/analyzer.dart';
import 'package:analyzer/dart/ast/token.dart';
import 'package:analyzer/src/dart/ast/token.dart';

String src = """
void main(){
String a ="hey";
String b ="there"; 
print(\$a);
}
""";

AstNode ast;

main() async {

  ast = parseCompilationUnit(src, parseFunctionBodies: true);
  print(ast.toString());
  Visitor v = new Visitor();
  ast.visitChildren(v);
  print(ast.toString());
}    

class Visitor extends SimpleAstVisitor {
  @override
  visitFunctionDeclaration(FunctionDeclaration node) {
    for (var cn in node.childEntities) {
      if (cn.runtimeType.toString() == "FunctionExpressionImpl") {
        Visitor v = new Visitor();
        cn.visitChildren(v);
      }
    }
  }

  @override
  visitBlockFunctionBody(BlockFunctionBody node) {
    Visitor v = new Visitor();
    node.visitChildren(v);
 }

  @override
   visitBlock(Block node) {
     for (var cn in node.childEntities) {
       if (cn.runtimeType.toString() == "ExpressionStatementImpl") {
         Visitor v = new Visitor();
         cn.visitChildren(v);
       }
     }
   }

  @override
  visitMethodInvocation(MethodInvocation node) {
  String result = "print(\$a\$b)";
  Token resultToken =
    new StringToken(TokenType.STRING, result, node.beginToken.offset);
  AstNode replacement = new SimpleStringLiteral(resultToken, result);
  node.parent.accept(new NodeReplacer(node, replacement));
 }
}

Read More

Dart Programming

Hey guys i am providing the solutions for the some of the problems that i have faced and worked on while exploring the dart programming language

Post 1

How to change dart code using dart analyser. (Abstract Syntax Tree)

Solution
You can find the solution for this here.

Read More

Compare two linked lists

Linked list Interview Question

Compare two linked lists

You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. The lists are equal only if they have the same number of nodes and corresponding nodes contain the same data. Either head pointer given may be null meaning that the corresponding list is empty.

Input Format

You have to complete the int CompareLists(Node* headA, Node* headB) method which takes two arguments - the heads of the two linked lists to compare. You should NOT read any input from stdin/console.

Output Format
Compare the two linked lists and return 1 if the lists are equal. Otherwise, return 0. Do NOT print anything to stdout/console.

Sample Input

NULL, 1 --> NULL
1 --> 2 --> NULL, 1 --> 2 --> NULL

Sample Output

0
1
Explanation 
1. We compare an empty list with a list containing 1. They don't match, hence return 0. 
2. We have 2 similar lists. Hence return 1.

int CompareLists(Node *headA, Node* headB)
{
    int flag=0;
  // This is a "method-only" submission. 
  // You only need to complete this method 
    while(headA!=NULL)
        {
        if(headA->data==headB->data)
            {
            flag=1;
        }
        else
            {
            flag=0;
            break;
        }
        headA=headA->next;
        headB=headB->next;
    }
    if(headB!=NULL)
        {
        flag=0;
    }
    return flag;
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Intersection in a given linked list

Linked list Interview Question

Intersection in a given linked list

Given pointers to the head nodes of linked lists that merge together at some point, find the Node where the two lists merge. It is guaranteed that the two head Nodes will be different, and neither will be NULL.
In the diagram below, the two lists converge at Node x:

[List #1] a--->b--->c
                     \
                      x--->y--->z--->NULL
                     /
     [List #2] p--->q

Complete the int FindMergeNode(Node* headA, Node* headB) method so that it finds and returns the data value of the Node where the two lists merge.
Input Format
The FindMergeNode(Node*,Node*) method has two parameters, and , which are the non-null head Nodes of two separate linked lists that are guaranteed to converge.
Do not read any input from stdin/console.
Output Format
Each Node has a data field containing an integer; return the integer data for the Node where the two lists converge. Do not write any output to stdout/console.
Sample Input
The diagrams below are graphical representations of the lists that input Nodes and are connected to. Recall that this is a method-only challenge; the method only has initial visibility to those Nodes and must explore the rest of the Nodes using some algorithm of your own design.

Test Case 0

 1
  \
   2--->3--->NULL
  /
 1
Test Case 1

1--->2
      \
       3--->Null
      /
     1
Sample Output

2
3
Explanation

Test Case 0: As demonstrated in the diagram above, the merge Node's data field contains the integer  (so our method should return ). 

Test Case 1: As demonstrated in the diagram above, the merge Node's data field contains the integer  (so our method should return ).


int FindMergeNode(Node *headA, Node *headB)
{
    // Complete this function
    // Do not write the main method.
    int a=0,b=0;
    struct Node* temp = headA;
    while(temp)
        {
        a++;
        temp=temp->next;
    }

    temp = headB;
    while(temp)
        {
        b++;
        
        temp=temp->next;
    }
   
    if(a>b)
        {
        a-=b;
        while(a)
            {
            headA=headA->next;
            a--;
        }
        while(headA==headB)
            {
            headA=headA->next;
             headB=headB->next;
        }
        return headA->data;
    }
    else
        {
        a=b-a;
        while(a!=0)
            {
            
            headB=headB->next;
            a--;
           
        }
        while(!(headA == headB))
            {
           
             headA=headA->next;
             headB=headB->next;
        }
             return headA->data;

    }
    return 0;
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Reverse of a given linked list

linked list Interview Question

Reverse of a given linked list

You’re given the pointer to the head node of a linked list. Change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty.

Input Format
You have to complete the Node* Reverse(Node* head) method which takes one argument - the head of the linked list. You should NOT read any input from stdin/console.
Output Format
Change the next pointers of the nodes that their order is reversed and return the head of the reversed linked list. Do NOT print anything to stdout/console.
Sample Input
NULL
2 --> 3 --> NULL

Sample Output
NULL
3 --> 2 --> NULL

Node* Reverse(Node *head)
{
  // Complete this method
    struct Node* prev = NULL;
    struct Node* next = NULL;
    while(head!=NULL)
        {
        next = head->next;
        head->next=prev;
        prev=head;
        head=next;
    }
    head=prev;
    return head;
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Insert Node at nth position in a linked list

linked list Interview Question

Insert Node at nth position in a linked list

You’re given the pointer to the head node of a linked list, an integer to add to the list & the position at which the integer must be inserted. Create a new node with the given integer, insert this node at the desired position and return the head node. A position of zero indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is empty.

Input Format

You have to complete the Node Insert(Node* head, int data, int position) method which takes three arguments the head of the linked list, the integer to insert and the position at which the integer must be inserted. You should NOT read any input from stdin/console. position will always be between 0 and the number of the elements in the list.

Output Format
Insert the new node at the desired position and return the head of the updated linked list. Do NOT print anything to stdout/console.
Sample Input
NULL, data = 3, position = 0
3 --> NULL, data = 4, position = 0
Sample Output

3 --> NULL
4 --> 3 --> NULL
Explanation

1. we have an empty list and position 0. 3 becomes head.
2. 4 is added to position 0, hence 4 becomes head.

Node* InsertNth(Node *head, int data, int position)
{
  // Complete this method only
  // Do not write main function. 
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node*));
    newnode->data=data;
    newnode->next=NULL;
    struct Node*  ptr = head; 
    if(ptr==NULL)
        {
        head = newnode;
        return head;
    }
    else if(position==0)
        {
        newnode->next=head;
        head=newnode;
        return head;
    }
    else
        {
        while(position>1)
        {   
            ptr=ptr->next;
            position--;
        }
        if(ptr->next==NULL)
        {
            ptr>next=newnode;
        }
        else
        {
            newnode>next=ptr->next;
            ptr->next=newnode;
        }
        return head;
    }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

linked list Interview Question

Hey guys i am providing the solution to the most comman linked list question asked in interview as linked list is most important data structure from interview point of view.All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 1
Print the nodes of the given linked list?

Solution
click here to find the solution

Question 2
Insert the nodes at the given position in linked list?

Solution
click here to find the solution

Question 3
Find the intersection in a given linked list?

Solution
click here to find the solution

Question 4
Reverse a linked list?

Solution
click here to find the solution

Question 5
Compare two linked list

Solution
click here to find the solution

Read More

How to print the node of the given linked list

Linklist Interview Question

How to print the node of the given linked list

If you're new to linked lists, this is a great exercise for learning about them. Given a pointer to the head node of a linked list, print its elements in order, one element per line. If the head pointer is null (indicating the list is empty), don’t print anything.

Input Format
The void Print(Node* head) method takes the head node of a linked list as a parameter. Each struct Node has a data field (which stores integer data) and a next field (which points to the next element in the list).

Note: Do not read any input from stdin/console. Each test case calls the Print method individually and passes it the head of a list.

Output Format
Print the integer data for each element of the linked list to stdout/console (e.g.: using printf, cout, etc.). There should be one element per line.

Sample Input
This example uses the following two linked lists:
NULL
1->2->3->NULL
and are the two head nodes passed as arguments to Print(Node* head).

Note: In linked list diagrams, -> describes a pointer to the next node in the list.

Sample Output

1
2
3
Explanation

Test Case 0: NULL. An empty list is passed to the method, so nothing is printed.

Test Case 1: 1->2->3->NULL. This is a non-empty list so we loop through each element and printing each element's data field on its own line.

Here i am only providing the main function you have to create the link list first then only you can print its nodes.

/*
  Print elements of a linked list on console 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
void Print(Node *head)
{
  // This is a "method-only" submission. 
  // You only need to complete this method. 
    while(head!=NULL)
        {
        cout<<head->data<<endl;
        head = head->next;
    }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Array Left Rotation

Array Interview Question

Hacker Rank Question

Array Left Rotation

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

A left rotation operation on an array of size shifts each of the array's elements unit to the left. For example, if left rotations are performed on array , then the array would become .
Given an array of integers and a number, , perform left rotations on the array. Then print the updated array as a single line of space-separated integers.
Input Format
The first line contains two space-separated integers denoting the respective values of (the number of integers) and (the number of left rotations you must perform). The second line contains space-separated integers describing the respective elements of the array's initial state.
Constraints
Output Format
Print a single line of space-separated integers denoting the final state of the array after performing left rotations.
Sample Input
5 4
1 2 3 4 5
Sample Output
5 1 2 3 4
Explanation
When we perform left rotations, the array undergoes the following sequence of changes:
Thus, we print the array's final state as a single line of space-separated values, which is 5 1 2 3 4.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) throws IOException{
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String as[]  =br.readLine().split("\\s");
        int n = Integer.parseInt(as[0]);
        int r = Integer.parseInt(as[1]);
        int c;
        String ele[] = br.readLine().split("\\s");
        ArrayList <Integer> arr = new ArrayList <Integer> ();
        for(int i=0;i<n;i++)
            {
             c = Integer.parseInt(ele[i]);
            arr.add(c);
        }
        for(int j=0;j<r;j++)
            {
             c = arr.remove(0);
            arr.add(c);
        }
        ListIterator <Integer> itr = null;
        itr  = arr.listIterator();
        while(itr.hasNext()){
       System.out.print(itr.next()+" ");
        }
    }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Arrays-String interview question 8

Cracking the coding interview

Arrays and String solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 8

Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to O.
Solution: You can find the solution for this problem here.
Solution 1 using java.
In this problem we are setting the elements in the particular column and row to zero if any element in that particular row or column is already zero initially. Here first we have to check which of the elements are initially zero in the matrix and save their row and column number in an array then we write a function to make all the elements of the particular row to zero and another function to make all the elements of the particular column to zero.

• So we have to write 3 functions
• To find the elements that are zero and and note their row and column in which they occur.
• next we have to write the function that make all the element of a particular row zero.
• and last function that make all the elements in the particular column to zero.
• This problem is very unique and easy as well just need a focus mind and little practice to solve this problem.

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int matrix[][]={{1,2,3},{4,5,6},{7,8,0}};
array(matrix);
for(int i=0;i<matrix.length;i++)
  {
   for(int j=0;j<matrix[0].length;j++)
   {
    System.out.print(matrix[i][j]);
   }
   System.out.println("");
  }
 }
 public static void array(int a[][])
 {
  int[] row = new int[a.length];
  int[] col = new int[a[0].length];
  int i=0,j=0;
  for(i=0;i<a.length;i++)
  {
   for(j=0;j<a[0].length;j++)
   {
    if(a[i][j]==0)
    {
     row[i]=1;
     col[j]=1;
    }
   }
  }
  //row nullfy
  for(i=0;i<row.length;i++)
  {
   if(row[i]==1)
   {
    for(j=0;j<a[i].length;j++)
    {
     a[i][j]=0;
    } 
   }
  }
  //column nullfy
  for(i=0;i<col.length;i++)
  {
   if(col[i]==1)
   {
    for(j=0;j<a.length;j++)
    {
     a[j][i]=0;
    } 
   } 
  }
 }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.
Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Arrays-String interview question 7

Cracking the coding interview

Arrays and String solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 7

Rotate Matrix: 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. (an you do this in place?

Solution

You can find the solution for this problem here.
Solution 1 using  java.

This problem is the most asked problem of all.This problem looks easy but it is very tricky to solve as you have to make a general function for the rotation of the matrix. As will all know that matrix can be rotated in either clockwise direction or anti-clockwise direction. Here i have written a function that rotates the matrix in the anti-clockwise direction by 90 degrees.

• Lets see how the rotation is taking place here
• First store the first element of the matrix in the temp variable and then is replaced it with the bottom left element of the matrix.
• Then replace the bottom left element of the matrix with the bottom right element of the matrix.
• Moving on replace the bottom right element of the matrix with the top right element of the matrix.
• Then replace the top right with the value stored in the temp variable.
• Make sure to carefully use the indexing for the row and col of the matrix as the tends to change as the loop runs.
• and also consider the inner matrix rotation while writing the program and for get correct result i suggest that you consider 4x4 matrix as an example.

If we have to talk about the complexity of this function then it is n square as we have to touch ever element twice in the matrix. import java.util.*; import java.lang.*; import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
 public static void main (String[] args) throws java.lang.Exception
 {
  int matrix[][]={{10,11,12,13},{14,15,16,17},{18,19,20,21},{22,23,24,25}};
  //int matrix[][]={{12,13,14},{15,16,17},{18,19,20}};
  array(matrix);
  for(int i=0;i<matrix.length;i++)
  {
   for(int j=0;j<matrix[0].length;j++)
   {
    System.out.print(matrix[i][j]+" ");
   }
   System.out.println("");
  }
 }
 public static void array(int arr[][])
 {
  int n=arr.length;
  for(int i=0;i<arr.length/2;i++)
  {
   int x=n-1-i;
   for(int j=i;j<x;j++)
   {
    int temp = arr[i][j];
    arr[i][j]=arr[n-1-j][i];
    arr[n-1-j][i]=arr[n-1-i][n-1-j];
    arr[n-1-i][n-1-j]=arr[j][n-1-i];
    arr[j][n-1-i]=temp;
   }
  } 
 }

}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Arrays-String interview question 6

Cracking the coding interview

Arrays and String solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 6

String Compression: Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).

Solution
You can find the solution for this problem here.
Solution 1 using java.
This problem is very unique and rarely asked in the interview question but it is always good to learn as much as you can and to prepare for the worst to achieve good things.In this problem you have to remove the repeating characters from the and string and place the number which is equal to the occurrence of that character which in turn reduces the length of the string with keep all the information about the string such as no of times character appearing in the string. But in this process a unique case might occur were the length of the compressed string is larger then the actual string in that case we have to give original strong not the compressed string because our aim is to reduce the length of the string let us understand with an example suppose if a given string is abcdefgh then the compressed sting of this string will be a1b1c1d1e1f1g1h1 as we can see that the length of the compressed string is more then the original string so we have to take care of this case also and write a program that handles this case also.

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
 public static void main (String[] args) throws java.lang.Exception
 {
  // your code goes here
  System.out.println(compress());
 }
 public static String compress()
 {
       String a="aaaaaaaabbbbbbbccccccccccccccccccddddddddddddddeeeeeeeeee";
         int ctr=0;
  StringBuilder b = new StringBuilder(a.length());
  for(int i=0;i=a.length()||a.charAt(i)!=a.charAt(i+1))
   {
    b.append(a.charAt(i));
    b.append(String.valueOf(ctr));
    ctr=0;
   }   
  }
  return b.length()>a.length()?a:b.toString();
 }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Arrays-String interview question 5

Cracking the coding interview

Arrays and String solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 5
There are three types of edits that can be performed on strings: insert a character, replace a character or remove a character; Given two strings, write a function to check if they are one edit (or zero edits) away. EXAMPLE
pale, ple -> true
pale. bake -> false
pale. bale -> true
pales. pale -> true

Here i am providing two solution for this problem one in which i have created separate functions for edit(insert , remove) and replace function, Here one thing is important to see that insert and remove are two side of one coin means to say that insert means that we are just adding one character to the previous sting and remove means that we are just deleting one char from the previous string so we can use only one function by just checking the length of two strings for insert and remove.

if you find this code hard to understand then please start writing your own code and use pen n paper for that so then you can keep track what is your code all about and what it is calculating.

this problem is one of the most asked question in the interviews so try ti understand this thoroughly and try similar problems like it.

Solution

You can find the solution for this problem here.
Solution 1 using  java separate functions.

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
 public static void main (String[] args) throws java.lang.Exception
 {
  System.out.println(oneInsert("apple","apples"));
 }

  public static boolean oneEdit(String a, String b)
 {
  boolean ctr=false;
    for(int i=0;i<a.length();i++){
   if(a.charAt(i)!=b.charAt(i)){
    if(ctr)
     return false;
    ctr=true; 
   }
  }
  return true;
 }
 public static boolean oneInsert(String s1,String s2)
 {
  String a = s1.length()>s2.length()?s1:s2;
  String b = s1.length()>s2.length()?s2:s1;
  for(int i=0,j=0;i<a.length()&&j<b.length();)
  {
   if(a.charAt(i)!=b.charAt(j))
   {
    if(i!=j)
    {
     return false;
    }
    i++; 
   }
   else
   {
    i++;
    j++;
   }
  }
  return true;
 }
}
Solution 2 using  java combined functions.

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
 public static void main (String[] args) throws java.lang.Exception
 {
  System.out.println(oneEdit("banana","banan"));
 }
 public static boolean oneEdit(String s1,String s2)
 {
  String a = s1.length()>s2.length()?s1:s2;
  String b = s1.length()>s2.length()?s2:s1;
  boolean ctr=false;

  for(int i=0,j=0;i<a.length()&&j<b.length();)
  {
   if(a.charAt(i)!=b.charAt(j))
   {
    if(i!=j)
    {
     return false;
    }
    if(ctr)
    {
     return false;
    }
    ctr=true;
    i++;
   }
   i++;
   j++;
  }
 return true;
 }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Arrays-String interview question 4

Cracking the coding interview

Arrays and String solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 4

Given a string, write a function to check if it is a permutation of a palindrome. Palindrome is a word that is the same forwards and backwards. A permutation is a rearrangement of letters. and remember that the palindrome does not need to be limited to just dictionary words there can be many more possible combinations.

EXAMPLE
Input: Tact Coa
Output: True ("taco cat". "atco cta".) means that they are palindrome permutation.
Solution
You can find the solution for this problem here.
Solution 1 using java .

Palindrome is the basic term that all programmers or who want to be become a programmer should know about it. Palindrome are basically those word that have same spelling when checked forward and backward here is the example NITIN is a palindrome means that we can write forward and backward it still be spelled NITIN. Remember this always as you will be facing many problem that have palindrome involved in it in one way or another. You can search more about palindrome and practice many more problems related to palindrome so that you become familiar with palindrome.

if you find this code hard to understand then please start writing your own code and use pen n paper for that so then you can keep track what is your code all about and what it is calculating.

this problem is one of the most asked question in the interviews so try ti understand this thoroughly and try similar problems like it.

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
 public static void main (String[] args) throws java.lang.Exception
 {
  System.out.println(permutation());
 }

  public static boolean permutation()
 {
    String a="tacocat";
    String b="atcocta";
    int count=0;
    int[] arr_a = new int[256];
    int[] arr_b = new int[256];
    if(a.length()!=b.length())
  {
       return false;
    }
  for(int i=0;i<a.length();i++)
    {
       arr_a[(int)(a.charAt(i))]++;
       arr_b[(int)(b.charAt(i))]++;
    }

  for(int i=0;i<a.length();i++)
    {
       if(arr_a[(int)(a.charAt(i))]!=arr_b[(int)(a.charAt(i))])
       {
         return false; 
       }
       if(arr_a[(int)(a.charAt(i))]==1)
       {
          count++; 
       }
    }
    if(count>1)
  {
       return false;
    }
    return true;
 }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Arrays-String interview question 3

Cracking the coding interview

Arrays and String solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 3 from the Cracking the coding interview.

Write a method to replace all spaces in a string with '%20. Assume that the string has sufficient space at the end to hold the additional characters, and that you are given the true length of the string. ( If implementing in Java, you can use a character array so that you can perform this operation in place.) or you can use string builder.

EXAMPLE
Input: "Mr John Smith "J 13
Output: "Mr%20John%20Smith"
Solution
You can find the solution for this problem here.

Solution 1 using java (Worst case Complexity N).

This is very simple problem if we talk about java implementation as java provide us String builder class which dynamically append characters to string.so we just need to check if the char in the original string is a blank space or not. if it is blank space then append the following text in the place of blank space and move on in the iteration. that is the simple logic behind this solution that i have followed.if you find this code hard to understand then please start writing your own code and use pen n paper for that so then you can keep track what is your code all about and what it is calculating.

This problem is one of the most asked question in the interviews so try ti understand this throughly and try similar problems like it.

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
 public static void main (String[] args) throws java.lang.Exception
 {
  String str ="asd fg hj";
    StringBuilder strb = new StringBuilder();
    for(int i=0;i<str.length();i++)
    {
       if(str.charAt(i)==' ')
       {
          strb.append("%20");
       }
       else
       {
          strb.append(str.charAt(i));
       }
    }
    System.out.println(strb);
 }
}

There are many other solution for this problem such as using string instead of string builder but it will consume more memory and you have to write extra line of code.You can traverse from the end of the string and add %20 to the string also.

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future. I wish best of luck to you for your future.

Read More

Arrays-String interview question 2

Cracking the coding interview

Arrays and String solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 2

Given two strings, write a method to decide if one is a permutation of the other. that means that they same number of characters in it but arrangement will be different or we can say that order is different.

Solution

• You can find the solution for this problem here.
• Very simple problem just sort the strings and then compare them.
• Sorting the string means that java will use their ascii value for the comparison process and arrange them in the increasing order and after that you can compare strings to be equal or not.
• As permutation means that you have the same characters in the string but they will be arranged in the different order sorting them will put them in the increasing order of their ascii value.

Remember this trick as it will be very help full in solving these type of questions in the interview but pretend that you have thought about it during the interview otherwise you might have to face more difficult question that you haven't heard of.
If you find this code hard to understand then please start writing your own code and use pen n paper for that so then you can keep track what is your code all about and what it is calculating.
This problem is one of the most asked question in the interviews so try ti understand this throughly and try similar problems like it.
I wish best of luck to you for your future.
Solution 1 using java.

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */

class Ideone
{
  public static void main (String[] args) throws java.lang.Exception
  {
   System.out.println(permutation());
  }
  public static boolean permutation()
 {
    String str ="asdfghj";
    String str1 = "jhgndsa";
        char[] str2 = str.toCharArray();
        char[] str3 = str1.toCharArray();
    Arrays.sort(str2);
    Arrays.sort(str3);
       str = new String(str2);
       str1 = new String(str3);
       return str.equals(str1);
 }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Arrays-String interview question 1

Cracking the coding interview

Arrays and String question solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 1

Implement an algorithm to determine if a string has all unique characters.Think what you can do if you cannot use additional data structures? means that all the characters in the string must be for one time only.

Solution
You can find the solution for this problem here

Here i am providing solutions for this question using different data structures to give to the knowledge about the them and to let you know that same problem can be solved in many different ways using different approaches that might be helpful to remember in your interviews.

If you find this code hard to understand then please start writing your own code and use pen n paper for that so then you can keep track what is your code all about and what it is calculating.

This problem is one of the most asked question in the interviews so try ti understand this thoroughly and try similar problems like it.

Solution 1 using hash map java (Worst case Complexity N)

This solution provides you the knowledge about using the hash map and functions of the hash map. Hash map is a data structure that has special key value mapping and used in many problems to reduce the complexity of the algorithm.

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
 public static void main (String[] args) throws java.lang.Exception
 {
  // your code goes here
  System.out.println(unique());
 }

  public static boolean unique()
{
  String str ="asdfjgh";
  HashMap < Character,Integer > map = new HashMap < Character,Integer > ();
  for(int i=0;i < str.length();i++)
  {

    if(map.containsKey(str.charAt(i)))
    {
       return false;
    }
    map.put(str.charAt(i),1);
 System.out.println(map.get('a'));
  }
return true;
}
}

Solution 2 using array java(Worst case Complexity N).

This method uses Boolean array to represent all the character and the value of the Boolean if the particular alphabet occurs one time in the string and that how this solution works checks if the particular alphabet has occur twice or not if yes the return false as the answer

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
 public static void main (String[] args) throws java.lang.Exception
 {
  // your code goes here
  System.out.println(unique());
 }

  public static boolean unique()
 {
    String str ="asdfghj";
    boolean arr[] = new boolean[256];
    for(int i=0;i < str.length();i++)
    {
      if(arr[i])
      {
          return false;
      }
      arr[i]=true;
    }
  return true;
 }

}

Solution 3 using array java(Worst case Complexity N2).

This is a simple iteration method that checks every alphabet with all the alphabet in the string to check if they match or not. If they matches then string is not unique.

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
 public static void main (String[] args) throws java.lang.Exception
 {
  // your code goes here
  System.out.println(unique());
 }

 public static boolean unique()
 {
    String str ="asdfghj";
    for(int i=0;i < str.length();i++)
    {
      char c = str.charAt(i);
      for(int j=i+1;j < str.length();j++)
      { 
          if(c==str.charAt(j))
          {
             return false;
          } 
      }
    }
    return true;
 }

}

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.

Read More

Arrays-String interview question solution

Cracking the coding interview

Arrays and String question solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding

Question 1

Implement an algorithm to determine if a string has all unique characters.Think what you can do if you cannot use additional data structures? means that all the characters in the string must be for one time only.

Solution
You can find the solution for this problem here.

Question 2

Given two strings, write a method to decide if one is a permutation of the other. that means that they same number of characters in it but arrangement will be different or we can say that order is different.

Solution
You can find the solution for this problem here.

Very simple problem just sort the strings and then compare them.

Solution 1 using java.

Question 3 from the Cracking the coding interview.

Write a method to replace all spaces in a string with '%20. Assume that the string has sufficient space at the end to hold the additional characters, and that you are given the true length of the string. ( If implementing in Java, you can use a character array so that you can perform this operation in place.) or you can use string builder.

EXAMPLE
Input: "Mr John Smith "J 13
Output: "Mr%20John%20Smith"

Solution
You can find the solution for this problem here.
Solution 1 using java click the following link to get the solution for this problem.

Question 4

Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

EXAMPLE
Input: Tact Coa
Output: True (permutations: "taco cat". "atco cta". etc.)

Solution

You can find the solution for this problem here.

Solution 1 using java .

Question 5

One Away: There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

EXAMPLE pale, ple -> true
pales. pale -> true
pale. bale -> true
pale. bake -> false

Solution
You can find the solution for this problem here.
Solution 1 using java separate functions.
Solution 2 using java combined functions.

Question 6

String Compression: Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).

Solution
You can find the solution for this problem here.
Solution 1 using java.

Question 7

Rotate Matrix: 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. (an you do this in place?)

Solution
You can find the solution for this problem here.
Solution 1 using java.

Question 8

Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to O.

Solution
You can find the solution for this problem here.
Solution 1 using java.

Question 9

String Rotation: Assume you have a method isSubstring which checks if one word is a sub string of another. Given two strings, S1 and S2, write code to check if S2 is a rotation of S1 using only one call to isSubstring (e.g., "waterbottle" is a rotation of"erbottlewat").

Solution
You can find the solution for this problem here.
Concatinate s1 with s1 and then use isSubstring function for the result.

Read More