Find the day on which stock should be bought and sell, to have maximum profit, Stock can be bought and sold only once.

Problem Explanation

Given an array with the price of stocks on different days. A person can buy and sell stock only once.Compute the maximum profit can be made in that single transaction.

If person cannot make any profit, return 0 as an answer

Example

Sample Input:  [9,8,7,6,5,4,3]  Expected output: 6 {9-3}

Sample Input:  [3,4,5,6,7,8,9]  Expected output: 0

Sample Input: [7,1,5,3,6,4]  Expected output: 6 {7-1}

Solution

For this solution we will use Print next Greatest Element for entry in an Array


public int currentSolution(int[] input){

<code class="java keyword">if</code><code class="java plain">(input == </code><code class="java keyword">null</code> <code class="java plain">|| input.length <=</code><code class="java value">1</code> <code class="java plain">) </code><code class="java keyword">return</code> 0;

int n = input.length;

int currentMax = 0;

String[] nextGreater = solution(input);

for(int i =0;i<n;i++){

String value = nextGreater[i];

if(value.equals("MAX")){

continue;

}

int nextValue =Integer.valueOf(value);

currentMax = Math.max(currentMax, nextvalue - input[i]);

}

return currentMax;

}

TimeComplexity: O(n)

Space Complexity: O(n)

 

 

 

 

 

Advertisements

Print next Greatest Element for entry in an Array.

Problem

Given an array, which can have positive and negative numbers, write a code to print the next greatest element for each element. For the last number, next greater element will always be Integer.MIN.

For element, for which no greater number is present, print Integer.MIN.

Example – input array – [7,1,5,3,6,4]

Expected output – [MIN,6,6,6,MIN,MIN] .{MIN is considered as Integer.MIN}

Method to implement :


public String[] solution(int[] input);

Solution


public String[] solution(int[] input){

if(input == null || input.length <=1 ) return null;
int n = input.length;
String[] result = new String[n];
Stack<Integer> s = new Stack<>();
result[n-1] = "MIN";
s.push(input[n-1]);

for(int i = n-2;i>=0;i--){

while (!s.empty() && s.peek() < input[i]){
s.pop();
}
if(s.isEmpty()){
result[i] = "MIN";
s.push(input[i]);

}else{
result[i] = s.peek().toString();

}

}
return result;
}

Implementation

 

 

ThoughtWorks-interview experience

Got a call from a consultant,

I am sharing my interview experience for the same with you.

  1. Telephonic [30 mins]
    1. Current Project, and how PMS work internally.
    2. The difference between quick sort and merge sort.
    3. Which sorting did java use internally?
    4. When to user Interface, and Abstract classes.
    5. How to make class Immutable, and if immutable class contain a list, how to handle it.
  2. Coding[With Laptop coding]
    1. Write a program to full fill following problem: two(times(three())) or nested cases also.All the operator should be there.[logic was important].Click Here to get the complete code of this problem
  3. Coding[With Laptop coding]
    1. Write a code to compute the cost of the checkout cart, have many items with quantity, the group of items can have the special price. Every item has there individual price.[Focus on domain design]
  4. F2F Interview
    1. Current project design, architecture, your role.
    2. Difference btw soap and rest service.
    3. Domain design for a ROOM.
    4. Multi-thread simple question,
    5. DB designing simple.
  5. F2F Interview
    1. this was more of a discussion rather than the interview, more related to culture and personality.They will try to understand who you are, what are your goals.Are you  right person or not for ThoughtWorks
  6. F2F Interview
    1. It was related to the 3 pillars that ThoughtWorks build on, and try will try to understand your point of view on various social issues
  7. Aptitude Test
    1. There are around 50 questions, you  have to complete as much as question in 12 min
  8. Logical Test
    1. There are 13 question which have to completed in 1 hour.
A major focus will be given to Domain Design, how the class is created and how the will interact.
OOPS, concepts are important.Name of the classes matter.
If really want to crack Thoughtworks, please check few books.

Given an array, find all the subsets

int arr[] = {1,2,3,4,5};
int level= 0;

for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
subset(arr[i]+””,i+1,arr);

}
}

private void subset(String i, int level,int[] arr) {

for (int j = level; j < arr.length; j++) {
System.out.println(i+””+arr[j]);
subset(i+””+arr[j],j+1,arr);

}

Find the all the lexical pair from the given array of strings.

lexical pairs

 

Vector<String> v = new Vector<String>();
Set<String> s = new HashSet<String>();
v.add(“Resistance”);
v.add(“Ancestries”);
v.add(“Gainly”);
v.add(“Laying”);
v.add(“test”);
v.add(“troop”);
v.add(“Amit”);
v.add(“Mait”);
v.add(“Self”);
v.add(“Taim”);
Boolean lexical = false,found = false;
System.out.println(“case 2”);

int lenght = v.size(),count = 0;

for (int i = 0; i < v.size(); i++) {
String source = v.get(i);

source = source.toLowerCase();
char[] sourceWord = source.toCharArray();
Arrays.sort(sourceWord);
source = new String(sourceWord);
//System.out.println(“source “+source);
count =0;
for (int j = i+1; j < v.size(); j++) {

String target = v.get(j);
target = target.toLowerCase();
char[] targetWord = target.toCharArray();
Arrays.sort(targetWord);
target = new String(targetWord);

if(source.equals(target)){
lexical = true;

System.out.print(v.get(i)+” “);
System.out.println(v.get(j));
continue;
// v.remove(v.get(j));

}

}
if(count>0)
System.out.println(“”);
}

if(!lexical){
System.out.println(“No such pairs”);
}

Given a matrix with each cell containing each number of candies, and a constraint that you can move only right or down, from the top left corner to the bottom right corner, find the path that gets you maximum candies.

Note: This result will print the all the possible path cost , you can fetch the path with maximum candies.

 

int matrix[][] = {{0,5,7},{7,9,1},{2,7,11}};
int rows = matrix.length,column = matrix[0].length;
System.out.println(“rows : “+rows );
System.out.println(“columns : “+column);
int TotalSum = 0,sum=0;

FindTheTotalSum(0,0,sum,rows,column,matrix);

}

private void FindTheTotalSum(int i, int j, int sum,int rows,int column,int[][] arr) {

if((i==column-1)&&(j==rows-1)){
System.out.println(sum+” sum of the path”);
}
sum = sum + arr[j][i];
if(i<column-1){
FindTheTotalSum(i+1, j, sum, rows, column,arr);
}
if(j<rows-1){
FindTheTotalSum(i, j+1, sum, rows, column,arr);
}

}