chisingh
BAN USERNonrecursive solution: (in PHP as per the question)
<?php
function find_sum($n) {
$array[1] = array("1");
for ($i=2; $i <= $n; $i++) {
$array[$i] = array();
for ($j=1; $j < $i; $j++) {
foreach ($array[$j] as $el) {
array_push($array[$i], $el.",".($i$j));
}
}
array_push($array[$i], $i);
}
return $array[$n];
}
$n = 4;
$res = find_sum($n);
foreach ($res as $str) {
if ($n == 1  $str != $n)
print "(".$str.")\n";
}
?>
output:
(1,3)
(1,1,2)
(2,2)
(1,2,1)
(1,1,1,1)
(2,1,1)
(3,1)
Yeah, so you can recursively solve the subproblems and memoize the results using dynamic programming. In other words:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int count_valid(char *str, int size, int *array) {
int n, count = 0;
char substr[2];
if (size == 0)
return 1;
if (size == 1) {
if (*str != '0')
return 1;
else return 0;
}
if (array[size] >= 0)
return array[size];
if (str[size1] != '0')
count += count_valid(str, size1, array);
strncpy(substr, str+(size2), 2);
n = atoi (substr);
if (n >= 1 && n <= 26)
count += count_valid(str, size2, array);
array[size] = count;
return count;
}
int main () {
char *input = "1234";
int i, size = strlen(input);
int *array = (int *) malloc (sizeof(int) * (size+1));
for (i=1; i <= size; i++)
array[i] = 1;
printf ("%d\n", count_valid(input, size, array));
}

chisingh
February 09, 2013 Here's a plain vanilla C implementation using Trie based suffix tree.
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
char key;
int value;
struct node *next, *children;
} node;
node *makeNode(char key, int value) {
node *n = (node *) malloc(sizeof(node));
n>key = key;
n>value = value;
n>next = n>children = NULL;
return n;
}
int insert (node *trie, char *str, int value) {
int ret = 1;
node *curr;
if (trie == NULL)
return 0;
curr = trie;
if (curr>children) {
curr = curr>children;
while (curr>key != *str) {
if (curr>next)
curr = curr>next;
else {
curr>next = makeNode(*str, value);
curr = curr>next;
ret = 0;
}
}
}
else {
curr>children = makeNode(*str, value);
curr = curr>children;
ret = 0;
}
if (*str == '\0')
return 0;
else
return ret + insert(curr, str+1, value);
}
int main () {
int i, n, max=0, index;
char str[] = "sdkljasdasdhjfhsfhsfdsjdjshjdshjdshhdsjdhhjhfhshhjshfjh";
node *trie;
trie = makeNode('\0', 0);
for (i=0; i < sizeof(str)/sizeof(char); i++) {
n = insert(trie, str+i, 0);
if (n > max) {
max = n;
index = i;
}
}
for (i=0; i<max; i++)
printf ("%c", str[index+i]);
printf ("\n");
}

chisingh
February 09, 2013 node *prepend(node * root, int k)
{
node *prev, *curr;
curr = root;
for (int i = 0; i < k; i++) {
curr = curr>next;
if (curr == NULL)
return NULL;
}
prev = root;
while (curr>next != NULL) {
curr = curr>next;
prev = prev>next;
}
curr>next = root;
root = prev>next;
prev>next = NULL;
return root;
}

chisingh
February 07, 2013 int maxLevel(node *root) {
int max, curr_level, max_level;
if (root == NULL)
return 0;
queue<node *> currentLevel, nextLevel;
currentLevel.push(root);
max = curr_level = 1;
while (!currentLevel.empty()) {
node *curr = currentLevel.front();
currentLevel.pop();
if (curr>left != NULL)
nextLevel.push(curr>left);
if (curr>right != NULL)
nextLevel.push(curr>right);
if (currentLevel.empty()) {
queue<node *> temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
curr_level ++;
if (currentLevel.size() > max) {
max = currentLevel.size();
max_level = curr_level;
}
}
}
return max_level;
}

chisingh
February 07, 2013 Alright, Let me try one more time.
As we know, each node in a maxheap can have at most children which are both smaller than the value of this node. Just like in array representation of heaps where children are located at 2*i+1 and 2*i+2, here in case of matrix, the children are located at [i1][j] and [i][j1]. There is absolutely no logical difference between this representation and the conventional array one. Now you just have to pop the root node of the heap k times and restore the original heap property by pushing up the node at [n][n] to it's correct place, where it is greater than its both children.
Please carefully look at the code to understand the rest of the minor details, since it's not easy to explain in words.
May be someone can provide a C/Java implementation of this method?
Why are you creating another heap when the input matrix is itself a heap? I would't recommend using high level library routines for programming interviews, since they trivialize the original problem. Do you think you should use the builtin sort() routine when the interviewer is asking you to write mergesort code?
 chisingh January 27, 2013Sure. The main function is popping the largest element k times, and replacing it with the smallest one. After swapping these two elements we need to restore the original property of the matrix. That is precisely what pushUp() function does. Just like we have heapify() for maxheaps. Only difference is for an element at [i,j] we have [i1][j] and [i][j1] as its 'children'.
 chisingh January 27, 2013Here is my correct working solution in python:
Assumed a square matrix, but the solution can be easily modified for a rectangular matrix.
def pushUp(m):
i = j = len(m)1
n = m[i][j]
while i > 0 and j > 0:
if m[i1][j] < n:
if m[i][j1] < n: return;
else:
m[i][j1], m[i][j] = m[i][j], m[i][j1]
j = 1
else:
if m[i][j1] < n:
m[i1][j], m[i][j] = m[i][j], m[i1][j]
i = 1
else:
x,y = i1, j
if m[i][j1] > m[i1][j]: x,y = i, j1
m[i][j], m[x][y] = m[x][y], m[i][j]
i,j = x,y
if __name__ == "__main__":
matrix = [[1, 2, 3, 25],
[4, 23, 30, 88],
[7, 82, 90, 100],
[8, 83, 91, 101]]
k = 7
n = len(matrix)1
while k > 1:
matrix[0][0], matrix[n][n] =  matrix[n][n], matrix[0][0]
pushUp(matrix)
k = 1
print matrix[n][n]
Very similar to extracting kth largest element from a maxheap.
 chisingh January 27, 2013
Replisafergusona, Consultant at Myntra
I am Lisa from Chicago,I am working as a Show host in the New World. I also work Performs ...
Rephoychrista, Blockchain Developer at ASU
Worked with Clients to guide them through the event details about copier leasing companies and served as their personal coordinator ...
Open Chat in New Window
How about this?
 chisingh June 09, 2013