Permutations of a string

Posted by

0

Lets take this old question and discuss a very elegant solution to it.

For a string “ABC”, we have these permutations : “ABC,ACB,BAC,BCA,CAB,CBA”
First, lets look at this elegant code below and try to find out how it works.

public class Permutations {

	public static void permute(String s){
		permute("",s);
	}
	private static void permute(String prefix, String s){
                System.out.println(prefix + "---"+ s);
		int n=s.length();
		if (n==0)
			System.out.println("-------------------------------"+prefix);
		else
		{
			for(int i=0;i<n;i++){
				permute(prefix + s.charAt(i), s.substring(0,i) + s.substring(i+1,n));
			}
		}
		
	}
	public static void main(String[] args) {
		// 
		permute("ABC");
	}
}

Note that line :
System.out.println(prefix + “—“+ s);
is just to debug this.
The output is very interesting.
private method permute is called with (“”,”ABC”) first time.
---ABC
A---BC
AB---C
ABC---
-------------------------------ABC
AC---B
ACB---
-------------------------------ACB
B---AC
BA---C
BAC---
-------------------------------BAC
BC---A
BCA---
-------------------------------BCA
C---AB
CA---B
CAB---
-------------------------------CAB
CB---A
CBA---
-------------------------------CBA
This is a good example of how recursion simplifies things.

Reverse Linked Lists – phew!

Posted by

2

I am not really a fan of this question but it seems to be quite a favorite question during technical interview. So, lets discuss reversing a linked-list problem at length.
Basically there are two methods of reversing a linked list – iterative and recursive. Lets discuss the iterative method :
Logic: Iterate trough the linked list. In loop, change next to prev, prev to current and current to next.

     
private static void reverseIterative()
        {
                Node prev=null;
                Node current= head;
                Node next=null;
                while(current != null)
                {
                        next = current.next;
                        current.next = prev;
                        prev = current;
                        current = next;
                }
                head = prev;
        }

This is simple and has the following complexity :
Time Complexity: O(n)
Space Complexity: O(1)

The recursive method needs a bit of thinking – lets visualize our problem first.

The logic looks like this :
1) Divide the list in two parts – first node and rest of the linked list.
2) Call reverse for the rest of the linked list.
3) Link rest to first.
4) Fix head pointer

Reverse a Linked List in groups of given size

Posted by

0

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

Example:
Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3
Output: 3->2->1->6->5->4->8->7->NULL.

Inputs: 1->2->3->4->5->6->7->80->NULL and k = 5
Output: 5->4->3->2->1->8->7->6->NULL.

Algorithm: reverse(head, k)
1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev.
2) head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
3) return prev /* prev becomes the new head of the list (see the diagrams of iterative method of this post) */

class ReverseKLL
{
        static class Node
        {
                int data;
                Node next;
                Node(int data)
                {
                        this.data = data;
                        next =null;
                }
        }
        public static Node head = null; //Create head node
        //Recursive Reversal of a group of k elements
        //1. Reverse the first sub-list of k element and keep track of next and previous nodes
        //2. head.next = reverse(next,k ) - recursively call this function on sub-groups
        //3. return prev  - prev becomes new next
        private static Node reverse(Node node, int k)
        {
                Node current = node;
                Node next= node, prev=null;
                int count = 0;
                //reverse first k elements
                while(current != null && count < k)
                {
                        next = current.next;
                        current.next = prev;
                        prev = current;
                        current=next;
                        count ++;
                }
                //next is now pointer to k+1th node. Recursively call reverse
                //for the list starting from that point 
                if (next!=null)
                {
                        node.next = reverse(next,k);
                }
                //prev is the new head
                return prev;
        }
        //utility methods
        //push a node in the ll
        private static void push(int data)
        {
                Node newnode= new Node(data);
                newnode.next = head;
                head = newnode;

        }
        public static void printList(Node node)
        {
                while (node != null)
                {
                        System.out.println(node.data);
                        node = node.next;
                }
        }
        public static void main(String args[])
        {
               ReverseKLL kll = new ReverseKLL();
               kll.push(8);
               kll.push(7);
               kll.push(6);
               kll.push(5);
               kll.push(4);
               kll.push(3);
               kll.push(2);
               kll.push(1);

               kll.printList(head);
               head=kll.reverse(head, 3);
               System.out.println("===========================");
               kll.printList(head);

        }
}

Intersection of two Arrays

Posted by

2

Very simple algorithm but somehow interviewers love this. So, here it is:
For example, if the input arrays are:
arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Then your program should print Intersection as {3, 5}.

Algorithm:
For Intersection of two arrays, print the element only if the element is present in both arrays.
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then increment i.
3) If arr1[i] is greater than arr2[j] then increment j.
4) If both are same then print any of them and increment both i and j.

Code:

a1 = [1,3,4,5,7]
a2 = [2,3,5,6]
i,j = 0,0

#Get length of the larger array as the count
count = (max(len(a1), len(a2))) 

for x in range(0,count):
        if (a1[i]  a2[j]):
                j = j+1
        elif (a1[i] == a2[j]):
                print a1[i]
                i = i+1
                j = j+1

Group all anagrams

Posted by

0

Given a set of words in a dictionary, write a program to group all words which are anagrams of each other in to sets.
input: “bat”, “tar”, “xyz” , “tab”, “tar”           output:[[“bat”, tab”], [“tar”, rat”],”xyz” ]

The simpler logic would be to :

  1. Use some sort of a hash structure
  2. Sort all words alphabetically and use the sorted word as the key
  3. If the key is found, keep on adding the original word to the ‘value’ list of strings

Continue reading →