sivapraneethalli
BAN USERI think the best solution is to load dictionary words in a Trie and iterate through characters and check if any words start with this character and so on. the Time complexity would be O(NS), N being length of char array and S being average length of a string
- sivapraneethalli December 05, 2016There exists a O(NM) solution. N is size of list and M is average size of each string in list.
M exist here because we need to reverse string and check if its palindrome. Here is my solution:
public class PalindromeConcatenation {
private static Set<String> buildSet(ArrayList<String> listOfWords){
return new HashSet<>(listOfWords);
}
public static void findPalindromes(ArrayList<String> listOfWords){
//for ex: a string "shiva" store "avihs" , "vihs" and "avih" are potential strings
//than can be present in the list can be concatenated to form palindrome
boolean flag=false;
Set<String> hashSet=buildSet(listOfWords);
for(String i:listOfWords){
String reverse= new StringBuilder(i).reverse().toString();
if(hashSet.contains(reverse)){
flag=true;
System.out.println(i+" and "+reverse+" are palindromes");
}
String reverseWithoutFirstChar=reverse.substring(1);
if(hashSet.contains(reverseWithoutFirstChar)){
flag=true;
System.out.println(i+" and "+reverseWithoutFirstChar+" are palindromes");
}
String reverseWithoutLastChar=reverse.substring(0,reverse.length()-1);
//System.out.println(reverseWithoutLastChar);
if(hashSet.contains(reverseWithoutLastChar)){
flag=true;
System.out.println(i+" and "+reverseWithoutLastChar+" are palindromes");
}
}
if(!flag){
System.out.println("No strings that can be concatenated to form a palindrome are present");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<String> listOfWords=new ArrayList<>();
listOfWords.add("shiva");
listOfWords.add("and");
listOfWords.add("are");
listOfWords.add("vihs");
listOfWords.add("avihs");
findPalindromes(listOfWords);
}
}
- sivapraneethalli November 24, 2016Time Complexity is O(N) where N is number of elements in Binary tree. If it is a BST then time complexity can be reduced to O(log n)
Note: **This code won't work if Nodes in binary tree were to have 2 or more digit number**
public class TargetNumber {
public static Node findStartNode(int num,Node root){
if(root!=null){
if(root.data==num){
return root;
}else{
Node left=findStartNode(num,root.left);
Node right=findStartNode(num, root.right);
return (left!=null) ? left : right;
}
}else{
return null;
}
}
public static boolean path(Node root,String num){
//find the start node. for ex "47" find node where 4 exists
int startNum=Character.getNumericValue(num.charAt(0));
Node start=findStartNode(startNum, root);
//return false if no node exists with startNum
for(int i=1;i<num.length();i++){
if(start!=null){
if(start.left!=null && start.left.data==Character.getNumericValue(num.charAt(i))){
start=start.left;
}else if (start.right!=null && start.right.data==Character.getNumericValue(num.charAt(i))){
start=start.right;
}else{
start=null;
}
}else{
return false;
}
}
return (start==null) ? false : true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//this method returns
Node root=new Node(3);
root.left=new Node(4);
root.right=new Node(5);
root.left.left=new Node(6);
root.left.right=new Node(7);
root.right.left=new Node(8);
root.right.right=new Node(9);
if(path(root, "10")){
System.out.println("True");
}else{
System.out.println("False");
}
}
}
- sivapraneethalli November 22, 2016using backtracking and recursion we can do this with simple code.Time complexity is 2^(total quantity of coins), in this case it is 12
public class CoinChangeQuantityGiven {
public static void generateSums(int[] coins,int[] quantity,int i,int sum,Set<Integer> set){
if(i==coins.length){
set.add(sum);
return;
}
if(quantity[i]==0){
set.add(sum);
generateSums(coins, quantity, i+1, sum,set);
}else{
set.add(sum);
quantity[i]=quantity[i]-1;
generateSums(coins, quantity, i, sum+coins[i],set);
//backtrack. now increase the quantity since we havent used the ith coin and moving to next coin
quantity[i]=quantity[i]+1;
generateSums(coins, quantity, i+1, sum, set);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] coins={10,50,100,500};
int[] quantity={5,3,2,2};
Set<Integer> set=new HashSet<>();
generateSums(coins, quantity, 0, 0,set);
System.out.println(set);
}
}
- sivapraneethalli November 21, 2016Overall time complexity is O(Log n)
public class NumberOfOccuranceOfn {
public static int first(int[] arr,int start,int last,int num){
int mid;
int foundAt=-1;
while(start<=last){
mid=(last+start)/2;
if(arr[mid]>num){
last=mid-1;;
}else if(arr[mid]<num){
start=mid+1;
}
//when found number, now we need to find the first occurrence of that repeated number
else{
foundAt=mid;
last=mid-1;
}
}
return foundAt;
}
public static int last(int[] arr,int start,int last,int num){
int mid;
int foundAt=-1;
while(start<=last){
mid=(last+start)/2;
if(arr[mid]>num){
last=mid-1;;
}else if(arr[mid]<num){
start=mid+1;
}
//when found number, now we need to find the first occurrence of that repeated number
else{
foundAt=mid;
start=mid+1;
}
}
return foundAt;
}
public static int NoOfOccurances(int[] arr,int num){
int start=first(arr, 0, arr.length-1, num);
int end=last(arr, 0, arr.length-1, num);
return end-start+1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={9,9,9,9,9,9};
System.out.println(NoOfOccurances(arr, 9));
}
}
- sivapraneethalli November 13, 2016Store all the words in Trie data structure. Trie structure is
class Trie{
HashMap<Character,Trie> book;
int pageNum;
Trie(int pageNum){
book=new HashMap<>();
this.pageNum=pageNum;
}
}
or store each page in a trie. start from the page 1 and insert words into trie, if a repeated word exists we already have the page number of the same word which occurred first. Time complexit is (w1.length+w2.length)
import java.util.*;
public class RootToLeafPath {
public static void path(Node root,ArrayList<String> pathList,String builder){
if(root.left==null && root.right==null){
pathList.add(builder+root.data);
}else{
String s= root.data+"->";
if(root.left!=null){
path(root.left, pathList,builder+s);
}
if(root.right!=null){
path(root.right, pathList, builder+s );
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Insert obj=new Insert();
Node root=obj.getSampleRoot();
ArrayList<String> pathList=new ArrayList<>();
path(root, pathList, "");
for(String path:pathList){
System.out.println(path);
}
}
}
- sivapraneethalli October 31, 2016Little trick is we don't have to track each person. we just need to count no of person present in room at any point of time.
package smapleQuestionsAlgorithms;
import java.util.Arrays;
public class FacebookQuestion {
public static int hoursWatched(int[] in,int[] out){
int count=0;
int i=0,j=0;
int watchedHours=0;
for(int h=0;h<=24;h++){
while( i<in.length && in[i]==h ){
i++;
count++;
}
while(j<out.length && out[j]==h ){
j++;
count--;
}
if(count>0){
watchedHours++;
}
}
return watchedHours;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] in={1,6,2,7,10};
int[] out={4,8,4,9,15};
Arrays.sort(in);
Arrays.sort(out);
System.out.println(hoursWatched(in, out));
}
}
package smapleQuestionsAlgorithms;
public class FirstNonRepeating {
public static char firstNonRepeating(int[] arr, String s){
for(int i=0;i<s.length();i++){
int index=(int)s.charAt(i);
if(arr[index]==0){
arr[index]=i;//we are encountering character for first time
}else{
arr[index]=-1;//means char is repeated.
}
}
int min=Integer.MAX_VALUE;
char first = ' ';
for(int i=0;i<arr.length;i++){
if(arr[i]<min && arr[i]>0){
min=arr[i];
first=(char) i;
}
}
return first;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr=new int[128];//lets assume string is 128 ASCII char set
System.out.println(firstNonRepeating(arr, "abcdefedcab"));
}
}
Apologise for duplicate submission.
- sivapraneethalli October 26, 2016Here is the solution. Please let me know if there is any mistake.
import java.util.HashSet;
import java.util.Set;
public class GoogleInterviewQuestion {
//swap positions. used for makeSentence() function
public static String swapStringIndexes(String s, int i, int j){
char[] arr=s.toCharArray();
char dummy=arr[i];
arr[i]=arr[j];
arr[j]=dummy;
return new String(arr);
}
//Generates permutations of string and returns a string if it is found in dictionary or return ""
public static String wordExists(String s,Set<String> dictionary,int i,int j){
if(i==j){
if(dictionary.contains(s)){
return s;
}
}else{
for(int k=i;k<j;k++){
String found=wordExists(swapStringIndexes(s, i, k),dictionary,i+1,j);
if(dictionary.contains(found)){
return found;
}
}
}
return "";
}
//return sentence if can be formed with the given string or return ""
public static String makeSentence(String s,Set<String> dictionary,String sentenceBuilder){
if(s.isEmpty()){
return sentenceBuilder; //sentenceBuilder;
}else{
for(int i=1;i<=s.length();i++){
String first=s.substring(0,i);
String second=s.substring(i);
String foundWord=wordExists(first, dictionary, 0, i);
if(!foundWord.isEmpty()){
String sentence=makeSentence(second, dictionary, sentenceBuilder+foundWord+" ");
if(!sentence.isEmpty()){
return sentence;
}
}
}
}
return "";
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Set<String> dictionary=new HashSet<>();
dictionary.add("hello");
dictionary.add("he");
dictionary.add("to");
dictionary.add("the");
dictionary.add("world");
System.out.println(makeSentence("elhloothtedrowl", dictionary,""));
}
}
Just want to solve using high level wait() and notify()
- sivapraneethalli December 26, 2017