Data Structure Used: Array
Algorithm: Question is really tricky if we don't think smartly !!!! :)
use two pointer & points l to 1st & r to 2nd array
if elementb in 1st is smaller trhen 2nd arraye elemnt at index i then increment 1st pointer
else
swap element at index i in both array &b incerment 1st pointer & sort 2nd
array its not necessary only if we need sorted output in each array
Solution:
size of a=m size of b =n
a[]={1,3,77,78,90} and b[]={2,5,79,81}
l r
while(l<=m && r<=n)
{
if(b[r]
{
swap(a[l],b[r]);
l++;
sort(b[]);
}
elseif(a[l]
l++;
}
Time Complexity O(mlogm) sorting to 2nd array
Space Complexity O(1)
Wednesday, July 13, 2011
Monday, July 11, 2011
Given a word, convert it into a palindrome with minimum addition of letters to it. letters can be added anywhere in the word. for eg if yahoo is given result shud be yahoohay.
e.g
ABBA : 0 (already a palindrome)
ABB: 1
FAE: 2
FOO: 1
Simple Algorithm Will be
You need to find the longest palindrome at the end of the string. An algorithm to see if a string is a palindrome can be created by simply running one pointer from the start of the string and one from the end, checking that the characters they refer to are identical, until they meet in the middle. Something like:
function isPalindrome(s):
i1 = 0
i2 = s.length() - 1
while i2 > i1:
if s.char_at(i1) not equal to s.char_at(i2):
return false
increment i1
decrement i2
return true
Try that with the full string. If that doesn't work, save the first character on a stack then see if the remaining characters form a palindrome. If that doesn't work, save the second character as well and check again from the third character onwards.
Eventually you'll end up with a series of saved characters and the remaining string which is a palindrome.
Best case is if the original string was a palindrome in which case the stack will be empty. Worst case is one character left (a one-character string is automatically a palindrome) and all the others on the stack.
The number of characters you need to add to the end of the original string is the number of characters on the stack.
To actually make the palindrome, pop the characters off the stack one-by-one and put them at the start and the end of the palindromic string.
Examples:
String Palindrome Stack Notes
------ ---------- ----- -----
ABBA Y - no characters needed.
String Palindrome Stack Notes
------ ---------- ----- -----
ABB N -
BB Y A one character needed.
ABBA Y - start popping, finished.
String Palindrome Stack Notes
------ ---------- ----- -----
FAE N -
AE N F
E Y AF two characters needed.
AEA Y F start popping.
FAEAF Y - finished.
String Palindrome Stack Notes
------ ---------- ----- -----
FOO N -
OO Y F one character needed.
FOOF Y - start popping, finished.
String Palindrome Stack Notes
------ ---------- ----- -----
HAVANNA N -
AVANNA N H
VANNA N AH
ANNA Y VAH three characters needed.
VANNAV Y AH start popping.
AVANNAVA Y H
HAVANNAVAH Y - finished.
ABBA : 0 (already a palindrome)
ABB: 1
FAE: 2
FOO: 1
Simple Algorithm Will be
You need to find the longest palindrome at the end of the string. An algorithm to see if a string is a palindrome can be created by simply running one pointer from the start of the string and one from the end, checking that the characters they refer to are identical, until they meet in the middle. Something like:
function isPalindrome(s):
i1 = 0
i2 = s.length() - 1
while i2 > i1:
if s.char_at(i1) not equal to s.char_at(i2):
return false
increment i1
decrement i2
return true
Try that with the full string. If that doesn't work, save the first character on a stack then see if the remaining characters form a palindrome. If that doesn't work, save the second character as well and check again from the third character onwards.
Eventually you'll end up with a series of saved characters and the remaining string which is a palindrome.
Best case is if the original string was a palindrome in which case the stack will be empty. Worst case is one character left (a one-character string is automatically a palindrome) and all the others on the stack.
The number of characters you need to add to the end of the original string is the number of characters on the stack.
To actually make the palindrome, pop the characters off the stack one-by-one and put them at the start and the end of the palindromic string.
Examples:
String Palindrome Stack Notes
------ ---------- ----- -----
ABBA Y - no characters needed.
String Palindrome Stack Notes
------ ---------- ----- -----
ABB N -
BB Y A one character needed.
ABBA Y - start popping, finished.
String Palindrome Stack Notes
------ ---------- ----- -----
FAE N -
AE N F
E Y AF two characters needed.
AEA Y F start popping.
FAEAF Y - finished.
String Palindrome Stack Notes
------ ---------- ----- -----
FOO N -
OO Y F one character needed.
FOOF Y - start popping, finished.
String Palindrome Stack Notes
------ ---------- ----- -----
HAVANNA N -
AVANNA N H
VANNA N AH
ANNA Y VAH three characters needed.
VANNAV Y AH start popping.
AVANNAVA Y H
HAVANNAVAH Y - finished.
Labels:Data
Strings
,
Yahoo Interview
Within a 2D space, there is a batch of points(no duplicate) in the region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide the region to 2 parts with half points in each .the input will be an array of points and the length of the array. struct point{ int x; int y; }; input : struct point * points, int length
Labels:Data
Google Interview
Within a 2D space, there is a batch of points(no duplicate) in the region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide the region to 2 parts with half points in each .the input will be an array of points and the length of the array. struct point{ int x; int y; }; input : struct point * points, int length
Labels:Data
Google Interview
Design a data structure that can be used instead of an array and avoids the "high-cost" (i.e. O(n)) of initializing the array. the data structure ought to holds n items and supports the following operations in O(1) time: * Init – Initializes the data structure to empty. * Set(i, x) – Sets item x at index i in the data structure. * Get(i) – Gets the item stored in index i (or 'empty' if nothing is there). Remark: the data structure should use O(n) space.
Labels:Data
Google Interview
Design a data structure that can be used instead of an array and avoids the "high-cost" (i.e. O(n)) of initializing the array. the data structure ought to holds n items and supports the following operations in O(1) time: * Init – Initializes the data structure to empty. * Set(i, x) – Sets item x at index i in the data structure. * Get(i) – Gets the item stored in index i (or 'empty' if nothing is there). Remark: the data structure should use O(n) space.
Labels:Data
Google Interview
You have to write a function checkRegex() which takes two strings as input, one string represents a regex expression and other is an input string to match with the regex expression passed as the other parameter. Return true if it matches, else false.
I found this question on one of the forum
Regex may contain characters ‘a-z’, ‘.’ and ‘*’ where ‘.’ matches any character and ‘*’ means 0 or more occurrences of the previous character preceding it.
Examples:
1) a*b matches b,ab,aab
2) a.b matches aab, abb, acb,…, azb
3) .* matches all the valid strings formed by using the lowercase letters
Status: Solved
Algorithm:Recursion
Time Complexity O(2^n)
Space Complexity O(1)
Regex may contain characters ‘a-z’, ‘.’ and ‘*’ where ‘.’ matches any character and ‘*’ means 0 or more occurrences of the previous character preceding it.
Examples:
1) a*b matches b,ab,aab
2) a.b matches aab, abb, acb,…, azb
3) .* matches all the valid strings formed by using the lowercase letters
Status: Solved
Algorithm:Recursion
Time Complexity O(2^n)
Space Complexity O(1)
Labels:Data
Facebook Interview
Given a php source file which contains a few classes defined in it. ,print the class hierarchy in the given desired format.
In PHP, there is concept of single class inheritance i.e. a new class can extend an existing class. You are given a php source file which contains a few classes defined in it. You have to print the class hierarchy in the given desired format.
For example, classes in php source file are A, B extending A, C extending B, D extending A, E.
The output should look like:
A
B
C
D
E
For example, classes in php source file are A, B extending A, C extending B, D extending A, E.
The output should look like:
A
B
C
D
E
Labels:Data
DFS
,
Facebook Interview
,
Graph World
,
Trees
Sunday, July 10, 2011
Find the length of the longest no-repeated substring e.g. string without repeating characters. For example, the longest substring without repeating letters
ExampleString s="abcabcbbba" Answer will be "abc" of length 3
Algorithm:
Algorithm:
Assuming string has small letter only temp array is of length 26.
Take an temp boolean array to set/reset character is present or not
while iterating through whole string using temp array If character value is already set or true then reset values from current index to previous starting index.and update max-length of non-repeated sub-string.e.g.When you have found a repeated character (let’s say at index j), it means that the current sub-string (excluding the repeated character of course) is a potential maximum, so update the maximum if necessary. It also means that the repeated character must have appeared before at an index i, where i is less than j.
Since you know that all sub-strings that start before or at index i would be less than your current maximum, you can safely start to look for the next sub-string with head which starts exactly at index i+1.
As we are using two indexes which iterates through string two times e.g. O(2m) where m is length of string and overall time complexity O(m) .
Lets have a look at Code
int
lengthOfLongestSubstring(string s)
{
int
m= s.length();
int
i = 0, j = 0;
int
maxLen = 0;
boolean temp[]=new boolean[256];
while
(j < m) {
if
(temp[s[j]]) {
maxLen = max(maxLen, j-i);
while
(s[i] != s[j])
{
temp
[s[i]] =
false
;
i++;
}
i++;
j++;
}
else
{
temp
[s[j]] =
true
;
j++;
}
}
maxLen = max(maxLen, m-i);
return
maxLen;
}
Time Complexity O(M) M is Length of String
Labels:Data
Google Interview
Subscribe to:
Posts
(
Atom
)