Practice with me- I try to code here and put up my solutions, let me know if you find a better solution than me
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4] Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105-30 <= nums[i] <= 30- The product of any prefix or suffix of
numsis guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
public int[] productExceptSelf(int[] nums) {
int arr [] = new int[nums.length];
int prod = 1;
int zerocount = 0;
for(int i=0;i<nums.length;i++)
{
if(nums[i]!=0)
{
prod = prod*nums[i];
}
else
{
zerocount = zerocount+1;
}
}
if(zerocount>=2)
{
return arr;
}
for(int i=0;i<nums.length;i++)
{
if(nums[i]==0)
{
arr [i] = prod;
}
else if(nums[i]!=0 && zerocount == 1)
{
arr[i] = 0;
}
else
{
arr [i] = prod/nums[i];
}
}
return arr;
}
}
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 105
class Solution {
public int maxProfit(int[] prices) {
int sum =0;
int p1 = -prices[0];
int p2 = Integer.MIN_VALUE;;
int p3 = Integer.MIN_VALUE;
int p4 = Integer.MIN_VALUE;
for(int i=0;i<prices.length;i++)
{
p1 = Math.max(p1,-prices[i]); //finding on first txn the lowest trade value
p2 = Math.max(p2,p1+prices[i]); //selling for max profit
p3 = Math.max(p3,p2-prices[i]); //adding first txn profit and reducing with lowest selling price for day 2 txn
p4 = Math.max(p4,p3+prices[i]); //selling the second txn for max profit
}
return Math.max(0,p4);
}
}
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Constraints:
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
public class solution3 {
public static void main(String[] args) {
secondQuestion(new int[]{7,1,5,3,6,4});
}
public static void secondQuestion(int []prices)
{
int sum = 0;
for(int i=0;i<prices.length-1;i++)
{
if(prices[i]<prices[i+1])
{
sum = sum+(prices[i+1]-prices[i]); //adding the total profit gained per day
}
}
System.out.println(sum);
}
}
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 104
SOLUTION -
public class solution3 {
public static void main(String[] args) {
maxProfit(new int[]{7,1,5,3,6,4}); //this solution is by using brute force
maxpr(new int[]{7,1,5,3,6,4}); //this is dynamic programming solution
}
public static void maxProfit(int[] prices) {
int max = 0;
for(int i=0;i<prices.length;i++)
{
for(int j=i+1;j<prices.length;j++)
{
if(prices[i]<prices[j])
{
if(prices[j]-prices[i]>max)
{
max = prices[j]-prices[i];
}
}
}
}
System.out.println("max is "+max);
}
public static void maxpr(int []prices)
{
int lsp = Integer.MAX_VALUE; //a randomly high value -> it will contain the least selling price(lsp)
int maxprofit = 0; //this contains maximum profit which can be earned going chronologically
for(int i=0;i<prices.length;i++)
{
if(prices[i]<lsp)
{
lsp = prices[i]; //update the least selling price
}
if(maxprofit<prices[i]-lsp) //calculate profit
{
maxprofit = prices[i]-lsp; //update if profit is max
}
}
System.out.println(maxprofit);
}
}
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd" Output: "bb"
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters.
public class solution2 {
public static void main(String[] args) {
System.out.println(longestpalindrome("cbbd"));
}
public static String longestpalindrome(String str)
{
int l = str.length();
if(l==1)
{
return str;
}
int arr[][] = new int[l][l];
for(int i=0;i<l;i++)
{
arr[i][i] = 1;
}
System.out.println("lem is"+l);
int max=0,r1=0,r2=0;
//for 2 digit pairs
for(int i=0;i<l;i++)
{
int j=i+1;
if(j<l && str.charAt(i)==str.charAt(j))
{
arr[i][j] = 1;
if(j>max)
{
max = j;
r1 = j;
r2 = i;
}
if(i>max)
{
max = i;
r1 = j;
r2 = i;
}
}
}
//for 3+ digit pairs
for(int i=3;i<=l;i++)
{
for(int j=0;j<l;j++)
{
//next index
int k = j+i-1;
if(k<l && str.charAt(j) == str.charAt(k) && arr[j+1][k-1]==1 )
{
arr[j][k] = 1;
if(j>max)
{
max = j;
r1 = i;
r2 = j;
}
if(k>max)
{
max = k;
r1 = i;
r2 = j;
}
}
}
}
//printing
for(int i=0;i<l;i++)
{
for(int j=0;j<l;j++)
{
System.out.print(arr[i][j]);
}
System.out.println();
}
System.out.println("r1:"+r1+" r2:"+r2);
return(str.substring(r2,r1+r2));
}
}
Source - Leetcode
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: rowIndex = 3 Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0 Output: [1]
Example 3:
Input: rowIndex = 1 Output: [1,1]
Constraints:
0 <= rowIndex <= 33
MY SOLUTION -
import java.util.ArrayList;
import java.util.List;
public class solution {
public static void main(String[] args)
{
System.out.println(mysol(10));
}
public static List<Integer> mysol(int rowIndex)
{
ArrayList<Integer> arr = new ArrayList<Integer>(rowIndex+1);
for(int i=0;i<rowIndex+1;i++)
{
arr.add(0);
for(int j=i;j>=0;j--)
{
if(j==0 || j==i)
{
arr.set(j,1);
System.out.println("IF"+arr);
}
else
{
arr.set(j, arr.get(j-1) + arr.get(j));
System.out.println("ELSE"+arr);
}
}
}
return arr;
}
}
Question-
Given two sequences A, B, count number of unique ways in sequence A, to form a subsequence that is identical to the sequence B.
Subsequence : A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).
Input Format:
The first argument of input contains a string, A.
The second argument of input contains a string, B.
Output Format:
Return an integer representing the answer as described in the problem statement.
Constraints:
1 <= length(A), length(B) <= 700
Example :
Input 1:
A = "abc"
B = "abc"
Output 1:
1
Explanation 1:
Both the strings are equal.
Input 2:
A = "rabbbit"
B = "rabbit"
Output 2:
3
Explanation 2:
These are the possible removals of characters:
=> A = "ra_bbit"
=> A = "rab_bit"
=> A = "rabb_it"
Note: "_" marks the removed character.SOLUTION -
public class handler {
public static void main(String args[]) {
// Your code goes here
//System.out.println("out is "+ numDistinct("aaaababbababbaabbaaababaaabbbaaabbb","bbababa"));
System.out.println("out is "+ numDistinct("babbab","bab"));
}
public static int numDistinct(String a, String b) {
int m = b.length();
int n = a.length();
if(m>n){
return 0;
}
int dp[][] = new int[m+1][n+1];
for(int i=1;i<=m;i++)
{
//setting first cloumn zero
dp[i][0]=0;
}
for(int i=0;i<=n;i++)
{
//setting first row 1
dp[0][i]=1;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(b.charAt(i-1)!=a.charAt(j-1)){
dp[i][j] = dp[i][j-1];
}
else{
dp[i][j] = dp[i][j-1]+dp[i-1][j-1];
}
}
//printing matrix
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
System.out.print(dp[i][j]+" ");
}
System.out.println();
}
return dp[m][n];
}
}
Question -
Problem Description
You may assume that the array is non-empty and the majority element always exist in the array.
Example :
Input : [2, 1, 2]
Return : 2 which occurs 2 times which is greater than 3/2.
question source - interviewbit.com
No comments:
Post a Comment