azambhrgn
BAN USERThere are two standard version of Fibonacci series -
1) 0,1,1,2,3,5,8....
2) 1,1,2,3,5,8.....
We will use first in our problem.
1- Find max in the array - O(n)
*max number will be used to generate Fibonacci series to the number max. In given example the max is 40.
2- Generate Fibonacci to the number max and store it in hashset/hashmap. in our eg. the fibset will be (0,1,2,3,5,8,13,21,34)
3- Traverse array again if the number is present in hashset/hashmap then add it to the list.
4- Return list
Time complexity - O(n)
public class FibonacciSubset {
private static ArrayList<Integer> findNumbers(int[] ar){
int max = findMax(ar);
ArrayList<Integer> list = new ArrayList<>();
Set<Integer> fibset = fiboNumbers(max);
for(int i=0;i<ar.length;i++){
if(fibset.contains(ar[i])){
list.add(ar[i]);
}
}
return list;
}
private static int findMax(int[] ar) {
int max= ar[0];
for(int i=1;i<ar.length;i++){
max = max > ar[i] ? max : ar[i];
}
return max;
}
private static Set<Integer> fiboNumbers(int max) {
HashSet<Integer> fibset = new HashSet<>();
fibset.add(0);
fibset.add(1);
int f = 0,s =1;
int res = f + s;
while(res < max){
fibset.add(res);
f = s;
s = res;
res = f + s;
}
return fibset;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] ar = {4,2,8,5,20,1,40,13,23};
ArrayList<Integer> list = findNumbers(ar);
for(int i=0;i<list.size();i++){
System.out.print(list.get(i) + " ");
}
}
}
There can be 2 solutions-
1- Sorting and comparing
a- SOrt any two array- O(nlogn)
b- find common of two sorted arrays and insert into the Set O(n)
c- Check for remaing arrays , whther elements of that array is present in the set or not. if yes then it is common element. O(n) for each new array
*set will not be modified after step b.
Time complexity O(nlogn) + O(n) ~= O(nlogn)
2- It can also be dome in O(n) time, by using hashmap and set-
a- Create an hash map of one array and aray element as key of the hashmap - O(n)
b- Traverse second array and check in hashmap for every element, if the key is present in hashmap then insert to the set. O(n)
Now you have set of common elements in 2 arrays.
c- Check for remaing arrays , whther elements of that array is present in the set or not. if yes then it is common element. - O(n) for each new array
*set will not be modified after step b.
Time complexity O(n) or O(k*n) ~= O(n) , where k is number of the arrays
I have written below code and tested for several test cases working fine -
Time complexity =~ O(n)
public static int findMaxSum(int[] ar,int k){
int max = ar[0]; // max inititalize with first element
int l = ar.length; // Length of array
int sum = ar[0]; // sum included ith item
int sum_e = 0; // Excluded ith item
int j = 0; // starting point of k or < k items sum
int i = 1; // index pointer
while(i < l){
if(i-j < k){
sum_e = sum;
sum = sum + ar[i];
//Used temp to find max of sum and sum_e without changing existing value of sum and
// sum_e as these will be needed for next iteration
int temp = sum > sum_e ? sum : sum_e;
max = max > temp ? max : temp;
i++;
}
if(ar[j] < 0 || i-j >= k) {
sum = sum -ar[j];
j++;
max = max > sum ? max : sum;
}
}
return max;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] ar0 = {-5,-10};
int[] ar1 = {-3,10};
int[] ar2 = {3,-10};
int[] ar3 = {-2,5,60,-10,23};
int[] ar4 = {6,2,4,-1,5,9,-2,10};
System.out.println(findMaxSum(ar0, 4));
System.out.println(findMaxSum(ar1, 4));
System.out.println(findMaxSum(ar2, 4));
System.out.println(findMaxSum(ar3, 4));
System.out.println(findMaxSum(ar4, 4));
}
o/p -
-5
10
3
78
22
Thanks
If i understand correctly -
String[] str = {"cat","dog","ogd","act","tca","ofg"}; is given
and the o/p -
dog ogd
cat act tca
ofg
There could be two ways to solve this question-
1- Create an auxilary array of same strings.
2- Sort the words inside the auxaliry array, Hence in our example - auxilary_array after sorting will be like {"act","dog","dog","act","act","fgo"}
3- create a hashmap with <string,Arraylist>, and put auxilary_array values as key and i/p array value as values.
Hence new result hashmap will be like -
act -> cat,act,tca
dog -> dog,ogd
fgo- > ofg
print all the values from hashmap
Problem with this approach are-
1- Extra space for the auxilary array
2- Time complxety will be n*klogk , where n is size of array of string and k is the maximum character word in array
Not a good approach
Second approach -
Why not we create a hashmap of the each words and then compare and add to the map for final result, But the problem is that what will you take as key of map.
words ? Not good , act and cat will be different keys
ASCII addition/multiplication of character in words ? There might be possible cases when you can get same values for different words. Not good
So if we write our own hasvalue function that will provide always unique values for words, but same for the anagrams , Then our problem can be solved.
Here is the way to write such type of hashfunction -
1- Create an array of size equals to unique character in i/p string, and assign a prime number for all chars.
We use english alphabates then there will be 26 char.
public static int[] hash = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101}; // 26 prime numbers
'a' will be mapped with first element of the array and 'z' with last. No uppercase
Below is working code-
//Our hashfunction will be (Similar approcah as Java's hashcode())-
public static int[] hash = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
public static int hashFunction(char[] ar){
int result = 1;
for(int i=0;i<ar.length;i++){
int prime = hash[(int)ar[i]-97]; // 97 because ascii value of a is 97 and index in array is start with 0
result = result*prime;
}
return result;
}
// if you test this function for different anagrams it will give same result . act and cat , will give 710.
public static void findSameANagram(String[] str){
HashMap<Integer, ArrayList<String>> result = new HashMap<>();
for(int i=0;i< str.length;i++){
int key = hashFunction(str[i].toCharArray());
if(result.containsKey(key)){
result.get(key).add(str[i]);
}else {
ArrayList<String> list = new ArrayList<>();
list.add(str[i]);
result.put(key,list);
}
}
//Print result hashmap to get all the results
}
public static void main(String[] args) {
String[] str = {"cat","dog","ogd","act","tca","ofg"};
findSameANagram(str);
}
We need extra space for creation of hash array , But the time complexity will be reduced to O(n*k) ~= O(n)
- azambhrgn May 12, 2017There could be two solution -
1- Using the linear search approach to find the index(say ind) of the point where words array of string stop the lexicographical increasing order.
Time complexity O(n)
2-We can reduce time complexity to the O(logn) time by using the Binary search approach, And I think it is the best solution for your question.
Approach -
Find the pivot point which is lesser in order(in dictionary) from prev string in your words array.
Below is running and tested code in java
public static int findTheRotation(String[] str,int l,int h){
// No rotation point will return -1
if(l > h){
return -1;
}
if(l == h) {
return h;
}
int mid = (l+h)/2;
//The rotation point is found at mid+1
if(mid < h && str[mid].compareTo(str[mid+1]) > 0){
return mid+1;
}
if(l < mid && str[mid-1].compareTo(str[mid]) > 0){
return mid;
}
//if Rotation point lies on left side
if(str[mid].compareTo(str[h]) < 0){
return findTheRotation(str, l, mid-1);
}
//Otherwise will check right array
return findTheRotation(str, mid+1, h);
}
Time complexity for above code is O(logn)
- azambhrgn May 12, 2017We can say , the Adjancy matrix representation of the graph is given , You have to create the tree from given 2D matrix.
I would have some other question as well to the Interviewer such as-
1- Graph is also a kind of tree , Printing a graph is answer? If yes then I will use BFS to print it.
If No.
2- How many child a tree can maximum have ?
Lets say 2
Then i will have to do following things-
1- Find the root Node from the graph, we can get the root by traversing the matrix and put every child in the set . One node must not be part of that set. That will be root.
2- Once we got the root... We can create a node in tree with root value.
3- Start DFS from root node and insert every node one by one.
We have to use DFS here because it will be easy to pass the parent as well with child to the calling function.
Node class for tree
class Node {
int val;
Node left, right;
public Node(int val) {
this.val = val;
}
}
public Node dfs(Node parent, int child, boolean visited[],int[][] G) {
Node temp = new Node(child);
visited[child] = true;
if (parent.left == null) {
parent.left = temp;
}else {
parent.right = temp;
}
int n = G.length;
for(int j=0;j<n;j++)
if(!visited[j] && G[child][j]==1)
dfs(temp,j,visited,G);
return parent ;
}
I will use Inheritance to design furniture shop-
I will create several classes like-
1- Items - Super class of all classes and will have common variable and methods for all items. such as - id,name,price,getprice(),updatePrice,quantity etc. Because these variables and methods will be common for every item.
2- Furniture- This will be the child class of Item class and can also have several child classes, such as-
a- WoodenFurniture
b- SteelFurniture etc.
Furniture class can also have the boolean flag isChildSafe , Because all the furnitures should have inherit the property of furniture class.
Lets come to the future item addition- Lets say Phone, Tablet , Medicines etc.
You can add all these things by creating several new classes and without making any changes in existing system-
3- Electronics - Child class of item and parent class for the Mobile class,Tablet class and other electronics. You can put boolean like isFireSafe ,isWaterSafe etc. in this class Which are applicable for all the child of Electronics class.
4- Medicine - Again child class of Items, and will have some child class if needed.
You can make Items,Furniture,Electronics,Medicine as abstract classes or Interface(Depends on the requirement).
By using this type of design you can expand your system without affecting existing design.
Assuming the list is singly circular linked list, Hence
Node can be inserted
- at beginning of the list O(1), Swap the data from new node and head and correct the next pointer reference
- In middle of the list - O(n), Traverse to the node
- at the end - O(n) ,
- List is empty and New node will be inserted As first node of the list O(1)
If LIst is doubly circular linked list
Node can be inserted
- at beginning of the list O(1),
- In middle of the list - O(n), Traverse to the node,
- at the end - O(1) , Check if new node has greater value then last node , then insert it at beginning and make second node as head, and new node as last pointer
- List is empty and New node will be inserted As first node of the list O(1)
Feel free to correct me.....
Can be solved using the sliding window approach in linear time.
function(int[] ar,int k), initialize sum =0, and two variables i and j;
j is starting index of window
and i is end point of window
1-Run a loop to length of the array-
a- if sum == k , return true
b- else if (sum > k), sum = sum - ar[j], j++ // exclude the first index from window
c- else if (sum < k), sum = sum + ar[i], i++; //include the current index
At this point - i reached to end but if sum > k then Need to run one more loop to check from j to i.
2- while(j > i && sum >= i)
a- if sum ==k , return true
b- sum = sum - ar[j], j++
3- return false
Below is working code-
public static boolean isSum(int[] ar, int k) {
int sum = 0;
int j = 0; // window's starting point
int i = 0; // windows end point
while (i < ar.length) {
if (sum == k) {
return true;
} else if (sum > k) {
sum = sum - ar[j];
j++;
} else if(sum < k){
sum = sum + ar[i];
i++;
}
}
while(j < i && sum >= k){
if(sum == k){
return true;
}
sum = sum - ar[j];
//System.out.println(sum);
j++;
}
return false;
}
TIme complexity =~O(n), and constant space complexity
- azambhrgn May 10, 2017a is the array and k is the given value
1- Sort the array
2- Assign two pointer start=0 and end=a.length-1
3- run loop while start < end
a- if(a[start] + a[end] == k), print pair values at start and end index, start++,end--
b- else if(a[start] + a[end] < k) , start++
c- else if(a[start] + a[end] > k) , end--
Time complexity O(nlogn), The above logic will work with all types of data.
@gator, My Logic is working fine, There is an if condition in second loop , That will add only numbers which are occurring more than 1 to the list. Kindly check again.
I have tested with few test cases.
@All , If you are down voting some answer then better give some explanation as well.
Its O(1),
The nextInt() method calls the "protected int next(int bits)" ,The next method has some predefined mathematical formulas to calculate the next number and then return to nextInt().
To more you can check on Java docs, the code for both the methods are there and it is easy to understand but the formula is little bit tricky.
Thanks,
It can be done by modifying the existing array -
Points to be noted from questions-
1- Element range in the array is 0-n-1, Hence we can use the indexes to get frequency.
2- O(1) extra space and O(n) time complexity
In our approach , we will modify the existing array to get frequency.
eg. a = [1,2,3,2] n = 4
Steps-
1- We will make the changes at index ind = a[i]%n , and will make a[ind] += n . Hence after first iteration our array will become [1,6,11,6]
2- Iterate again to get the repeated elements-
we will check if arr[i]/n > 1 => i is repeating element in the array and i can be added to resultant list, e.g. a[2]/n = 2, Hence 2 is repeating 2 times
public static List<Integer> repeated(int[] a){
ArrayList<Integer> list = new ArrayList<>();
int n = a.length;
for(int i=0;i<n;i++){
int ind = a[i]%n;
a[ind] = a[ind] + n;
}
for(int i=0;i<n;i++){
if(a[i]/n > 1){
list.add(i);
}
}
return list;
}
The question is to print the number in descending order based on frequency(number of occurrence) .
1- Create an hashmap with key as number and value as the occurrence. O(1)
2- Traverse the array, Increase the count(value in hash) if the number is repeated. else put value = 1 if number came first time. O(n)
3- Sort the hashMap based on value and print it. O(nlogn)
Total time complexity O(n) + O(nlogn) => O(nlogn)
1- Compare current and next element in array , if current is greater than next then
a- if the diff between these two numbers is 1 then swap
b- else set boolean flag false and break the loop as it can not be sorted
2- If flag is true then print yes else print no
time complexity - O(n)
for(int i=0; i < a.length -1 ;i++){
if(a[i] > a[i+1] ){
if(a[i] - a[i+1] == 1){
swap(a,i,i+1);
}else {
flag = false;
break;
}
}
}
if(flag){
System.out.println("Yes");
}else{
System.out.println("No");
}
The solution code in java is here -
public class MinimumCoin {
public static int findMin(int[] prfct, int k) {
int[] arr = new int[k + 1];
arr[0] = 0;
for (int i = 1; i < arr.length; i++) {
arr[i] = Integer.MAX_VALUE;
for (int j = 0; j < prfct.length; j++) {
if (prfct[j] <= i) {
int temp = arr[i - prfct[j]] + 1;
arr[i] = arr[i] > temp ? temp : arr[i] ;
}
}
}
return arr[k];
}
public static int[] buildArray(int N) {
int l = (int) Math.sqrt(N);
int[] prfct = new int[l];
//System.out.println(prfct.length);
for(int i=1;i<=l;i++) {
prfct[i-1] = i*i;
}
return prfct;
}
public static void main(String[] args) {
int N = 20;
int[] prfct = buildArray(N); // Build the perfect square array
int output = findMin(prfct, N); // find the minimum using Dynamic programming approach
System.out.println(output);
}
}
Similar to DP problem , Minimum number of coins needed to make a given some.
Here instead of coin you have to take perfect square.
It will be like -
if n = 20
coins = {1,4,9,16}
By using minimum number of above coins you have to make a sum = 20
I will post code in other comment.
The question is similar to minimum number of plateforms needed for the bus/rail station.
My solution for this very specific question is -
A[] = {1,2,10,5,5} // checkin array
D[] = {4,5,12,9,12} // checkout array
sort(A) // {1,2,5,5,10}
sort(D) // {4,5,9,12,12}
count = 1 // first person checked in
int i = 1; // to traverse A
int j = 0; // to traverse D
int max= 0;
int day = A[i];
while(i < n && j < n) {
if(A[i] <= D[j]) {
count++;
i++;
if(count > max) {
max = count ;
day = A[i];
}
} else {
count--;
j++;
}
}
return day;
The time complexity will be O(nlogn).
Explanation is below -
C - checkin
D - checkout
count - number of people at same time in hotel
Day ---- C/D ------ count
1 C 1
2 C 2 // Increase count on checkin
4 D 1 // Decrease count on checkout
5 C 2
5 C 3 // maximum number of people in hotel -- return the day
9 D 2
12 D 1
12 D 0
Taking same example but with 2 value of s[] , e[] and h[].
a[] = [2,4,8,6,7]
s[] = [1,0]
e[] = [3,4]
h[] = [5,4]
o/p = [4,4,4,4,4] max = 4
for(int i=0;i<s.length;i++) {
int start = s[i];
int end = e[i];
while(start < end) {
if(a[start] > h[i]) {
a[start] = h[i];
}
start++;
}
}
findMax() // iterate array to find maximum in O(n)
Time complexity in worst case will be- O(k*n)
k is the length of s[] . and n is length of a[]
It Can also be solve by using time overlap with stack algorithm.
As per my understanding,
We have to find a number in array which is greater than all numbers lies on left side and lesser than all numbers lies on right side in the array.
e.g.
arr[] = 5,4,3,7,4,1,2,8,10
Output - 8 (all elements at left side are lesser than 8 and all elements at right side are greater than 8).
My solution-
I will create 2 arrays-
1- First array will hold max value in array before that index.(Traverse from left side to get the values), for above array , the array will be -
lmax = 5,5,5,5,7,7,7,7,8 (Take first element as it is in origin array)
2- Second array will hold min value in array after the index.(Traverse from right side to get the values), For above array, the second array will be -
rmin = 1,1,1,1,1,2,8,10,10 (Take last element as it is in origin array)
Now traverse the origin array and check condition-
if(arr[i] >= lmax[i] && arr[i] <= rmin[i]){
print(arr[i])
}
Space complexity O(2n) - Need to create min max array
Time complexity - O(n)
It seems like , you have to find the number from 10 to 1000 , which is divisible by given numbers (10,15,55).
There should be 2 loops ,
1- From 10 to 1000
2- To check for all coins
Break the inner loop on finding any suc number which is divisible by given coins.
for(int i=10;i<=1000;i++) {
for(int j = 0; j< coins.length;j++){
if(i%coins[j] == 0) {
System.out.println(i);
break;
}
}
}
Given n= 1000 and k = numbers of coins i.e 3
The time complexity of above code in worst case will be O(kn).
Agreed with Siva's answer except one case - Missing numbers of one chunk can be present in other chunk. So you have to put a check to verify it.
I will divide memory in 2 parts 9000 + 1000 (As mentioned few hundreds , and i am assuming it is not more than 1000 missing numbers)
First 9k
1- Take chunk with 9k , sort it
2- Traverse it and create a hashMap with missing number as key
For the remaining numbers
3- Clean the 9k memory and take another chunk if numbers are available
4- Push the chunk in memory and verify the hashMap with each number, If number is in hashMap then delete the entry from hashMap
5- Sort it and push missing number in the hashMap as key
After final iteration the hashMap keys will be the missing numbers.
Overall time complexity will be n + nlogn
Thanks
Simple solution -
Step 1- Find the node with first element of the given array
if node is present then go for step 2
else No path is present
Step 2-
Check for the remaining elements of the given array in child tree of the node.
If any level with no match elements then return false.
else keep matching for remaining elements of array and return true on all match found
We can consider few more conditions-
Restaurant has a Menu (Menu class)
Menu has items (Item class)
User can order (Order class)
Order can have many selectedItems(SelectItem class)
User has to pay the BIll (Bill class)
There also be a Payment class(That must be thread safe)
Total - 8 classes
Restaurant
User
Menu
Item
Order
SelectItem
Bill
Payment
Lets see classes one by one -
Restuarant
-----------
- name : String
- location : string
- conatct : string
-----------
+ isOpen() : boolean
+ getName() : String
+ getLoaction() : String
+ getContact() : String
+ setContact()
+ displayMenu()
+ updateMenu)_
+ generateBill()
User
-----------
- uid : String
- contact : String
-----------
+ setContact()
+ getContact()
+ getUid()
+ searchRestauranr()
+ selectRestuarant()
+ newOrder()
+ cancelOrder()
+ trackOrder()
+ payBill()
Menu
---------
- menu : List<Item>
---------
+ displayMenu()
+ updateMenu()
+ addItem()
+ deleteItem()
Item
----------
- itemId : String
- price : float
- name : String
----------
+ setItemId(String)
+ setName(String)
+ setPrice(float)
+ getItemId()
+ getName()
+ getPrice()
Order
-----------
- orderId : String
-----------
+ getStatus() // To track the order
+ updateStatus() // Restaurant admin can update it
+ getOrderId()
+ selectItem()
+ removeItem()
+ updateItem()
SelectItem
-----------
- itemId
- quantity : int
-----------
+ getItem()
+ setItem()
+ getQuantity()
+ setQuantity()
Bill
------------
- billNum
- orderId
------------
+ getBillNum()
+ getTotalAmount()
+ displayBill()
Payment
------------
- pid : String
- pType : String
- billNum : String
-------------
+ successfulyPaid() : boolean
We can solve it using recursion-
Algo-
1- if node is null return false;
2- if node have both left and right child then it will return true. (node + 2 child = 3 node (Odd number))
3- if node does not have any child then also it will return true. (node itself)
4- else it will return false.
- azambhrgn April 04, 2019