s*********3
发帖数: 389 | 1 I wrote some Java code afterwards. It seems not very clean. Please comment.
import java.util.*;
//Assumptions:
//1. We can move either up or down or left or right at any point in time,
but not diagonally.
//2. One item in the matrix can not be used twice to compose of the pattern
string.
//3. If different routes lead to the same indexes of matrix items to compose
of the pattern string, display them.
//4. The maximum number of movable steps is (matrix.length - 1) + (matrix[0]
.length - 1) = matri... 阅读全帖 |
|
x*****p
发帖数: 1707 | 2 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 | 3 // 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****o
发帖数: 2260 | 4 One mistake in the code:
//java code
String GetCommonPrefix(String a, String b)
{
char[] aChar = a.toCharArray();
char[] bChar = b.toCharArray();
int startIndex = 0;
//choose short length as the end index
int needLength= aChar.length>bChar.length?bChar.length:aChar.length;
while(startIndex
{
if(aChar[startIndex]!=bChar[startIndex])//find different!
break;
else
startIndex++;
}
return a.subString(0, startIndex);
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>... 阅读全帖 |
|
m*******m
发帖数: 82 | 5 Interview Questions：
Redefine a function (signature given) to write data to a new replacement for
an antiquated database (which you previously designed)
Answer Question：
Write a function to return the longest common prefix between two strings.
//java code
String GetCommonPrefix(String a, String b)
{
char[] aChar = a.toCharArray();
char[] bChar = b.toCharArray();
int startIndex = 0;
//choose short length as the end index
int needLength= aChar.length>bChar.length?bChar.length:aChar.lengt... 阅读全帖 |
|
f*****n
发帖数: 15 | 6 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... 阅读全帖 |
|
w********p
发帖数: 948 | 7 根据你提供的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) {
|
|
c*****e
发帖数: 3226 | 8 哦，对的。不过还是觉得扫描２次这个方法很蠢。
搜了一下，网上有别的解法，而且通过了leetcode online judge.
public static int longestValidParentheses(String s) {
Stack stack = new Stack();
int len = 0;
int maxLen = 0;
int startIndex = s.length();
for(int i = 0; i < s.length(); ++i) {
if(s.charAt(i) == '(') {
stack.push(i);
continue;
}
if(stack.isEmpty()) {
startIndex = s.length();
} else {
... 阅读全帖 |
|
c*****e
发帖数: 3226 | 9 哦，对的。不过还是觉得扫描２次这个方法很蠢。
搜了一下，网上有别的解法，而且通过了leetcode online judge.
public static int longestValidParentheses(String s) {
Stack stack = new Stack();
int len = 0;
int maxLen = 0;
int startIndex = s.length();
for(int i = 0; i < s.length(); ++i) {
if(s.charAt(i) == '(') {
stack.push(i);
continue;
}
if(stack.isEmpty()) {
startIndex = s.length();
} else {
... 阅读全帖 |
|
i***e
发帖数: 452 | 10 我都试过你的code， 可以过的啊。
给你贴个我写的吧 ：
TreeNode* help(vector& inorder, int startIndex, int n, vector&
postorder, int start2)
{
if(n < 1) return NULL;
TreeNode* root = new TreeNode(postorder[start2+n-1]);
if(n == 1) return root;
int index = startIndex;
for(;;index++)
if(inorder[index] == root->val)
break;
int l = index - startIndex;
root->left = help(inorder, startIndex, l, postorder,start2);
root->ri... 阅读全帖 |
|
i**********e
发帖数: 1145 | 11 写了一个 O(n) 的 in-place insert。
如果有 overlap 多个区间就左移数组（因为所有overlap区间被merge成一个大区间）
，然后更改第一个overlap的区间。
如果没有overlap的话，那要注意是否在某个区间前面。如果是的话，就右移数组一位
，然后insert。
如果以上两种情况都不符合的话，就简单了。只剩下最后一个可能：
把区间push到最后边。
class Solution {
public:
vector intervals;
void insert(Interval newInterval) {
int n = intervals.size();
for (int i = 0; i < n; i++) {
if (newInterval.end < intervals[i].start) {
moveRight(i, 1);
intervals[i] = newInterval;
return;
} else {
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 12 写了一个 O(n) 的 in-place insert。
如果有 overlap 多个区间就左移数组（因为所有overlap区间被merge成一个大区间）
，然后更改第一个overlap的区间。
如果没有overlap的话，那要注意是否在某个区间前面。如果是的话，就右移数组一位
，然后insert。
如果以上两种情况都不符合的话，就简单了。只剩下最后一个可能：
把区间push到最后边。
class Solution {
public:
vector intervals;
void insert(Interval newInterval) {
int n = intervals.size();
for (int i = 0; i < n; i++) {
if (newInterval.end < intervals[i].start) {
moveRight(i, 1);
intervals[i] = newInterval;
return;
} else {
... 阅读全帖 |
|
l*****a
发帖数: 559 | 13 如二爷所述，的确是走的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()){
... 阅读全帖 |
|
b********r
发帖数: 620 | 14 贴个自己写的，所有test都pass了。不知道怎么用地跪。恳请大牛批评指正。
public static int selectGasStation(int[] stationGasAvailability, int[]
requiredGasAvailabilityForDriving) {
if (stationGasAvailability.length == 0 ||
requiredGasAvailabilityForDriving.length == 0) {
return -1;
} else if (stationGasAvailability.length == 1) {
// if there is only one station we can always do
return 0;
}
// check total availability vs total requirement
int totalAva... 阅读全帖 |
|
g**u
发帖数: 504 | 15 Yes, got it.
Here is the revised one, it works. Now it's almost same as swan's.
void myrotate(int* a, int N, int k)
{
if (N<=1) return;
if (k>N) k=k%N;
if (k==0) return;
int currentIndex,nextIndex;
int currentValue,nextValue;
int numMove=0;
int startIndex;
for (int i=0; numMove
startIndex=i;
currentIndex = i;
currentValue=a[currentIndex];
while(1){
numMove++;
nextIndex=(currentIndex+N-k)%N;
... 阅读全帖 |
|
S******1
发帖数: 269 | 16 Basically the same solution with repeatable candidates. Recursion, time
complexity should be O(n!)?
import java.util.*;
public class Solution {
public ArrayList> combinationSum2(int[] num, int
target) {
ArrayList> result= new ArrayList
Integer>> ();
ArrayList item=new ArrayList ();
Arrays.sort(num);
if(num!=null || num.length>0)
combinations(num, target, result, item, 0);
... 阅读全帖 |
|
n*s
发帖数: 752 | 17 the return value here is the startIndex,
for endIndex, one can traverse from startIndex
,v
endindex=
]= |
|
a*******y
发帖数: 1040 | 18 我就在想有没有更好的办法出了用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++)
{
... 阅读全帖 |
|
发帖数: 1 | 19 背景：CS PhD + 1.5 years. 非CS行业的一个小公司骑驴找马。大概准备了七八个月的
时间吧，晚上回来陪娃睡了然后自己刷题。很不幸，还是全挂了。另外很多大公司现在
也不招opt身份的非new grad。FLA都没有给我面试。有时候想想，大概这种水平的CS
PhD就我一个了吧（呵呵）。还是喜欢写程序的，可是越来越觉得自己似乎并没有这方
面的天分。骑的驴也没积累到什么CS的经验，做了很多business相关的东西。感觉在这
里待得时间越久，自己的career荒废的越多。而且有了几年工作经验之后就会被问很多
design相关的东西，可是我的实际工作中也没涉及多少。用的也是那套软轮。从当年的
认为只要自己努力什么都能做到的少年，慢慢变成了如今已经习惯了生活会经常跟我开
玩笑的准大叔。身份也没有。PTO也差不多用光（每次都要从东海岸飞西海岸，然后面
试当晚红眼飞回来上班）。娃们还嗷嗷待哺。总是想不通，到底是哪一步走错了，才与
其他当初一起上学的小伙伴们的差距越来越大。不过我在帮助国人方面，问心无愧。只
要经过我手的国人来面试我们公司，我都给过了。 牢骚发了不老少，下面回归正题吧
。... 阅读全帖 |
|
|
|
w********p
发帖数: 948 | 22 本来觉得我的算法在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 | 23
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 | 24 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 |
|
x*********s
发帖数: 2604 | 25 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？ |
|
x*****p
发帖数: 1707 | 26 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. |
|
F**********r
发帖数: 237 | 27 不是很明白startindex从0到2的过程要做些什么？这个slide window要怎么用呢？谢谢！
( |
|
n******n
发帖数: 49 | 28 Given a list of words with a same size and a big string that
contains one of the permutation of all the words combined(say p),
find the start index of the string p in the big string.
现在能想到的解法就是：
- find the positions of all the words in the big string
- if you mod with the size of word(same for all words)
should give the same value for all the word positions in the big string and
the lowest position is the startindex.
不知道大家有什么更好的办法没有？这题要用trie吗？ |
|
n******n
发帖数: 49 | 29 Given a list of words with a same size and a big string that
contains one of the permutation of all the words combined(say p),
find the start index of the string p in the big string.
现在能想到的解法就是：
- find the positions of all the words in the big string
- if you mod with the size of word(same for all words)
should give the same value for all the word positions in the big string and
the lowest position is the startindex.
不知道大家有什么更好的办法没有？这题要用trie吗？ |
|
S**********d
发帖数: 133 | 30 在Glassdoor看到的，条件不是特别清楚：
"Given a list of words with the same size and a big string that contains one
of the permutation of all the words combined (say p), find the startindex
of the string p in the big string."
大概用Trie可以做出来，不过有很多小edge case不知道怎么处理得好，比较说如果其
中一个string 的后缀是另一个的前缀好像会出现些问题。
还请各位大牛说说思路！ |
|
i***e
发帖数: 452 | 31 感觉第三题是有点难写， 应为平时都没注意要记录index。 不过可以用两个
startIndex, endIndex 来存当前最优的。 然后相应的update这两index.
第一有parent pointer 吗？ 这个class只有一个.next的函数还是怎么样的？ |
|
i***e
发帖数: 452 | 32 感觉第三题是有点难写， 应为平时都没注意要记录index。 不过可以用两个
startIndex, endIndex 来存当前最优的。 然后相应的update这两index.
第一有parent pointer 吗？ 这个class只有一个.next的函数还是怎么样的？ |
|
e****e
发帖数: 418 | 33 这个单竖线分割符是逻辑上的。。。，我在的例子中表示出来主要是为了看起来容易区
别前后两部分。实际partition的时候，partition的位置，是（startIndex+endIndx）
/2 算出来的，这个位置是前半部分的最后一个元素的位置。
stack |
|
f*******7
发帖数: 943 | 34 我的意思是如何计distinct这个个数啊
比如这个case
abcabcd 3 返回abcabc, 当startIndex = 0时，endIndex = 3时nums[3] = a, 此时
distinctCount = 3, 当endIndex = 4时，distinctCount依然是3，如何update这个
distinctCount啊 |
|
|
|
g****h
发帖数: 771 | 37 搬家出售：
1. 煮蛋器 Dash Go Rapid Egg Cooker, Black https://www.amazon.com/gp/product/
B00DDXWFY0/ref=oh_aui_detailpage_o02_s00?ie=UTF8&psc=1),只用过几次，$8.
2.熨衣服 Steamfast SF-407 Fabric Steamer https://www.amazon.com/gp/product/
B000BQRD0I/ref=oh_aui_detailpage_o01_s00?ie=UTF8&psc=1), $35.
3. 铲子 AAA 4004 Red Aluminum Sport Utility Shovel https://www.amazon.com/
gp/
your-account/order-history/ref=oh_aui_pagination_3_4?ie=UTF8&orderFilter=
year-2015&search=&startIndex=30),买来没有用过，$12.
4. 餐桌 5-Piece Dining... 阅读全帖 |
|
|
|
|
|
|
|
T*******n
发帖数: 493 | 44 Look in the .cls and you should find the definition of an
environment called "theindex". This is where the page
layout of the index is usually defined.
You can try the following, add before \begin{document}:
\usepackage{makeidx}
\usepackage{multicol}
\makeatletter
\newcommand{\startindex}[0]{%
\chapter*{\indexname\@mkboth{\indexname}{\indexname}}%
\addcontentsline{toc}{chapter}{\indexname}%
}
\renewenvironment{theindex}{%
\par
\setlength{\columnseprule}{\z@}%
\setlength{\columnsep}{12 |
|
