praveen
BAN USER- 0of 0 votes
AnswersFind the kth largest element in the union of two sorted arrays (with duplicates)
- praveen in United States| Report Duplicate | Flag | PURGE
Algorithm
Algorithm:
1. Start i = 0.
2. If you find 0..i as a valid string.
3. Then at ith position, I need to recursively call the method and check if we get a word on the right hand side for the given left hand side of i. ie. 0..i substring is a valid word if and only if i+1..end can make a list of words successfully. Otherwise I would increment i.
I think this way we can get the solution
General working of TinyUrl is:
If same long url is given multiple times (or multiple users), different tiny urls need to be given.
So, we can start with a 3 character combination and increase the number of character combinations when they are exhausted. Add the character combination as a key and the long url as value in the hashtable. So when the tinyurl is given, the value against this in the hash table is fetched in constant time.
Please do comment your opinions.
public class Point implements Comparable<Point>{
int x;
int y;
public Point() {
this(0, 0);
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point other) {
if (this.y == other.y) return 0;
return this.y < other.y ? -1 : 1;
}
}
public int findRangeOfIntervals(Point[] points) {
List<Point> list = Arrays.asList(points);
Collections.sort(list);
int lowerBound = -1;
int upperBound = -1;
int result = 0;
for (int i = 0; i < list.size(); i++) {
Point p = list.get(i);
if (p.x <= upperBound) {
if (p.y > upperBound) {
upperBound = p.y;
}
} else {
lowerBound = p.x;
upperBound = p.y;
}
if (result < upperBound - lowerBound) {
result = upperBound - lowerBound;
}
}
return result;
}
If you want to use an array, instead of using the count for the respective character, try to use the index as a value and if you find any character repeating( i.e. if the corresponding value in the array is positive, then make it -1). after entire stream is over, you can find the minimum value >= 0 from the array which is the index of the first non repeating character.
- praveen November 15, 2012void longestSeq(int arr[], int index, int size)
{
int idx = 0, b = arr[0], sz = 0, mIdx = 0, mSize = 0;
for (int i = 0; i < size, i++)
{
if(arr[i] == b+1)
{
sz++;
}
else{
idx = i;
sz = 1;
}
if (mSize < sz)
{
mIdx = idx;
mSize = sz;
}
}
for(int j = mIdx ; j < mSize; j++)
cout << arr[j] << ' ' ;
}
Please comment if anything is wrong
- praveen November 15, 2012void findANYThreeNodesWithSumK(node* head, node* sumarr[], int num, int K) {
if (head == NULL)
return;
findANYThreeNodesWithSumK(head->left, sumarr, num, K);
findANYThreeNodesWithSumK(head->right, sumarr, num, K);
sumarr[num] = head;
findANYThreeNodesWithSumK(head->left, sumarr, num+1, K-head->data);
findANYThreeNodesWithSumK(head->right, sumarr, num+1, K-head->data);
if (K == 0 && num == 3) {
//print all the nodes in sumarr
num = 0;
//flush sumarr so that it can continue further
}
}
char findFirstNonRepeatingCharInaString(char* arr, int size) {
int a[256] = {0};
int c = 0;
int min = -1;
for (int i = 0; i < size; i++) {
c = arr[i];
//if repeated then make it negative
if (a[c] > 0)
a[c] = -1;
//store the index instead of the number of occurences
else if (a[c] == 0)
a[c] = i;
else {
}
}
//find the minimum index in the array
for (int i = 0; i < 256; i++) {
if (a[i] > 0 && a[i] < min)
min = a[i];
}
if (min >= 0)
return arr[min];
else
return 0;
}
In the below algorithm, checker works similar to an array of bits. When it does an |= operation, it sets the bit of the particular number.
void retUniqueCharsINPLACE(char* &str) {
int checker = 0, i =0;
int c;
int flag = 0;
while (str[i] != '\0') {
c = str[i] - 'a';
if ((checker & (1 << c)) > 0) {
str[i] = 0;
if (flag ==0)
flag = i;
} else {
checker |= (1 << c);
if (flag != 0) {
str[flag] = str[i];
str[i] = 0;
while (flag <= i && str[flag] != 0) {
flag++;
}
}
}
i++;
}
}
Please comment if anything you feel is wrong.
This algorithm takes O(1) space and inplace but not sure if it is O(n) as there is a loop that is used to find the blanks.
node* findLCABinaryTree(node* head, node* a, node* b)
{
if(head == NULL)
return NULL;
if(head == a || head == b) return head;
node *L, *R;
L = findLCABinaryTree(head->left, a, b);
R = findLCABinaryTree(head->right, a, b);
if(L != NULL && R!= NULL)
return head;
if(L == NULL && R!= NULL)
return R;
if(R == NULL && L!= NULL)
return L;
return NULL;
}
Slightly different version to sonny.c.patterson!!
Please comment, if anything is wrong.
- praveen October 06, 2014