1)Given an unsorted list of repeated elements in an array, Find the element with maximum frequency.
Solution:
2) Given a string containing characters and brackets, find if the brackets are paired in the string.
Solution:
3) Given a set of integers, find the third maximum sum of two elements from the set.
Solution:
There are two approaches for this:
1)Naive Approach: Need two loop,outer-inner and outer loop will pick element and will traverse and inner loop will just count the duplicate.
Time Complexity: o(n^2)
2)Better Approach:
Time Complexity: o(n) and o(k) for space where k=size;
/*
* @author Abhinaw.Tripathi
*
*/
public class MaxRepeatingApp
{
public static void main(String[] args)
{
int arr[] = {2, 3, 3, 5, 3, 4, 1, 7};
int n = arr.length;
int k=8;
System.out.println("Maximum repeating element is: " +maxRepeating(arr,n,k));
}
public static int maxRepeating(int[] arr,int n,int k)
{
for(int i=0;i<n;i++)
arr[(arr[i])%k] +=k;
int max=arr[0],result=0;
for(int i=0;i<n;i++)
{
if(arr[i] > max)
{
max=arr[i];
result=i;
}
}
return result;
}
}
Result: Maximum repeating element is: 3
Solution:
public static boolean pairedNotpaired(String str)
{
Stack stack=new Stack();
boolean result=true;
for(int i=0;i<str.length();i++)
{
char c=str.charAt(i);
switch (c)
{
case ')':
if((Character)stack.pop()!=null)
{
return false;
}
case '}':
if((Character)stack.pop()!=null)
{
return false;
}
break;
case ']' :
{
if((Character)stack.pop()!=null)
{
return false;
}
}
default:
stack.push(c);
break;
}
}
return result;
}
3) Given a set of integers, find the third maximum sum of two elements from the set.
Solution:
/**
* @author Abhinaw.Tripathi
*
*/
public class ThirdlargestSumApp {
public static int swap(int a, int b)
{
return a;
}
public static void main (String[] args) throws java.lang.Exception
{
int k = 3; //Finding kth largest pair sum in array "a".
int []a = {-2, 3, 4, -1, 5, 7, 8}; //input array
int []b = new int[k]; //Holds the calculated pair sum. Not more than k highest pair-sum arerequired at any moment.
for(int i = 0; i < k; i++)
b[i] = Integer.MIN_VALUE;
for(int i = 0; i < a.length-1; i++)
{
int pair = a[i] + a[i+1];
if(pair > b[0])
{ //Compare with the Min Value i.e. b[0].
b[0] = pair;
System.out.println("All Sum:" +b[0]);
if(b[1] < b[0])
{
b[1] = swap(b[0], b[0]=b[1]); // To satisfy parent(b[0]) <= left_child(b[1]) constraint for MinHeap
}
if(b[2] < b[0])
{
b[2] = swap(b[0], b[0]=b[2]); // To satisfy parent(b[0]) <= right_child(b[1]) constraint for MinHeap
}
}
}
System.out.println( "\n" +"3rd Sum:" +b[0]);
}
}
4)Find middle element efficiently of a Circular Linked List.
Solution:
class LinkedList
{
Node head;
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void printMiddle()
{
Node slow_ptr = head;
Node fast_ptr = head;
if (head != null)
{
while (fast_ptr != null && fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
System.out.println("The middle element is [" +
slow_ptr.data + "] \n");
}
}
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
public void printList()
{
Node tnode = head;
while (tnode != null)
{
System.out.print(tnode.data+"->");
tnode = tnode.next;
}
System.out.println("NULL");
}
public static void main(String [] args)
{
LinkedList llist = new LinkedList();
for (int i=5; i>0; --i)
{
llist.push(i);
llist.printList();
llist.printMiddle();
}
}
}
5) Given a string ,find the longest sub-string with all distinct characters in it.If there are multiple such strings,print them all.
Solution:
/**
*
*/
/**
* @author Abhinaw.Tripathi
*
*/
import java.util.*;
public class UniqueSubStringApp
{
static boolean isValid(int count[],int k)
{
int val = 0;
for (int i=0; i<26; i++)
if (count[i] > 0)
val++;
return (k >= val);
}
static int uniquesubstring(String s,int k)
{
int u=0;
int max=0,max_start=0;
int cur_start=0;
int cur_end=0;
int n=s.length();
int count[]=new int[27];
Arrays.fill(count,0);
for(int i=0;i<n;i++)
{
if(count[s.charAt(i)-'a']==0)
{
u++;
}
count[s.charAt(i)-'a']++;
}
if(u<k)
{
System.out.printf("k is greater than no of characters");
return 0;
}
Arrays.fill(count,0);
count[s.charAt(0)-'a']++;
for(int i=1;i<n;i++)
{
count[s.charAt(i)-'a']++;
cur_end++;
while(!isValid(count,k))
{
count[s.charAt(cur_start)-'a']--;
cur_start++;
}
if(cur_end-cur_start+1>max)
{
max=cur_end-cur_start+1;
max_start=cur_start;
}
}
System.out.println("Max substring "+s.substring(max_start,cur_end+1));
System.out.println("length "+max);
return 0;
}
public static void main (String[] args) throws java.lang.Exception
{
String s="aabacbebebe";
int k=3;
uniquesubstring(s,3);
}
}
No comments:
Post a Comment