Q****s
发帖数: 1301 | 1 pair longestContinousSubArray(int arr, int n) {
if (n==0) return pair(0,0);
if (n==1) return pair(0,1);
int beginIndex = retBegin = 0;
int endIndex = 1;
int len = retLen =1;
for (endIndex=1; endIndex
if (arr[endIndex] > arr[endIndex-1]) len++;
else {
len=1;
beginIndex = endIndex;
}
if (retLen
retLen = len;
retBegin = endIndex;
}
}
return pair(retBegin, retLe... 阅读全帖 |
|
f*****n
发帖数: 15 | 2 one way to solve it is to use DP. runtime is O(n^2) and it requires O(n)
extra space.
import java.util.ArrayList;
import java.util.List;
public class StringOperation {
public static void main(String[] args) {
StringOperation strOp = new StringOperation();
System.out.println(strOp.findLongRepeatedString("banana"));
System.out.println(strOp.findLongRepeatedString("aaaaa"));
}
public String findLongRepeatedString(String src) {
Result longestResult = n... 阅读全帖 |
|
v***d
发帖数: 51 | 3 试着做了一下
Node* findAllBSTs(int beginIndex, int endIndex, Node* origHead, Node*
curParent) {
if ( endIndex - beginIndex < 0 )
return NULL;
else if ( endIndex - beginIndex == 0 ) {
Node* newNode = new Node(values[beginIndex], NULL, NULL);
return newNode;
}
else {
for ( int i = beginIndex; i <= endIndex; i++ ) {
curParent->value = values[i];
if ( beginIndex <= i-1 )
curParent->leftChild = new Node(0, N... 阅读全帖 |
|
x*****p
发帖数: 1707 | 4 Using recursive.
Suppose an array A of integers is given to hold all golden pieces. Its index
is from 0 to N-1.
Let function f(int startIndex, int endIndex) returns the maximum money you
can get.
int f(A, int startIndex, int endIndex) {
int sum = summation from A[startIndex] to A[endIndex];
if (startIndex==endIndex) return A[startIndex];
int choice1 = sum - f(A, startIndex+1, endIndex);
int choice2 = sum - f(A, startIndex, endIndex-1);
return (choice1>choice2?choice1:choice2)... 阅读全帖 |
|
S******1
发帖数: 269 | 5 // Find the longest subarray with equal 1 and 0.
public static int[] longestSub(int[] inputArray) {
int length = inputArray.length;
int[][] record = new int[length][length];
//Initial
for (int i = 0; i < length; i++)
if (inputArray[i] == 1)
record[i][i] = 1;
else
record[i][i] = -1;
for (int i = 0; i < length; i++) {
for (int j = i; j < length; j++) {
if (i < j)
... 阅读全帖 |
|
w********p
发帖数: 948 | 6 根据你提供的algorithm and feedback, 从写思路. one time scan
running time O(n) space O(1)
Please correct me, if logic error
//n is the array size
maxSum=-99999999;
if (k>n) return failed
for (int i=0; i
startIndex=i;
endIndex= (i+k-1)% n;
//get the sum of k number from startIndex to endIndex
sum=SumKMember(startIndex, endIndex， sum);
if (sum>maxSum ) { maxSum = sum; retrunIndex=startIndex }
}
//get sum only one time scan
int SumKMember(int startIndex, int endIndex, sum) {
|
|
i**********e
发帖数: 1145 | 7 Code for 2).
Idea is to use binary search to find the first occurence where A[i] == k.
Then apply binary search again to find both the lower and upper range.
int binarySearchLower(int A[], int n, int l, int h, int k) {
int lo = l;
int hi = h;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (A[mid] < k)
lo = mid+1;
else
hi = mid-1;
}
assert(lo >= 0 && lo <= n-1); assert(A[lo] == k); assert(lo == 0 || (lo >=
1 && A[lo-1] < k));
return lo;
}
int binarySearchUpper... 阅读全帖 |
|
i**********e
发帖数: 1145 | 8 Code for 2).
Idea is to use binary search to find the first occurence where A[i] == k.
Then apply binary search again to find both the lower and upper range.
int binarySearchLower(int A[], int n, int l, int h, int k) {
int lo = l;
int hi = h;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (A[mid] < k)
lo = mid+1;
else
hi = mid-1;
}
assert(lo >= 0 && lo <= n-1); assert(A[lo] == k); assert(lo == 0 || (lo >=
1 && A[lo-1] < k));
return lo;
}
int binarySearchUpper... 阅读全帖 |
|
S**I
发帖数: 15689 | 9 ☆─────────────────────────────────────☆
recursive (递归) 于 (Mon Apr 11 10:56:49 2011, 美东) 提到:
大半夜收到HR的thank you note。不用管什么NDA了
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the out... 阅读全帖 |
|
l*****a
发帖数: 559 | 10 如二爷所述，的确是走的two pointers的套路。
string findLongest(string s){
int maxLen = 0;
int startIndex = 0;
int endIndex = 0;
int i = 0;
int j = 0;
unordered_map m;
while(j < s.length()){
if(m.size() < 2 || m.find(s[j]) != m.end()){
m[s[j]]++;
j++;
if(maxLen < j - i){
maxLen = j - i;
startIndex = i;
endIndex = j;
}
}else if(m.find(s[j]) == m.end()){
... 阅读全帖 |
|
n*s
发帖数: 752 | 11 the return value here is the startIndex,
for endIndex, one can traverse from startIndex
,v
endindex=
]= |
|
a*******y
发帖数: 1040 | 12 我就在想有没有更好的办法出了用sufix tree
写了个傻的，不过觉得有更好的
bool strMatch(char* str, int start, int length)
{
for (int i = 0; i
{
if (str[start+i] != str[start-length+i])
return false;
}
return true;
}
bool ReturnConsecutiveString(char* str, int n, int& startindex, int&
endindex)
{
int i = 1, j,k;
bool bfail = false;
while (i < n)
{
for (j = 1; (i+j < n) && (i-j-1 >=0);j++)
{
for (k = 0; k<=j;k++)
{
... 阅读全帖 |
|
b*******3
发帖数: 109 | 13 贴个java solution O(n m) :
public String minWindow (String originalString, String patternString)
{
List valuePairs = new ArrayList();
int shortestWindowLength = originalString.length();
int shortestHolderIndex = 0;
for (int i=0; i< originalString.length(); i++)
{
if (patternString.indexOf(originalString.charAt(i))>=0)
{
ValuePair valuePair = new ValuePair(originalSt... 阅读全帖 |
|
f*******7
发帖数: 943 | 14 我的意思是如何计distinct这个个数啊
比如这个case
abcabcd 3 返回abcabc, 当startIndex = 0时，endIndex = 3时nums[3] = a, 此时
distinctCount = 3, 当endIndex = 4时，distinctCount依然是3，如何update这个
distinctCount啊 |
|
w********p
发帖数: 948 | 15 本来觉得我的算法在nlgn和n^2之间，没在意
看了楼上的link一眼，觉得可能接近。写出来讨论一下, 不知道我的火星文有没有人看
得懂
assuming T=16
list after sorted
1, 2, 3, 6, 7, 8, 9
1. 简化问题。 如果只考虑sum of 2 elements in an array equals to value T
1)sort array
2)use two points point to start and end of the list....
find the 2 elements in O(n)
function: find2Element(startIndex, endIndex, array, T)
2. sum of 3 elements .....
for each number only need to find2Element on partial array
1) the T value should between
sum of the first 3 number < T < sum of the las |
|
w********p
发帖数: 948 | 16
1. 简化问题。 如果只考虑sum of 2 elements in an array equals to value T
1)sort array
2)use two points point to start and end of the list....
find the 2 elements in O(n)
function: find2Element(startIndex, endIndex, array, T)
2. sum of 3 elements .....
for each number only need to find2Element on partial array
1) the T value should between
sum of the first 3 number < T < sum of the last 3 number , otherwise return
false;
2) pick up number from the end of the array,
Num=array[len-i-1]=9; i=0, numberIndex=le |
|
w********p
发帖数: 948 | 17 code is here, I run it simply, it looks good
O(n) for running time, and O(1) for space
#include
#include
#include
using namespace std;
int SumKMember(int iArray[],int startIndex, int endIndex, int sum);
int main (int argc, char *args[]) {
if (argc != 2) {
cout<<"comment line: a.exe number\n";
return 0;
}
int k=atoi(args[1]);
//n is the array size
int maxSum=-99999999;
int iArray[] = {1, 2 , 4 , -3, 5 ,2};
int n = sizeof( iArray) /sizeof |
|
d****j
发帖数: 293 | 18 第一轮第二题
电面之前刚好练过这道题，但是用ArrayList 和ArrayList of ArrayList 实现的，用
recrusive 的方法，返回前k个元素的幂集合之后，再复制一边添加当前k+1元素入每个
子集合。最终返回幂集之后在打印，效率不好。但是当时想都没想就写上去了。
面完了就想起，完全可以用一个等长的int数组来标识是否取当前元素，代码如下。（
Careercup有这道题，使用一个int数i的每一位来做标识，把i从0递增到2^32-1就能打
印出所有的subsets，但最多只能实现到32个数的数组）
public static void printPowerSet(int[] set) {
int[] index = new int[set.length];
int endidx = 0;
printPowerSetSolver(set, index, endidx);
}
public static void printPowerSetSolver(int[] set, int[] index, int endidx) {
if (... 阅读全帖 |
|
d****j
发帖数: 293 | 19 第一轮第二题
电面之前刚好练过这道题，但是用ArrayList 和ArrayList of ArrayList 实现的，用
recrusive 的方法，返回前k个元素的幂集合之后，再复制一边添加当前k+1元素入每个
子集合。最终返回幂集之后在打印，效率不好。但是当时想都没想就写上去了。
面完了就想起，完全可以用一个等长的int数组来标识是否取当前元素，代码如下。（
Careercup有这道题，使用一个int数i的每一位来做标识，把i从0递增到2^32-1就能打
印出所有的subsets，但最多只能实现到32个数的数组）
public static void printPowerSet(int[] set) {
int[] index = new int[set.length];
int endidx = 0;
printPowerSetSolver(set, index, endidx);
}
public static void printPowerSetSolver(int[] set, int[] index, int endidx) {
if (... 阅读全帖 |
|
x*********s
发帖数: 2604 | 20 Given a sorted array with duplicates and a number, find the range in the
form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3
10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).
Upon further probe:
1. Do better than linear scan, which is O(n). 2. You can just work out how
to find the start index, and I will assume that you know how to find the end.
有没有办法用binary search来找start和end？ |
|
f*********8
发帖数: 34 | 21 这是用python写的吗
是不是没有考虑到a[m]第一次正好等于v的情况呢，比如a[9]={0,1,2,3,3,3,4,7,10},v
=3
那么按照你的程序m=(0+8)/2=4,a[m]=3=v,那么一次就决定了r=4,但是实际上endindex=
5，因为后面还有个3，同理对求l来说也存在一样的问题。
我觉得在跳出while循环得到r后还应该再检查一下a[r+1]!=v（如果用a[r+1]>v这个判
断条件的话当v=10也就是数组最后一个数的时候会出现错判），如果a[r]==v&&a[r+1]=
=v,那么还要继续增加r直到找到a[r+1]!=v的那个r |
|
x*****p
发帖数: 1707 | 22 No, this is not a dp problem. It uses a block that contains startIndex,
endIndex and sum. It goes over the array and update the block. |
|
i***e
发帖数: 452 | 23 感觉第三题是有点难写， 应为平时都没注意要记录index。 不过可以用两个
startIndex, endIndex 来存当前最优的。 然后相应的update这两index.
第一有parent pointer 吗？ 这个class只有一个.next的函数还是怎么样的？ |
|
i***e
发帖数: 452 | 24 感觉第三题是有点难写， 应为平时都没注意要记录index。 不过可以用两个
startIndex, endIndex 来存当前最优的。 然后相应的update这两index.
第一有parent pointer 吗？ 这个class只有一个.next的函数还是怎么样的？ |
|
g*****c
发帖数: 106 | 25 求问一道pocket gems的面试题 ：
写一个mutable string。 里面有三个methods, charAt(int i), substring(int
beginIndex, int endIndex), setcharAt(int i, char c); 只能是O（1） space
毫无头绪。。。这些不是c++ stl 自带的函数么。。。跪求指导。。。最好用c++
谢谢！ |
|
T****U
发帖数: 3344 | 26 想简单的话，直接用string类的各种methods就好了
int indexOf(String str)
Returns the index within this string of the first occurrence of th
e specified substring.
String substring(int beginIndex, int endIndex)
Returns a new string that is a substring of this string. |
|
