lilzh4ng
BAN USER- 10of 12 votes
AnswersGiven a max-heap represented as an array, return the kth largest element without modifying the heap. I was asked to do it in linear time, but was told it can be done in log time.
- lilzh4ng in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
Answers// Finds and returns the value of the element that occurs an odd number of times
- lilzh4ng in United States
// in the input array. Examples:
// [1000000] => 1000000
// [2, 2, 2] => 2
// [1, 3, 3] => 1
// [1, 2, 3, 1, 2, 3, 4] => 4
// [1, 2, 3, 2, 1, 2, 3, 2, 1] => 1
// etc.
int findOdd(int[] input, int length) {
}| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer
I'm confused about your explanation. I don't think that is what my algorithm is doing.
Let's use this example which is similar to yours: 3 1's a 2 then 2 1s.
111211
First you have a pointer at the first and last chars. This will be represented by brackets
[1]1121[1]
You compare these two chars. If they are the same, increment the first pointer and decrement the last pointer.
1[1]12[1]1
Compare again. Both are equal
11[1][2]11
These two chars are different. Now you set the start pointer back to the beginning and compare
[1]11[2]11
They aren't equal again, but with my logic you only decrement the last pointer
[1]1[1]211
These are the same pointers
1[[1]]1211
Now we know 111 is the smallest palindrome where the first char is the first char of the original string. Now we find the length of the string that isn't part of the palindrome and add it to the original length which will be your answer. This example answer is 9. (112111211)
public String pattern(int input){
return patternUtil(input, "1");
}
public String patternUtil(int input, String result)
{
if(input == 0) {
return result;
}
char curChar = result.charAt(0);
String newResult = "";
int counter = 0;
for(int i = 0; i< result.length(); i++) {
char character = result.charAt(i);
if(character != curChar) {
newResult = newResult + counter;
newResult = newResult + curChar;
counter = 0;
curChar = character;
}
counter ++;
}
newResult = newResult + counter;
newResult = newResult + curChar;
return patternUtil(input -1 , newResult);
}
I look for the shortest Palindrome where the first char is the first char of String s. Then I find the length of the part of the string that isn't a palindrome and add it to the length of string s. This should be O(n) because the end pointer never resets
public int shortestPalindromePossible(String s)
{
if(s.length() == 0) return 0;
int start = 0;
int end = s.length() - 1;
int realend = s.length() - 1;
while(start < end) {
if(s.charAt(start) == s.charAt(end))
{
start++;
end--;
continue;
}
if(start == 0) {
end--;
}
start = 0;
realend = end;
}
return (s.length() - (realend + 1)) + s.length();
}
My answer was:
int findOdd(int[] input, int length) {
if(input.size() == 1)
{
return input[0];
}
sort(&input);
counter = 1;
for(int i = 1; i < input.size(); i++)
{
if(input[i - 1] < input[i])
{
if(counter % 2 == 1)
return input[i - 1];
else
counter = 0;
}
counter++;
}
return input[input.size() - 1];
}
What? If the input is 112111 how can it be 5? The question states you can only added characters in front of it. The answer is 7: 1112111.
- lilzh4ng November 22, 2014Am I going crazy? It's either I don't understand the question or no one here does