Harsh Bhardwaj
BAN USER- 0of 0 votes
Answersfind the isomorphic pairs of string !!
- Harsh Bhardwaj in India
a string is said to be isomorphic if its each alphabets can be replaced by another alphabet
for ex "abca" and "zxyz" are isomorphic but "abca" and "pqrs" is not isomorphic
conditions :
1 - A character can be replaced by itself. for ex "abcd" and "pbfg" are isomorphic .
2- No two characters can be replaced by same character . for ex "abcd" and "bbcd" are not isomorphic .| Report Duplicate | Flag | PURGE
AppPerfect Software Engineer Algorithm - 0of 0 votes
AnswersFind the longest cycle in a graph ?
- Harsh Bhardwaj in United States| Report Duplicate | Flag | PURGE
Algorithm
please improve my answer if i missed anything or stated something wrong
So a ticket booking system
ticket booking applications use a an Api for manage data of seat booked/free, show timing etc in real time and always sync with the databases the Theaters are using.
so when ever a user booked a ticket for a specific theater from an app , the information is updated to the theaters db and the same case happen when any user booked tickets physically through theaters, this is how you can see seats marked booked or free
using users location, app can recommend nearby theaters to the user on the basis of the movie he wants to see and where seats are available we can use treemap here to sort acc to the tickets available .
Both Sql and No-sql will be used , No sql will used to store information about theater like PVR/INOX , facility available , Movies running in theaters and other similar tags
also the db would be like { "userID" :"155366",{"theaterID":"67q4q99","MovieId":"63geud3","TicketId":{ "SeatNUM":[ 143,172,183,273.... ] } }}
To maintain concurrency , SQL transaction db could used , when users book the tickets on the same time period , apps allow them to complete the payment within a time counter, followed by the steps in transactional db, the user that complete the process first would get the tickets, there are also some waiting queue sort of concept
The dp approach to find the length of subset whose sum is equals to the given sum
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
{
TreeMap<Integer,Integer> tmap=new TreeMap<Integer,Integer>();
int k=6;
void calSum(int b,int e,int a[]){
int tempSum=0;
for(int i=b;i<=e;i++){
tempSum=tempSum+a[i];
}
if(tempSum==k){
tmap.put(e-b+1,e-b+1);
}
}
int function(int beg,int end ,int arr[]){
if(beg<=end){
calSum(beg,end,arr);
function(beg+1,end-1,arr);
function(beg+1,end,arr);
function(beg,end-1,arr);}
else{
return 0;
}
return 0;
}
void seeResult(){
System.out.println(tmap.lastKey().toString());
}
public static void main (String[] args) throws java.lang.Exception
{
int array[]={-2,1,-3,4,-1,2,1,-5,4};
Ideone id=new Ideone();
id.function(0,array.length-1,array);
id.seeResult();
}
}
using dp approach
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
{
TreeMap<Integer,Integer> tmap=new TreeMap<Integer,Integer>();
void calSum(int b,int e,int a[]){
int tempSum=0;
for(int i=b;i<=e;i++){
tempSum=tempSum+a[i];
}
tmap.put(tempSum,tempSum);
}
int function(int beg,int end ,int arr[]){
if(beg<=end){
calSum(beg,end,arr);
function(beg+1,end-1,arr);
function(beg+1,end,arr);
function(beg,end-1,arr);}
else{
return 0;
}
return 0;
}
void seeResult(){
System.out.println(tmap.lastKey().toString());
}
public static void main (String[] args) throws java.lang.Exception
{
int array[]={-2,1,-3,4,-1,2,1,-5,4};
Ideone id=new Ideone();
id.function(0,array.length-1,array);
id.seeResult();
}
}
This could be solved using minimum spanning tree concept
***assume taxi is large enough for all passengers****
Arrange all the pickup locations as vertices of a graph along with the present location of the taxi as
one of the vertex
now start with the present location and add that edge with has lowest weight ,this means we have
visited to the location which is nearby and pic all the passangers, then search for the next nearby location
locations and so on until all the locations are visited once
___QUESTIONS___
Giving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.
eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"
this can be solved in nlogn time complexity with O(n) extra space
step 1-
Insert the string S in Map<C,I> where C is the character present in S and I is its corresponding frequency.
step 2-
now sort the dictionary in decreasing order and check for words in it ....if all the characters present in the word is also present in the S , then S can be converted into that word .
The question is not very clear because it depends upon the initial no. of people in hotel.
- Harsh Bhardwaj February 05, 2017import java.util.*;
import java.io.*;
import java.lang.*;
public class Solution {
boolean function(int a[],int val){
if(a[0]==0){ if(a[1]!=1){val--;}}
if(a[a.length-1]==0){if(a[a.length-2]!=1){val--;}}
int j=a.length;
while(j>0){
if(a[j]==0){if(a[j-1]!=1&&a[j+1]!=1){val--;}}
j--;
}
if(val==0){return true;}
else{return false;}
}
public static void main(String[] args) {
Solution solution=new Solution();
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int array[]=new int[n];
for(int i=0;i<n;i++){
array[i]=sc.nextInt();
}
int person=sc.nextInt();
if(solution.function(array, person)==true){System.out.println("possible");}
else{System.out.println("Not possible");}
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
public class Solution {
Map<Character,Integer> map=new HashMap<Character,Integer>();
Boolean function(String string,int kval){
char array[]=string.toCharArray();
for(int i=0;i<array.length;i++){
if(map.containsKey(array[i])==false){map.put(array[i],1);}
}
if(map.size()==kval){
map.clear();
return true;
}
else{
map.clear();
return false;}
}
Set<String> Hash = new HashSet<String>();
void getSubstring(String strng,int Kval){
if(function(strng, Kval)==true){Hash.add(strng);}
else{
String st1=strng.substring(0,strng.length()-1);
String st2=strng.substring(1,strng.length());
getSubstring(st1, Kval);
getSubstring(st2, Kval);
}
}
void showSet(){
System.out.println(Hash);
}
public static void main(String[] args) {
Solution solution=new Solution();
Scanner sc=new Scanner(System.in);
int k=sc.nextInt();
String st=sc.next();
solution.getSubstring(st, k);
solution.showSet();
}
}
one of the solution could be that !
- Harsh Bhardwaj June 08, 20171- Each application may have different parameters as per requirement in the log file.
2- Each log file have Application_id which is unique for each application .
3- Apart this application id each each log will have LOG_LEVEL, DATE, TIME_STAMP, BODY,
STATUS.
4- Store LOG from each application into the log_distributed system.
5- map each application_name with application_id the system, now we can query to get all the logs with the application _name .
6- We can query all the logs we the given time_stamp. and LOG_LEVEL