Showing posts with label programming interview question. Show all posts
Showing posts with label programming interview question. Show all posts

Tuesday, October 25, 2016

Array Product

Problem source gfg

http://stackoverflow.com/questions/2680548/given-an-array-of-numbers-return-array-of-products-of-all-other-numbers-no-div

Given an array of numbers, return array of products of all other numbers (no division)


solution:

#include <iostream>
using namespace std;

void fill(int *a,int size)
{
    for(int i=0;i<size;i++)
    {
        a[i] = 1;
    }
}
int* createProduct(int* a,int size)
{
  
  
    int temp = 1;
    int* products = new int[size];
    fill(products,size);
    for(int i=0;i<size;i++)
    {
        products[i] = temp;
        temp *= a[i];
    }
    temp = 1;
    for(int i=size-2;i>=0;i--)
    {
        
        temp *= a[i+1];
        products[i] *= temp;
    }
    return products;
    
}
void disp(int* a,int size)
{
       for(int i=0;i<size;i++)
    {
        cout<<a[i]<<"\t";
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    int a[] = {6,7,8,4,5};
    
    int size = sizeof(a)/sizeof(*a);
    //cout<<sizeof(*a);
    int* res = createProduct(a,size);
    disp(res,size);
    return 0;
}
Posted by at No comments:
Labels: , , ,

Friday, August 26, 2016

Leetcode Palindrome Partitioning

Question Reference:
https://leetcode.com/problems/palindrome-partitioning/

 Solution Reference:
http://www.programcreek.com/2013/03/leetcode-palindrome-partitioning-java/

package palindrome_partioning;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

public class Solution {
public static void main (String args[])
{
Solution s1 = new Solution();
String input = "aab";
System.out.println(s1.partition(input));
}
public static  ArrayList<ArrayList<String>> partition(String a) 
{
    ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
    if(a==null||a.length()==0)
    {
    return res;
    }
    ArrayList<String> temp = new ArrayList<String>();
    partition(a,temp,res,0);
    return res;
}
    public static void partition(String a,ArrayList<String> temp,ArrayList<ArrayList<String>> res,int start)
    {
    if(start==a.length())
    {
    res.add(new ArrayList(temp));
    return;
    }
        
    for(int i = start+1;i<=a.length();i++)
    {
    if(isPalindrome(a.substring(start, i)))
    {

    temp.add(a.substring(start,i));
    partition(a,temp,res,i);
    temp.remove(temp.size()-1);
    }  
    }
    }
    public static boolean isPalindrome(String input)
    {
    int start = 0,end=input.length()-1;
    while(start<=end)
    {
    if(input.charAt(start)!=input.charAt(end))
    {
    return false;
    }
    start++;
    end--;
    }
    return true;
    }
    
}


Tracing the above program for input string "aab"


start  = 0i= 1
subString isa
start  = 1i= 2
subString isa
start  = 2i= 3
subString isb
start equals to length of the string hence:
result arraylist at the end of this start=3is[[a, a, b]]
start  = 1i= 3
No substring in this iteration since  ab  is not a palindrome
start  = 0i= 2
subString isaa
start  = 2i= 3
subString isb
start equals to length of the string hence:
result arraylist at the end of this start=3is[[a, a, b], [aa, b]]
start  = 0i= 3
No substring in this iteration since  aab  is not a palindrome
final output list is[[a, a, b], [aa, b]]


Tracing the above program for input string "helloworld"

start  = 0i= 1
subString ish
start  = 1i= 2
subString ise
start  = 2i= 3
subString isl
start  = 3i= 4
subString isl
start  = 4i= 5
subString iso
start  = 5i= 6
subString isw
start  = 6i= 7
subString iso
start  = 7i= 8
subString isr
start  = 8i= 9
subString isl
start  = 9i= 10
subString isd
start equals to length of the string hence:
result arraylist at the end of this start=10is[[h, e, l, l, o, w, o, r, l, d]]
start  = 8i= 10
No substring in this iteration since  ld  is not a palindrome
start  = 7i= 9
No substring in this iteration since  rl  is not a palindrome
start  = 7i= 10
No substring in this iteration since  rld  is not a palindrome
start  = 6i= 8
No substring in this iteration since  or  is not a palindrome
start  = 6i= 9
No substring in this iteration since  orl  is not a palindrome
start  = 6i= 10
No substring in this iteration since  orld  is not a palindrome
start  = 5i= 7
No substring in this iteration since  wo  is not a palindrome
start  = 5i= 8
No substring in this iteration since  wor  is not a palindrome
start  = 5i= 9
No substring in this iteration since  worl  is not a palindrome
start  = 5i= 10
No substring in this iteration since  world  is not a palindrome
start  = 4i= 6
No substring in this iteration since  ow  is not a palindrome
start  = 4i= 7
subString isowo
start  = 7i= 8
subString isr
start  = 8i= 9
subString isl
start  = 9i= 10
subString isd
start equals to length of the string hence:
result arraylist at the end of this start=10is[[h, e, l, l, o, w, o, r, l, d], [h, e, l, l, owo, r, l, d]]
start  = 8i= 10
No substring in this iteration since  ld  is not a palindrome
start  = 7i= 9
No substring in this iteration since  rl  is not a palindrome
start  = 7i= 10
No substring in this iteration since  rld  is not a palindrome
start  = 4i= 8
No substring in this iteration since  owor  is not a palindrome
start  = 4i= 9
No substring in this iteration since  oworl  is not a palindrome
start  = 4i= 10
No substring in this iteration since  oworld  is not a palindrome
start  = 3i= 5
No substring in this iteration since  lo  is not a palindrome
start  = 3i= 6
No substring in this iteration since  low  is not a palindrome
start  = 3i= 7
No substring in this iteration since  lowo  is not a palindrome
start  = 3i= 8
No substring in this iteration since  lowor  is not a palindrome
start  = 3i= 9
No substring in this iteration since  loworl  is not a palindrome
start  = 3i= 10
No substring in this iteration since  loworld  is not a palindrome
start  = 2i= 4
subString isll
start  = 4i= 5
subString iso
start  = 5i= 6
subString isw
start  = 6i= 7
subString iso
start  = 7i= 8
subString isr
start  = 8i= 9
subString isl
start  = 9i= 10
subString isd
start equals to length of the string hence:
result arraylist at the end of this start=10is[[h, e, l, l, o, w, o, r, l, d], [h, e, l, l, owo, r, l, d], [h, e, ll, o, w, o, r, l, d]]
start  = 8i= 10
No substring in this iteration since  ld  is not a palindrome
start  = 7i= 9
No substring in this iteration since  rl  is not a palindrome
start  = 7i= 10
No substring in this iteration since  rld  is not a palindrome
start  = 6i= 8
No substring in this iteration since  or  is not a palindrome
start  = 6i= 9
No substring in this iteration since  orl  is not a palindrome
start  = 6i= 10
No substring in this iteration since  orld  is not a palindrome
start  = 5i= 7
No substring in this iteration since  wo  is not a palindrome
start  = 5i= 8
No substring in this iteration since  wor  is not a palindrome
start  = 5i= 9
No substring in this iteration since  worl  is not a palindrome
start  = 5i= 10
No substring in this iteration since  world  is not a palindrome
start  = 4i= 6
No substring in this iteration since  ow  is not a palindrome
start  = 4i= 7
subString isowo
start  = 7i= 8
subString isr
start  = 8i= 9
subString isl
start  = 9i= 10
subString isd
start equals to length of the string hence:
result arraylist at the end of this start=10is[[h, e, l, l, o, w, o, r, l, d], [h, e, l, l, owo, r, l, d], [h, e, ll, o, w, o, r, l, d], [h, e, ll, owo, r, l, d]]
start  = 8i= 10
No substring in this iteration since  ld  is not a palindrome
start  = 7i= 9
No substring in this iteration since  rl  is not a palindrome
start  = 7i= 10
No substring in this iteration since  rld  is not a palindrome
start  = 4i= 8
No substring in this iteration since  owor  is not a palindrome
start  = 4i= 9
No substring in this iteration since  oworl  is not a palindrome
start  = 4i= 10
No substring in this iteration since  oworld  is not a palindrome
start  = 2i= 5
No substring in this iteration since  llo  is not a palindrome
start  = 2i= 6
No substring in this iteration since  llow  is not a palindrome
start  = 2i= 7
No substring in this iteration since  llowo  is not a palindrome
start  = 2i= 8
No substring in this iteration since  llowor  is not a palindrome
start  = 2i= 9
No substring in this iteration since  lloworl  is not a palindrome
start  = 2i= 10
No substring in this iteration since  lloworld  is not a palindrome
start  = 1i= 3
No substring in this iteration since  el  is not a palindrome
start  = 1i= 4
No substring in this iteration since  ell  is not a palindrome
start  = 1i= 5
No substring in this iteration since  ello  is not a palindrome
start  = 1i= 6
No substring in this iteration since  ellow  is not a palindrome
start  = 1i= 7
No substring in this iteration since  ellowo  is not a palindrome
start  = 1i= 8
No substring in this iteration since  ellowor  is not a palindrome
start  = 1i= 9
No substring in this iteration since  elloworl  is not a palindrome
start  = 1i= 10
No substring in this iteration since  elloworld  is not a palindrome
start  = 0i= 2
No substring in this iteration since  he  is not a palindrome
start  = 0i= 3
No substring in this iteration since  hel  is not a palindrome
start  = 0i= 4
No substring in this iteration since  hell  is not a palindrome
start  = 0i= 5
No substring in this iteration since  hello  is not a palindrome
start  = 0i= 6
No substring in this iteration since  hellow  is not a palindrome
start  = 0i= 7
No substring in this iteration since  hellowo  is not a palindrome
start  = 0i= 8
No substring in this iteration since  hellowor  is not a palindrome
start  = 0i= 9
No substring in this iteration since  helloworl  is not a palindrome
start  = 0i= 10
No substring in this iteration since  helloworld  is not a palindrome
final output list is[[h, e, l, l, o, w, o, r, l, d], [h, e, l, l, owo, r, l, d], [h, e, ll, o, w, o, r, l, d], [h, e, ll, owo, r, l, d]]



Posted by at No comments:
Labels: , , , , ,
Subscribe to: Posts (Atom)