ram.prasad.prabu
BAN USERCan we build a suffix tree with the long string and find the short string permutation in it ??
- ram.prasad.prabu August 04, 2015We can use a combination of Heap and Trie based solution.
- ram.prasad.prabu July 14, 2015Use a Trie.
Time : O(row * col)
Space : O(row * col)
1. Insert the first row in the trie.
2. Then for every row, check if the row is available (similar) in the trie, if yes ignore that row.
else print the row and insert into the trie.
@Zortlord : my mistake.. updated now :)
public static void surpass(int[] a){
int max = 0; int result[] = new int[a.length];
for(int i=1; i<a.length; i++){
for(int j=0; j<i; j++){
if(a[i] > a[j]){
result[j] +=1;
max = Math.max(max, result[j]);
}
}
}
}
public static void surpass(int[] a){
int max = 0; int result[] = new int[a.length];
for(int i=1; i<a.length; i++){
for(int j=0; j<i; j++){
if(a[i] > a[j]){
result[j] +=1;
max = Math.max(max, result[j]);
}
}
}
}
This is ugly number problem. Please find the below code
void getNthUglyNo(unsigned n)
{
int ugly = new int[n];
int i2 = 0, i3 = 0, i4 = 0, i7=0;
int i;
int next_multiple_of_2 = 2;
int next_multiple_of_3 = 3;
int next_multiple_of_4 = 4;
int next_multiple_of_7 = 7;
int next_ugly_no = 1;
ugly[0] = 1;
for(i=1; i<n; i++)
{
next_ugly_no = Math.min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_4,
next_multiple_of_7);
ugly[i] = next_ugly_no;
if(next_ugly_no == next_multiple_of_2)
{
i2 = i2+1;
next_multiple_of_2 = ugly[i2]*2;
}
if(next_ugly_no == next_multiple_of_3)
{
i3 = i3+1;
next_multiple_of_3 = ugly[i3]*3;
}
if(next_ugly_no == next_multiple_of_4)
{
I4 = i4+1;
next_multiple_of_4 = ugly[i4]*4;
}
if(next_ugly_no == next_multiple_of_7)
{
i7 = i7+1;
next_multiple_of_7 = ugly[i7]*7;
}
} /*End of for loop (i=1; i<n; i++) */
return next_ugly_no;
}
This is a pretty simple problem.
Algorithm
Recusrively reduce the sum from current node value and check both left & right tree if there is a path with Subsum ( current node value - sum)
hasPathSum(Node root, int sum){
if(root == null)
return (root.data == sum);
int subSum = sum - root.data;
return (hasPathSum(root.left, subSum) || hasPathSum(root.right, subSum));
}
Lets say a=5, b=10, y=0, x = 0 or 1
if( x & 1){ // use bitwise
assign(b,y);
}
else{
assign(a,y);
}
assign(int ab, int y){
ab = ab^y;
y = ab^y; // y is now assigned
}
Here is the algorithm.
1. First find the number of digits in first operand 'a' ( this is equal to the power of 10)
2. We need to multiply this power of 10 with the second operand 'b'.
3. Then OR (|) result from step 2 and the first operand 'a'.
public class Concatenate {
public static void main(String[] args) {
int a = 12;
int b = 36;
int digit_count = (int) Math.log10(a)+1; // To find the number of digits in first operand
int c = 0;
switch(digit_count){
case 1 : // Power of 10 is 1.
c = (b << 3) + (b << 1); // 10^1(10) = 2^3(8)+ 2^1(2)
break;
case 2 : // Power of 10 is 2.
c = (b << 6) + (b << 5)+ (b << 2); // 10^2(100) = 2^6(64)+ 2^5(32)+ 2^2(4)
break;
}
c = c | a; // Add the both the values to get the output.
System.out.println(c); // Outputs 3612
}
}
Simple solution in Java
StringBuilder sb = new StringBuilder();
//Serialize the content
public void serialize(TreeNode root, StringBuilder sb){
if(root == null){
sb.append("# ");
return;
}
sb.append(root.value+ " ");
serialize(root.Left, sb);
serialize(root.Right, sb);
}
//Deserialize the content
public TreeNode deserialize(String s){
if (s == null || s.length() == 0) return null;
StringTokenizer st = new StringTokenizer(s, " "); //Use space (" ") as token
return deserialize(st);
}
private TreeNode deSerialize(StringTokenizer st){
if (!st.hasMoreTokens())
return null;
String val = st.nextToken();
if(value.equals("#")){
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(value));
root.left = deserialize(st);
root.right = deserialize(st);
return root;
}
Algorithm
1. Find the pivot element index in the array (pivot element is the first smallest element in the array input)
2. Subtract : array.length - pivot_elem_index to get the number of rotations.
Step 1: Find Pivot Index
public static int pivot(int a[]){
int low = 0; int high = a.length -1;
while(a[low] > a[high]){
int mid = (low+high) >> 1;
if(a[mid] > a[high]){
low = mid+1;
}
else{
high = mid;
}
}
//System.out.println("pivot : "+a[low]);
return low;
}
Step 2 : (a.length - low) = No of rotations
Pretty simple one !! Source : Cracking the coding interviews
say Input: N = 1000000000, M = 10011, i = 2(startIndex), j = 6(endIndex)
The algorithm would look like
1. Clearing the bits j through i in N
2. Shift M so that it lines up with bits j through i
3. Merge M and N.
public static int updateBits(int n, int m, int i, int j) {
int max = ~0; /* All 1’s */
// 1’s through position j, then 0’s
int left = max - ((1 << j) - 1);
// 1’s after position i
int right = ((1 << i) - 1);
// 1’s, with 0s between i and j
int mask = left | right;
// Clear i through j, then put m in there
return (n & mask) | (m << i);
}
Its similar to RGB problem. Here is the code. This works only for remainder 0-2.
public class SortByModulo {
static int[] a = {1,2,3,4,5};
public static void main(String[] args) {
sort(a.length);
print();
}
public static void sort(int n){
int low=0, mid=0, high=n-1;
while(mid <= high){
switch(a[mid]%3){
case 0:
swap(low, mid);
low++;mid++;
break;
case 1:
mid++;
break;
case 2:
swap(mid, high);
high--;
break;
}
}
}
private static void swap(int aa , int b){
int temp = a[aa];
a[aa] = a[b];
a[b] = temp;
}
private static void print(){
for(int i: a)
System.out.print(i+ " ");
}
}
Hi could you clarify these both statements in the problem .
1. First it says, keycode panel does not reset when incorrect sequence is entered.
2. Next in the below lines it says, panel does not reset after every sequence.
when does the sequence actually does not reset ? and also when correct code is sequence of 5 digits, are we allowed to enter more than 5 digits at a time ???
L M N - I think the letters having straight lines are in the series
Repleancpuryear, Data Scientist at Adjetter Media Network Pvt Ltd.
Hi guys!! My name is Lean C Puryear and I love fashion, I hope to some day get into the ...
Is it not similar to job matching problem solved using Graph ??
- ram.prasad.prabu August 04, 2015